Review of Multiple Traveling Salesman Model and Its Application

doi:10.3778/j.issn.1673-9418.2112006

Abstract

Abstract:

As a generalization of the classical traveling salesman problem (TSP), the multiple traveling salesman problem (MTSP) is one of the well-known combinatorial optimization problems. However, as a classical NP hard problem, the problem scale and computational complexity of the multiple traveling salesman problem have very high requirements for the solution method. This paper focuses on the multiple traveling salesman problem. Firstly, several characteristics, objective functions, problem constraints and variants of MTSP model are subdivided. Secondly, it classifies and sorts out the specific methods of several common heuristic algorithms in solving MTSP, and compares the similarities and differences of optimization objectives and solutions under different algorithms, so as to understand the general methods of solving multiple traveling salesman problems among different algorithms more intuitively. With the continuous development of multiple traveling salesman problem, scholars are not satisfied with simply solving mathematical problems, and try to regard many practical problems that meet conditions as multiple traveling salesman problems. This paper summarizes the specific construction methods of MTSP model in the context of practical applications such as logistics distribution, wireless sensor network, emergency rescue and UAV collaborative task planning. From the perspective of application results, using MTSP model to solve practical problems can not only reduce enterprise and individual costs, improve revenue, but also promote the development of this field towards a more efficient and intelligent direction. This paper mainly studies the multiple traveling salesman model and its application, which fills the gap in this research field.

Key words: multiple traveling salesman, path planning, heuristic algorithms, model application

摘要：

多旅行商问题（MTSP）作为经典旅行商问题（TSP）的一种泛化,是著名的组合优化问题之一。但多旅行商问题作为经典NP-hard问题,其问题规模以及运算复杂度都对求解方法有着极高的要求。重点关注多旅行商问题,首先对MTSP模型的几种特征、目标函数、问题约束以及变体进行了细分。其次对目前常见的几种启发式算法在求解MTSP上的具体方法进行了归类与整理,同时比较了在不同算法下优化目标与解决方法的相同之处与不同之处,以便于更直观理解不同算法间解决多旅行商问题的一般方法。随着多旅行商问题的不断发展,学者们已不满足于单纯解决数学问题,开始尝试将许多符合条件的实际问题看作多旅行商问题。归纳了在物流配送、无线传感网、应急救援和无人机协同任务规划等实际应用背景下MTSP模型的具体构建方式,从应用成果来看,利用MTSP模型解决实际问题不仅可以降低企业和个人成本,提升收益,还可以推动该领域向着更高效智能的方向发展。主要针对多旅行商模型及其应用展开了研究,填补了这一研究领域的空白。

关键词: 多旅行商, 路径规划, 启发式算法, 模型应用

CLC Number:

TP301.6

ZHANG Shuohang, GUO Gaizhi. Review of Multiple Traveling Salesman Model and Its Application[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1516-1528.

张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7): 1516-1528.

Figures/Tables 7

Fig.1 Development history of TSP scale

Table 1 Calculation amount and calculation time of TSP

城市数n	回路数 $(n - 1)! 2$	各回路和 $n! 2$	搜索时间
5	12	60	6.00×10^-12 s
10	1.81×10⁵	1.81×10⁶	1.81×10^-7 s
40	1.02×10⁴⁶	4.08×10⁴⁷	1.32×10²⁷ a
100	4.60×10¹⁵⁷	4.60×10¹³⁶	1.48×10¹³⁶ a
200	5.00×10³⁷¹	1.00×10³⁷⁴	3.22×10³⁵⁶ a

Table 1 Calculation amount and calculation time of TSP

城市数n	回路数 $(n - 1)! 2$	各回路和 $n! 2$	搜索时间
5	12	60	6.00×10^-12 s
10	1.81×10⁵	1.81×10⁶	1.81×10^-7 s
40	1.02×10⁴⁶	4.08×10⁴⁷	1.32×10²⁷ a
100	4.60×10¹⁵⁷	4.60×10¹³⁶	1.48×10¹³⁶ a
200	5.00×10³⁷¹	1.00×10³⁷⁴	3.22×10³⁵⁶ a

Fig.2 MTSP route plan

Table 2 Segmentation of optimization goals

优化目标
最小化任务时间
最小化能源消耗
最小化旅行商数目
最小化最高的总成本（距离或时间）

Fig.3 Main features of MTSP

Table 3 Similarities and differences between optimization objectives and solutions under different algorithms

