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