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.
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
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.
Weichen Liu, Thomas Weise, Yuezhong Wu, and Qi Qi. Combining Two Local Searches with Crossover: An Efficient Hybrid Algorithm for the Traveling Salesman Problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'17), July 15-19, 2017, Berlin, Germany, New York, NY, USA: ACM Press, pages 298-305, ISBN: 978-1-4503-4920-8.
doi:10.1145/3071178.3071201 / paper / slides / blog entry 1 / blog entry 2
Thomas Weise. From Standardized Data Formats to Standardized Tools for Optimization Algorithm Benchmarking. In Newton Howard, Yingxu Wang, Amir Hussain, Freddie Hamdy, Bernard Widrow, and Lotfi A. Zadeh, editors, Proceedings of the 16th IEEE Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC'17), July 26-28, 2017, University of Oxford, Oxford, UK, pages 490-497. Los Alamitos, CA, USA: IEEE Computer Society Press, ISBN: 978-1-5386-0770-1.
accepted as full paper.
paper / slides / blog entry
Thomas Weise, Yuezhong Wu, Raymond Chiong, Ke Tang, and Jörg Lässig. Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. Journal of Global Optimization 66(3):511-534, November 2016.
doi:10.1007/s10898-016-0417-5 / pdf
Indexing: EI:20160902030834, WOS:000386373700007, SCI
Yuezhong Wu, Thomas Weise, and Weichen Liu. Hybridizing Different Local Search Algorithms with Each Other and Evolutionary Computation: Better Performance on the Traveling Salesman Problem. In Proceedings of the 18th Genetic and Evolutionary Computation Conference (GECCO'16), Denver, Colorado, USA, July 20–24, 2016, pages 57-58, New York, NY, USA: Association for Computing Machinery (ACM). ISBN: 978-1-4503-4323-7
doi:10.1145/2908961.2909001 / pdf / poster
Indexing: EI:20163702804277, WOS:000383741800029
Weichen Liu, Thomas Weise, Yuezhong Wu, Dan Xu, and Raymond Chiong. An Improved Ejection Chain Method and Its Hybrid Versions for Solving the Traveling Salesman Problem. Journal of Computational and Theoretical Nanoscience 13(6):3601-3610, June 2016
Weichen Liu, Thomas Weise, Yuezhong Wu, and Raymond Chiong. Hybrid Ejection Chain Methods for the Traveling Salesman Problem. In Proceedings of the 10th International Conference on Bio-Inspired Computing – Theories and Applications (BIC-TA'15), Maoguo Gong, Linqiang Pan, Tao Song, Ke Tang, and Xingyi Zhang, editors, September 25-28, 2015, Hefei, Anhui, China, volume 562 of Communications in Computer and Information Science. Berlin/Heidelberg: Springer-Verlag, pages 268-282, ISBN 978-3-662-49013-6.
doi:10.1007/978-3-662-49014-3_25 / pdf
Indexing: EI:20160300001732, WOS:000369890300025
Dan Xu, Thomas Weise, Yuezhong Wu, Jörg Lässig, and Raymond Chiong. An Investigation of Hybrid Tabu Search for the Traveling Salesman Problem. In Proceedings of the 10th International Conference on Bio-Inspired Computing – Theories and Applications (BIC-TA'15), Maoguo Gong, Linqiang Pan, Tao Song, Ke Tang, and Xingyi Zhang, editors, September 25-28, 2015, Hefei, Anhui, China, volume 562 of Communications in Computer and Information Science. Berlin/Heidelberg: Springer-Verlag, pages 523-537, ISBN 978-3-662-49013-6.
doi:10.1007/978-3-662-49014-3_47 / pdf
Indexing: EI:20160300001756, WOS:000369890300047
Yuezhong Wu, Thomas Weise, and Raymond Chiong. Local Search for the Traveling Salesman Problem: A Comparative Study. In Proceedings of the 14th IEEE Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC'15), July 6-8, 2015, Beijing, China, pages 213-220, Los Alamitos, CA, USA: IEEE Computer Society Press, ISBN: 978-1-4673-7289-3.
doi:10.1109/ICCI-CC.2015.7259388 / pdf
Indexing: EI:20161202119039, WOS:000380466100034
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, pages 148-155. Los Alamitos, CA, USA: IEEE Computer Society Press. ISBN 978-1-4799-5375-2.
doi:10.1109/CIPLS.2014.7007174 / pdf
Indexing: EI:20150700522268, WOS:000380487400021
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.
Featured article and selected paper at the website of the IEEE Computational Intelligence Society (http://cis.ieee.org/).
doi:10.1109/MCI.2014.2326101 / pdf
Indexing: EI:20143117995681, WOS:000340271800004, SCI, Google Scholar
3. Organized Events
Thomas Weise, Bin Li, Markus Wagner, Xingyi Zhang, and Jörg Lässig. International Workshop on Benchmarking of Computational Intelligence Algorithms (BOCIA) at the Tenth International Conference on Advanced Computational Intelligence (ICACI 2018), March 29-31, 2018 in Xiamen, China
website / Call for Papers (CfP)
Thomas Weise and Jörg Lässig. Special Session on Benchmarking and Testing for Production and Logistics Optimization of the 2014 IEEE Symposium on Computational Intelligence in Production and Logistics at the 2014 IEEE Symposium Series on Computational Intelligence (SSCI 2014), December 9-12, 2014, Orlando, Florida, USA