The objective of the shortest-route problem is to find the shortest distance from one location to another. In a network, this often involves determining the shortest route from one node to each of the other nodes. This problem can be modeled as a linear program with 0 and 1 variables, or it could be modeled and solved using a specialized algorithm that is presented in Module 8. The following example is a typical shortest-route problem.

Every day, Ray Design, Inc., must transport beds, chairs, and other furniture items from the factory to the warehouse. This involves going through several cities, and there are no direct interstate highways to make the delivery easier. Ray would like to find the route with the shortest distance. The road network is shown in Figure 9.5.

The shortest-route problem may be viewed as a special type of transshipment problem with one source having a supply of 1, one destination having a demand of 1, and a number of transshipment points. This type of problem can be modeled as a linear program with 0 and 1 variables. Ray is trying to decide which of the routes (arcs) to choose to be a part of the delivery system. Therefore, the decision variables will indicate whether a particular arc is chosen to be a part of the route taken. For the Ray Design, Inc., example, the objective is to minimize the total distance (cost) from the start to the finish. The constraints will specify that the number of units (either 0 or 1) going into a node must equal the number going out of that node. The variables are defined as

Since the starting point is node 1, we will not include variables going from node 2 or 3 back to node 1. Similarly, since node 6 is the final destination, we will not include any variable that starts at node 6. Viewing this as a transshipment problem, the origin node (node 1) must have one unit shipped out of it. This would be

The final destination node (node 6) must have one unit shipped to it, and this is written as

Each intermediate node will have a constraint requiring the amount coming into the node to equal the amount going out of that node (i.e., the flow into a node minus the flow out of a node must equal zero). For node 2, this would be

This simplifies to

The other constraints would be constructed in a similar manner. The linear program is

subject to

While this problem could be solved as a linear program, using Excel QM is the easiest way to obtain the solutions. To solve a shortest-route problem, from the Excel QM ribbon, select Network Analysis as LP and then choose Shortest Path. In the initialization window that opens, you enter the number of nodes (6) and click OK. A worksheet is developed, as seen in Program 9.7. Enter the data for the distances, and then click Solver from the Data ribbon. Click Solve from the Solver input window, and the results (flows) are put into the worksheet. From Program 9.7, we see that

So Ray will travel from city 1 to city 2, then to city 3, then to city 5, and then to the final destination, city 6. The total distance is 290 miles.