Shortest Path Exercises
Uploaded by
ScribdTranslationsShortest Path Exercises
Uploaded by
ScribdTranslationsOPERATIONS RESEARCH
SHORTEST PATH PROBLEMS
Exercise 1 (Hillier & Lieberman, 2009). Recently, the area of SEERVADA PARK was reserved for walks and
camps. Car entry is not allowed, but there is a system of narrow and winding roads for trams and
for 'jeeps' driven by the park rangers. The figure shows this road system—without the curves—where
This is the entrance to the park; the other letters represent the location of the ranger stations and other facilities.
of service. The numbers are the distances in miles of these rough roads. The park contains a viewpoint to a
beautiful landscape at the station. A few trucks transport visitors from the entrance to the station.
vice versa. At this moment, the administration wishes to determine which route, from the entrance of the park to station T, is the one that
represents the shortest total distance for the operation of trams.
Exercise 2 (Taha, 2010). The cell phone company Tell-ll provides service to six geographic areas. The distances of
satellite (in miles) between the six areas is given in the figure. Tell-All needs to determine the most efficient routes to send the
messages that must be established between each two areas in the network.
Use Dijkstra's algorithm to find the most efficient route between area 1 and area 6.
2. Set up the PLE and build an Excel solver file that allows you to find the efficient route between any pair of
nodes.
Exercise 3 (Hillier & Lieberman, 2009). Use Dijkstra's algorithm to find the shortest path through the networks.
a) and b), in which the numbers represent the real distances between the corresponding nodes.
Exercise 4 (Hillier & Lieberman, 2009). A Speedy Airlines flight is about to take off from Seattle non-stop to
London. There is some flexibility in choosing the precise route, depending on the weather conditions. The following network describes the
possible routes considered, where SE and LN are Seattle and London, respectively, and the other nodes represent various
intermediate places. The wind along each arc considerably affects the flight time, and therefore, the
fuel consumption. Based on the current weather report, the flight times are shown alongside the arcs.
(in hours). Due to the high cost of fuel, management has adopted the policy of choosing the route that minimizes the
total flight time.
What role do 'distances' play in the interpretation of this problem?
2. Use Dijkstra's algorithm to solve this shortest route problem.
3. Formulate the programming model in GAMS, solve it and interpret the results.
Exercise 5 (Winston, 2003). Suppose it costs $10,000 to purchase a new car. The annual operating cost and resale value of a
Used cars are shown in the table. Assuming that one now has a new car, determine a replacement policy that minimizes the net.
costs of owning and operating a car for the next six years. Use Dijkstra's algorithm to solve the problem
Exercise 6 (Winston, 2003). It costs $40 to buy a telephone from the department store. Assume that I can keep a telephone for
at most five years and that the estimated maintenance cost each year of operation is as follows: year 1, $20; year 2, $30; year
3, $40; year 4, $60; year 5, $70. I have just purchased a new telephone. Assuming that a telephone has no salvage value,
determine how to minimize the total cost of purchasing and operating a telephone for the next six years.
Exercise 7 (Winston, 2003). At the beginning of year 1, a new machine must be purchased. The cost of maintaining a machine
iyears old is given in Table 5. The cost of purchasing a machine at the beginning of each year is given in Table. There is no
trade-in value when a machine is replaced. Your goal is to minimize the total cost (purchase plus maintenance) of having a
machine for five years. Determine the years in which a new machine should be purchased.
BIBLIOGRAPHY
Hillier, F. S., & Lieberman, G. J. (2009). Introduction to Operations Research (9th edition, p. 1088). McGraw-Hill
Professional.
Operations Research: An Introduction
Winston, W. L. (2003). Operations Research: Applications and Algorithms (4 edition, p. 1440). Cengage Learning.
