Print this page

TSP Suite

1. Short Description

The TSPSuite is a holistic benchmarking environment for algorithms solving the Traveling Salesman Problem (TSP) written in Java. It is based on the TSPLib benchmark cases and offers integrated support for implementing, testing, benchmarking, and comparing algorithms. It also features a large set of implemented algorithms. In the TSPSuite, we focus on collecting information regarding how long an algorithm needs to reach a certain solution quality and what solution quality we can expect after a certain runtime. This is especially interesting for comparing anytime algorithms, such as metaheuristics that step-by-step refine and combine solutions in order to obtain better tours. For each algorithm tested, comprehensive logging information is collected regarding not only the solution quality and runtime (according to different time measures such as FEs and real time), but also the environment the algorithm was executed in and the parameters of the algorithm, rendering each log file self- explaining. TSPSuite contains an evaluator utility which can load these log files and create a LaTeX or XHTML document summarizing an algorithm's performance from different perspectives and comparing different algorithms. Finally, we also implement a set of basic algorithms for solving TSPs. All of this is done in Java 1.7 and under the LGPL license version 3, 29 June 2007.

2. Involved Researchers

  • Thomas Weise, Assoc. Prof.
  • Liu Weichen [刘伟臣], MSc. Student
  • Yan Jiang [江炎], MSc. Student
  • Yuezhong Wu [吴越钟], MSc. Student

3. Funding

  • "A Framework for Next Generation Algorithm Benchmarking: Performance Testing and Community Building", Funding Body: The University of Newcastle (UoN), Callaghan, NSW, Australia, Duration: 2014
  • "Intelligent Transportation Planning: Benchmarking of Novel Business Analytics Techniques using the Travelling Salesman Problem as a Test-Bed", Funding Body: The University of Newcastle (UoN), Callaghan, NSW, Australia, Duration: 2013

4. Resulting Publications

4.1. Refereed Journal Articles

  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.

4.2. Refereed Conference Papers

  1. Yan Jiang, Thomas Weise, Jörg Lässig, Raymond Chiong, and Rukshan Athauda. "Comparing a Hybrid Branch and Bound Algorithm with Evolutionary Computation Methods, Local Search and their Hybrids on the TSP". In Proceedings of the IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS’14), Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI’14), Orlando, FL, USA: Caribe Royale All-Suite Hotel and Convention Center, December 9–12, 2014. Los Alamitos, CA, USA: IEEE Computer Society Press.

5. Collaborators

  • Raymond Chiong from the Applied Informatics Research (AIR) group at the University of Newcastle (UoN)
  • Prof. Jörg Lässig from the Enterprise Application Development Group (EAD) of the University of Applied Sciences of Zittau/Görlitz (HSZG)