next up previous
Next: 3. Improving Solutions Up: TSP Algorithms in Action Previous: 1. Introduction

Subsections

   
2. Construction Heuristics

A construction heuristic is an algorithm that determines a tour according to some construction rules, but does not try to improve upon this tour. A tour is successively built and parts already built remain unchanged throughout the algorithm. A detailled discussion of construction heuristics can be found in [2].

We will discuss

   
2.1 Nearest Neighbor Heuristic

The salesman starts at some city and then visits the city nearest to the starting city. From there he visits the nearest city that was not visited so far, etc., until all cities are visited, and the salesman returns to the start.

This is the first heuristic that almost everyone comes up with. It is probably close the real salesman's approach. It is a poor heuristic, however. As can be seen by playing with the demo below, several cities are ``forgotten'' during the course of the algorithm. They have to be inserted at high costs in the end.

Sorry, your browser is not enabled to execute a Java applet.

Though usually rather bad, nearest neighbor tours only contain a few severe mistakes, but at the same time contain long segments connecting nodes with short edges. Therefore, such tours can serve as good starting tours for improvement methods 3.

   
2.2 Insertion Heuristics

An intuitive approach to the TSP is to start with a subtour, i.e. a tour on small subsets of nodes, and then extend this tour by inserting the remaining nodes one after the other until all nodes have been inserted.

There are several possibilities for implementing such an insertion scheme. They can be classified according to these features:

The starting tour is usually some tour on three nodes, e.g. those nodes that form the largest triangle. For Euclidean problems, a good starting tour is the tour that follows the convex hull of all nodes. This is a reasonable choice since the sequence of nodes from the convex hull tour is respected in any optimal tour. The convex hull is used as a starting tour in the Java demo below.

A new node is usually inserted into the tour at the point that causes the minimum increase in the length of the tour. We follow this receipt in the demo below.

The major difference between insertion schemes is the order in which the nodes are inserted. The Java applet below demonstrates two strategies:

Cheapest Insertion: Among all nodes not inserted so far, choose a node whose insertion causes the lowest increase in the length of the tour. The idea behind this strategy is pure greediness, of course.

Farthest Insertion: Insert the node whose minimal distance to a tour node is maximal. The idea behind this strategy is to fix the overall layout of the tour early in the insertion process.

Sorry, your browser is not enabled to execute a Java applet.


next up previous
Next: 3. Improving Solutions Up: TSP Algorithms in Action Previous: 1. Introduction
Stephan Mertens
1999-05-10