K-DSA for the multiple traveling salesman problem

doi:10.23919/JSEE.2023.000023

Abstract

Abstract:

Aimed at a multiple traveling salesman problem (MTSP) with multiple depots and closed paths, this paper proposes a k-means clustering donkey and a smuggler algorithm (K-DSA). The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples; the large-scale MTSP is divided into multiple separate traveling salesman problems (TSPs), and the TSP is solved through the DSA. The proposed algorithm adopts a solution strategy of clustering first and then carrying out, which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained. The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms, the K-DSA has good solving performance and computational efficiency in MTSPs of different scales, especially with large-scale MTSP and when the convergence speed is faster; thus, the advantages of this algorithm are more obvious compared to other algorithms.

Key words: k-means clustering, donkey and smuggler algorithm (DSA), multiple traveling salesman problem (MTSP), multiple depots and closed paths

Sheng TONG, Hong QU, Junjie XUE. K-DSA for the multiple traveling salesman problem[J]. Journal of Systems Engineering and Electronics, 2023, 34(6): 1614-1625.

Figures/Tables 18

Fig 1

Fig 2

Fig 3

Table 1

Fig 4

Table 2

Fig 5

Table 3

Table 4

Table 5

Table 6

Table 7

Fig 6

Fig 7

Fig 8

Table 8

Fig 9

Table 9

References 39

