一种基于空间信息的旅行商问题求解方法

《The Professional Geographer》：A Spatially Informed Solving Approach for the Traveling Salesman Problem

该研究针对旅行商问题（TSP）计算复杂度高的问题，提出空间信息整合的SI-TSP方法，结合骨骼Voronoi多边形与混合整数规划，利用邻近区域空间信息区分决策变量，有效缩减问题规模并保持最优解质量，数值实验验证其有效性。

　　

摘要

旅行商问题（TSP）是一个组合优化问题，旨在确定一条能够使旅行成本最小化的最优路径，这些节点来自给定的集合。由于解决TSP问题本质上需要进行穷举搜索，即检查所有可能的路径以找到最优解，因此计算难度较大，尤其是当问题规模增大时。如何在保证最优性的同时使问题在大规模情况下仍具有可解性是一个关键问题，这也是许多启发式方法在处理TSP时的核心关注点。尽管已经做出了各种努力来提高计算性能，但很少有研究探索将空间信息纳入其中，以系统地减小问题规模同时保持解决方案的质量。为了解决这个问题，本研究提出了一种基于空间信息的有效方法，称为SI-TSP，该方法将骨架Voronoi多边形方法融入到混合整数规划框架中。SI-TSP利用从给定节点的邻近区域提取的关键空间信息，来区分在确定最优路径过程中重要的和非重要的决策变量。数值实验表明，SI-TSP是一种有效且有前景的方法，可以应用于类似的网络路由问题，尤其是在寻找最优解是主要目标的情况下。