计算机科学与探索

作者：张硕航, 郭改枝

单位：内蒙古师范大学 计算机科学技术学院,呼和浩特 010022

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

基金：内蒙古自然科学基金(2020MS06029);内蒙古自然科学基金(2021LHMS06013);内蒙古自然科学基金(2020LH06009);内蒙古自治区科技计划项目(2020GG0165);内蒙古高等学校科学研究项目(NJZY21553)

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

来源：2022年第7期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2022年第7期