Heuristic Algorithms
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.
Example 9.3-2
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.
Example
9.3-3
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.
Excel Moment.
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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.