文件名称：用节点和细分覆盖Salesman问题
文件大小：1.68MB
文件格式：PDF
更新时间：2023-06-24 14:04:03
推销员问题 用节点和细分覆盖Salesman问题 组合优化问题 本地搜寻方式
在Covering Salesman Problem（CSP）中，提供了节点的分布，目的是识别所有给定节点的子集的最短行程，以使每个节点不在半径r范围内的行程中。游览中的任何节点。 在本文中，我们定义了一个新的覆盖问题，称为带有节点和段的CSP（CSPNS）。 CSPNS和CSPNS之间的主要区别在于，在CSPNS中，不仅巡回路线上的节点，而且巡回路线上的路段也可以覆盖不在巡回路线上的节点。 我们通过整数编程制定了CSPNS，并通过使用通用混合整数程序求解器找到了最佳解决方案。 CSPNS的基准实例是由DIMACS生成的，它是“旅行推销员问题”的基准问题之一。 对于大型实例，无法在合理的时间范围内获得最佳解决方案。 因此，在这项研究中，我们开发了一种简单的启发式方法来找到CSPNS的良好近似最优解。 所提出的启发式方法很快找到了很好的解决方案。