On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem

✍ Scribed by Selim G. Akl

• Publisher: Elsevier Science
• Year: 1981
• Tongue: English
• Weight: 138 KB
• Volume: 7
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/0771-050x(81)90057-7

✦ Synopsis

An algorithm for empirically calculating the expected number of optimal and near-optimal solutions in a random Euclidean travelling salesman problem is presented. The algorithm is based on well known geometric properties of the optimal tour. For problems involving up to 15 points uniformily distributed in the unit square, experiments show this expected number to be extremely small.

The Euclidean travelling salesman problem (ETSP) is stated as follows :

Given a set S of n points (cities) in the plane, it is required to find a polygon (tour) of minimum perimeter through S. The solution is called an optimal tour [ 1,2].