Tour construction: Nearest Neighbor (NN)

The simplest reasonable method of constructing initial tour is Nearest Neighbor heuristic: start from some city and walk to its nearest neighbor; then from this second city walk to its nearest neighbor (excluding already visited city); then from this third city...

1. Choose an arbitrary city as startCity, then add it to the empty tour as last city and mark it as visited city.
2. Find out the candidate among unvisited cities with the shortest distance to last city in tour.
3. Add candidate city to the tour; now it becomes the last city, mark it as visited.
4. Repeat from step 2 until all the cities are visited.

proc Build_Nearest_Neighbor_Tour(startCity: City_Number): Tour_Array =
  ## Start with given city, then always go to the nearest unvisited city
  var
    tour: Tour_Array
    last, candidate: City_Number
    minDist: Length
    visited: array[0..N-1, bool]

  for city in 0 .. N-1:
    visited[city] = false

  tour[0] = startCity   # start with this city
  visited[startCity] = true

  for pos in 1 .. N-1:
    # find the closest city to the (pos-1)-th city in tour
    last = tour[pos-1]
    minDist = high(Length)  # infinity
    for city in 0 .. N-1:
      if not visited[city]:
        if distance(last, city) < minDist:
          minDist = distance(last, city)
          candidate = city
    #end_for city loop
    tour[pos] = candidate
    visited[candidate] = true

  result = tour

The simplicity is not the only advantage of NN algorithm. It's easy to understand, easy to implement, executes quickly and provides quite good initial tours for local optimization. The latter feature should be properly understood: NN produces good initial tours for further improvements. In fact, NN tours are on average 25% longer than optimal (for sets of cities with random coordinates in a square).

This average reflects two factors. Firstly, for some sets of cities NN provides better solutions than for others. The theoretical worst case for any type of TSP problem is limited by inequity:

$$\frac{L_{NN}}{L_{opt}} \le \frac{1}{2} \log_{2} N + \frac{1}{2}$$

While other tour construction heuristics have lower bounds for theoretical worst cases, they are more complicated and slower.

Secondly, a tour created by NN depends on startCity – for the same set of cites choosing different city for the starting point results in different tour (see below).

Some simple statistics

Relative best length, average length and worst length of all tours created by NN heuristic. Random planar problems, N=100.

Problem #	Best	Avg	Worst
1	100.00	111.34	120.07
2	100.00	108.58	117.59
3	100.00	108.93	124.21
4	100.00	108.58	117.59
5	100.00	110.42	121.03
6	100.00	108.82	118.76
7	100.00	110.47	120.50
8	100.00	106.84	119.16
9	100.00	108.93	119.16
10	100.00	107.30	116.08