算法	文献	目标	方法
ACO	文献[13]	最小化无人水下航行器总行程	多蚁群系统
	文献[14]	最小化总行程（不区分主体）	最大-最小蚁群
	文献[15]	最小化多机器人巡逻总行程	双目标蚁群优化模因算法
	文献[17]	最小化物流车辆总车程	改进信息素模型
GA	文献[18]	最小化总行程（不区分主体）	两部分染色体编码
	文献[19]		复杂突变树多染色体编码
	文献[20]		序列编码的单亲遗传算法
	文献[21]		带繁殖机制的单亲遗传算法
	文献[22]	平衡快递员配送任务	杂草算法中引入繁殖机制
	文献[23]	最小化总距离（不区分主体）	非支配排序遗传算法
	文献[24]	最小化机器人数量、巡视时间	非支配排序遗传算法
	文献[25]	节省网络能量,提高数据包传输速率	基于平滑路径构建算法
	文献[26]	优化网络中消息传递的加权延迟	在GA中构建集群节点
PSO	文献[27]	最小化机器人总行程、旅行成本	基于帕累托策略的多目标PSO
PSO	文献[30]	平衡多机器人任务分配	动态分布式的PSO
其他	文献[31]	最小化总距离和最大距离最小化	基础ABC
	文献[34]	最小化所有无人机飞行距离总和	禁忌搜索法
	文献[16]	最小化总距离和最大距离最小化	模糊逻辑法
混合算法	文献[35]	优化无人机数量,最小化无人机路程	GA和K-means协同优化
	文献[36]	最小化总行程（不区分主体）	ACO-PGA融合算法
	文献[37]	优化任务分配,全局总代价最低	PSO-AFSA融合算法
	文献[38]	最小化护工总路程,平衡工作时间	ACO与记忆算法混合

Table 4 Classification under different variants of MTSP

变体	优势	适用场景	局限性
人	灵活性和自由度高,受限少	1. 快递员调度问题 2. 不区分场景的MTSP	适用场景局限,在领域上很难有创新型突破
卡车	1. 装载能力强：适用于公路长途运输,可以运输大体积货物,是主流物流运输的传统媒介 2. 自主性强：在救援任务中负责救援人员和应急物资的运送 3. 自动化：代替人工执行农业机械的调度任务	1. 公路运输 2. 救援任务车辆调度 3. 农业自动化车辆调度	有容量和成本的约束,应用场景单一,只能执行传统的地面任务
无人机	1. 成本低：适用于近距离运输和运输小体积物品 2. 机动性强：可以很容易地部署来执行搜索和救援任务或监控给定的区域	1. 空中运输 2. 无人机协同任务规划 3. 自然灾害监测 4. 精准农业中农药喷洒	有能量的约束,具有不可控性,可能面临无人机的损毁、丢失等问题
机器人	1. 效率高：代替人们完成复杂和危险的任务,节省人工成本和时间 2. 一致性：不受外界因素影响,自动化比人工更可靠 3. 配合度高：执行人机协同任务	1. 货物的分拣搬运 2. 搜救和巡逻问题 3. 收集和转发数据 4. 智慧农业中监控与检测	缺乏应急能力,同时还需建立安全措施确保机器人不会伤害人员及其他工作设备

References 59

[1]	RABINER L. Book reviews: combinatorial optimization: algorithms and complexity[J]. IEEE ASSP Magazine, 1984, 1(4): 22. DOI URL
[2]	DANTZIG G B, FULKERSON D R, JOHNSONS M. On a linear-programming, combinatorial approach to the traveling-salesman problem[J]. Operations Research, 1959, 7(1): 58-66. DOI URL
[3]	许玲. 优化穷举法求旅行商问题的近似最优解[J]. 微型机与应用, 1998, 4(10): 20.
	XU L. Approximate optimal solution of traveling salesman problem by optimization exhaustive method[J]. Microcomputer and Application, 1998, 4(10): 20.
[4]	WANG S, LIU M, CHU F. Approximate and exact algorithms for an energy minimization traveling salesman problem[J]. Journal of Cleaner Production, 2020, 249: 119433. DOI URL
[5]	张松灿, 普杰信, 司彦娜. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
	ZHANG S C, PU J X, CI Y N. Adaptive improved ant colony algorithm based on population similarity and its application[J]. Computer Engineering and Application, 2021, 57(8): 70-77.
[6]	陈思远, 林丕源, 黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
	CHEN S Y, LIN P Y, HUANG P J. Pointer network improved genetic algorithm for solving traveling salesmen problem[J]. Computer Engineering and Applications, 2020, 56(19): 231-236.
