Management Science Network Flow Model I

Network Flow Model I

Bumho Son
College of Business Administration, CAU
Management Science Network Flow Model I

Network
▪ Network
▪ A set of nodes and connecting arcs or branches
▪ Can be useful in representing various systems, such as:
• distribution systems, production systems, transportation systems, social relations,
supply chain networks…

▪ Network models are an important approach for problem solving

because:
▪ They can be used to model a wide range of problems
▪ They are relatively simple to work with
▪ They provide a visual portrayal of a problem

2
Management Science Network Flow Model I

Network Components
▪ A network is an arrangement of paths (branches) connected at various
points (nodes) through which one or more items move from one point
to another

▪ The network is drawn as a diagram providing a picture of the system,

thus enabling visual representation and enhanced understanding

▪ A large number of real-life systems can be modeled as networks which

are relatively easy to conceive and construct

3
Management Science Network Flow Model I

Network Components
▪ Network diagrams consist of nodes and branches

▪ Nodes (circles), represent junction points, or locations

▪ Branches (lines), connect nodes and represent flow

4
Management Science Network Flow Model I

Network Components
▪ Four nodes, four branches in figure
▪ “Atlanta”, node 1, termed the origin; any of others, destination
▪ Branches identified by beginning and ending node numbers
▪ Value assigned to each branch (distance, time, cost, etc.)

5
Management Science Network Flow Model I

Node and Arcs (Branches)

Node

Arc (branch, edge)

: connects two nodes

This network has 4 nodes and 5 arcs

6
Management Science Network Flow Model I

Frequently Used Problems

▪ Shortest-Route Problem
▪ Determining the shortest time, distance, or cost from an origin to a destination
through a network.

▪ Minimum Spanning Tree Problem

▪ Determining the minimum distance (cost, time) needed to connect a set of
locations into a single system.

▪ Maximal Flow Problem

▪ Determining the greatest amount of flow that can be transmitted through a
system in which various branches, or connections, have specified flow capacity
limitations.

7
Management Science Network Flow Model I

Shortest Route Problem

8
Management Science Network Flow Model I

Shortest Route Problem: Definition and Example

▪ Find the shortest route from 1 to 6

Source, 2
Origin Destination,
5 13
Target
6
8 3 7
1 5 6
1 6
6 16

9
Management Science Network Flow Model I

Shortest Route Problem

▪ Labeling Procedure (Dijkstra Algorithm)
▪ A label is developed for each node
▪ The labels consist of two numbers separated by a comma
▪ The first number refers to the distance from Source node to the labeled node
along a certain path (current shortest distance)
▪ The second number refers to the node that immediately precedes this node
along that path (immediate predecessor)

(Current Shortest Distance, Immediate Predecessor)

10
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Step 1.
▪ Begin at Node 1. Label Node 1 with a permanent label [0,S].
▪ Find the distance from Node 1 to each node that can be reached directly from Node 1.
▪ Temporarily label each of these nodes with their distance from Node 1 followed by a comma
and number 1.
▪ Then select the node that has the smallest distance from Node 1 and make its label
permanent. (by shading in the node and/or bracketing the label)
▪ Step 2.
▪ Find the distance from the new permanent node to each nonpermanent node that can be
reached directly from this node.
▪ Temporarily label each of these nodes with the cumulative distance from Node 1 if a node
has no label, or update node label if the new distance is shorter than its current temporary
label.
▪ Then, consider all nodes that have temporary labels and permanently label the node that
has the smallest cumulative distance from Node 1.
▪ Step 3.
▪ Repeat the preceding step until all nodes have permanent labels.
▪ Step 4.
▪ Identify the shortest route to each node from Node 1 by working backwards through the tree,
according to the nodes specified in the node labels.

11
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Initialization
▪ Label source node with (0,S)
• distance=0, predecessor=none
▪ Make source node’s label permanent (by shading and brackets)
• Permanent label will never change
▪ Update labels of directly reachable nodes from node 1, and make those labels temporary (do
not shade, keep parenthesis)
• Temporary labels can be changed later

(5,1)
2

5 13
(8,1)
[0,S] 6
8 3 7
1 5 6
1 6
6
(6,1) 16

12
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ First Iteration
▪ Determine which temporary label has the smallest distance, and make its label
permanent
▪ Update labels of directly reachable nodes from the newly added permanent node
• unless the node already has permanent label
• unless the distance cannot be improved (if tie exists, specify both)
▪ Stop when destination node have permanent label
[5,1]
2

5 13
(8,1)
[0,S] 6 (18,2)
8 3 7
1 5 6
1 6
6
(6,1) 16

13
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Second Iteration
▪ Determine which temporary label has the smallest distance, and make its label
permanent
▪ Update labels of directly reachable nodes from the newly added permanent node
• unless the node already has permanent label
• unless the distance cannot be improved (if tie exists, specify both)
▪ Stop when destination node have permanent label
[5,1]
2

13
5 (7,4)
[0,S] 6 (8,1) (18,2)
8 7
1 3 5 6 (22,4)
1 6
6
[6,1] 16

