TY - JOUR
T1 - Delaunay-Triangulation-Based Variable Neighborhood Search to Solve Large-Scale General Colored Traveling Salesman Problems
AU - Xu, Xiangping
AU - Li, Jun
AU - Zhou, Meng Chu
N1 - Funding Information:
Manuscript received August 2, 2019; revised November 7, 2019; accepted January 24, 2020. Date of publication February 21, 2020; date of current version March 1, 2021. This work was supported in part by the National Natural Science Foundation of China under Grant 61773115, Grant 61374069, and Grant 61374148, in part by the Jiangsu Province Natural Science Foundation under Grant BK20161427, in part by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, under Grant 422-135-D1441, and in part by the Suzhou Industrial Technology Innovation Special Project under Grant SS201704. The Associate Editor for this article was J. Sanchez-Medina. (Corresponding author: Jun Li.) Xiangping Xu and Jun Li are with the Ministry of Education, Key Laboratory of Measurement and Control of CSE, Southeast University, Nanjing 210096, China (e-mail: xpxu1990@gmail.com; j.li@seu.edu.cn).
Publisher Copyright:
© 2000-2011 IEEE.
PY - 2021/3
Y1 - 2021/3
N2 - A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. It utilizes colors to differentiate the accessibility of its cities to its salesmen. In our prior work, CTSPs are formulated over graphs associated with a city-color matrix. This work redefines a general colored traveling salesman problem (GCTSP) in the framework of hypergraphs and reveals several important properties of GCTSP. In GCTSP, the setting of city colors is richer than that in CTSPs. As results, it can be used to model and address various complex scheduling problems. Then, a Delaunay-triangulation-based Variable Neighborhood Search (DVNS) algorithm is developed to solve large-scale GCTSPs. At the beginning stage of DVNS, a divide and conquer algorithm is exploited to prepare a Delaunay candidate set for lean insertion. Next, the incumbent solution is perturbed by utilizing greedy multi-insertion and exchange mutation to obtain a variety of neighborhoods. Subsequently, 2-opt and 3-opt are used for local search in turn. Extensive experiments are conducted for many large scale GCTSP cases among which two maximal ones are up to 33000+ cities for 4 salesmen and 240 salesmen given 11000+ cities, respectively. The results show that the proposed method outperforms the existing four genetic algorithms and two VNS methods in terms of search ability and convergence rate.
AB - A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. It utilizes colors to differentiate the accessibility of its cities to its salesmen. In our prior work, CTSPs are formulated over graphs associated with a city-color matrix. This work redefines a general colored traveling salesman problem (GCTSP) in the framework of hypergraphs and reveals several important properties of GCTSP. In GCTSP, the setting of city colors is richer than that in CTSPs. As results, it can be used to model and address various complex scheduling problems. Then, a Delaunay-triangulation-based Variable Neighborhood Search (DVNS) algorithm is developed to solve large-scale GCTSPs. At the beginning stage of DVNS, a divide and conquer algorithm is exploited to prepare a Delaunay candidate set for lean insertion. Next, the incumbent solution is perturbed by utilizing greedy multi-insertion and exchange mutation to obtain a variety of neighborhoods. Subsequently, 2-opt and 3-opt are used for local search in turn. Extensive experiments are conducted for many large scale GCTSP cases among which two maximal ones are up to 33000+ cities for 4 salesmen and 240 salesmen given 11000+ cities, respectively. The results show that the proposed method outperforms the existing four genetic algorithms and two VNS methods in terms of search ability and convergence rate.
KW - Colored traveling salesman problem
KW - Delaunay triangulation
KW - genetic algorithm
KW - hypergraph
KW - intelligent optimization
KW - variable neighborhood search
UR - http://www.scopus.com/inward/record.url?scp=85102335362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102335362&partnerID=8YFLogxK
U2 - 10.1109/TITS.2020.2972389
DO - 10.1109/TITS.2020.2972389
M3 - Article
AN - SCOPUS:85102335362
SN - 1524-9050
VL - 22
SP - 1583
EP - 1593
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 3
M1 - 9007037
ER -