1	YAN C, WANG Z J Study on the TSP based on an improved energy function and transiently chaotic neural network model. Journal of System Simulation, 2006, 18 (5): 1402- 1405.
2	BALACHANDAR S R, KANNAN K Randomized gravitational emulation search algorithm for symmetric traveling salesman problem. Applied Mathematics and Computation, 2007, 192 (2): 413- 421. doi: 10.1016/j.amc.2007.03.019
3	YANG N, TIAN W F, JIN Z H Crossover tabu search for traveling salesman problem. Journal of System Simulation, 2006, 18 (4): 897- 899.
4	SHEN X J, LIU Y Y, HUANG Y P, et al Fast ant colony algorithm for solving traveling salesman problem. Journal of Jilin University: Engineering and Technology Edition, 2013, 43 (1): 147- 151.
5	WANG Y P, LI Y H A novel quantum genetic algorithm for TSP. Chinese Journal of Computers, 2007, 30 (5): 748- 755.
6	GAO H B, ZHOU C, GAO L General particle swarm optimization model. Chinese Journal of Computers, 2005, 28 (5): 1980- 1987.
7	REN Z W, XIONG R, CHU J Hybrid quantum differential evolutionary algorithm and its applications. Control Theory & Applications, 2011, 28 (10): 1349- 1355.
8	ZHOU Y Q, HUANG Z X Artificial glow worm swarm optimization algorithm for TSP. Control and Decision, 2012, 27 (12): 1816- 1821.
9	FENG X, ZHANG J W, YU H Q Mosquito host-seeking algorithm for TSP problem. Chinese Journal of Computers, 2014, 37 (8): 1794- 1808.
10	WU H S, ZHANG F M, LI H, et al Discrete wolf pack algorithm for traveling salesman problem. Control and Decision, 2015, 30 (10): 1861- 1867.
11	ZHANG X L, CHEN X W, XIAO H, et al A new imperialist competitive algorithm for solving TSP problem. Control and Decision, 2013, 31 (4): 586- 592.
12	WANG J W, DAI G M, XIE B Q A survey of solving the traveling salesman problem. Computer Engineering & Science, 2008, 30 (2): 72- 74.
13	WANG Y Z, CHEN Y, YU Y Y Improved grouping genetic algorithm for solving multiple traveling salesman problem. Journal of Electronics & Information Technology, 2017, 39 (11): 198- 205.
14	RIGHINI G, TRUBIAN M A note on the approximation of the asymmetric traveling salesman problem. European Journal of Operational Research, 2004, 153 (1): 255- 265. doi: 10.1016/S0377-2217(02)00794-4
15	GORENSTEIN S Printing press scheduling for multi-edition periodicals. Management Science, 1970, 16 (6): 373- 383. doi: 10.1287/mnsc.16.6.B373
16	ZHANG T H, GRUVER W A, SMITH M H Team scheduling by genetic search. Proc. of the 2nd International Conference on Intelligent Processing and Manufacturing of Materials, 1999, 839- 844.
17	ANGEL R D, CAUDLE W L, NOONAN R, et al Computer assisted school bus scheduling. Management Science, 1972, 18 (6): 279- 288. doi: 10.1287/mnsc.18.6.B279
18	GILBERT K C, HOFSTRA R B A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem. Decision Sciences, 1992, 23 (1): 250- 259. doi: 10.1111/j.1540-5915.1992.tb00387.x
19	BRUMMIT B, STENTZ A Dynamic mission planning for multiple mobile robots. Proc. of the IEEE International Conference on Robotics and Automation, 1996, 2396- 2401.
20	ZHONG Y, LIANG J H, GU G C, et al An implementation of evolutionary computation for path planning of cooperative mobile robots. Proc. of the 4th World Congress on Intelligent Control and Automation, 2002, 1798- 1802.
21	CARTER A E, RAGSDALE C T A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 2006, 175 (1): 246- 257. doi: 10.1016/j.ejor.2005.04.027
22	ZHOU H L, SONG M L, PEDRYCZ W A comparative study of improved GA and PSO in solving multiple traveling salesmen problem. Applied Soft Computing, 2018, 64, 564- 580. doi: 10.1016/j.asoc.2017.12.031
23	SINGH S, VENKATESH S K, WANG Z, et al Diagnostic performance of magnetic resonance elastography in staging liver fibrosis: a systematic review and meta-analysis of individual participant data. Clinical Gastroenterology and Hepatology, 2015, 13 (3): 440- 451. doi: 10.1016/j.cgh.2014.09.046
24	REN H, HUANG H, SONG Z, et al Genetic algorithm on MTSP within polar coordinates and time consumption with respect to various variables. International Core Journal of Engineering, 2021, 7 (1): 291- 296.
25	BEKTAS T The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 2006, 34 (3): 209- 219. doi: 10.1016/j.omega.2004.10.004
26	FANG H Y, YANG T H, ZONG F X, et al Path optimization of multi-UAV cooperative reconnaissance based on MMTSP algorithm. Journal of Logistical Engineering University, 2017, 33 (3): 85- 90.
27	HOU M S, LIU D B A novel method for solving the multiple traveling salesmen problem with multiple depots. Chinese Science Bulletin, 2012, 57 (15): 1886- 1892. doi: 10.1007/s11434-012-5162-7
28	RAMADHANI T, HERTONO G F, HANDARI B D. An ant colony optimization algorithm for solving the fixed destination multi-depot multiple traveling salesman problem with non-random parameters. AIP Conference Proceedings, 2017, 1862(1): 30−123.
29	KOUBAA A, CHEIKHROUHOU O, BENNACEUR H, et al Move and improve: a market-based mechanism for the multiple depot multiple travelling salesmen problem. Journal of Intelligent & Robotic Systems, 2017, 85 (2): 307- 330.
30	ZHOU H L, SONG M L. An improvement of partheno-genetic algorithm to solve multiple travelling salesmen problem. Proc. of the 15th International Conference on Computer and Information Science, 2016. DOI: 10.1109/ICIS.2016.7550780.
31	HE L, WU L D, CAI Y C Summary of clustering algorithms in data mining. Application Research of Computers, 2007, 24 (1): 10- 13.
32	XIE C B, YUAN C Y Improved method of fuzzy partition clustering for optimal classification. System Engineering, 1997, 15 (1): 58- 63.
33	CILIBRASI R L, VITANYI P M B A fast quartet tree heuristic for hierarchical clustering. Pattern Recognition, 2011, 44 (3): 662- 677. doi: 10.1016/j.patcog.2010.08.033
34	LI K, WANG L Research on cluster integration method of hierarchical clustering. Computer Engineering and Applications, 2010, 46 (27): 120- 123.
35	WU J W, LI X F, SUN T Neighborhood balanced density clustering algorithm. Computer Research and Development, 2010, 47 (6): 1044- 1052.
36	CHEN N, CHEN A, ZHOU L X Density-based incremental grid clustering algorithm. Journal of Software, 2002, 13 (1): 1- 7.
37	KANUNGO T, MOUNT D M A local search approximation algorithm for k-means clustering. Computational Geometry, 2004, 28 (2/3): 89- 112.
38	ELKAN C Using the triangle inequality to accelerate k-means. Proc. of the 2nd AAAI International Conference on Machine Learning, 2003, 147- 153.
39	SHAMSALDIN A S, RASHID T A, AL-RASHID A R A, et al Donkey and smuggler optimization algorithm: a collaborative working approach to path finding. Journal of Computational Design and Engineering, 2019, 6 (4): 562- 583. doi: 10.1016/j.jcde.2019.04.004

City with number		Distance/km
City 1	City 2	11
	City 3	13
	City 4	12
	City 5	15
City 2	City 1	11
	City 3	14
	City 4	16
	City 5	9
City 3	City 1	13
	City 2	14
	City 4	10
	City 5	15
City 4	City 1	12
	City 2	16
	City 3	10
	City 5	15
City 5	City 1	16
	City 2	9
	City 3	15
	City 4	17

Initial city	Possible path
City 1	1	2	5	3	4
City 2	2	5	3	4	1
City 3	3	4	1	2	5
City 4	4	3	1	2	5
City 5	5	2	1	4	3

Path	Cities to take in sequence	Weight
A	1→2→5→3→4→1	57
B	1→3→4→2→5→1	64
C	1→4→3→2→5→1	61
D	1→5→2→3→4→1	60

Path	Cities to take in sequence	Weight
A	2→1→4→3→5→2	57
B	2→3→4→1→5→2	60
C	2→4→3→1→5→2	63
D	2→5→3→4→1→2	57

Path	Cities to take in sequence	Weight
A	3→1→2→5→4→3	60
B	3→2→5→1→4→3	61
C	3→4→1→2→5→3	57
D	3→5→2→1→4→3	57