Optimization Benchmarking

TSP Suite Example: The Traveling Salesman Problem

10 May 2016

We added an new example data set] from several algorithms solving the Traveling Salesman Problem (TSP) gathered with the TSP Suite. The TSP Suite [1] is the direct predecessor of the optimizationBenchmarking.org framework. Here we conduct experiments based on the 68 smallest-scale symmetric benchmark instances from the TSPLib benchmark set [2].

The TSP is maybe the oldest and most well-known combinatorial optimization problem. Given are n cities. A salesman starts at one of these cities. He wants to visit all other cities (each exactly once) and then return to his origin. The question for the shortest tour that he can take to realize this travel is NP-hard and the best exact algorithms for solving this problem need a runtime exponential in n to find the best-possible solution in the worst case.

As benchmark problems for our TSP example, we use some instances from the well-known TSPLib [2]. We pick the 68 smallest-scale instances from 110 symmetric instances to run out experiments.

Here we investigate twelve anytime optimization methods for the TSP, i.e., algorithms that can step-wise improve their best guess of the solution. They can provide an approximate solution at any time. Among the tested algorithms, you can find 11 metaheuristics and one branch and bound algorithm.

References

  1. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine (CIM). 9(3):40-52. August 2014. Piscataway, NJ, USA: IEEE Computational Intelligence Society. pdf, doi:10.1109/MCI.2014.2326101. Featured article and selected paper at the website of the IEEE Computational Intelligence Society (http://cis.ieee.org/).
  2. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing. 3(4):376-384. 1991. Operations Research Society of America (ORSA). doi:10.1287/ijoc.3.4.376

[home] • [status] • [atom feed] • [rss feed]

Contact: Dr.  Thomas Weise, http://www.it-weise.de, tweise@ustc.edu.cn