NETWORK OPTIMIZATION MODELS:THE SHORTEST-PATH PROBLEM

THE SHORTEST-PATH PROBLEM

Although several other versions of the shortest-path problem (including some for directed networks) are mentioned at the end of the section, we shall focus on the following simple version. Consider an undirected and connected network with two special nodes called the origin and the destination. Associated with each of the links (undirected arcs) is a non- negative distance. The objective is to find the shortest path (the path with the minimum total distance) from the origin to the destination.

A relatively straightforward algorithm is available for this problem. The essence of this procedure is that it fans out from the origin, successively identifying the shortest path to each of the nodes of the network in the ascending order of their (shortest) distances from the origin, thereby solving the problem when the destination node is reached. We shall first outline the method and then illustrate it by solving the shortest-path problem encountered by the Seervada Park management in Sec. 10.1.

Algorithm for the Shortest-Path Problem

Objective of nth iteration: Find the nth nearest node to the origin (to be repeated for n = 1, 2, . . . until the nth nearest node is the destination.

Input for nth iteration: n - 1 nearest nodes to the origin (solved for at the previous iterations), including their shortest path and distance from the origin. (These nodes, plus the origin, will be called solved nodes; the others are unsolved nodes.)

Candidates for nth nearest node: Each solved node that is directly connected by a link to one or more unsolved nodes provides one candidate— the unsolved node with the shortest connecting link to this solved node. (Ties provide additional candidates.)

Calculation of nth nearest node: For each such solved node and its candidate, add the distance between them and the distance of the shortest path from the origin to this solved node. The candidate with the smallest such total distance is the nth nearest node (ties provide additional solved nodes), and its shortest path is the one generating this distance.

Applying This Algorithm to the Seervada Park Shortest-Path Problem The Seervada Park management needs to find the shortest path from the park entrance (node O) to the scenic wonder (node T ) through the road system shown in Fig. 10.1. Ap- plying the above algorithm to this problem yields the results shown in Table 10.2 (where the tie for the second nearest node allows skipping directly to seeking the fourth nearest node next). The first column (n) indicates the iteration count. The second column simply lists the solved nodes for beginning the current iteration after deleting the irrelevant ones (those not connected directly to any unsolved node). The third column then gives the candidates for the nth nearest node (the unsolved nodes with the shortest connecting link to a solved node). The fourth column calculates the distance of the shortest path from the origin to each of these candidates (namely, the distance to the solved node plus the link

distance to the candidate). The candidate with the smallest such distance is the nth near- est node to the origin, as listed in the fifth column. The last two columns summarize the information for this newest solved node that is needed to proceed to subsequent iterations (namely, the distance of the shortest path from the origin to this node and the last link on this shortest path).

Now let us relate these columns directly to the outline given for the algorithm. The input for nth iteration is provided by the fifth and sixth columns for the preceding itera- tions, where the solved nodes in the fifth column are then listed in the second column for the current iteration after deleting those that are no longer directly connected to unsolved nodes. The candidates for nth nearest node next are listed in the third column for the cur- rent iteration. The calculation of nth nearest node is performed in the fourth column, and the results are recorded in the last three columns for the current iteration.

For example, consider the n = 4 iteration in Table 10.2. The objective of this iteration is to find the 4th nearest node to the origin. The input is that we already have found the three nearest nodes to the origin (A, C, and B) and their minimum distances from the origin (2, 4, and 4, respectively), as recorded in the fifth and sixth columns of the table. The next step is to list these solved nodes in the second column of the table for this n = 4 iteration. Node A is directly connected to just one unsolved node (node D), so node D automatically becomes a candidate to be the 4th nearest node to the origin. Its minimum distance from the origin is the minimum distance from the origin to node A (2, as recorded in the sixth column) plus the distance between nodes A and D (7), for a total of 9. Node B is directly connected to two unsolved nodes (D and E), but node E is chosen to be the next candidate to be the 4th nearest node to the origin because it is closer to node B than node D is. The sum of the minimum distance from the origin to node B and the distance between node B and node E is 4 + 3 = 7, as recorded in the fourth column. Finally, node C is directly connected to just one unsolved node (node E), so node E again becomes a candidate to be the 4th nearest node to the origin, but via node C this time. The total dis- tance involved in this case is 4 + 4 = 8. The smallest of the three total distances involved just calculated is the middle case of 4 + 3 = 7, so the closest connected unsolved node listed in this middle row of the iteration (node E) has been found to be the 4th nearest node to the origin, via the BE connection. Recording these results in the fifth and seventh columns of the table completes the iteration.

After the work shown in Table 10.2 is completed, the shortest path from the desti- nation to the origin can be traced back through the last column of Table 10.2 as either T --- D --- E --- B --- A --- O or T --- D --- B --- A --- O. Therefore, the two alternates for the shortest path from the origin to the destination have been identified as O --- A --- B ---

E --- D --- T and O --- A --- B --- D --- T, with a total distance of 13 miles on either path.

Using Excel to Formulate and Solve Shortest-Path Problems

This algorithm provides a particularly efficient way of solving large shortest-path problems. However, some mathematical programming software packages do not include this algorithm. If not, they often will include the network simplex method described in Sec. 10.7, which is another good option for these problems.

Since the shortest-path problem is a special type of linear programming problem, the general simplex method also can be used when better options are not readily available. Although not nearly as efficient as these specialized algorithms on large shortest-path problems, it is quite adequate for problems of even very substantial size (much larger than the Seervada Park problem). Excel, which relies on the general simplex method, provides a convenient way of formulating and solving shortest-path problems with dozens of arcs and nodes.

A spreadsheet formulation for the Seervada Park shortest-path problem, where the changing cells OnRoute (D4:D17) show the optimal solution obtained by Solver and the objective cell TotalDistance (D19) gives the total distance (in miles) of this shortest path. The network next to the spreadsheet shows the road system for Seervada Park that was originally depicted in Fig. 10.1.

Figure 10.4 shows an appropriate spreadsheet formulation for the Seervada Park shortest-path problem. Rather than using the kind of formulation presented in Sec. 3.5 that uses a separate row for each functional constraint of the linear programming model, this formulation exploits the special structure by listing the nodes in column G and the arcs in columns B and C, as well as the distance (in miles) along each arc in column E. Since each link in the network is an undirected arc, whereas travel through the shortest path is in one direction, each link can be replaced by a pair of directed arcs in opposite directions. Thus, columns B and C together list both of the nearly vertical links in Fig. 10.1 (B–C and D–E) twice, once as a downward arc and once as an upward arc, since either direction might be on the chosen path. However, the other links are only listed as left-to-right arcs, since this is the only direction of interest for choosing a shortest path from the origin to the destination.

A trip from the origin to the destination is interpreted to be a “flow” of 1 on the chosen path through the network. The decisions to be made are which arcs should be included

An Application Vignette

Incorporated in 1881, Canadian Pacific Railway (CPR) was Canada’s first transcontinental railway. CPR transports rail freight over a 14,000-mile network extending across Canada. It also serves a number of major cities in the United States, including Minneapolis, Chicago, and New York. Alliances with other carriers extend CPR’s market reach into the major business centers of Mexico as well.

Every day CPR receives approximately 7,000 new shipments from its customers going to destinations across North America and for export. It must route and move these shipments in railcars over the network of track, where a railcar may be switched a number of times from one locomotive engine to another before reaching its destination. CPR must coordinate the shipments with its operational plans for 1,600 locomotives, 65,000 rail- cars, over 5,000 train crew members, and 250 train yards.

CPR management turned to an OR consulting firm, MultiModal Applied Systems, to work with CPR employees in developing an operations research approach to this problem. A variety of OR techniques were used to create a new operating strategy. However, the foundation of the approach was to represent the flow of blocks of railcars as flow through a network where each node corresponds to both a location and a point in time. This representation then enabled the application of network optimization tech- niques. For example, numerous shortest path problems are solved each day as part of the overall approach.

This application of operations research is saving CPR roughly US$100 million per year. Labor productivity, loco- motive productivity, fuel consumption, and railcar velocity have improved very substantially. In addition, CPR now provides its customers with reliable delivery times and has received many awards for its improvement in service. This application of network optimization techniques also led to CPR winning the prestigious First Prize in the 2003 international competition for the Franz Edelman Award for Achievement in Operations Research and the Management Sciences.

Source: P. Ireland, R. Case, J. Fallis, C. Van Dyke, J. Kuehn, and M. Meketon: “The Canadian Pacific Railway Transforms Operations by Using Models to Develop Its Operating Plans,” Interfaces, 34(1): 5–14, Jan.–Feb. 2004. (A link to this article is provided on our website, www.mhhe.com/hillier.)

in the path to be traversed. A flow of 1 is assigned to an arc if it is included, whereas the flow is 0 if it is not included. Thus, the decision variables are

for each of the arcs under consideration. The values of these decision variables are entered in the changing cells On Route (D4:D17).

Each node can be thought of as having a flow of 1 passing through it if it is on the se- lected path, but no flow otherwise. The net flow generated at a node is the flow out minus the flow in, so the net flow is 1 at the origin, -1 at the destination, and 0 at every other node. These requirements for the net flows are specified in column J of Fig. 10.4. Using the equa- tions at the bottom of the figure, each column H cell then calculates the actual net flow at that node by adding the flow out and subtracting the flow in. The corresponding constraints, NetFlow (H4:H10) = SupplyDemand (J4:J10), are specified in the Solver parameters box.

The objective cell TotalDistance (D19) gives the total distance in miles of the cho- sen path by using the equation for this cell given at the bottom of Fig. 10.4. The goal of minimizing this objective cell has been specified in Solver. The solution shown in column D is an optimal solution obtained after running Solver. This solution is, of course, one of the two shortest paths identified earlier by the algorithm for the shortest-path algorithm.

Other Applications

Not all applications of the shortest-path problem involve minimizing the distance traveled from the origin to the destination. In fact, they might not even involve travel at all. The links (or arcs) might instead represent activities of some other kind, so choosing a path through the network corresponds to selecting the best sequence of activities. The numbers giving the “lengths” of the links might then be, for example, the costs of the activities, in which case the objective would be to determine which sequence of activities minimizes the total cost. The Solved Examples section of the book’s website includes another example of this type that illustrates its formulation as a shortest-path problem and then its solution by using either the algorithm for such problems or Solver with a spreadsheet formulation.

Here are three categories of applications:

1. Minimize the total distance traveled, as in the Seervada Park example.

2. Minimize the total cost of a sequence of activities. (Problem 10.3-3 is of this type.)

3. Minimize the total time of a sequence of activities. (Problems 10.3-6 and 10.3-7 are of this type.)

It is even possible for all three categories to arise in the same application. For example, sup- pose you wish to find the best route for driving from one town to another through a number of intermediate towns. You then have the choice of defining the best route as being the one that minimizes the total distance traveled or that minimizes the total cost incurred or that minimizes the total time required. (Problem 10.3-2 illustrates such an application.)

Many applications require finding the shortest directed path from the origin to the destination through a directed network. The algorithm already presented can be easily modified to deal just with directed paths at each iteration. In particular, when candidates for the nth nearest node are identified, only directed arcs from a solved node to an un- solved node are considered.

Another version of the shortest-path problem is to find the shortest paths from the origin to all the other nodes of the network. Notice that the algorithm already solves for the shortest path to each node that is closer to the origin than the destination. Therefore, when all nodes are potential destinations, the only modification needed in the algorithm is that it does not stop until all nodes are solved nodes.

An even more general version of the shortest-path problem is to find the shortest paths from every node to every other node. Another option is to drop the restriction that “distances” (arc values) be nonnegative. Constraints also can be imposed on the paths that can be followed. All these variations occasionally arise in applications and so have been studied by researchers.

The algorithms for a wide variety of combinatorial optimization problems, such as certain vehicle routing or network design problems, often call for the solution of a large number of shortest-path problems as subroutines. Although we lack the space to pursue this topic further, this use may now be the most important kind of application of the shortest-path problem.