Colorado Technical University
MATH 451-1404B-
Shortest-Path Model
Shortest-Path Model
Introduction
In shortest path model, you are looking for the paths to get you from any node to any other node in shortest path
...
Colorado Technical University
MATH 451-1404B-
Shortest-Path Model
Shortest-Path Model
Introduction
In shortest path model, you are looking for the paths to get you from any node to any other node in shortest path
with regard to distance, time, or other measure. In this section, you will consider an application of a delivery pizza
man to deliver the pizza hot and fresh by the shortest time from the pizza store to the customer house. You will
present the objective function as well as flow balance equations. You will then find the shortest time to deliver the
pizza.
Learning Materials
Shortest Path Model is Important
In some applications, it is critical to save time or mileage if you are repeating the same task over and over.
Example
A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. Of course, it may
be possible to travel a longer distance to achieve shorter time in not congested roads.
Chart
The following table shows the required time in minutes going from node 1 (store) to node 6 (customer house).
Other nodes are the intersection between any two roads.
Why is the shortest path modeling considered a transshipment problem?
Shortest path modeling can be considered as transshipment problem with the origin being the supply node (pizza
store) and the destination node is the demand node (customer house). The value of the supply and destination nodes
is unity with all other nodes as transshipment nodes because no pizza is made nor is consumed at those nodes.
Write the Objective Function
The objective function is to minimize the total time spent on the road. The objective function can then be written as:
Minimize the time = T12 + T13 + T14 + T15 + T16 + T24 + T26 + …
subject to the following flow balance equations
T12 + T13 + T14 + T15 + T16 - (T21 + T31 + T51 + T61) = 1 Supply of 1 unit at supply node (store)
T42 + T62 - (T24 + T26) = 0 Transshipment at node 2
T72 + T73 + T74 + T76 - (T27 + T37 + T47 + T67) = 1 Demand of 1 unit at destination node (house)
Figure 1 shows the Excel’s Solver program used to solve the shortest path model containing all of the required excel
functions.
Figure 1: Excel’s Solver Program Used to Solve the Shortest Path Model
Figure 2 shows the same program containing the numerical values of the decision-making variables and the amount
of resources consumed.
Figure 2: Results of the Application Using Excel’s Solver
Understanding the Results
As you may have noticed, you place a large amount of time (100 minutes) on the roads which actually do not exist
between any two nodes and any nodes to itself to discourage the Excel’s Solver to consider such a nonexistence
roads and looping in the intersections.
A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following
table shows the required time in minutes going from node 1 (store) to node 7 (customer house).
What is the flow balance for node 1, the store?
T13 + T14 + T16 + (T31 + T41 + T51) = 1
T13 + T14 + T16 + (T31 + T41 + T51) = 0
T13 + T14 + T16 - (T31 + T41 + T51) = 0
T13 + T14 + T16 - (T31 + T41 + T51) = 1
Suppose that there is a network with 13 nodes, 1 through 13, with the following distances:
What is the length of the shortest path from node 1 to node 13?
84
115
185
104
Suppose that there is a network with 13 nodes, 1 through 13, with the following distances:
Suppose that you accidentally miscode the length from node 2 to 8 as -23. For this problem, you can assume that the
segment between nodes 2 and node 8 would not be used if the length was correctly entered as 23. When solving, you
notice that the Solver seems to be assigning unreasonably large values to some of the segments, and because it
makes sense that a segment is only used once, you limit the decision variables to be at most 1.
What happens with this new restriction?
The restriction does not help, and the Solver still reports an error.
The correct path is found, and the negative link is added in both directions, resulting in a total distance that is too low
by 46.
The correct path and total distance are found. The negative path is added in both directions.
Another path is found, which is not optimal.
Suppose that there is a network of 13 nodes, with the costs shown below. Note that these are directed paths.
How long is the shortest path from node 1 to node 13?
16
12
14
10
A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following
table shows the required time in minutes going from node 1 (store) to node 7 (customer house).
How many arcs does the network have?
48
24
7
49
What is the function of a shortest path model?
Minimizing distance while maximizing time
Minimizing total distance, cost, time, or other measure
Finding the shortest distance connecting all nodes together
Minimizing time while maximizing distance
How many decision variables does the network have?
49
24
48
7
Suppose that there is a problem at node 3, so no traffic can come in or out. It turns out that your surveyor did not
calibrate the instruments properly, and each path should be 1 longer. By how much does the length of the path
increase?
7 4 6 3
Suppose that you accidentally miscode the length from node 2 to 8 as -23. For this problem, you can assume that the
segment between nodes 2 and node 8 would not be used if the length was correctly entered as 23. What will happen
if you attempt to solve this using the Solver?
The Solver will find the correct path and ignore the bad data.
The Solver will assign negative weights to the link with the negative distance.
The Solver will fail with an error message about a failure to converge.
The Solver will find the correct path, but the total distance shown will be lower by 23.
It turns out that the link directly from node 1 to node 10 was a mistake and is not really there. Also, the link from 4
to 10 was misreported and should have a length of 69.38. How long is the shortest path? Round your answer off to
the nearest tenth.
63.1
83.6
38.7
36.6
Which of the following nodes is not the starting and ending nodes?
Destination
Supply or destination
Transshipment
Supply
What value is assigned to the starting (supply) node in shortest path model?
It must be given by the application
0
Any large number is fine
1
What value do you insert for those arcs with no connections and for any node to itself?
1 0
Leave the cells blank
Infinity or artificially a high number
Which of the following is an objective function?
Maximize the time = T12 + T13 + T14 + T15 + T16 + T17 + T21 + T23 + T24 + T25 + …
Minimize the time = 3 * T13 + 12 * T14 + 20 * T16 + 20 * T24 + 18 * T26 + …
Minimize the time = 3 + 12 + 20 + 20 + 18 + …
Minimize the time = T13 + T14 + T14 + T16 + T24 + T26 + T31 + …, Minimize the time = T12 + T13 + T14 + T15 +
T16 + T17 + T21 + T23 + T24 + T25 + …
What is the flow balance for node 2?
T32 + T42 + T52 - (T24 + T26) = 0
T32 + T42 + T52 - (T24 + T26) = 1
T32 + T42 + T52 + (T24 + T26) = 1
T32 + T42 + T52 + (T24 + T26) = 0
A pizza deliveryman should find the path with the shortest time to deliver the pizza fresh and hot. The following
table shows the required time in minutes going from node 1 (store) to node 7 (customer house).
What is the value of the objective value?
100 minutes
4 minutes
19 minutes
20 minutes
What value is assigned to the ending (demand) node in shortest path model?
0
Any large number is fine
1
It must be given by the application
What is the length of shortest path from node 1 to node 10? Round your answer off to the nearest tenth.
59.3
24.4
41.8
37.0
[Show More]
