Ant Colony Optimization for Multiple Travelling Salesmen Problem with Pivot Cities

被引:1
作者
Xu, Nun [1 ]
Wu, Deming [1 ]
Yang, Qiang [2 ]
Wang, Hua [3 ]
Zhou, Xiangmin [4 ]
Zeng, Zhonglong [1 ]
Ge, Yisu [5 ]
Gao, Xudong
机构
[1] Zhejiang Normal Univ, Coll Math & Comp Sci, Jinhua, Peoples R China
[2] Nanjing Univ Informat Sci & Technol, Sch Artificial Intelligence, Nanjing, Peoples R China
[3] Victoria Univ, Inst Sustainable Ind Liveable Cities, Melbourne, Vic, Australia
[4] RAIIT Univ, Sch Comp Technol, Melbourne, Vic, Australia
[5] Wenzhou Univ, Coll Comp Sci & Artificial Intelligence, Wenzhou, Peoples R China
来源
2023 15TH INTERNATIONAL CONFERENCE ON ADVANCED COMPUTATIONAL INTELLIGENCE, ICACI | 2023年
基金
中国国家自然科学基金; 新加坡国家研究基金会;
关键词
Multiple Traveling Salesmen Problem; Ant Colony Optimization; Pivot Cities; Solution Construction;
D O I
10.1109/ICACI58115.2023.10146169
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Multiple travelling salesmen problem with pivot cities (PCMTSP) is a variant of the multiple travelling salesmen problem (MTSP). The same with MTSP, in PCMTSP, multiple salesmen visit all cities together. However, different from MTSP, in PCMTSP, some cities can be visited multiple times by multiple salesmen. Such cities are called pivot cities. The objective of this new problem is to minimize both the total travelling cost of all salesmen and the path difference among salesmen on the condition that only the pivot cities are visited by multiple travelers, while the other cities are only visited once by only one salesman. To tackle this new problem, this paper adapts ant colony optimization (ACO) by maintaining ant groups to find the shortest paths of all salesmen. In particular, each ant group contains the same number of ants with that of the salesmen, and each ant is employed to build the path of one salesman. To maintain a good balance among the paths of all salesmen, four ant selection strategies are further devised to build the paths of all salesmen city by city, namely In-turn Selection (IS), Shortest City Distance Biased Selection (SCDBS), Shortest Path Biased Selection (SPBS) and City First Path Second Based Selection (CFPSBS). To further promote the solution accuracy, the 2-opt operator is employed to locally optimize the paths of all salesmen. At last, experiments are conducted on four TSPLIB benchmark instances with different numbers of travelling salesmen. Experimental results have demonstrated the effectiveness of the four proposed selection schemes. Particularly, among the devised four ant selection strategies, SPBS assists ACO to attain the best optimization performance in coping with PCMTSP.
引用
收藏
页数:8
相关论文
共 37 条
[1]  
Bao Cong, 2022, 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), P3033, DOI 10.1109/SMC53654.2022.9945175
[2]   Ant Colony Optimization with Shortest Distance Biased Dispatch for Visiting Constrained Multiple Traveling Salesmen Problem [J].
Bao, Cong ;
Yang, Qiang ;
Gao, Xu-Dong ;
Lu, Zhen-Yu ;
Zhang, Jun .
PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2022, 2022, :77-80
[3]   A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy [J].
Cheikhrouhou, Omar ;
Khoufi, Ines .
COMPUTER SCIENCE REVIEW, 2021, 40
[4]   Ant Colony Optimization for the Control of Pollutant Spreading on Social Networks [J].
Chen, Wei-Neng ;
Tan, Da-Zhao ;
Yang, Qiang ;
Gu, Tianlong ;
Zhang, Jun .
IEEE TRANSACTIONS ON CYBERNETICS, 2020, 50 (09) :4053-4065
[5]   Ant Colony Optimization Based Memetic Algorithm to Solve Bi-Objective Multiple Traveling Salesmen Problem for Multi-Robot Systems [J].
Chen, Xinye ;
Zhang, Ping ;
Du, Guanglong ;
Li, Fang .
IEEE ACCESS, 2018, 6 :21745-21757
[6]  
COLORNI A, 1992, FROM ANIM ANIMAT, P134
[7]   ITO algorithm with local search for large scale multiple balanced traveling salesmen problem [J].
Dong, Xueshi ;
Xu, Min ;
Lin, Qing ;
Han, Shuning ;
Li, Qingshun ;
Guo, Qingteng .
KNOWLEDGE-BASED SYSTEMS, 2021, 229
[8]   Parameter optimization of control system design for uncertain wireless power transfer systems using modified genetic algorithm [J].
Gao, Xudong ;
Cao, Wenjie ;
Yang, Qiang ;
Wang, Honglin ;
Wang, Xiaolei ;
Jin, Guang ;
Zhang, Jun .
CAAI TRANSACTIONS ON INTELLIGENCE TECHNOLOGY, 2022, 7 (04) :582-593
[9]   Parallel Performance of an Ant Colony Optimization Algorithm for TSP [J].
Gu Weidong ;
Feng Jinqiao ;
Wang Yazhou ;
Zhong Hongjun ;
Huo Jidong .
PROCEEDINGS OF 8TH INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTATION TECHNOLOGY AND AUTOMATION (ICICTA 2015), 2015, :625-629
[10]   Modeling and optimization of multiple traveling salesmen problems: An evolution strategy approach [J].
Karabulut, Korhan ;
Oztop, Hande ;
Kandiller, Levent ;
Tasgetiren, M. Fatih .
COMPUTERS & OPERATIONS RESEARCH, 2021, 129