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

摘要

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

关键词

足够接近的旅行商问题 / 启发式算法 / 路径规划 / 模型应用

基金资助

国家自然科学基金(批准号：62076108;61872159;61672261)