Fakultät Verkehrswissenschaften „Friedrich List“

Arbeitsgruppe Verkehrslogistik

Network Flow and Network Design

Content

(1) Maximum Flow

(2) Minimum Cost Flow

(3) Multi Commodity Flow

(4) Service Network Design

Folie 2
Maximum Flow Problem
Network Flow Model

Question:

„How many cargo units can be transported from

one source to one destination?“ from Claire Claassen: Competitive Programming & Problem Solving

… using the network elements

… without violating the capacities on arcs and

nodes

from Henry Wang: Maximum Flow Problem with R

Folie 3
Network Flow Model - Examples
 material flow system for conveying and processing pallets

Source: Fa. Baust

Folie 4
Network Flow Model - Examples
 flight networks for the tansportation of air cargo

Source: Lin, Nguyen (2018)

Folie 5
Network Flow Model - Examples
 intermodal networks for cargo tansportation

Source: Le, Rianmora, Kewcharoewong (2018)

Folie 6
Network Flow Model - Examples
 liquid flows through pipes

Source: Fragiadakis et al. (2013)

Folie 7
Network Flow Model
Representation by a directed Graph 𝐺 = (𝑉, 𝐴) with

 set 𝑉: nodes (vertices) containing

- source node 𝑠
- target node 𝑡
from Claire Claassen: Competitive Programming & Problem Solving

 set 𝐴: arcs (directed connections between the nodes)

 for 𝑖, 𝑗 ∈ 𝐴:

upper bound (capacity) 𝑐𝑖𝑗 ≥ 0

lower bound 𝑙𝑖𝑗 (often zero)

from Henry Wang: Maximum Flow Problem with R

Folie 8
Maximum Flow Problem
Flow properties

Capacity on arcs 0 ≤ 𝑓𝑖𝑗 ≤ 𝑐𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴

… meet capacity limits on arcs

… no negative flows

if 𝑖, 𝑗 ∉ 𝐴 then 𝑐𝑖𝑗 = 0

… for practical reasons:

(1) define 𝐴 = 𝑉 ∗ 𝑉

(2) assign capacities > 0 for all „real“ arcs

Folie 9
Maximum Flow Problem
Flow properties

Flow conservation σ𝑖∈V 𝑓𝑖𝑗 − σ𝑖∈𝑉 𝑓𝑗𝑖 = 0 ∀𝑗 ∈ V\{𝑠, 𝑡}

… total incoming flow = total outgoing flow

Folie 10
 Maximum Flow Problem
Flow properties

Skew symmetry 𝑓𝑖𝑗 = −𝑓𝑗𝑖 ∀ 𝑖, 𝑗 ∈ 𝐴

10 CU DRS to MUC = -10 CU from MUC to DRS

𝑹
Capacity Flow Residual Capacity 𝒄𝒊𝒋 = 𝒄𝒊𝒋 − 𝒇𝒊𝒋

20 10 / 20 20 – 10 = 10

i j i j i j

0 - 10 / 0 0 – (-10) =10
You can add another 10 CU to flow (i,j).
You can delete 10 CU from the flow (i,j).

Folie 11
Maximum Flow Problem
Flow properties

Net Flow

 𝒇𝒏𝒆𝒕 = σ𝑖∈𝑉 𝑓𝑠𝑖 = σ𝑖∈𝑉 𝑓𝑖𝑡

12 units 12 units
leaving s arriving at t

Folie 12
Maximum Flow Problem
Problem Formulation

Variables: 𝑓𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴 … non-negative flow on arc (i,j)

Objective: 𝑚𝑎𝑥 σ𝑗∈𝑉 𝑓𝑠𝑗 … maximize total outgoing flow from source s

Constraints:

Flow conservation σ𝑖∈V 𝑓𝑖𝑗 − σ𝑖∈𝑉 𝑓𝑗𝑖 = 0 ∀𝑗 ∈ V\{𝑠, 𝑡}

… total incoming flow = total outgoing flow

Capacity on arcs 0 ≤ 𝑓𝑖𝑗 ≤ 𝑐𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴

… meet capacity limits on arcs

Integrality theorem:

If all arc capacities are integers, then the optimal solution only contains integer flow values.

Folie 13
Maximum Flow Problem
Solution

(1) Modeling as Linear Program using ZIMPL/SCIP

(2) Ford-Fulkerson-Algorithm

(3) Edmonds-Karp-Algorithm

Folie 14
Maximum Flow Problem

Folie 15
Maximum Flow Problem
Ford-Fulkerson-Algorithm (1956 by Lester R. Ford and Delbert R. Fulkerson)

 computes the maximum flow in flow networks

 Idea:
Increase the flow from source node to target node as long as there is a path with available capacity (a so
called augmenting path)! So the idea is to search for such a path.

 Auxiliary means:
Residual network 𝐺 𝑅 = 𝑉, 𝐴𝑅 , where all arcs have a capacity 𝑐𝑖𝑗
𝑅
= 𝑐𝑖𝑗 − 𝑓𝑖𝑗 , containing also back-arcs
(describing flows that can be added or delete from an arc)

