计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (7): 1516-1528.DOI: 10.3778/j.issn.1673-9418.2112006

• 综述·探索 • 上一篇    下一篇

多旅行商模型及其应用研究综述

张硕航, 郭改枝+()   

  1. 内蒙古师范大学 计算机科学技术学院,呼和浩特 010022
  • 收稿日期:2021-12-01 修回日期:2022-01-24 出版日期:2022-07-01 发布日期:2022-07-25
  • 作者简介:张硕航(1996—),女,内蒙古赤峰人,硕士研究生,主要研究方向为数据处理。
    ZHANG Shuohang, born in 1996, M.S. candidate. Her research interest is data processing.
    郭改枝(1968—),女,内蒙古呼和浩特人,硕士,教授,硕士生导师,主要研究方向为信息和数据处理等。
    GUO Gaizhi, born in 1968, M.S., professor, M.S. supervisor. Her research interests include information and data processing, etc.
  • 基金资助:
    内蒙古自然科学基金(2020MS06029);内蒙古自然科学基金(2021LHMS06013);内蒙古自然科学基金(2020LH06009);内蒙古自治区科技计划项目(2020GG0165);内蒙古高等学校科学研究项目(NJZY21553)

Review of Multiple Traveling Salesman Model and Its Application

ZHANG Shuohang, GUO Gaizhi+()   

  1. School of Computer Science and Technology, Inner Mongolia Normal University, Hohhot 010022, China
  • Received:2021-12-01 Revised:2022-01-24 Online:2022-07-01 Published:2022-07-25
  • Supported by:
    the Natural Science Foundation of Inner Mongolia(2020MS06029);the Natural Science Foundation of Inner Mongolia(2021LHMS06013);the Natural Science Foundation of Inner Mongolia(2020LH06009);the Science and Technology Plan Project of Inner Mongolia Autonomous Region(2020GG0165);the Scie.pngic Research Project of Inner Mongolia Higher Education(NJZY21553)

摘要:

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

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

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

中图分类号: