This section presents two heuristics: the nearest-neighbor and the subtour-reversal algorithms. The first is easy to implement and the second requires more computations. The tradeoff is that the second algorithm generally yields better results. Ultimately, the two heuristics are combined into one heuristic, in which the output of the nearest-neighbor algorithm is used as input to the reversal algorithm.
The Nearest-Neighbor Heuristic. As the name of the heuristic suggests, a "good" solution of the TSP problem can be found by starting with any city (node) and then connecting it with the closest one. The just-added city is then linked to its nearest unlinked city (with ties broken arbitrarily). The process continues until a tour is formed.
The matrix below summarizes the distances in miles in as-city TSP problem.
The heuristic can start from any of the five cities. Each starting city may lead to a different tour. The following table provides the steps of the heuristic starting at city 3.
Notice the progression of the steps: Comparisons exclude distances to nodes that are part of a constructed partial tour. These are indicated by (-) in the Action column of the table.
The resulting tour 3-2-4-1-5-3 has a total length of 80 + 110 + 150 + 210 + 185 = 735 miles. Observe that the quality of the heuristic solution is starting-node dependent. For example, starting from node 1, the constructed tour is 1-2-3-4-5-1 with a total length of 780 miles (try it!).
Subtour Reversal Heuristic. In an n-city situation, the subtour reversal heuristic starts with a feasible tour and then tries to improve on it by reversing 2-city subtours, followed by 3-city subtours, and continuing until reaching subtours of size n - 1.
Consider the problem of Example 9.3-2. The reversal steps are carried out in the following table using the feasible tour 1-4-3-5-2-1 of length 745 miles:
The two-at-a-time reversals of the initial tour 1-4-3-5-2-1 are 4-3, 3-5, and 5-2, which leads to the given tours with their associated lengths of 820, 725, and 730. Since 1-4-5-3-2-1 yields a smaller length (= 725), it is used as the starting tour for making the three-at-a-time reversals. As shown in the table, these reversals produce no better results. The same result applies to the four-at-a-time reversal. Thus, 1-4-5-3-2-1 (with length 725 miles) provides the best solution of heuristic.
Notice that the three-at-a-time reversals did not produce a better tour, and, for this rea-son, we continued to use the best two-at-a-time tour with the four-at-a-time reversal. Notice also that the reversals do not include the starting city of the tour (= 1 in this example) because the process does not yield a tour. For example, the reversal 1-4 leads to 4-1-3-5-2-1, which is not a tour.
The solution determined by the reversal heuristic is a function of the initial feasible tour used to start the algorithm. For example, if we start with 2-3-4-1-5-2 with length 750 miles, the heuristic produces the tour 2-1-4-3-5-2 with length 745 miles (verify!), which is inferior to the solution we have in the table above. For this reason, it may be advantageous to first utilize the nearest-neighbor heuristic to determine all the tours that result from using each city as a starting node and then select the best as the starting tour for the reversal heuristic. This combined heuristic should, in general, lead to superior solutions than if either heuristic is applied separately. The following table shows the application of the composite heuristic to the present example.
Figure 9.12 provides a general Excel template (file exceITSP.xls) for the heuristics. It uses three execution options depending on the entry in cell H3:
1. If you enter a city number, the nearest-neighbor heuristic is used to find a tour starting with the designated city.
2. If you enter the word "tour" (without the quotes), you must simultaneously provide an initial feasible tour in the designated space. In this case, only the reversal heuristic is applied to the tour you provided.
3. If you enter the word "all," the nearest-neighbor heuristic is used first, and its best tour is then used to execute the reversal heuristic.
File exceITSP.v2.xls automates the operations of Step 3.
PROBLEM SET 9.3B
1. Apply the heuristic to the following problems:
a) The paint sequencing problem of Example 9.3-1.
b) Problem 1 of Set 9.3a.
c) Problem 2 of Set 9.3a.
d) Problem 3 of Set 9.3a.