Network Flow

303. Network Flow

Types of Problems:

Node $𝑖$

Units shipped from node $𝑖$ to node $𝑗$ :

𝑥_{𝑖 𝑗}

Minimize:

𝑍 = \sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

s.t.

\sum_{𝑘} 𝑥_{𝑘 𝑖} - \sum_{𝑙} 𝑥_{𝑖 𝑙} = or \leq or \geq 𝑏_{1}

𝑙_{𝑖 𝑗} \leq 𝑥_{𝑖 𝑗} \leq 𝑢_{𝑖 𝑗}

Where:

If:

Total Supply $=$ Total Demand[Inflow to $𝑖$ ] - [Outflow from $𝑖$ ] $=$ $𝑏_{𝑖}$
Total Supply $>$ Total Demand[Inflow to $𝑖$ ] - [Outflow from $𝑖$ ] $\geq$ $𝑏_{𝑖}$
Total Supply $<$ Total Demand[Inflow to $𝑖$ ] - [Outflow from $𝑖$ ] $\leq$ $𝑏_{𝑖}$

Important:

Example

Minimize

\begin{matrix} 𝑍 = 30 𝑥_{12} + 40 𝑥_{14} + 50 𝑥_{23} + 35 𝑥_{35} + 40 𝑥_{53} \\ + 30 𝑥_{54} + 35 𝑥_{56} + 25 𝑥_{65} + 50 𝑥_{74} + 45 𝑥_{75} + 50 𝑥_{76} \end{matrix}

s.t.

$𝑥_{12} + 𝑥_{14} \leq 200$ (Node 1)

$𝑥_{12} + 𝑥_{23} \geq 100$ (Node 2)

$𝑥_{23} + 𝑥_{53} - 𝑥_{35} \geq 60$ (Node 3)

$𝑥_{14} + 𝑥_{54} + 𝑥_{74} \geq 80$ (Node 4)

$𝑥_{35} + 𝑥_{65} + 𝑥_{75} - 𝑥_{53} - 𝑥_{54} - 𝑥_{56} \geq 170$ (Node 5)

$𝑥_{56} + 𝑥_{76} - 𝑥_{65} \geq 70$ (Node 6)

$𝑥_{76} + 𝑥_{75} + 𝑥_{74} \leq 300$ (Node 7)

$𝑥_{𝑖 𝑗} \geq 0$ $\forall (𝑖, 𝑗) \in 𝐸$

Example

Minimize:

\sum_{𝑖 𝑗} (𝑐_{𝑖 𝑗}^{𝑓} \cdot 𝑦_{𝑖 𝑗}) + \sum_{𝑖 𝑗} (𝑐_{𝑖 𝑗}^{𝑣} \cdot 𝑥_{𝑖 𝑗}) + \sum_{𝑖} (𝑐_{𝑖}^{𝑓} \cdot 𝑦_{𝑖}) + \sum_{𝑖} (𝑝_{𝑖} \cdot 𝑠_{𝑖}) +

Where:

s.t.

$\sum_{𝑗} 𝑥_{𝑗 𝑖} - \sum_{𝑗} 𝑥_{𝑖 𝑗} = or \leq or \geq 𝑑_{𝑖}$ Flow Conservation

$𝑏_{𝑖 𝑗}^{𝑙} \leq 𝑥_{𝑖 𝑗} \leq 𝑏_{𝑖 𝑗}^{𝑢}$ Lower & Upper Flow Bound

$𝑥_{𝑖 𝑗} \leq 𝑀 \cdot 𝑦_{𝑖 𝑗}$ Fixed Cost Route

$\sum_{𝑖} (𝑥_{𝑗 𝑖} + 𝑥_{𝑖 𝑗}) \leq 𝑀 \cdot 𝑦_{𝑖}$ Fixed Cost Node

$\sum_{𝑖} 𝑥_{𝑖 𝑗} + 𝑠_{𝑗} \geq 𝑑_{𝑗}$ Unmet Demand Penalty

$𝑥_{𝑖 𝑗} \geq 0$ $\forall (𝑖, 𝑗) \in 𝐸$ Non Negative Flow

Node Properties:

Node Type: Source, sink, or intermediary.
Supply (Source): Flow capacity of source nodes.
Holding Cost (Intermediary): Inventory cost for stored goods.
Service Time: Processing time at the node.
Demand: Required flow at sink nodes.
Storage Capacity (Intermediary): Maximum amount of goods that can be held at a node
Penalty for Unfulfilled Demand (Sink): Cost for unmet demand.
Disruption Risk (All Nodes): Probability of a node being unavailable due to unforeseen circumstances

Edge Properties:

Edge Type: Transport mode (air, water, road, rail).
Fixed Cost: Cost incurred for using the edge, regardless of flow.
Reliability: Probability of edge availability.
Flow Bounds: Minimum and maximum allowable flow.
Unit Cost: Cost per unit of flow.
Lead Time: Time it takes for flow to travel along the edge.
Environmental Impact: Account for the carbon footprint of using certain transport modes.