Solving the clustered traveling salesman problem via traveling salesman problem methods

Yongliang Lu; Jin-Kao Hao; Qinghua Wu

doi:10.7717/peerj-cs.972

Solving the clustered traveling salesman problem via traveling salesman problem methods

PeerJ Comput Sci. 2022 Jun 13:8:e972. doi: 10.7717/peerj-cs.972. eCollection 2022.

Authors

Yongliang Lu¹, Jin-Kao Hao², Qinghua Wu³

Affiliations

¹ School of Economics and Management, Fuzhou University, Fuzhou, China.
² LERIA, Université d'Angers, Angers, France.
³ School of Management, Huazhong University of Science and Technology, Wuhan, China.

Abstract

The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.

Keywords: Clustered traveling salesman, Problem transformation; Heuristics; Traveling salesman.

Grants and funding

This work was supported by the National Natural Science Foundation of China (No. 72122006). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.