足够接近的旅行商问题研究综述

来源：吉林大学学报·理学版杂志2025年第1期北京时间：

作者：史丰源, 欧阳丹彤, 张立明

单位：1. 吉林大学 计算机科学与技术学院, 长春 130012；2. 吉林大学 符号计算与知识工程教育部重点实验室, 长春 130012

摘要：考虑组合优化问题中的经典问题旅行商问题(traveling salesman problem, TSP)的变体——足够接近的旅行商问题(close-enough traveling salesman problem, CETSP). 首先, 综合介绍TSP和CETSP的历史、 求解方法和算法, 包括精确算法（如分支定界法、 线性规划）和启发式算法（如粒子群优化、 贪心算法等）.TSP要求在给定城市列表和距离的条件下, 找到访问每座城市一次并回到起点的最短路径. CETSP是TSP的推广, 允许在每个目标的邻域内选择任意点进行访问, 而非精确位置, 适用于可容忍误差的实际应用, 如物流配送、 智能交通、 无线传感器网络等. CETSP具有更高的灵活性和适应性, 可大幅度减少计算资源和时间消耗, 特别在大规模问题中有更大优势. 其次, 介绍CETSP在实际应用中的潜力, 尤其在物流、 工业制造、 交通规划、 信息通讯等领域, 为提高效率、 降低成本、 推动智能化决策提供了有效解决方案. 最后, 指出了CETSP的一些未来研究方向.

关键词：足够接近的旅行商问题,启发式算法,路径规划,模型应用