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
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.
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.
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:
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.