Reversing a segment

One of the standard transformations of a tour used in local optimization is reversing a segment. In the new tour all the cities of the segment occur in reverse order.

pos.    0 1 2 3 4 5 6 7 ...
before  A-B-C-D-E-F-G-H-...
after   A-B-F-E-D-C-G-H-...

We use the following algorithm: swap the first and the last city of the segment, then the second and one before last, and so on, to the middle of the segment. This way number of swaps is equal half of the segment size.

Beware

We should not forget that a tour is cyclic, and therefore after tour[N-1] city (in ascending order of indices) goes tour[0], to close the tour. Therefore segment from tour[N-2] to tour[2] is 5 cities long — it constists of: tour[N-2], tour[N-1], tour[0], tour[1] and tour[2], in this order. Note that reversing the complementary segment, consisting of the cities on positions from 2 to (N-2), is not the exactly same and in some cases may lead to erroneous results. (But see later reversing a segment given by city numbers, not by positions, more complex and using additional structure, but where this problem does not occur).

proc Reverse_Segment(tour: var Tour_Array;
                     startIndex, endIndex: Tour_Index) =
  ## Reverses order of elements in segment [startIndex, endIndex]
  ## of tour.
  ## NOTE: Final and initial part of tour make one segment.
  ## NOTE: While the order of arguments can be safely changed when
  ## reversing segment in 2-optimization, it makes difference for
  ## 3-opt move - be careful and do not reverse (x,z) instead of (z,x).
  var
    left, right: Tour_Index

  let inversionSize = ((N + endIndex - startIndex + 1) mod N) div 2
   
  left  = startIndex
  right = endIndex

  for counter in 1 .. inversionSize:
    swap(tour[left], tour[right])
    left  = (left + 1) mod N
    right = (N + right - 1) mod N

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

Local optimization – general idea

proc improveTour(tour: var Tour_Array) =
  ## scheme of most of local improvement algoritms
  var
    locallyOptimal: bool = false
    improved: bool
  
  while not locallyOptimal:
    locallyOptimal = true
    for pos in low(tour) .. high(tour):  # that is: in 0 .. N-1
      improved = false
      improved = optimizeFromPosition(pos)  # opt. trial
      if improved:
        locallyOptimal = false
        break

Data structures

N

It’s a common convention to use N for overall number of cities (points/vertices) in a problem. Since number of cities in given problem doesn’t change during searching for solutions and we do not deal with input/output questions, for simplicity in all places we use positive integer N just as it were a constant:

  const N = 100

Yet there should be no problem to make it a global variable assigned once, in proc reading a problem. In this case arrays dependent on it (see below) would be openarrays or sequences. Anyway in all algorithms we treat N as given and not changing.

City_Number

Cities are identified by their numbers. We starting numbering them from zero and for clarity use a distinct type:

  type City_Number = range[0 .. N-1]

You may replace it by int (see above).

Tour_Array and Tour_Index

Tours are represented by arrays. Tour_Index type is introduced to easily and clearly distinguish between a city number and a number representing position of city in tour.

  type Tour_Index = range[0 .. N-1]
  type Tour_Array = array[Tour_Index, City_Number]

Note that this representation suggest us the “natural” direction in tour, where in fact none of both directions is anyway natural or better than the other. Tour properties considered in symmetric TSP problem are the same in both directions. Even if we — because of ascending array index — tend to treat the direction from tour[i] to tour[i+1] as obvious and preferred “forward”.

Note also that array representation forces us to keep an eye on boundaries and to not forget that a tour is cyclic — and therefore after tour[N-1] city (in ascending order of indices) goes tour[0], to close the tour.

Additional remark

If the difference between City_Number and Tour_Index, both integers ranging from zero to N-1, is not clear enough for you, consider two examples:

  type City_Number = range[0 .. 4]
  type Tour_Index = range[0 .. 4]

Here a variable of type Tour_Array has indices ranging from 0 to 4 and contains numbers of subsequent cities on tour, e.g.: tour[3] == 4 (position no. 3 in tour is occupied by city number 4).

  type City_Number = range["A" .. "D"]
  type Tour_Index = range[0 .. 4]

And here a variable of type Tour_Array has indices ranging from 0 to 4 and contains letters of subsequent cities on tour, e.g. tour[2] == "C" (position no. 2 in tour is occupied by city “C”).

Length and Length_Gain

Numbers representing distances between two cities, sums of such distances, lengths of parts or of whole tour are all of Length type. We follow a common custom of using distances rounded to integers. Differences between lengths, computed during optimizations, are of Length_Gain type.

type
  Length = range[0 .. high(int)] # length is non-negative
  Length_Gain = int              # could be negative (loss)

distance(...)

The most often used function in solving TSP problems is distance(), returning the distance between two cities given as parameters.

proc distance(X, Y: City_Number): Length =
  ...

Important

To speed up processing for small problems distances are usually precomputed and stored in an array, then function returning suitable element from this array is used.

Introduction

What it is about?

The main purpose of these notes is to clearly show the key ideas of tour construction and local optimization used in solving Symmetric Traveling Salesman Problem.

Due to its natural syntax and readability for users of imperative languages Nim programming language have been chosen. The code is to be simple and easy to understand, not to be very efficient.

To show the ideas in simple and clear way, the code itself is often not optimized. For example: constructing a tour by nearest neighbour method and, needed in some methods, creating neighbour lists – both actions involve searching or sorting cities by distance from given city.

The Traveling Salesman Problem

The TSP problem can be formulated as follows:

1. [constraints] A salesman has a list of cities and the distances between each pair of cities. He must visits each city exactly once and return to the origin city.
2. [goal] Find the shortest possible route.

Special cases of TSP

Usually we deal with a TSP problem defined as symmetric, that is: for each pair of cities A and B the distance beetwen them is the same in each opposite direction:

$$d_{AB} = d_{BA}$$

This feature is often used in solving methods. In fact the most of basic algorithms assume symmetry but doesn’t need any other conditions concerning distances.

A special case of symmetric TSP is metric TSP, where triangle inequity is satisfied, that is: for each three cities A, B, C the direct connection from A to B is always shorter or equal to the route from A to B via C:

$$d_{AB} \le d_{AC} + d_{CA}$$

Euclidean TSP is a special case of metric TSP, where the distance between two cities is the Euclidean distance between the corresponding points:

$$d_{AB} = \sqrt{ (x_A-x_B)^2 + (y_A-y_B)^2 }$$

Local optimization

Because exact algorithms work reasonably fast only for small problem sizes, we redefine the goal in the problem. Instead of rigid condition of the optimal solution we accept solutions as short as we can find within our limitations: hardware, softwares, time, knowledge, cleverness. So we use “suboptimal” or heuristic algorithms, that is algorithms that in reasonable time deliver good solutions, but which could be not optimal.

There are several categories of TSP heuristics. The oldest and the simpliest idea of solving the problem consists two phases:

• build a short initial tour from scratch using one of construction heuristics
• iteratively improve this tour using improvement heuristics

In the second phase we move from solution to solution by applying local changes to the tour, until no improving moves can be found (or a time bound is elapsed).