[7]	YU H, ZHANG K. Optimizing the greedy algorithm used in the TSP abstract problems[J]. Applied Mechanics and Materials, 2014, 3512: 2352-2355.
[8]	王原, 陈名, 邢立宁, 等. 用于求解旅行商问题的深度智慧型蚁群优化算法[J]. 计算机研究与发展, 2021, 58(8): 1586-1598.
	WANG Y, CHEN M, XING L N, et al. Deep intelligent ant colony optimization for solving travelling salesman problem[J]. Computer Research and Development, 2021, 58(8): 1586-1598.
[9]	VESSELINOVA N, STEINERT R, PEREZ-RAMIREZ D F, et al. Learning combinatorial optimization on graphs: a survey with applications to networking[J]. IEEE Access, 2020, 8: 120388-120416. DOI URL
[10]	LI J, ZHOU M C, SUN Q, et al. Colored traveling salesman problem[J]. IEEE Transactions on Cybernetics, 2015, 45(11): 2390. DOI URL
[11]	ALI A I, KENNINGTON J L. The asymmetric M-travelling salesmen problem: a duality based branch-and-bound algori-thm[J]. Discrete Applied Mathematics, 1986, 13(2/3): 259-276. DOI URL
[12]	GAVISH B, SRIKANTH K. An optimal solution method for large-scale multiple traveling salesmen problems[J]. Opera-tions Research, 1986, 34(5): 698-717.
[13]	XU Z Z, LI Y P, FENG X S. Constrained multi-objective task assignment for UUVs using multiple ant colonies system[C]// Proceedings of the 2008 ISECS International Collo-quium on Computing, Communication, Control, and Manage-ment, Guangzhou, Aug 3-4, 2008. Piscataway: IEEE, 2008: 462-466.
[14]	LU L C, YUE T W. Mission-oriented ant-team ACO for min-max MTSP[J]. Applied Soft Computing, 2019, 76: 436-444. DOI URL
[15]	CHEN X, ZHANG P, DU G, et al. Ant colony optimization based memetic algorithm to solve bi-objective multiple trave-ling salesmen problem for multi-robot systems[J]. IEEE Access, 2018, 6: 21745-21757. DOI URL
[16]	TRIGUI S, CHEIKHROUHOU O, KOUBAA A, et al. FL-MTSP: a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems[J]. Soft Computing, 2017, 21(24): 7351-7362. DOI URL
[17]	WANG M, MA T M, LI G L, et al. Ant colony optimization with an improved pheromone model for solving MTSP with capacity and time window constraint[J]. IEEE Access, 2020, 8: 106872-106879. DOI URL
[18]	YUAN S, SKINNER B, HUANG S D, et al. A new cross-over approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European Journal of Operational Research, 2013, 228(1): 72-82. DOI URL
[19]	叶多福, 刘刚, 何兵. 一种多染色体遗传算法解决多旅行商问题[J]. 系统仿真学报, 2019, 31(1): 36-42. DOI
	YE D F, LIU G, HE B. Multi-chromosome genetic algori-thm for multiple traveling salesman problem[J]. Journal of System Simulation, 2019, 31(1): 36-42.
[20]	ZHOU H L, SONG M L, PEDRYCZ W. A comparative study of improved GA and PSO in solving multiple traveling sale-smen problem[J]. Applied Soft Computing, 2018, 64: 564-580. DOI URL
[21]	WANG Z J, FANG X, LI H, et al. An improved partheno-genetic algorithm with reproduction mechanism for the mul-tiple traveling salesperson problem[J]. IEEE Access, 2020, 8: 102607-102615. DOI URL
[22]	胡士娟, 鲁海燕, 黄洋, 等. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
	HU S J, LU H Y, HUANG Y, et al. Improved genetic algorithm for solving multiple traveling salesman problem with balanced workload[J]. Computer Engineering and Appli-cations, 2019, 55(17): 150-155.