14
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Third Iteration
▪ Determine which temporary label has the smallest distance, and make its label
permanent
▪ Update labels of directly reachable nodes from the newly added permanent node
• unless the node already has permanent label
• unless the distance cannot be improved (if tie exists, specify both)
▪ Stop when destination node have permanent label
[5,1]
2

13
5 [7,4] (14,3)
[0,S] 6 (8,1) (18,2)
8 7
1 3 5 6 (22,4)
1 6
6
[6,1] 16

15
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Fourth Iteration
▪ Determine which temporary label has the smallest distance, and make its label
permanent
▪ Update labels of directly reachable nodes from the newly added permanent node
• unless the node already has permanent label
• unless the distance cannot be improved (if tie exists, specify both)
▪ Stop when destination node have permanent label
[5,1]
2

13
5 [7,4] [14,3]
[0,S] 6 (8,1) (18,2) (20,5)
8 7
1 3 5 6 (22,4)
1 6
6
[6,1] 16

16
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Fifth Iteration
▪ Determine which temporary label has the smallest distance, and make its label
permanent
▪ Update labels of directly reachable nodes from the newly added permanent node
• unless the node already has permanent label
• unless the distance cannot be improved (if tie exists, specify both)
▪ Stop when destination node have permanent label

[5,1]
2

13
5 [7,4] [14,3]
[0,S] 6 (8,1) (18,2) [20,5]
8 7
1 3 5 6 (22,4)
1 6
6
[6,1] 16

4
17
Management Science Network Flow Model I

Shortest Route Problem Procedure

▪ Construct the shortest route by Backtracking
▪ Begin with node 6, follow the predecessor.
• 6->5->3->4->1
▪ The shortest route from 1 to 6 is identified as :
• 1-4-3-5-6 (distance=20)
▪ All of the shortest route from 1 to any node can be found similarly
• iterate until all the nodes have permanent labels
• shortest route from 1 to 3?

[5,1]
2

13
5 [7,4] [14,3]
[0,S] 6 (8,1) (18,2) [20,5]
8 7
1 3 5 6 (22,4)
1 6
6
[6,1] 16

4
18
Management Science Network Flow Model I

Shortest Route Problem Exercise

▪ Find the shortest route from node 1 to node 7

2 5

5 15
2 6

1 4 2 7

8
6 10 9
3 6

19
Management Science Network Flow Model I

Shortest Route Problem Example

▪ Problem: Determine the shortest routes from the origin(LA) to all
destinations

20
Management Science Network Flow Model I

Shortest Route Problem Example

21
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

▪ Determine the initial shortest route from the origin (node 1) to the
closest node (3)

The permanent set indicates the

nodes for which the shortest route
to has been found

22
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

▪ Determine all nodes directly connected to the permanent set

23
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

▪ Redefine the permanent set

24
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

25
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

26
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

27
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

▪ Network with optimal routes from LA to all destinations

28
Management Science Network Flow Model I

Shortest Route Problem Example Solution Approach

▪ Shortest travel time from origin to each destination

29
Management Science Network Flow Model I

Summary
1. Select the node with the shortest direct route from the origin

2. Establish a permanent set with the origin node and the node that was
selected in step 1

3. Determine all nodes directly connected to the permanent set nodes

4. Select the node with the shortest route from the group of nodes
directly connected to the permanent set nodes

5. Repeat steps 3 & 4 until all nodes have joined the permanent set

30
Management Science Network Flow Model I

Shortest Route Problem Exercise

▪ Find the shortest route from node 1 to every other nodes

2 5

5 15
2 6

1 4 2 7

8
6 10 9
3 6

31
Management Science Network Flow Model I

Shortest Route Problem Solution: Formulation

▪ Find shortest path from node 1 to node 7
▪ Formulation as a 0 - 1 integer linear programming problem
▪ 𝒙𝒊𝒋 = 𝟎 if branch i-j is not selected as part of the shortest route and 1 if
it is selected

Minimize Z = 16x12 + 9x13 + 35x14 + 12x24 + 25x25 + 15x34 + 22x36

+ 14x45 + 17x46 + 19x47 + 8x57 + 14x67

subject to: x12 + x13 + x14= 1

x12 - x24 - x25 = 0
x13 - x34 - x36 = 0
x14 + x24 + x34 - x45 - x46 - x47 = 0
x25 + x45 - x57 = 0
x36 + x46 - x67 = 0
x47 + x57 + x67 = 1 xij = 0 or 1

32
Management Science Network Flow Model I

Shortest Route Problem Solution: Excel Solution

Total hours

First constraint;
=A6+A7+A8

Constraint for node 2;

=A6-A9-A10

Decision variables

33
Management Science Network Flow Model I

Shortest Route Problem Solution: Excel Solution

One truck leaves node 1,

and one truck ends
at node 7

Flow constraints

34
Management Science Network Flow Model I

Shortest Route Problem Solution: Excel Solution

One truck flows

out of node 1;
one truck flows
into node 7

35
Management Science Network Flow Model I

Q&A

36