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
- Thomas Weise, Yan Jiang, Qi Qi, and Weichen Liu. A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem. International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13(3):1-18, Fall 2019
doi:10.4018/IJCINI.2019070101
Indexing: ESCI - Thomas Weise, Yuezhong Wu, Weichen Liu, and Raymond Chiong. Implementation Issues in Optimization Algorithms: Do they matter? Journal of Experimental & Theoretical Artificial Intelligence (JETAI) 31(4):533–554, 2019.
doi:10.1080/0952813X.2019.1574908
Indexing: EI, ESCI, 4区, CCF-C类 - Thomas Weise, Xiaofeng Wang, Qi Qi, Bin Li, and Ke Tang. Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
doi:10.1016/j.asoc.2018.08.030 / blog entry
Indexing: EI, WOS:000450124900027, ESCI, 1区 - Qi Qi, Thomas Weise, and Bin Li. Optimization Algorithm Behavior Modeling: A Study on the Traveling Salesman Problem. In Proceedings of the Tenth International Conference on Advanced Computational Intelligence (ICACI 2018), March 29-31, 2018 in Xiamen [厦门], Fujian [福建省], China, IEEE, pages 861–866. ISBN: 978-1-5386-4362-4. Appeared in the International Workshop on Benchmarking of Computational Intelligence Algorithms (BOCIA) at the ICACI 2018.
doi:10.1109/ICACI.2018.8377576 / pdf / slides / workshop website - 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
Indexing: EI:20173104005769, CCF-C类 - 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.
doi:10.1109/ICCI-CC.2017.8109794 / paper / slides / blog entry
Indexing: EI - 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, 2区 - 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, CCF-C类 - 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
doi:10.1166/jctn.2016.5189
Indexing: EI:20164002870059 - 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, 1区, Google Scholar
Organized Events
- Thomas Bäck, Thomas Bartz-Beielstein, Jakob Bossek, Bilel Derbel, Carola Doerr, Tome Eftimov, Pascal Kerschke, William La Cava, Arnaud Liefooghe, Manuel López-Ibáñez, Boris Naujoks, Pietro S. Oliveto, Patryk Orzechowski, Mike Preuss, Jérémy Rapin, Ofer M. Shir, Olivier Teytaud, Heike Trautmann, Ryan J. Urbanowicz, Vanessa Volz, Markus Wagner, Hao Wang, Thomas Weise, Borys Wróbel, and Aleš Zamuda. Good Benchmarking Practices for Evolutionary Computation (BENCHMARK@PPSN) Workshop at the Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN XVI), September 5-9, 2020 in Leiden, The Netherlands.
website / Call for Papers (CfP) - Thomas Bäck, Carola Doerr, Tome Eftimov, Pascal Kerschke, William La Cava, Manuel López-Ibáñez, Boris Naujoks, Pietro S. Oliveto, Patryk Orzechowski, Mike Preuss, Jérémy Rapin, Ofer M. Shir, Olivier Teytaud, Heike Trautmann, Ryan J. Urbanowicz, Vanessa Volz, Markus Wagner, Hao Wang, Thomas Weise, Borys Wróbel, and Aleš Zamuda. Good Benchmarking Practices for Evolutionary Computation (BENCHMARK@GECCO) Workshop at the Genetic and Evolutionary Computation Conference (GECCO 2020), July 8-12, 2020, Cancún, Quintana Roo, Mexico.
website / Call for Papers (CfP) / slides@google: 1,2,3 / slides@iao: 1,3 - Carola Doerr, Pietro S. Oliveto, Thomas Weise, Borys Wróbel, and Aleš Zamuda. Black Box Discrete Optimization Benchmarking (BB-DOB) Workshop at the Genetic and Evolutionary Computation Conference (GECCO 2019), July 13-17, 2019, Prague, Czech Republic.
website / Call for Papers (CfP) - Thomas Weise, Bin Li, Markus Wagner, Xingyi Zhang, and Jörg Lässig, eds. Special Issue on Benchmarking of Computational Intelligence Algorithms published in the Applied Soft Computing journal published by Elsevier B.V. and indexed by EI and SCIE. The special issue was open for submissions from July 2018 and closed in April 14, 2019. It is a virtual special issues, where papers will be published as soon as they are accepted.
website / CfP-website / Call for Papers (CfP) - Pietro S. Oliveto, Markus Wagner, Thomas Weise, Borys Wróbel, and Aleš Zamuda. Black-Box Discrete Optimization Benchmarking (BB-DOB@PPSN) Workshop at the Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN XV), 8-9 September 2018, Coimbra, Portugal
website / Call for Papers (CfP) - Pietro S. Oliveto, Markus Wagner, Thomas Weise, Borys Wróbel, and Aleš Zamuda. Black-Box Discrete Optimization Benchmarking (BB-DOB@GECCO) Workshop at the 2018 Genetic and Evolutionary Computation Conference (GECCO 2018), July 15-19, 2018 in Kyoto, Japan
website / Call for Papers (CfP) - 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 [厦门], Fujian [福建省], China, IEEE, ISBN: 978-1-5386-4362-4.
website / Call for Papers (CfP) - Thomas Weise and Jörg Lässig. SITA-UBRI Joint Workshop on Sustainable Logistics, November 5, 2015, Hefei, Anhui, China
- 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