公平旅行商问题精确算法：整数规划与启发式方法

"这篇研究论文探讨了公平旅行商问题（ETSP）的精确算法，这是一种在加权图中寻找两个完美匹配，同时满足形成哈密顿循环和最小化匹配成本差的优化问题。该问题被证明是NP-Hard，即使在完全图中也难以解决。作者提出了两种整数规划模型，分别采用分支定界和切割以及分支和价格及切割框架来求解。此外，还实现了一个简单的局部搜索启发式方法，并在TSPLib实例上进行了实验，以比较不同方法的性能。实验结果显示，Cplex中的分支定界和切割方法在大多数情况下表现最佳。" 在这篇论文中，公平旅行商问题（ETSP）是主要关注的焦点。这是一个在图论和组合优化中的复杂问题，它扩展了经典的旅行商问题（TSP）。在ETSP中，不仅要找到一条遍历所有节点的哈密顿循环，还要确保这个循环是由两个完美匹配组成的，且这两个匹配的成本差异最小化。完美匹配是指图中每个节点都被一条边恰好连接一次，使得所有节点都被匹配。 论文首先指出了ETSP的NP-Hard性质，这意味着在多项式时间内找到最优解是极其困难的，尤其是在图是完全的情况下。为了解决这个问题，作者提出了两种整数规划模型。第一种是基于分支定界和切割的模型，这种技术通过系统地分割问题空间并添加切割平面来减少搜索空间，从而逼近最优解。第二种模型则采用了分支和价格及切割框架，这种方法结合了分支定界与网络流问题的定价过程，以更有效地探索解空间。 此外，为了进一步处理ETSP，作者实现了一个局部搜索启发式算法。这种算法通常从一个初始解出发，通过小步迭代改进解的质量，但可能无法保证全局最优。在实验部分，研究人员使用了各种源自TSPLib的实例，这是一个广泛使用的TSP和相关问题的测试集合。实验结果表明，尽管不同的方法在不同类型的实例中表现各异，但Cplex中的分支定界和切割策略总体上提供了最有效的解决方案。 这篇论文的研究成果对于理解并解决公平旅行商问题具有重要的理论和实践价值，特别是在图优化和组合优化领域。通过提供精确算法和实验结果，它为未来的研究提供了基础，并可能启发新的求解策略或算法设计。