M8.4 Shortest-Route Problem
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.
Shortest-Route Technique
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. Ray Design would like to find the route with the shortest distance. The road network is shown in Figure M8.6.
Figure M8.6 Roads from Ray Design’s Plant to Warehouse
The shortest-route technique can be used to minimize total distance from any starting node to a final node. The technique is summarized in the following steps.
Steps of the Shortest-Route Technique
Find the nearest node to the origin (plant). Put the distance in a box by the node.
Find the next-nearest node to the origin (plant), and put the distance in a box by the node. In some cases, several paths will have to be checked to find the nearest node.
Repeat this process until you have gone through the entire network. The last distance at the ending node will be the distance of the shortest route. You should note that the distance placed in the box by each node is the shortest route to this node. These distances are used as intermediate results in finding the next-nearest node.
Looking at Figure M8.6, we can see that the nearest node to the plant is node 2, with a distance of 100 miles. Thus, we will connect these two nodes. This first iteration is shown in Figure M8.7.
Figure M8.7 First Iteration for Ray Design
Now we look for the next-nearest node to the origin. We check nodes 3, 4, and 5. Node 3 is the nearest, but there are two possible paths. Path 1–2–3 is nearest to the origin, with a total distance of 150 miles (see Figure M8.8).
Figure M8.8 Second Iteration for Ray Design
We repeat the process. The next-nearest node is either node 4 or node 5. Node 4 is 200 miles from node 2, and node 2 is 100 miles from node 1. Thus, node 4 is 300 miles from the origin. There are two paths for node 5, 2–5 and 3–5, to the origin. Note that we don’t have to go all the way back to the origin because we already know the shortest route from node 2 and node 3 to the origin. The minimum distances are placed in boxes by these nodes. Path 2–5 is 100 miles, and node 2 is 100 miles from the origin. Thus, the total distance is 200 miles. In a similar fashion, we can determine that the path from node 5 to the origin through node 3 is 190 (40 miles between node 5 and 3 plus 150 miles from node 3 to the origin). Thus, we pick node 5 going through node 3 to the origin (see Figure M8.9).
Figure M8.9 Third Iteration for Ray Design
The next-nearest node will be either node 4 or node 6, as the last remaining nodes. Node 4 is 300 miles from the origin ( from node 4 to node 2 plus 100 from node 2 to the origin). Node 6 is 290 miles from the origin Node 6 has the minimum distance, and because it is the ending node, we are done (refer to Figure M8.10). The shortest route is path 1–2–3–5–6, with a minimum distance of 290 miles. This problem can be solved in QM for Windows.
