摘要
多旅行商问题(MTSP)作为经典旅行商问题(TSP)的一种泛化,是著名的组合优化问题之一。但多旅行商问题作为经典NP-hard问题,其问题规模以及运算复杂度都对求解方法有着极高的要求。重点关注多旅行商问题,首先对MTSP模型的几种特征、目标函数、问题约束以及变体进行了细分。其次对目前常见的几种启发式算法在求解MTSP上的具体方法进行了归类与整理,同时比较了在不同算法下优化目标与解决方法的相同之处与不同之处,以便于更直观理解不同算法间解决多旅行商问题的一般方法。随着多旅行商问题的不断发展,学者们已不满足于单纯解决数学问题,开始尝试将许多符合条件的实际问题看作多旅行商问题。归纳了在物流配送、无线传感网、应急救援和无人机协同任务规划等实际应用背景下MTSP模型的具体构建方式,从应用成果来看,利用MTSP模型解决实际问题不仅可以降低企业和个人成本,提升收益,还可以推动该领域向着更高效智能的方向发展。主要针对多旅行商模型及其应用展开了研究,填补了这一研究领域的空白。
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.
作者
张硕航
郭改枝
ZHANG Shuohang;GUO Gaizhi(School of Computer Science and Technology,Inner Mongolia Normal University,Hohhot 010022,China)
出处
《计算机科学与探索》
CSCD
北大核心
2022年第7期1516-1528,共13页
Journal of Frontiers of Computer Science and Technology
基金
内蒙古自然科学基金(2020MS06029,2021LHMS06013,2020LH06009)
内蒙古自治区科技计划项目(2020GG0165)
内蒙古高等学校科学研究项目(NJZY21553)。
关键词
多旅行商
路径规划
启发式算法
模型应用
multiple traveling salesman
path planning
heuristic algorithms
model application