Using skew symmetry 𝑓𝑖𝑗 = −𝑓𝑗𝑖 ∀ 𝑖, 𝑗 ∈ 𝐴

10 CU from DRS to MUC = -10 CU from MUC to DRS

(offers the possibility to delete some CU from DRS to MUC if necessary)

Folie 16
Maximum Flow Problem
Ford-Fulkerson-Algorithm (1956 by Lester R. Ford and Delbert R. Fulkerson)

Input: Given a network G=(V,A) with flow capacity, source node and target node

1. Initialization: 𝑓𝑖𝑗 ← 0 ∀ 𝑖, 𝑗 ∈ 𝐴 … all flows are zero

𝑓𝑗𝑖 ← 0 ∀ 𝑗, 𝑖 ∈ 𝐴∗ … introduce additional reverse arcs

2. While there is a path 𝑝 from s to t in 𝐺 𝑅 with 𝑐 𝑅 > 0 ∀ 𝑖, 𝑗 ∈ 𝑝:

a) Find 𝑐 𝑅 𝑝 = min{𝑐𝑖𝑗
𝑅
∶ 𝑖, 𝑗 ∈ 𝑝} … determine the bottleneck section of the path

b) For each arc 𝑖, 𝑗 ∈ 𝑝

i) original arc: 𝑓𝑖𝑗 ← 𝑓𝑖𝑗 + 𝑐 𝑅 (𝑝) … add flow to the original arc

ii) reverse arc: 𝑓𝑗𝑖 ← 𝑓𝑗𝑖 − 𝑐 𝑅 (𝑝) … delete flow from the original arc

Output: Compute a flow 𝑓 from s to t of maximum value

Folie 17
Maximum Flow Problem
Ford-Fulkerson-Algorithm (1956 by Lester R. Ford and Delbert R. Fulkerson)

Input: Given a network G=(V,A) with flow capacity, source node and target node

1. Initialization: 𝑓𝑖𝑗 ← 0 ∀ 𝑖, 𝑗 ∈ 𝐴 … all flows are zero

𝑓𝑗𝑖 ← 0 ∀ 𝑗, 𝑖 ∈ 𝐴∗ … introduce additional reverse arcs

2. While there is a path 𝑝 from s to t in 𝐺 𝑅 with 𝑐 𝑅 > 0 ∀ 𝑖, 𝑗 ∈ 𝑝: How to find out?

a) Find 𝑐 𝑅 𝑝 = min{𝑐𝑖𝑗
𝑅
∶ 𝑖, 𝑗 ∈ 𝑝} … determine the bottleneck section of the path

b) For each arc 𝑖, 𝑗 ∈ 𝑝

i) original arc: 𝑓𝑖𝑗 ← 𝑓𝑖𝑗 + 𝑐 𝑅 (𝑝) … add flow to the original arc

ii) reverse arc: 𝑓𝑗𝑖 ← 𝑓𝑗𝑖 − 𝑐 𝑅 (𝑝) … delete flow from the original arc

Output: Compute a flow 𝑓 from s to t of maximum value

Folie 18
Maximum Flow Problem
Edmonds-Karp-Algorithm (1956 by Lester R. Ford and Delbert R. Fulkerson)

 Intension: Find short augmenting paths (with a small number of arcs)

 Use breath-first-search for finding augmenting paths

Folie 19
Maximum Flow Problem

Some tricks for Ford/Fulkerson and Edmond/Karp

Reverse arcs

 Avoid reverse arcs in the original graph. They would appear in the residual graph as well.
This may cause some confusion.
 Instead: Introduce an addition node

Folie 20
Maximum Flow Problem

Some tricks for Ford/Fulkerson and Edmond/Karp

Node capacity

 Split the node and introduce an arc between. Assign the node capacity to this arc.

Folie 21
Maximum Flow Problem

Max Flow / Min Cut theorem

 A „cut“ divides the set of nodes into a subset including the source and a subset including the target (sink).
 The minimal cut represents the (composed) bottleneck of the network and therefore is equal to the
maximum network flow.

Folie 22
Minimum Cost Flow Problem
Problem Formulation

Variables: 𝑓𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴 … non-negative flow on arc (i,j)

Objective: 𝑚𝑖𝑛 σ 𝑖,𝑗 ∈𝐴 𝑓𝑖𝑗 𝑎𝑖𝑗 … maximize total outgoing flow from source s

… with a[i,j] as cost that occure for using arc (i,j)

Constraints:

Flow conservation σ𝑖∈V 𝑓𝑖𝑗 − σ𝑖∈𝑉 𝑓𝑗𝑖 = 0 ∀𝑗 ∈ V\{𝑠, 𝑡}

… total incoming flow = total outgoing flow

Capacity on arcs 0 ≤ 𝑓𝑖𝑗 ≤ 𝑐𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴

… meet capacity limits on arcs

Required Flow σ𝑖∈𝑉 𝑓𝑠𝑖 = σ𝑖∈𝑉 𝑓𝑖𝑡 = 𝑑

…set a defined flow from s to t

Folie 23