Page 383 -

MAXIMAL FLOW PROBLEM 363

Route CSD–C now becomes permanent. The next CSD – Clinic A 50 minutes
iteration is then: CSD – Clinic B 60 minutes
CSD – Clinic C 70 minutes
A–D 110 minutes
CSD – Clinic D 80 minutes (via Clinic B)
B–D 80 minutes
CSD – Clinic E 90 minutes (via Clinic B)
B–E 90 minutes
We can also see by inspection of the network that
Route B–D is now permanent giving the next iteration:
when the new road is constructed there will be an
D–E 120 minutes arc (route) between Clinic C and Clinic E, with a
B–D 90 minutes travel time of 15 minutes. This will then be the pre-
ferred route to Clinic E with a total time from the
with the B–D route the shortest option. We now have central supply depot of 85 minutes compared with
our solution. The supply routes from the Central the current 90 minutes.
supply depot to each clinic are:

Problems

1 Find the shortest route from node 1 to each of the other nodes in the transportation
network shown.

2 5
7 3 5
4 6
9
1 3 2 7
3
18
3 6
4

2 For the GDA problem (see Figure 8.1), assume that node 7 is GDA’s warehouse and
supply centre. Several daily trips are commonly made from node 7 to the other nodes or
construction sites. Using node 7 as the starting node, find the shortest route from this node
to each of the other nodes in the network.
3 In the original GDA problem, we found the shortest distance from the office (node 1) to
each of the other nodes or construction sites. Because some of the roads are
highways and others are country tracks, the shortest-distance routes between the
office and the construction sites may not necessarily provide the quickest or shortest-
time routes. Shown here is the road network with travel time values rather than
distance values. Find the shortest route from GDA’s office to each of the construction
sites if the objective is to minimize travel time rather than distance.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.