[23]	BOLAÑOS R I, ECHEVERRY M G, ESCOBAR J W. A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the multiple traveling salesman problem[J]. Decision Science Letters, 1924, 4(4): 559-568. DOI URL
[24]	KHOUFI I, HADDED M, MINET P, et al. Optimized trajec-tories of multi-robot deploying wireless sensor nodes[C]// Proceedings of the 11th IEEE International Conference on Wireless and Mobile Computing, Networking and Communi-cations, Abu Dhabi, Oct 19-21, 2015. Washington: IEEE Computer Society, 2015: 724-731.
[25]	WICHMANN A, KORKMAZ T. Smooth path construction and adjustment for multiple mobile sinks in wireless sensor networks[J]. Computer Communications, 2015, 72: 93-106. DOI URL
[26]	HAROUNABADI M, BOCKSBERGER M, MITSCHELE-THIEL A. Evolutionary path planning for multiple UAVs in message ferry networks applying genetic algorithm[C]// Pro-ceedings of the 29th IEEE Annual International Symposium on Personal, Indoor and Mobile Radio Communications, Bolog-na, Sep 9-12, 2018. Piscataway: IEEE, 2018: 1-7.
[27]	WEI C Y, JI Z, CAI B L. Particle swarm optimization for cooperative multi-robot task allocation: a multi-objective approach[J]. IEEE Robotics and Automation Letters, 2020, 5(2): 2530-2537. DOI URL
[28]	KIM M, HIROYASU T, MIKI M, et al. SPEA2+: improving the performance of the strength Pareto evolutionary algorithm 2[C]// LNCS 3242:Proceedings of the 8th International Con-ference, Birmingham, Sep 18-22, 2004. Berlin, Heidelberg:Springer, 2004: 742-751.
[29]	DEB K, AGARWAL S, PRATAP A, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transac-tions on Evolutionary Computation, 2002, 6(2): 182-197.
[30]	AYARI A, BOUAMAMA S. PSO-based dynamic distributed algorithm for automatic task clustering in a robotic swarm[J]. Procedia Computer Science, 2019, 159: 1103-1112. DOI URL
[31]	VENKATESH P, SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing Journal, 2015, 26: 74-89. DOI URL
[32]	PANDIRI V, SINGH A. A swarm intelligence approach for the colored traveling salesman problem[J]. Applied Intelligence, 2018, 48(11): 4412-4428. DOI URL
[33]	DONG X, LIN Q, XU M, et al. A.pngicial bee colony algori-thm with generating neighbourhood solution for large scale coloured traveling salesman problem[J]. IET Intelligent Tran-sport Systems, 2019, 13(10): 1483-1491.
[34]	VENKATACHALAM S, SUNDAR K, RATHINAM S. A two-stage approach for routing multiple unmanned aerial vehicles with stochastic fuel consumption[J]. Sensors, 2018, 18(11): 3756. DOI URL
[35]	JIANG C, WAN Z, PENG Z. A new efficient hybrid algorithm for large scale multiple traveling salesman problems[J]. Expert Systems with Applications, 2020, 139: 112867. DOI URL
[36]	MA Y H, ZHANG H, ZHANG Y Z, et al. Coordinated optimization algorithm combining GA with cluster for multi-UAVs to multi-tasks task assignment and path planning[C]// Proceedings of the 15th IEEE International Conference on Control and Automation, Edinburgh, Jul 16-19, 2019. Pisca-taway: IEEE, 2019: 1026-1031.
[37]	张富震, 朱耀琴. 复杂环境中多无人机协同侦察的任务分配方法[J]. 系统仿真学报, 2022. DOI: 10.16182/j.issn-1004731x.joss.21-0552. DOI
	ZHANG F Z, ZHU Y Q. Task allocation method of multi- UAV cooperative reconnaissance in complex environment[J]. Journal of System Simulation, 2022. DOI: 10.16182/j.issn1004731x.joss.21-0552. DOI
[38]	DECERLE J, GRUNDER O, HASSANI A H E, et al. A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchroni-zation and working time balancing[J]. Swarm and Evolu-tionary Computation, 2019, 46: 171-183.
[39]	REHMAN K S A. The drivers and barriers of green supply chain management: in the context of manufacturing firms of Pakistan[D]. Xi’an: Chang’an University, 2018.
[40]	袁雨果. 多快递员的电商物流“最后一公里”配送研究[J]. 怀化学院学报, 2017, 36(7): 39-44.
	YUAN Y G. Study on last mile delivery of multi-couriers e-logistics[J]. Journal of Huaihua University, 2017, 36(7): 39-44.
[41]	SHI Y, YANG Z F, YAN H, et al. Delivery efficiency and supplier performance evaluation in China’s E-retailing indus-try[J]. Journal of Systems Science and Complexity, 2017, 30(2): 392-410. DOI URL
[42]	潘成浩, 郭敏. 仓储物流机器人批量拣选路径规划仿真[J]. 计算机与现代化, 2017(2): 12-16.
	PAN C H, GUO M. Batch picking path planning simulation of warehouse mobile robot[J]. Computer and Modernization, 2017(2): 12-16.
