Management of Transportation

Supplement 1 - Basic Network Flow Models

Dr. Yassine BENRQYA

Al Akhawayn University in Ifrane, Morocco

Y.Benrqya@aui.ma

Spring 2024

February 7, 2024
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 1 / 51
Outline

1 Introduction

2 The Transportation Problem

3 The Transshipment Problem

4 The Shortest Path Problem

5 The Maximum Flow Problem

6 The Minimum Cost Flow Problem

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 2 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;
4 managing container terminals at ports;

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;
4 managing container terminals at ports;
5 managing flight of planes between interconnected airports;

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;
4 managing container terminals at ports;
5 managing flight of planes between interconnected airports;
6 etc.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;
4 managing container terminals at ports;
5 managing flight of planes between interconnected airports;
6 etc.
Network flow models provide efficient ways to represent and to
understand the problems’ underlying structure.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Introduction

Network and network flows are fundamental concepts in logistics and

transportation.
Example of logistical problems that can using network flow models
include:
1 goods being transported in the supply chain;
2 traffic moving in urban networks;
3 connecting cities by roads or railway;
4 managing container terminals at ports;
5 managing flight of planes between interconnected airports;
6 etc.
Network flow models provide efficient ways to represent and to
understand the problems’ underlying structure.
They provide significant advantages over traditional linear mixed
integer programming models in terms of computational efficiency
thanks to specialized solution algorithms.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 3 / 51

Transportation in the Economy
Significant economic impact

This chapter: a gentle introduction to a few basic network flow models.

The Transportation Problem.
The Transshipment Problem.
The Shortest Path Problem.
The Maximum Flow Problem.
The Minimum Cost Flow Problem.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 4 / 51

The Transportation Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 5 / 51

The Transportation Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 5 / 51

The Transportation Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 Each unit produced at supply node i and shipped to demand node j
incurs a variable cost of cij , i = 1, 2, ..., m, j = 1, 2, ..., n.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 5 / 51

The Transportation Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 Each unit produced at supply node i and shipped to demand node j
incurs a variable cost of cij , i = 1, 2, ..., m, j = 1, 2, ..., n.
Decisions variables:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 5 / 51

The Transportation Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 Each unit produced at supply node i and shipped to demand node j
incurs a variable cost of cij , i = 1, 2, ..., m, j = 1, 2, ..., n.
Decisions variables:
1 xij = quantity of the good shipped from supply node i to demand node
j, i = 1, 2, ..., m,j = 1, 2, ..., n.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 5 / 51

The Transportation Problem
General Formulation

General formulation
Objective:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 6 / 51

The Transportation Problem
General Formulation

General formulation
Objective:
∑
m ∑
n
Min cij xij
i=1 j=1

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 6 / 51

The Transportation Problem
General Formulation

General formulation
Objective:
∑
m ∑
n
Min cij xij
i=1 j=1

Constraints:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 6 / 51

The Transportation Problem
General Formulation

General formulation
Objective:
∑
m ∑
n
Min cij xij
i=1 j=1

