Circular Jaccard distance based multi-solution optimization for traveling salesman problems

Hui Li; Mengyao Zhang; Chenbo Zeng; Hui Li; Mengyao Zhang; Chenbo Zeng

doi:10.3934/mbe.2022206

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 5: 4458-4480. doi: 10.3934/mbe.2022206

Previous Article Next Article

Research article Special Issues

Circular Jaccard distance based multi-solution optimization for traveling salesman problems

Department of Computer Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China

Academic Editor: Raffaele Mascella

Received: 13 October 2021 Revised: 08 January 2022 Accepted: 14 February 2022 Published: 02 March 2022

Traveling salesman problem is a widely studied NP-hard problem in the field of combinatorial optimization. Many and various heuristics and approximation algorithms have been developed to address the problem. However, few studies were conducted on the multi-solution optimization for traveling salesman problem so far. In this article, we propose a circular Jaccard distance based multi-solution optimization (CJD-MSO) algorithm based on ant colony optimization to find multiple solutions for the traveling salesman problem. The CJD-MSO algorithm incorporates "distancing" niching technique with circular Jaccard distance metric which are both proposed in this paper for the first time. Experimental results verify that the proposed algorithm achieves good performance on both quality and diversity of the optimal solutions.
- traveling salesman problem,
- multimodal optimization,
- multi-solution optimization,
- Jaccard distance,
- metaheuristics
Citation: Hui Li, Mengyao Zhang, Chenbo Zeng. Circular Jaccard distance based multi-solution optimization for traveling salesman problems[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4458-4480. doi: 10.3934/mbe.2022206

Related Papers:

Abstract

Traveling salesman problem is a widely studied NP-hard problem in the field of combinatorial optimization. Many and various heuristics and approximation algorithms have been developed to address the problem. However, few studies were conducted on the multi-solution optimization for traveling salesman problem so far. In this article, we propose a circular Jaccard distance based multi-solution optimization (CJD-MSO) algorithm based on ant colony optimization to find multiple solutions for the traveling salesman problem. The CJD-MSO algorithm incorporates "distancing" niching technique with circular Jaccard distance metric which are both proposed in this paper for the first time. Experimental results verify that the proposed algorithm achieves good performance on both quality and diversity of the optimal solutions.

References

[1]	M. Dorigo, Traveling salesman problem, in IEEE International Conference Evolutionary Computation, (2013).
[2]	R. M. Al-Khatib, K. M. O. Nahar, SRT-GA: smart real-time system using a powerful genetic algorithm for school bus routing problem, in 2017 2nd International Conference on the Applications of Information Technology in Developing Renewable Energy Processes & Systems (IT-DREPS), (2017), 1–8. https://doi.org/10.1109/IT-DREPS.2017.8277816
[3]	S. Ma, Y. Hao, Research on the order picking optimization problem of the automated warehouse, in 2009 Chinese Control and Decision Conference, (2009), 990–993. https://doi.org/10.1109/CCDC.2009.5192816
[4]	T. Ghorpade, C. G. Corlu, Selective pick-up and delivery problem: a simheuristic approach, in 2020 Winter Simulation Conference (WSC), (2020), 1468–1479. https://doi.org/10.1109/WSC48552.2020.9384060
[5]	P. Kalita, B. Kalita, SCS and TSP in DNA sequencing, Int. J. Management It Eng., 3 (2013), 263–277.
[6]	M. Cygan, L. Kowalik, A. Socala, Improving TSP tours using dynamic programming over tree decomposition, ACM Trans. Algorithms, 15 (2019), 1–19.
[7]	J. L. An, J. Gao, J. H. Lei, G. H. Gao, An improved algorithm for TSP problem solving with Hopfield neural networks, Adv. Mater. Res., 143 (2011), 538–542. https://doi.org/10.4028/www.scientific.net/AMR.143-144.538 doi: 10.4028/www.scientific.net/AMR.143-144.538
[8]	T. Liu, H. Zhang, Y. Gao, Solving TSP via fuzzy dynamic PSO and HNN algorithm, in 2012 7th International Conference on Computer Science Education (ICCSE), (2012), 105–109. https://doi.org/10.1109/ICCSE.2012.6295036
[9]	H. Li, X. Liu, Z. Huang, C. Zeng, P. Zou, Z. Chu, et al., Newly emerging nature-inspired optimization - algorithm review, unified framework, evaluation, and behavioral parameter optimization, IEEE Access, 8 (2020), 72620–72649.
[10]	H. Li, Z. Huang, X. Liu, C. Zeng, P. Zou, Multi-fidelity Meta-optimization for nature inspired optimization algorithms, Appl. Soft Comput., 96 (2020), 106619. https://doi.org/10.1016/j.asoc.2020.106619 doi: 10.1016/j.asoc.2020.106619
[11]	H. Li, J. Zhang, Fast source term estimation using the PGA-NM hybrid method, Eng. Appl. Artif. Intel., 62 (2017), 68–79. https://doi.org/10.1016/j.engappai.2017.03.010 doi: 10.1016/j.engappai.2017.03.010
[12]	L. Wang, J. Zhang, H. Li, An improved genetic algorithm for TSP, in 2007 International Conference on Machine Learning and Cybernetics, (2007), 925–928. https://doi.org/10.1109/ICMLC.2007.4370274
[13]	G. C. Chen, Y. U. Jin-Shou, Particle swarm optimization algorithm, Inf. Control, (2005), 454–458.
[14]	J. Zhang, W. Si, Improved enhanced self-tentative PSO algorithm for TSP, in 2010 Sixth International Conference on Natural Computation, (2010), 2638–2641. https://doi.org/10.1109/ICNC.2010.5583011
[15]	M. Dorigo, G. D. Caro, L. M. Gambardella, Ant algorithms for discrete optimization, Artif. Life, 5 (1999), 137–172. https://doi.org/10.1162/106454699568728 doi: 10.1162/106454699568728
[16]	F. Valdez, I. Chaparro, Ant colony optimization for solving the TSP symetric with parallel processing, in 2013 Joint IFSA World Congress and NAFIPS Annual Meeting (IFSA/NAFIPS), (2013), 1192–1196. https://doi.org/10.1109/IFSA-NAFIPS.2013.6608570
[17]	S. Gao, J. Zhong, Y. Cui, C. Gao, X. Li, A novel pheromone initialization strategy of ACO algorithms for solving TSP, in 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), (2017), 243–248. https://doi.org/10.1109/FSKD.2017.8393155
[18]	Y. Zhang, C. Wang, H. Li, X. Su, M. Zhao, N. Zhang, An improved 2-Opt and ACO hybrid algorithm for TSP, in 2018 Eighth International Conference on Instrumentation Measurement, Computer, Communication and Control (IMCCC), (2018), 547–552. https://doi.org/10.1109/IMCCC.2018.00121
[19]	R. W. Dewantoro, P. Sihombing, Sutarman, The combination of ant colony optimization (ACO) and Tabu search (TS) algorithm to solve the traveling salesman problem (TSP), in 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering (ELTICOM), (2019), 160–164. https://doi.org/10.1109/ELTICOM47379.2019.8943832
[20]	T. Öncan, A survey of the generalized assignment problem and its applications, INFOR Inform. Syst. Oper. Res., 45 (2008), 123–141. https://doi.org/10.3138/infor.45.3.123 doi: 10.3138/infor.45.3.123
[21]	T. Huang, Y. J. Gong, J. Zhang, Seeking multiple solutions of combinatorial optimization problems: a proof of principle study, in 2018 IEEE Symposium Series on Computational Intelligence (SSCI), (2018), 18–21. https://doi.org/10.1109/SSCI.2018.8628856
[22]	T. Huang, Y. J. Gong, S. Kwong, H. Wang, J. Zhang, A niching memetic algorithm for multi-solution traveling salesman problem, IEEE Trans. Evolut. Comput., 24 (2020), 508–522. https://doi.org/10.1109/TEVC.2019.2936440 doi: 10.1109/TEVC.2019.2936440
[23]	X. C. Han, H. W. Ke, Y. J. Gong, Y. Lin, W. L. Liu, J. Zhang, Multimodal optimization of traveling salesman problem: a niching ant colony system, Proc. Genet. Evol. Comput. Conf. Companion, (2018), 87–88. https://doi.org/10.1145/3205651.3205731 doi: 10.1145/3205651.3205731
[24]	L. Gilbert, The traveling salesman problem: an overview of exact and approximate algorithms, Eur. J. Oper. Res., 59 (1992), 231–247. https://doi.org/10.1016/0377-2217(92)90138-Y doi: 10.1016/0377-2217(92)90138-Y
[25]	B. Fleischmann, A cutting plane procedure for the travelling salesman problem on road networks, Eur. J. Oper. Res., 21 (1985), 307–317. https://doi.org/10.1016/0377-2217(85)90151-1 doi: 10.1016/0377-2217(85)90151-1
[26]	H. P. Hipólito, S. G. Juan, A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Discrete Appl. Math., 145 (2004), 126–139. https://doi.org/10.1016/j.dam.2003.09.013 doi: 10.1016/j.dam.2003.09.013
[27]	M. Dorigo, L. M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput., 1 (1997), 53–66. https://doi.org/10.1109/4235.585892 doi: 10.1109/4235.585892
[28]	K. A. De Jong, An Analysis of the Behavior of A Class of Genetic Adaptive Systems, ProQuest Dissertations Publishing, 1975.
[29]	D. E. Goldberg, J. Richardson, Genetic algorithms with sharing for multimodal function optimization, in Genetic Algorithms and Their Applications, Proceedings of the Second International Conference on Genetic Algorithms, Proc Icga, (1987), 41—49.
[30]	A. Petrowski, A clearing procedure as a niching method for genetic algorithms, in Proceedings of IEEE International Conference on Evolutionary Computation, (1996), 798–803. https://doi.org/10.1109/ICEC.1996.542703
[31]	G. R. Harik, Finding multimodal solutions using restricted tournament selection, in Proceedings of the 6th International Conference on Genetic Algorithms, (1995), 24–31.
[32]	J. P. Li, M. E. Balazs, G. T. Parks, P. J. Clarkson, A species conserving genetic algorithm for multimodal function optimization, Evol. Comput., 10 (2002), 207–234. https://doi.org/10.1162/106365602760234081 doi: 10.1162/106365602760234081
[33]	X. Li, M. G. Epitropakis, K. Deb, A. Engelbrecht, Seeking multiple solutions : an updated survey on niching methods and their applications, IEEE Trans. Evol. Comput., 21 (2017), 518–538. https://doi.org/10.1109/TEVC.2016.2638437 doi: 10.1109/TEVC.2016.2638437
[34]	H. Li, P. Zou, Z. Huang, C. Zeng, X. Liu, Multimodal optimization using whale optimization algorithm enhanced with local search and niching technique, Math. Bio. Eng., 17 (2020), 1–27. https://doi.org/10.3934/mbe.2020001 doi: 10.3934/mbe.2020001
[35]	T. Bektas, L. Gouveia, Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?, Eur. J. Oper. Res., 236 (2014), 820–832. https://doi.org/10.1016/j.ejor.2013.07.038 doi: 10.1016/j.ejor.2013.07.038
[36]	G. Szekely, M. L. Rizzo, N. K. Bakirov, Measuring and testing dependence by correlation of distances, Ann. Statist., 35 (2007), 2769–2794. https://doi.org/10.1214/009053607000000505 doi: 10.1214/009053607000000505
[37]	J. Bank, B. Cole, Calculating the Jaccard similarity coefficient with map reduce for entity pairs in wikipedia, Wikipedia Similarity Team, 1 (2008), 94.
[38]	M. Shameem, R. Ferdous, An efficient k-means algorithm integrated with Jaccard distance measure for document clustering, in Asian Himalayas International Conference on Internet, (2009), 1–6. https://doi.org/10.1109/AHICI.2009.5340335
[39]	G. A. Croes, A method for solving travelling salesman problems, Oper. Res., 6 (1958), 791–812. https://doi.org/10.1287/opre.6.6.791 doi: 10.1287/opre.6.6.791

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)