[43]	MURRAY C C, RAJ R. The multiple flying sidekicks trave-ling salesman problem: parcel delivery with multiple drones[J]. Transportation Research Part C: Emerging Technologies, 2020, 110: 368-398. DOI URL
[44]	KITJACHAROENCHAI P, VENTRESCA M, MOSHREF-JAVADI M, et al. Multiple traveling salesman problem with drones: mathematical model and heuristic approach[J]. Com-puters & Industrial Engineering, 2019, 129: 14-30.
[45]	刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例[J]. 系统管理学报, 2014, 23(2): 247-254.
	LIU M, ZHANG P Y. A new hybrid genetic algorithm for solving multi traveling salesman problem: taking emergency material distribution as an example[J]. Journal of System Management, 2014, 23(2): 247-254.
[46]	姚书婷, 胡志华, 魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
	YAO S T, HU Z H, WEI C. Distribution recovery from multiple forbidding time windows at customers[J]. Computer Engineering and Applications, 2019, 55(12): 265-270.
[47]	CHEN C H, LEE Y C, CHEN A Y. A building information model enabled multiple traveling salesman problem for buil-ding interior patrols[J]. Advanced Engineering Informatics, 2021, 47: 101237. DOI URL
[48]	陈昕叶. 动态环境下多机器人协同搜救任务分配方法研究[D]. 广州: 华南理工大学, 2020.
	CHEN X Y. Research on task allocation method of multirobot cooperative search and rescue in dynamic environment[D]. Guangzhou: South China University of Technology, 2020.
[49]	HAYAT S, YANMAZ E, BROWN T X, et al. Multi-objective UAV path planning for search and rescue[C]// Proceedings of the 2017 IEEE International Conference on Robotics and Automation, Singapore, May 29-Jun 3, 2017. Piscataway:IEEE, 2017: 5569-5574.
[50]	ZHU Z W, GUO X, DIAO X M. Research on path planning of WSN mobile sink using hybrid immune particle swarm optimization[J]. Microelectronics & Computer, 2018, 35(5): 89-94.
[51]	HUANG H L, SAVKIN A V. Viable path planning for data collection robots in a sensing field with obstacles[J]. Computer Communications, 2017, 111: 84-96. DOI URL
[52]	WEI Z, XIA C, YUAN X, et al. The path planning scheme for joint charging and data collection in WRSNs: a multi-objective optimization method[J]. Journal of Network and Computer Applications, 2020, 156: 102565. DOI URL
[53]	徐国训, 梁晓龙, 张佳强, 等. 航空集群多目标群攻击路径规划仿真研究[J]. 计算机仿真, 2017, 34(6): 66-70.
	XU G X, LIANG X L, ZHANG J Q, et al. Simulation research on path planning of aircraft swarms attacking multi-target group[J]. Computer Simulation, 2017, 34(6): 66-70.
[54]	ZHU X N, ZHU X P, YAN R, et al. Optimal routing, aborting and hitting strategies of UAVs executing hitting the targets considering the defense range of targets[J]. Reliability Engin-eering & System Safety, 2021, 215: 107811.
[55]	CAO Y, WEI W Y, BAI Y, et al. Multi-base multi-UAV co-operative reconnaissance path planning with genetic algori-thm[J]. Cluster Computing, 2019, 22: 5175-5184. DOI URL
[56]	MERNOUT B, MARCO H, TAMÁS K. Complete field coverage as a multi-vehicle routing problem[J]. IFAC Pro-ceedings Volumes, 2013, 46(18): 97-102.
[57]	SRIKAKULAPU R, VINATHA U. Optimized design of collector topology for offshore wind farm based on ant colony op-timization with multiple travelling salesman problem[J]. Jour-nal of Modern Power Systems and Clean Energy, 2018, 6: 1181-1192.
[58]	李涛, 邱权, 赵春江, 等. 矮化密植果园多臂采摘机器人任务规划[J]. 农业工程学报, 2021, 37(2): 1-10.
	LI T, QIU Q, ZHAO C J, et al. Task planning of multi-arm harvesting robots for high-density dwarf orchards[J]. Tran-sactions of the Chinese Society of Agricultural Engineering, 2021, 37(2): 1-10.
[59]	LI X M, MA Z Y, CHU X, et al. A cloud-assisted region monitoring strategy of mobile robot in smart greenhouse[J]. Mobile Information Systems, 2019(1): 1-10.