Review of Solution Approaches for the Symmetric Traveling Salesman Problem

Introduction

One of the most well-known computational optimization problems is the traveling salesman problem (TSP). Consider a salesman who has to visit n cities, the TSP asks for the shortest tour through all the cities such that no city is visited twice and the salesman returns at the end of the tour back to the starting point. Let G=(V,A) be a graph where V is a set of n vertices and Aa set of arcs. Let C=(c_ij) be a distance matrix associated with A. The TSP consists of determining a minimum distance circuit passing through each vertex once and only once. Such a circuit is known as a tour or Hamiltonian cycle (or tour). In several application of TSP C could be a cost, travel time, fuel consumption, emissions, environmental externalities etc. In some case the matrix C is symmetrical (c_ij= c_ji) and in some other case asymmetrical (c_ij ≠ c_ji). The Euclidean TSP is a special case of symmetric TSP when V is a set of point in and c_ij is the straight line distance between i and j.

TSP formulations and solution approaches are used for computer wiring, wallpaper cutting, hole punching, job sequencing, dartboard design, crystallography etc. There are many theoretical results concerning the optimal solution of the TSP. Some of them talk about the properties of the optimal solution and some other for novel formulations which in some cases can provide the optimal solution faster than other approaches.

Warren (1992) presents 3 theorems about the optimality of a selected arc based on the structure of the length matrix of the TSP. These theorems give the conditions under which an arc is part of the optimal tour in general, when the matrix is symmetric and when it contains only 0-1 value. Codenotti and Margara (1992) present a local search heuristics for solving general optimization problems which satisfies a simple difference equation. If this equation is satisfied then the solutions obtained by the local search heuristics have interesting structural properties. The authors prove that the TSP with certain notions of neighborhood satisfies the above-mentioned difference equation and that its solution applying local search heuristics has certain structural properties. The main structural properties are that: a) the average cost over all the feasible solutions depends on the cost of a specific feasible solution x and on the costs of the solutions which belong to its neighborhood, b) the average cost of the solutions belonging to the neighborhood of any solution x is linearly related to the cost of x and c) the average cost of the solutions belonging to the neighborhood of any solution x (AVE(x)), the average cost over all the feasible solutions (AVE), and the cost of x (COST(x)) satisfy one and only one of the following 3 relations: or or .

Warburton (1993) presents, a tight worst-case performance analysis of some convex hull insertion heuristics for the Euclidean TSP. Insertion algorithms are based on the idea that between two selected points constructing a subtour, a third point will be selected based on a criterion and inserted between the two original points (ex. select to insert the point which is nearest to the starting point). Specifically, Warburto studies the cheapest and nearest insertion algorithm. The main theoretical result of the paper is that starting these insertion algorithms with the convex hull subtour rather than with a single city subtour may considerably enhance the overall performance of an insertion heuristic.