Details of Research Outputs

TitleMulti-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems
Author (Name in English or Pinyin)
Zhou, Yangming1; Xu W.2; Fu, Zhanghua3; Zhou, Mengchu4
Date Issued2022
Source PublicationIEEE Transactions on Intelligent Transportation Systems
ISSN15249050
EISSN1558-0016
Volume23Issue:9Pages:16072-16082
AbstractA coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen's the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.
KeywordUrban areas Color Traveling salesman problems Simulated annealing Biological cells Upper bound Robots Multi-neighborhood search simulated annealing iterated local search colored traveling salesman problem
DOI10.1109/TITS.2022.3147924
Indexed BySCIE
language英语
Funding ProjectFundo Para o Desenvolvimento das Ciencias da Tecnologia (FDCT) [0047/2021/A1]; National Natural Science Foundation of China [61903144]; Shanghai Sailing Program [19YF1412400]; Macau Young Scholars Program [AM2020011]; Open Project of the Shenzhen Institute of Artificial Intelligence and Robotics for Society [AC01202005002]
WOS Research AreaEngineering ; Transportation
WOS SubjectEngineering, Civil ; Engineering, Electrical & Electronic ; Transportation Science & Technology
WOS IDWOS:000767802500001
PublisherIEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Original Document TypeArticle
Firstlevel Discipline信息科学与系统科学
Education discipline科技类
Published range国外学术期刊
References
[1] J. Li, Q. Sun, M. Zhou, X. Yu, and X. Dai, "Colored traveling salesman problem and solution, " IFAC Proc. Volumes, vol. 47, no. 3, pp. 9575-9580, 2014.
[2] T. Bektas, "The multiple traveling salesman problem: An overview of formulations and solution procedures, " Omega, vol. 34, no. 3, pp. 209-219, Jun. 2006.
[3] J. Li, X. H. Meng, and X. Dai, "Collision-free scheduling of multibridge machining systems: A colored traveling salesman problem-based approach, " IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 139-147, Jan. 2018.
[4] L. Huang, M. Zhou, K. Hao, and E. Hou, "A survey of multi-robot regular and adversarial patrolling, " IEEE/CAA J. Automatica Sinica, vol. 6, no. 4, pp. 894-903, Jul. 2019.
[5] J. Li, M. Zhou, Q. Sun, X. Dai, and X. Yu, "Colored traveling salesman problem, " IEEE Trans. Cybern., vol. 45, no. 11, pp. 2390-2401, Nov. 2015.
[6] X. Meng, J. Li, M. C. Zhou, X. Dai, and J. Dou, "Population-based incremental learning algorithm for a serial colored traveling salesman problem, " IEEE Trans. Syst., Man, Cybern. Syst., vol. 48, no. 2, pp. 277-288, Feb. 2018.
[7] X. Dong and Y. Cai, "A novel genetic algorithm for large scale colored balanced traveling salesman problem, " Future Gener. Comput. Syst., vol. 95, pp. 727-742, Jun. 2019.
[8] P. He and J.-K. Hao, "Iterated two-phase local search for the colored traveling salesmen problem, " Eng. Appl. Artif. Intell., vol. 97, Jan. 2021, Art. no. 104018.
[9] X. Xu, J. Li, and M. Zhou, "Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems, " IEEE Trans. Intell. Transp. Syst., vol. 22, no. 3, pp. 1583-1593, Mar. 2021.
[10] X. Xu, J. Li, and M. Zhou, "Bi-objective colored traveling salesman problems, " IEEE Trans. Intell. Transp. Syst., early access, Jun. 16, 2021, doi: 10. 1109/TITS. 2021. 3086625.
[11] P. He, J.-K. Hao, and Q. Wu, "Grouping memetic search for the colored traveling salesmen problem, " Inf. Sci., vol. 570, pp. 689-707, Sep. 2021.
[12] Z. Shen, M. Dessouky, and F. Ordónez, "Stochastic vehicle routing problem for large-scale emergencies, " Working Paper, Tech. Rep., 2007.
[13] T. Cheong and C. C. White, "Dynamic traveling salesman problem: Value of real-time traffic information, " IEEE Trans. Intell. Transp. Syst., vol. 13, no. 2, pp. 619-630, Jun. 2012.
[14] S. A. Bouziaren and B. Aghezzaf, "An improved augmented _-constraint and branch-and-cut method to solve the TSP with profits, " IEEE Trans. Intell. Transp. Syst., vol. 20, no. 1, pp. 195-204, Jan. 2019.
[15] M. Dell'Amico, J. C. D. Díaz, G. Hasle, and M. Iori, "An adaptive iterated local search for the mixed capacitated general routing problem, " Transp. Sci., vol. 50, no. 4, pp. 1223-1238, Jun. 2016.
[16] E. A. Lemamou, P. Galinier, and S. Chamberland, "A hybrid iterated local search algorithm for the global planning problem of survivable 4G wireless networks, " IEEE/ACM Trans. Netw., vol. 24, no. 1, pp. 137-148, Feb. 2016.
[17] Y. Zhou and J.-K. Hao, "An iterated local search algorithm for the minimum differential dispersion problem, " Knowl.-Based Syst., vol. 125, pp. 26-38, Jun. 2017.
[18] H. R. Lourenço, O. C. Martin, and T. Stützle, "Iterated local search: Framework and applications, " in Handbook of Metaheuristics. Cham, Switzerland: Springer, 2019, pp. 129-168.
[19] V. R. Máximo and M. C. V. Nascimento, "A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem, " Eur. J. Oper. Res., vol. 294, no. 3, pp. 1108-1119, Nov. 2021.
[20] X. Meng, J. Li, X. Dai, and J. Dou, "Variable neighborhood search for a colored traveling salesman problem, " IEEE Trans. Intell. Transp. Syst., vol. 19, no. 4, pp. 1018-1026, Apr. 2018.
[21] X. Dong, W. Dong, and Y. Cai, "Ant colony optimisation for coloured travelling salesman problem by multi-task learning, " IET Intell. Transp. Syst., vol. 12, no. 8, pp. 774-782, Oct. 2018.
[22] Y. Feng et al., "Target disassembly sequencing and scheme evaluation for CNC machine tools using improved multiobjective ant colony algorithm and fuzzy integral, " IEEE Trans. Syst., Man, Cybern., Syst., vol. 49, no. 12, pp. 2438-2451, Dec. 2019.
[23] V. Pandiri and A. Singh, "A swarm intelligence approach for the colored traveling salesman problem, " Appl. Intell., vol. 48, no. 11, pp. 4412-4428, 2018.
[24] X. Dong, Q. Lin, M. Xu, and Y. Cai, "Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem, " IET Intell. Transp. Syst., vol. 13, no. 10, pp. 1483-1491, Oct. 2019.
[25] X. Wang, S. Shao, and J. Tang, "Iterative local-search heuristic for weighted vehicle routing problem, " IEEE Trans. Intell. Transp. Syst., vol. 22, no. 6, pp. 3444-3454, Jun. 2021.
[26] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing, " Science, vol. 220, no. 4598, pp. 671-680, 1983.
[27] V. Cerný, "Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, " J. Optim. Theory Appl., vol. 45, no. 1, pp. 41-51, Jan. 1985.
[28] Y. Zhou, W. Xu, Z.-H. Fu, and M. Zhou, "Solving colored traveling salesman problem via multi-neighborhood simulated annealing search, " in Proc. IEEE 18th Int. Conf. Netw., Sens. Control, Dec. 2021, pp. 1-6.
[29] A. Franzin and T. Stützle, "Revisiting simulated annealing: A component-based analysis, " Comput. Oper. Res., vol. 104, pp. 191-206, Apr. 2019.
[30] Y. Nagata and S. Kobayashi, "A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem, " INFORMS J. Comput., vol. 25, no. 2, pp. 346-363, May 2013.
[31] K. Helsgaun, "General k-opt submoves for the Lin-Kernighan TSP heuristic, " Math. Program. Comput., vol. 1, nos. 2-3, pp. 119-163, Oct. 2009.
[32] J. Zheng, K. He, J. Zhou, Y. Jin, and C. Li, "Combining reinforcement learning with Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem, " in Proc. 35th AAAI Conf. Artif. Intell., 2021, pp. 12445-12452.
[33] D. L. Applegate et al., "Certification of an optimal TSP tour through 85, 900 cities, " Oper. Res. Lett., vol. 37, no. 1, pp. 11-15, Jan. 2009.
[34] K. Helsgaun, "An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems, " Dept. People Technol., Roskilde Univ., Roskilde, Denmark, Tech. Rep., 2017.
[35] Y. Nagata and S. Kobayashi, "Edge assembly crossover: A high-power genetic algorithm for the travelling salesman problem, " in Proc. 7th Int. Conf. Genetic Algorithms, 1997, pp. 450-457.
[36] J. Demšar, "Statistical comparisons of classifiers over multiple data sets, " J. Mach. Learn. Res., vol. 7, pp. 1-30, Jan. 2006.
[37] L. Kotthoff, "Algorithm selection for combinatorial search problems: A survey, " AI Mag., vol. 35, no. 3, pp. 48-60, Sep. 2014.
[38] R. M. Aiex, M. G. C. Resende, and C. C. Ribeiro, "TTT plots: A perl program to create time-to-target plots, " Optim. Lett., vol. 1, no. 4, pp. 355-366, Oct. 2007.
[39] X. Jin, H. Qin, Z. Zhang, M. Zhou, and J. Wang, "Planning of garbage collection service: An arc-routing problem with time-dependent penalty cost, " IEEE Trans. Intell. Transp. Syst., vol. 22, no. 5, pp. 2692-2705, May 2021.
[40] Z. Zhao, S. Liu, M. Zhou, and A. Abusorrah, "Dual-objective mixed integer linear program and memetic algorithm for an industrial group scheduling problem, " IEEE/CAA J. Automatica Sinica, vol. 8, no. 6, pp. 1199-1209, Jun. 2021.
[41] C. Liu, F. Zhu, Q. Liu, and Y. Fu, "Hierarchical reinforcement learning with automatic sub-goal identification, " IEEE/CAA J. Autom. Sinica, vol. 8, no. 10, pp. 1686-1696, Oct. 2021.
[42] Z. Zhang, H. Liu, M. Zhou, and J. Wang, "Solving dynamic traveling salesman problems with deep reinforcement learning, " IEEE Trans. Neural Netw. Learn. Syst., 2021, doi: 10. 1109/TNNLS. 2021. 3105905.
Data SourceWOS
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
Identifierhttps://irepository.cuhk.edu.cn/handle/3EPUXD0A/3260
CollectionInstitute of Robotics and Intelligent Manufacturing
School of Science and Engineering
Shenzhen Institute of Artificial Intelligence and Robotics for Society
Corresponding AuthorZhou, Mengchu
Affiliation
1.Sino-US Global Logistics Institute, Shanghai Jiao Tong University, Shanghai 200030, China, and also with the Macau Institute of Systems Engineering, Macau University of Science and Technology, Macao 999078, China.
2.Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China.
3.Institute of Robotics and Intelligent Manufacturing, and the Shenzhen Institute of Artificial Intelligence and Robotics for Society, The Chinese University of Hong Kong (Shenzhen), Shenzhen 518172, China.
4.Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102 USA
Recommended Citation
GB/T 7714
Zhou, Yangming,Xu W.,Fu, Zhanghuaet al. Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems[J]. IEEE Transactions on Intelligent Transportation Systems,2022,23(9):16072-16082.
APA Zhou, Yangming, Xu W., Fu, Zhanghua, & Zhou, Mengchu. (2022). Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems. IEEE Transactions on Intelligent Transportation Systems, 23(9), 16072-16082.
MLA Zhou, Yangming,et al."Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems".IEEE Transactions on Intelligent Transportation Systems 23.9(2022):16072-16082.
Files in This Item:
There are no files associated with this item.
Related Services
Usage statistics
Google Scholar
Similar articles in Google Scholar
[Zhou, Yangming]'s Articles
[Xu W.]'s Articles
[Fu, Zhanghua]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, Yangming]'s Articles
[Xu W.]'s Articles
[Fu, Zhanghua]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, Yangming]'s Articles
[Xu W.]'s Articles
[Fu, Zhanghua]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.