In 2014, we published TSP Suite, a Java experimentation framework for the Traveling Salesman Problem (TSP), the classical and most important logistic planning problem. The TSP Suite follows a holistic approach: It supports researchers in implementing and JUnit testing their algorithms, running experiments in a parallel and distributed fashion, and has an evaluator component which can compare the performance of different algorithms over time according to several different statistical measures automatically.

With our work on this topic, we want to make it easier for other researchers to run comprehensive experiments and to statistically rigorously evaluate algorithms. We believe that if we want to do good research in the domain of optimization, we need sound experiments and clear and comprehensive algorithm comparisons. This, however, costs a lot of work and thus, tool support is needed. Our holistic concepts in the TSP Suite approach are the right idea for this. We later extended this concept to allow for comparing the performance of arbitrary optimization algorithms implemented in arbitrary programming languages applied to arbitrary problems in form of the optimizationBenchmarking.org framework.

Introduction

The TSP Suite is based on the TSPLib benchmark cases and offers integrated support for implementing, testing, benchmarking, and comparing algorithms. 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 wide set of basic and state-of-the-art algorithms for solving TSPs.

The TSP is one of the oldest and most well-researched combinatorial problems in logistics planning and operations research as a whole. In this problem, a set of n cities (nodes in a graph) are given and the goal is to find the tour that visits each of the cities exactly once and then returns back to its origin with the lowest possible distance (or cost). Two cities i and j have the distance dist(i,j). The starting city (to which the tour must return) can freely be chosen. The problem is known to be NP-hard, but today, even large-scale TSP instances can be solved to optimality.

The TSP is well-known and well-researched, but much works focus on the final result quality or on whether a problem instance can be solved to optimality, i.e., whether the globally shortest round-trip tour can be found. Especially achieving the latter with a given algorithm may require a long runtime. The former, the final solution quality obtained with a TSP solver, does not give much information if we do not know the runtime necessary to reach it.

A more detailed documentation about the TSP Suite can be found here.

Publications

Organized Events