Constraints:
∑
n
xij ≤ si i = 1, . . . , m (node i’s supply)
j=1
∑m
xij ≥ dj j = 1, . . . , n (node j’s demand)
i=1
xij ≥ 0 i = 1, . . . , m j = 1, . . . , n (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 6 / 51

The Transportation Problem
Illustrative Example

Powerco Electricity Distribution:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 7 / 51

The Transportation Problem
Illustrative Example

Powerco Electricity Distribution:

Powerco has three electric power plants that supply the needs of four cities. Each power
plant can supply the following numbers of kilowatt-hours (KWh) of electricity: plant 1,
35 million; plant 2, 50 million; plant 3, 40 million. The peak power demands in these
cities, which occur at the same time (2 PM), are as follows (in KWh): city 1, 45 million;
city 2, 20 million; city 3, 30 million; city 4, 30 million. The costs of sending 1 million
KWh of electricity from plant to city are indicated below.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 7 / 51

The Transportation Problem
Illustrative Example

Powerco Electricity Distribution:

Powerco has three electric power plants that supply the needs of four cities. Each power
plant can supply the following numbers of kilowatt-hours (KWh) of electricity: plant 1,
35 million; plant 2, 50 million; plant 3, 40 million. The peak power demands in these
cities, which occur at the same time (2 PM), are as follows (in KWh): city 1, 45 million;
city 2, 20 million; city 3, 30 million; city 4, 30 million. The costs of sending 1 million
KWh of electricity from plant to city are indicated below.

To
From Supply (million KWh)
City 1 City 2 City 3 City 4
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12 $13 $7 50
Plant 3 $14 $9 $16 $5 40
Demand (million KWh) 45 20 30 30

Problem:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 7 / 51

The Transportation Problem
Illustrative Example

Powerco Electricity Distribution:

Powerco has three electric power plants that supply the needs of four cities. Each power
plant can supply the following numbers of kilowatt-hours (KWh) of electricity: plant 1,
35 million; plant 2, 50 million; plant 3, 40 million. The peak power demands in these
cities, which occur at the same time (2 PM), are as follows (in KWh): city 1, 45 million;
city 2, 20 million; city 3, 30 million; city 4, 30 million. The costs of sending 1 million
KWh of electricity from plant to city are indicated below.

To
From Supply (million KWh)
City 1 City 2 City 3 City 4
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12 $13 $7 50
Plant 3 $14 $9 $16 $5 40
Demand (million KWh) 45 20 30 30

Problem:
Powerco would like to determine how electricity should be transported such that each
city’s peak power demand is met at the minimum total electricity transportation cost.
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 7 / 51
The Transportation Problem
Illustrative Example

Decision variables: xij , the amount of electricity in (million) KWh

generated at plant i and sent to city j, i ∈ 1, 2, 3 and j ∈ 1, 2, 3, 4.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 8 / 51

The Transportation Problem
Illustrative Example

Decision variables: xij , the amount of electricity in (million) KWh

generated at plant i and sent to city j, i ∈ 1, 2, 3 and j ∈ 1, 2, 3, 4.
Min 8x11 + 6x12 + 10x13 + 9x14 + 9x21 + 12x22 + 13x23 + 7x24 + 14x31 + 9x32 +
16x33 + 5x34

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 8 / 51

The Transportation Problem
Illustrative Example

Decision variables: xij , the amount of electricity in (million) KWh

generated at plant i and sent to city j, i ∈ 1, 2, 3 and j ∈ 1, 2, 3, 4.
Min 8x11 + 6x12 + 10x13 + 9x14 + 9x21 + 12x22 + 13x23 + 7x24 + 14x31 + 9x32 +
16x33 + 5x34

s.t. x11 + x12 + x13 + x14 ≤ 35 (Plant 1 supply)

x21 + x22 + x23 + x24 ≤ 50 (Plant 2 supply)
x31 + x32 + x33 + x34 ≤ 40 (Plant 3 supply)
x11 + x21 + x31 ≥ 45 (City 1 demand)
x12 + x22 + x32 ≥ 20 (City 2 demand)
x13 + x23 + x33 ≥ 20 (City 3 demand)
x14 + x24 + x34 ≥ 30 (City 4 demand)
xij ≥ 0 i = 1, . . . , 4 j = 1, . . . , 3(non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 8 / 51

The Transportation Problem
Illustrative Example - The Minimum Cell Cost Method

The Minimum Cell Cost Algorithm

1 Select the cell with the least unit transportation cost and allocate as
many units as possible to that cell.
2 If the minimum cost exists in several cells, select a cell arbitrarily and
assign the possible number of goods. Then consider the remaining
cells of the same unit transportation cost.
3 Select a cell with the next higher unit transportation cost and
continue the process till all requirements are met.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 9 / 51

The Transportation Problem
Illustrative Example - Stepping Stone Method

1 Firstly, the empty cell is selected and then the closed path is created which starts from the
unoccupied cell and returns to the same unoccupied cell, called as a “closed loop”. For creating
a closed loop the following conditions should be kept in mind:
In a closed loop, cells are selected in a sequence such that one cell is unused/unoccupied, and all
other cells are used/occupied.
A pair of Consecutive used cells lies either in the same row or the same column.
No three consecutive occupied cells can either be in the same row or column.
The first and last cells in the closed loop lies either in the same row or column.
Only horizontal and vertical movement is allowed.
2 Once the loop is created, assign “+” or “–“ sign alternatively on each corner cell of the loop,
but begin with the “+” sign for the unoccupied cell.
3 Repeat these steps again until all the unoccupied cells get evaluated.
4 Now, if all the computed changes are positive or are equal to or greater than zero, then the
optimal solution has been reached.
5 But in case, if any, value comes to be negative, then there is a scope to reduce the transportation
cost further. Then, select that unoccupied cell which has the most negative change and assign
as many units as possible. Subtract the unit that added to the unoccupied cell from the other
cells with a negative sign in a loop, to balance the demand and supply requirements.
6 With the new matrix so formed, again the empty cells will be evaluated through a loop
formation and signs will be assigned accordingly. The cell with the highest opportunity cost will
be assigned the units, and this process will repeat until the best optimum solution is obtained or
the opportunity cost of all the unoccupied cells comes to be negative.
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 10 / 51
The Transportation Problem
Exercise

A paper manufacturer having two mills must supply weekly three printing plants
with newsprint. The shipping costs, in dollars per ton, the supply and the demand
are as follows:

To
From Supply
Plant 1 Plant 2 Plant 3
Mill 1 $17 $22 $15 350
Mill 2 $18 $16 $12 550
Demand (tons of newsprint per week) 275 325 300

Part 1: The problem is to determine how many tons each mill should ship to each
plant so that the total transportation cost is minimal.
Formulate the problem using linear programming
Solve using Excel.
Part 2: In the above transportation problem, suppose that the truck assigned to
the Mill 2 to Plant 2 route is temporarily out of service, and that if this shipping
link is to be utilized, a replacement vehicle must be rented, at a weekly rate of
$700 (plus the variable shipping cost).
Formulate the new problem using linear programming. Solve using Excel
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 11 / 51
The Transportation Problem
Exercise

Part 1:
To formulate the mathematical model, let xij denote the amount in tons to be
shipped weekly from Mill i to Plant j, for i = 1, 2 and j = 1, 2, 3. Then each xij
must be nonnegative. Moreover, the amount shipped from each mill cannot exceed
the supply:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 12 / 51

The Transportation Problem
Exercise

Part 1:
To formulate the mathematical model, let xij denote the amount in tons to be
shipped weekly from Mill i to Plant j, for i = 1, 2 and j = 1, 2, 3. Then each xij
must be nonnegative. Moreover, the amount shipped from each mill cannot exceed
the supply:

x11 + x12 + x13 = 350 (Mill 1 supply)

x21 + x22 + x23 = 550 (Mill 2 supply)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 12 / 51

The Transportation Problem
Exercise

Part 1:
To formulate the mathematical model, let xij denote the amount in tons to be
shipped weekly from Mill i to Plant j, for i = 1, 2 and j = 1, 2, 3. Then each xij
must be nonnegative. Moreover, the amount shipped from each mill cannot exceed
the supply:

x11 + x12 + x13 = 350 (Mill 1 supply)

x21 + x22 + x23 = 550 (Mill 2 supply)

We have equalities here, since the total weekly supply is equal to the total
demand, and thus all the available newsprint at both mills must be shipped,
leaving no surplus:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 12 / 51

The Transportation Problem
Exercise

Part 1:
To formulate the mathematical model, let xij denote the amount in tons to be
shipped weekly from Mill i to Plant j, for i = 1, 2 and j = 1, 2, 3. Then each xij
must be nonnegative. Moreover, the amount shipped from each mill cannot exceed
the supply:

x11 + x12 + x13 = 350 (Mill 1 supply)

x21 + x22 + x23 = 550 (Mill 2 supply)

We have equalities here, since the total weekly supply is equal to the total
demand, and thus all the available newsprint at both mills must be shipped,
leaving no surplus:

x11 + x21 = 275 (Plant 1 demand)

x12 + x22 = 325 (Plant 2 demand)
x13 + x23 = 300 (Plant 3 demand)
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 12 / 51
The Transportation Problem
Exercise

Part 1:
The total shipping cost is:

Min 17x11 + 22x12 + 15x13 + 18x21 + 16x22 + 12x23

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 13 / 51

The Transportation Problem
Exercise

Part 2:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 14 / 51

The Transportation Problem
Exercise

Part 2:
x11 + x12 + x13 = 350 (Mill 1 supply)
x21 + x22 + x23 = 550 (Mill 2 supply)
x11 + x21 = 275 (Plant 1 demand)
x12 + x22 = 325 (Plant 2 demand)
x13 + x23 = 300 (Plant 3 demand)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 14 / 51

The Transportation Problem
Exercise

Part 2:
x11 + x12 + x13 = 350 (Mill 1 supply)
x21 + x22 + x23 = 550 (Mill 2 supply)
x11 + x21 = 275 (Plant 1 demand)
x12 + x22 = 325 (Plant 2 demand)
x13 + x23 = 300 (Plant 3 demand)

If the link Mill 2 to Plant 2 is used, the rental fee of $700 is independent of the
number of tons shipped; the product 700x22 cannot be simply added to the above
cost function. What is needed is an ”on/off” variable, a variable that is 1 if the
link is used (x22 > 0) and 0 if the link is not used (x22 = 0). Using y to denote the
variable, we add to the above constraints the restrictions y ≥ 3251
x22 , and to the
cost function the term 700y:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 14 / 51

The Transportation Problem
Exercise

Part 2:
x11 + x12 + x13 = 350 (Mill 1 supply)
x21 + x22 + x23 = 550 (Mill 2 supply)
x11 + x21 = 275 (Plant 1 demand)
x12 + x22 = 325 (Plant 2 demand)
x13 + x23 = 300 (Plant 3 demand)

If the link Mill 2 to Plant 2 is used, the rental fee of $700 is independent of the
number of tons shipped; the product 700x22 cannot be simply added to the above
cost function. What is needed is an ”on/off” variable, a variable that is 1 if the
link is used (x22 > 0) and 0 if the link is not used (x22 = 0). Using y to denote the
variable, we add to the above constraints the restrictions y ≥ 3251
x22 , and to the
cost function the term 700y:
1
y≥ 325 x22

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 14 / 51

The Transportation Problem
Exercise

Part 2:
x11 + x12 + x13 = 350 (Mill 1 supply)
x21 + x22 + x23 = 550 (Mill 2 supply)
x11 + x21 = 275 (Plant 1 demand)
x12 + x22 = 325 (Plant 2 demand)
x13 + x23 = 300 (Plant 3 demand)

If the link Mill 2 to Plant 2 is used, the rental fee of $700 is independent of the
number of tons shipped; the product 700x22 cannot be simply added to the above
cost function. What is needed is an ”on/off” variable, a variable that is 1 if the
link is used (x22 > 0) and 0 if the link is not used (x22 = 0). Using y to denote the
variable, we add to the above constraints the restrictions y ≥ 3251
x22 , and to the
cost function the term 700y:
1
y≥ 325 x22

Min 17x11 + 22x12 + 15x13 + 18x21 + 16x22 + 12x23 + 700y

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 14 / 51
The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.
Shipping problems with any or all of these characteristics are
transshipment problems.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.
Shipping problems with any or all of these characteristics are
transshipment problems.
In what follows, we define:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.
Shipping problems with any or all of these characteristics are
transshipment problems.
In what follows, we define:
a supply point to be a point that can send goods to another point but
cannot receive goods from any other point.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.
Shipping problems with any or all of these characteristics are
transshipment problems.
In what follows, we define:
a supply point to be a point that can send goods to another point but
cannot receive goods from any other point.
a demand point is a point that can receive goods from other points
but cannot send goods to any other point.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
Introduction

A transportation problem allows only shipments that go directly from

a supply point to a demand point.
Sometimes there may also be points (called transshipment points)
through which goods can be transshipped.
Shipping problems with any or all of these characteristics are
transshipment problems.
In what follows, we define:
a supply point to be a point that can send goods to another point but
cannot receive goods from any other point.
a demand point is a point that can receive goods from other points
but cannot send goods to any other point.
A transshipment point is a point that can both receive goods from
other points and send goods to other points.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 15 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 A set of l transshipment nodes that serve as intermediaries between
supply and demand nodes. Transshipment node k = 1, 2, ..., l has no
demand or supply of its own.
4 Each unit produced at supply node i and shipped to transshipment
node k incurs a variable cost of cik , i = 1, 2, ..., m, k = 1, 2, ..., l.
5 Each unit shipped from transshipment node k to demand node j incurs
a variable cost of ckj , k = 1, 2, ..., l, j = 1, 2, ..., n.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 A set of l transshipment nodes that serve as intermediaries between
supply and demand nodes. Transshipment node k = 1, 2, ..., l has no
demand or supply of its own.
4 Each unit produced at supply node i and shipped to transshipment
node k incurs a variable cost of cik , i = 1, 2, ..., m, k = 1, 2, ..., l.
5 Each unit shipped from transshipment node k to demand node j incurs
a variable cost of ckj , k = 1, 2, ..., l, j = 1, 2, ..., n.
Decisions variables:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 A set of l transshipment nodes that serve as intermediaries between
supply and demand nodes. Transshipment node k = 1, 2, ..., l has no
demand or supply of its own.
4 Each unit produced at supply node i and shipped to transshipment
node k incurs a variable cost of cik , i = 1, 2, ..., m, k = 1, 2, ..., l.
5 Each unit shipped from transshipment node k to demand node j incurs
a variable cost of ckj , k = 1, 2, ..., l, j = 1, 2, ..., n.
Decisions variables:
1 xik = quantity of the good shipped from supply node i to
transshipment node k, i = 1, 2, ..., m, k = 1, 2, ..., l.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51

The Transshipment Problem
General Formulation

Parameters:
1 A set of m supply nodes from which a good is shipped. Supply node
i = 1, 2, ..., m can supply at most a quantity si .
2 A set of n demand nodes to which a good is shipped. Demand node
j = 1, 2, ..., n needs to receive at least a quantity dj .
3 A set of l transshipment nodes that serve as intermediaries between
supply and demand nodes. Transshipment node k = 1, 2, ..., l has no
demand or supply of its own.
4 Each unit produced at supply node i and shipped to transshipment
node k incurs a variable cost of cik , i = 1, 2, ..., m, k = 1, 2, ..., l.
5 Each unit shipped from transshipment node k to demand node j incurs
a variable cost of ckj , k = 1, 2, ..., l, j = 1, 2, ..., n.
Decisions variables:
1 xik = quantity of the good shipped from supply node i to
transshipment node k, i = 1, 2, ..., m, k = 1, 2, ..., l.
2 xik = quantity of the good shipped from transshipment node k to
demand node j, k = 1, 2, ..., l, j = 1, 2, ..., n.
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 16 / 51
The Transshipment Problem
General Formulation

Objective:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 17 / 51

The Transshipment Problem
General Formulation

Objective:
∑
m ∑
l ∑
l ∑
n
Min cik xik + ckj xkj
i=1 k=1 k=1 j=1

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 17 / 51

The Transshipment Problem
General Formulation

Objective:
∑
m ∑
l ∑
l ∑
n
Min cik xik + ckj xkj
i=1 k=1 k=1 j=1

Constraints:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 17 / 51

The Transshipment Problem
General Formulation

Objective:
∑
m ∑
l ∑
l ∑
n
Min cik xik + ckj xkj
i=1 k=1 k=1 j=1

Constraints:
∑
l
xik ≤ si i = 1, . . . , m (node i’s supply)
k=1
∑
l
xkj ≥ dj j = 1, . . . , n (node j’s demand)
k=1
∑
m ∑
ln
xik = xkj k = 1, . . . , l (flow balance at ode k)
i=1 j=1

xik ≥ 0 i = 1, . . . , m k = 1, . . . , l (non-negativity)
xkj ≥ 0 j = 1, . . . , n k = 1, . . . , l (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 17 / 51

The Transshipment Problem
Illustrative Example

Smartwind:
Smartwind manufactures windows at two factories, one in Fes and one in Tangier.
Windows are shipped by trucks to two wholesalers in Marrakech and Agadir. Because of
some regulations, Smartwind needs to first transship windows to Casablanca or Rabat
and then transport them to their final destinations. The costs of transporting a Window
are shown in the table below. Smartwind wants to minimize the total cost of
transporting the required windows to its customers.

To (MAD)
From Supply
Rabat Casablanca Marrakech Agadir
Fes 250 200 0 0 120
Tangier 350 400 0 0 220
Rabat 0 0 400 430
Casablanca 0 0 300 350
Demand 150 150

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 18 / 51

The Transshipment Problem
Illustrative Example

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 19 / 51

The Transshipment Problem
Illustrative Example

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 19 / 51

The Transshipment Problem
Illustrative Example

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Min 250x13 + 200x14 + 350x23 + 400x24 + 400x35 + 430x36 + 300x45 + 350x46

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 19 / 51

The Transshipment Problem
Illustrative Example

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Min 250x13 + 200x14 + 350x23 + 400x24 + 400x35 + 430x36 + 300x45 + 350x46

s.t. x13 + x14 ≤ 120 (Fes supply)

x23 + x24 ≤ 220 (Tangier supply)
x13 + x23 = x35 + x36 (Balance at Rabat)
x14 + x24 = x45 + x46 (Balance at Casablanca)
x35 + x45 ≥ 150 (Marrakech demand)
x36 + x46 ≥ 150 (Agadir demand)
xij , xjk ≥ 0 i = 1, 2 k = 3, 4 j = 5, 6 (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 19 / 51

The Transshipment Problem
Exercise

Widgetco:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 20 / 51

The Transshipment Problem
Exercise

Widgetco:
Widgetco manufactures widgets at two factories, one in Memphis and one in Denver.
Widgets are shipped by air to customers in Los Angeles and Boston. Because of the
deregulation of airfares, Widgetco believes that it may be cheaper to first fly some
widgets to New York or Chicago and then fly them to their final destinations. The costs
of flying a widget are shown in Table below. Widgetco wants to minimize the total cost
of shipping the required widgets to its customers.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 20 / 51

The Transshipment Problem
Exercise

Widgetco:
Widgetco manufactures widgets at two factories, one in Memphis and one in Denver.
Widgets are shipped by air to customers in Los Angeles and Boston. Because of the
deregulation of airfares, Widgetco believes that it may be cheaper to first fly some
widgets to New York or Chicago and then fly them to their final destinations. The costs
of flying a widget are shown in Table below. Widgetco wants to minimize the total cost
of shipping the required widgets to its customers.

To
From Supply
Memphis Denver N.Y. Chicago L.A. Boston
Memphis $0 - $8 $13 $25 $28 150
Denver - $0 $15 $12 $26 $25 200
N.Y. - - $0 $6 $16 $17
Chicago - - $6 $0 $14 $16
L.A. - - - - $0 -
Boston - - - - - $0
Demand 130 130

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 20 / 51

The Transshipment Problem
Exercise

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 21 / 51

The Transshipment Problem
Exercise

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 21 / 51

The Transshipment Problem
Exercise

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Min 250x13 + 200x14 + 350x23 + 400x24 + 400x35 + 430x36 + 300x45 + 350x46

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 21 / 51

The Transshipment Problem
Exercise

xik , the number of windows produced at plant i and sent to transshipment k,

i ∈ 1, 2 and k ∈ 3, 4.
xkj , the number of windows transshipped at k and sent to wholesaler j,
k ∈ 3, 4 and j ∈ 5, 6.

Min 250x13 + 200x14 + 350x23 + 400x24 + 400x35 + 430x36 + 300x45 + 350x46

s.t. x13 + x14 ≤ 150 (Fes supply)

x23 + x24 ≤ 200 (Tangier supply)
x13 + x23 = x35 + x36 (Balance at Rabat)
x14 + x24 = x45 + x46 (Balance at Casablanca)
x35 + x45 ≥ 150 (Marrakech demand)
x36 + x46 ≥ 150 (Agadir demand)
xij , xjk ≥ 0 i = 1, 2 k = 3, 4 j = 5, 6 (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 21 / 51

The Shortest Path Problem
Example

Another Powerco Electricity Distribution Problem:

The company needs to send power from a plant located at node 1 to a city located at
node 6. Power transported needs to move through relay substations located at nodes 2
to 5. For any pair of nodes between which power can be transported, the figure below
gives the distance (in miles) between the nodes. Powerco wants the power sent from the
origin plant to the destination city to travel the minimum possible distance, so it must
determine the shortest path that joins node 1 to node 6.

3
2 4

2
4

1 6
3

2
3
3 5

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 22 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Powerco’s small instance straightforward to solve by inspection.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 23 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Powerco’s small instance straightforward to solve by inspection.

We need an algorithm for efficient solution of large instances.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 23 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Powerco’s small instance straightforward to solve by inspection.

We need an algorithm for efficient solution of large instances.

Dijkstra’s Algorithm

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 23 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Powerco’s small instance straightforward to solve by inspection.

We need an algorithm for efficient solution of large instances.

Dijkstra’s Algorithm
To begin, label node 1 with a permanent label of 0. Then label each
node i connected to node 1 by an arc with a temporary label of +∞.
Associate with each node i ̸= 1, a predecessor denoted pred(i).

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 23 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Powerco’s small instance straightforward to solve by inspection.

We need an algorithm for efficient solution of large instances.

Dijkstra’s Algorithm
To begin, label node 1 with a permanent label of 0. Then label each
node i connected to node 1 by an arc with a temporary label of +∞.
Associate with each node i ̸= 1, a predecessor denoted pred(i).
After this initialization step, do the following until all nodes receive a
permanent label.
1 Choose the node with the smallest temporary label and make this label permanent.
2 Assume that the node chosen is node i.
3 For all nodes j that are immediate successors of i in the network and do not have a
permanent label yet, do the following: if label(j) > label(i) + distance(i, j) then
replace label(j) with label(i) + distance(i, j) and replace pred(j) with i.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 23 / 51

The Shortest Path Problem
Dijkstra’s Algorithm

Solve the problem represented by the network below using Dijkstra’s

Algorithm. Show clearly all the steps of the algorithm in action.

1
a b
5

4
2
s e
3

1
1

2
1

5
c d

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 24 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.
4 ckj : the cost of traveling on arc (i, j), (i, j) ∈ A.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.
4 ckj : the cost of traveling on arc (i, j), (i, j) ∈ A.
Imagine we are sending a single (virtual) token from o to d.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.
4 ckj : the cost of traveling on arc (i, j), (i, j) ∈ A.
Imagine we are sending a single (virtual) token from o to d.
Node o has a supply of 1, node d has a demand of 1, and all other
nodes in the network have no supply or demand (transshipment
nodes).

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.
4 ckj : the cost of traveling on arc (i, j), (i, j) ∈ A.
Imagine we are sending a single (virtual) token from o to d.
Node o has a supply of 1, node d has a demand of 1, and all other
nodes in the network have no supply or demand (transshipment
nodes).
Decisions variables:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Parameters:
1 N: a set of nodes.
2 Origin node o ∈ N, destination node d ∈ N.
3 A: a set of arcs.
4 ckj : the cost of traveling on arc (i, j), (i, j) ∈ A.
Imagine we are sending a single (virtual) token from o to d.
Node o has a supply of 1, node d has a demand of 1, and all other
nodes in the network have no supply or demand (transshipment
nodes).
Decisions variables:
1 xik = 1 if arc (i, j) ∈ A is used in the shortest path, and = 0 otherwise.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 25 / 51

The Shortest Path Problem
An Integer Programming Model

Objective:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 26 / 51

The Shortest Path Problem
An Integer Programming Model

Objective: ∑
Min cij xij
(i,j)∈A

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 26 / 51

The Shortest Path Problem
An Integer Programming Model

Objective: ∑
Min cij xij
(i,j)∈A

Constraints:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 26 / 51

The Shortest Path Problem
An Integer Programming Model

Objective: ∑
Min cij xij
(i,j)∈A

Constraints:
∑ ∑
xoj − xjo = 1 (node o’s supply of 1)
j∈Succ(o) j∈Pred(o)
∑ ∑
xdj − xjd = −1 (node d’s demand of -1)
j∈Succ(d) j∈Pred(d)
∑ ∑
xij − xji = 0 i ∈ N, i ̸= o, d (no supply or demand)
j∈Succ(i) j∈Pred(i)

xij = 0, 1 (arc(i, j) used or not) (i, j) ∈ A (non-negativity)

Pred(i):set of all immediate predecessors of node i ∈ N and Succ(i) is the set
of all immediate successors of i ∈ N.
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 26 / 51
The Shortest Path Problem
Exercise

Formulate this problem as a linear (possibly binary) programming

problem. Indicate clearly the problem’s decision variables, objective,
and constraints.
Solve the problem using Excel Solver.

1
a b
5

4
2

s e
3

1
1

2
1

5
c d

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 27 / 51

The Maximum Flow Problem
Illustrative Example

Sunco Oil:
Sunco Oil wants to ship the maximum possible amount of oil (per hour) via
pipeline from node so to node si in Figure below. On its way from node so to node
si, oil must pass through some or all of stations 1, 2, and 3. The various arcs
represent pipelines of different diameters. The maximum number of barrels of oil
(millions of barrels per hour) that can be pumped through each arc is shown in the
figure. Each number is called an arc capacity.
We want to formulate an LP that can be used to determine the maximum number
of barrels of oil per hour that can be sent from so to si .

4 1
3
3 3 2
so 1 2 si

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 28 / 51

The Maximum Flow Problem
Illustrative Example

Sunco Oil:
For reasons that will soon become clear, we have added an artificial arc ao from
the sink to the source. The flow through ao is not actually oil, hence the term
artificial arc.
To formulate an LP that will yield the maximum flow from node so to si , we
observe that Sunco must determine how much oil (per hour) should be sent
through arc (i, j). Thus, we define
(i, j) millions of barrels of oil per hour that will pass through arc (i,j) of pipeline

4 1
3
3 3 2
so 1 2 si

3
ao

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 29 / 51

The Maximum Flow Problem
an Integer Programming Model

Parameters:
1 N: a set of nodes.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 30 / 51

The Maximum Flow Problem
an Integer Programming Model

Parameters:
1 N: a set of nodes.
2 A: a set of arcs.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 30 / 51

The Maximum Flow Problem
an Integer Programming Model

Parameters:
1 N: a set of nodes.
2 A: a set of arcs.
3 uij : the capacity of arc (i, j), (i, j) ∈ A; i.e., it is not possible to send
more than uij units of flow of arc

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 30 / 51

The Maximum Flow Problem
an Integer Programming Model

Parameters:
1 N: a set of nodes.
2 A: a set of arcs.
3 uij : the capacity of arc (i, j), (i, j) ∈ A; i.e., it is not possible to send
more than uij units of flow of arc
Decisions variables:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 30 / 51

The Maximum Flow Problem
an Integer Programming Model

Parameters:
1 N: a set of nodes.
2 A: a set of arcs.
3 uij : the capacity of arc (i, j), (i, j) ∈ A; i.e., it is not possible to send
more than uij units of flow of arc
Decisions variables:
1 xij = ”the flow moved on arc (i, j), (i, j) ∈ A”
2 Add a ”dummy” arc (si, so) linking the sink to the source, and
associate the flow variable xsi,so with it.

4 1
3
3 3 2
so 1 2 si

3
ao

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 30 / 51

The Maximum Flow Problem
an Integer Programming Model

Objective:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 31 / 51

The Maximum Flow Problem
an Integer Programming Model

Objective:
Max xsi,so

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 31 / 51

The Maximum Flow Problem
an Integer Programming Model

Objective:
Max xsi,so

Constraints:

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 31 / 51

The Maximum Flow Problem
an Integer Programming Model

Objective:
Max xsi,so

Constraints:
∑ ∑
xij − xji = 0 i∈N (flow conservation at all nodes)
j∈Succ(i) j∈Pred(i)

xij ≤ uji (i, j) ∈ A (capacity constraint)

xij ≥ 0 (i, j) ∈ A ∪ (si, so) (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 31 / 51

The Maximum Flow Problem
Exercise

Fly-By-Night Flight Connection:

Fly-by-Night Airlines must determine how many connecting flights daily can be arranged
between Juneau, Alaska, and Dallas, Texas. Connecting flights must stop in Seattle and
then stop in Los Angeles or Denver. Because of constraints on landing space,
Fly-by-Night is limited to making the number of daily flights between pairs of cities
shown below.

Cities Max. Nbr. of Daily Flights

Juneau - Seattle (J, S) 3
Seattle - L.A. (S, L) 2
Seattle - Denver (S, De) 3
L.A. - Dallas (L, D) 1
Denver - Dallas (De, D) 2

The airline wants to determine a daily flight program in order to maximize the number of
connecting flights from Juneau to Dallas.
1 Formulate this problem as a linear programming problem. Indicate clearly the problem’s
decision variables, objective, and constraints.
2 Solve the problem using Excel Solver.
Dr. Yassine BENRQYA Management of Transportation February 7, 2024 32 / 51
The Maximum Flow Problem
Ford and Fulkerson

The traditional way to solve the maximum flow problem is with the
flow augmenting algorithm developed by Ford and Fulkerson.
The algorithm begins with a feasible set of arc flows obtaining some
value, v0 , for the flow out of the source and into the sink. A search is
then made in the network for a path from source to sink that can
deliver an increased flow. This is called a flow augmenting path. The
flow is increased along that path as much as possible. The process
continues until no such path can be found, at which time the
algorithm terminates.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 33 / 51

The Maximum Flow Problem
Ford and Fulkerson

1 Start with the zero flow (xij = 0 for every edge)

2 On each iteration, try to find a flow-augmenting path from source to sink, along which
some additional flow can be sent
3 If a flow-augmenting path is found, adjust the flow along the edges of this path to get a
flow of increased value and try again
4 If no flow-augmenting path is found, the current flow is maximum
Flow-Augmenting path:
To find a flow-augmenting path, consider paths from source to sink in the underlying
undirected graph in which any two consecutive nodes i, j are either:
connected by a directed edge (i to j) with some positive unused capacity rij = uij − xij
known as forward edge (→)
OR
connected by a directed edge (j to i) with positive flow xij
known as backward edge (←)
If a flow-augmenting path is found, the current flow can be increased by r units by
increasing xij by r on each forward edge and decreasing xij by � on each backward edge,
where r = min rij on all forward edges, xij on all backward edges

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 34 / 51

The Maximum Flow Problem
Ford and Fulkerson

0| 4 0| 1
3
0|2 0|3 0|2
so 1 2 si
0|3

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 35 / 51

The Maximum Flow Problem
Ford and Fulkerson

0| 4 0| 1
3
0|2 0|3 0|2
so 1 2 si
0|3

Augmenting flow on (so, 1, 2, si), with v1 = 2

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 36 / 51

The Maximum Flow Problem
Ford and Fulkerson

0| 4 0| 1
3
2|2 2|3 2|2
so 1 2 si 2
0|3

Augmenting flow on (so, 1, 2, si), with v1 = 2

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 37 / 51

The Maximum Flow Problem
Ford and Fulkerson

0| 4 0| 1
3
2|2 2|3 2|2
so 1 2 si 2
0|3

Augmenting flow on (so, 2, 1,3, si), with v2 = 3

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 38 / 51

The Maximum Flow Problem
Ford and Fulkerson

1| 4 1| 1
3
2|2 1|3 2|2
so 1 2 si 3
1|3

Augmenting flow on (so, 2, 1,3, si), with v2 = 3

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 39 / 51

The Maximum Flow Problem
Ford and Fulkerson

Review of Fig reveals no additional flow augmenting paths so the

maximum flow has been obtained.

1| 4 1| 1
3
2|2 1|3 2|2
so 1 2 si 3
1|3

No Augmenting flow

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 40 / 51

The Maximum Flow Problem
Ford and Fulkerson

Another example:

0|4
1 3
0 0| 1
0| 1 0

0| 8
so si
0|2

0|6
0| 1 0
0 0| 1

0|9
2 4

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 41 / 51

The Maximum Flow Problem
Ford and Fulkerson

Another example:

4|4
1 3
9|1
|10 0
10

6|8
so si
0|2

5|6
19
9|1
0 |10
10

9|9
2 4

Total flow = 19

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 42 / 51

The Maximum Flow Problem
Exercise

Find the maximum flow for the network below using Ford and Fulkerson
algorithm:

5
1 3

5 15

so 5 si
15 5
5

5
2 4

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 43 / 51

The Maximum Flow Problem
Exercise

Find the maximum flow for the network below using Ford and Fulkerson
algorithm:
|5
2 7
|6 |3

|1
2
|1

3
|4 |3

|3 |10
1 3 8 10
|4 |5
|2

2
6

|1
0

|5 |3

|10
4 9

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 44 / 51

The Minimum Cost Flow Problem
Introduction

To define the Minimum Cost Flow problem lets consider the network below:

The transportation, transshipment, shortest-path and maximum flow are all special cases
of the minimum-cost network flow problem (MCNFP).
Each node where the et amount of flow generated (outflow minus inflow) is a fixed
positive number is a supply node.
Each node where the net amount of flow generated is a fixed negative number is a
demand node.
Any node where the net amount of flow generated is fixed at zero is a transshipment
node. Having the amount of the node equal the amount of flow into the node is refereed
to as the conservation of flow.
The maximum amount of flow allowed through an arc is referred to as the capacity of
that arc

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 45 / 51

The Minimum Cost Flow Problem
General Formulation

Parameters:
1 N: a set of nodes.
2 A: a set of arcs.
3 bi : net supply (outflow - inflow) at node i
4 cij : the cost of traveling on arc (i, j).
5 Lij : lower bound on flow through arc (i, j), (”if there is no lower
bound”, letLij = 0)
6 Uij : Upper bound on flow through arc (i, j), (”if there is no Upper
bound”, letUij = ∞)
Decisions variables:
1 xij = ”number of units of flow sent from node i to node j through arc
(i, j)”.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 46 / 51

The Minimum Cost Flow Problem
General Formulation

Objective: ∑
Min cij xij
(i,j)∈A

Constraints:
∑ ∑
xij − xji = bi i∈N (flow conservation at all nodes)
j∈Succ(i) j∈Pred(i)

Lji ≤ xij ≤ Uji (i, j) ∈ A (capacity constraint)

xij ≥ 0 (i, j) ∈ A (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 47 / 51

The Minimum Cost Flow Problem
Exercise

A logistics manager wants to ship materials to customers locations. The materials

are available in warehouses located in Phoenix, Austin, and Gainesville, while
customers are in New York, Chicago, Dallas, Los Angeles, and Atlanta. The
transportation network is depicted below, with supply nodes (in yellow)
representing the warehouses and demand nodes (in blue) the clients. Associated
with each node is its supply (> 0) or demand (< 0). Arcs represent transportation
links between the nodes. Associated with each arc is the unit cost of transport on
the arc. Finally, all arcs have the same flow upper bound (capacity) of 200, and a
lower bound of 0.

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 48 / 51

The Minimum Cost Flow Problem
Exercise

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 49 / 51

The Minimum Cost Flow Problem
Exercise

Decisions variables:

x12 : (flowtransportedbetweenPhoenixandLosAngeles)
x13 : (flowtransportedbetweenPhoenixandChicago)
x14 : (flowtransportedbetweenPhoenixandDallas)
..
..
..
..
x78 : (flowtransportedbetweenGainesvilleandNewYork)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 50 / 51

The Minimum Cost Flow Problem
Exercise

Objective:
Min 4x12 + 6x13 + 3x14 + ....7x78
Constraints:

x12 + x13 + x14 + x15 = 700 (Phoenix)

−x12 − x42 − x62 = −200 (LosAngeles)
−x13 − x43 − x53 = −200 (Chicago)
x42 + x43 + x45 + x48 − x14 − x54 − x64 − x74 = −300 (Dallas)
x53 + x54 + x58 − x15 − x45 − x65 − x75 = −150 (Atlanta)
x62 + x64 + x65 = 200 (Austin)
x74 + x75 + x78 = 200 (Gainesville)
−x48 − x58 − x78 = −250 (NewYork)

xij ≥ 0 (i, j) ∈ A (non-negativity)

Dr. Yassine BENRQYA Management of Transportation February 7, 2024 51 / 51