** 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

- Nearest Neighbor Heuristic 2.1
- Insertion Heuristics 2.2
- Savings Heuristic (in the near future)

##

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.

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:

- How to construct the initial tour.
- How to choose next node to be inserted.
- Where to insert chosen node .

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.

** Next:** 3. Improving Solutions
** Up:** TSP Algorithms in Action
** Previous:** 1. Introduction
*Stephan Mertens*

*1999-05-10*