公平旅行商问题的精确算法-研究论文

给定一个加权图 G = (V, E)，公平旅行商问题 (ETSP) 要求 G 中的两个完美匹配，使得 (1) 这两个匹配一起形成 G 中的哈密顿循环和 (2) 的绝对差两个匹配之间的成本被最小化。 该问题被证明是 NP-Hard 问题，即使图 G 是完整的。 我们提出了两个整数规划模型来解决 ETSP 问题。 一个模型是通过分支定界和切割来解决的，而另一个模型是通过分支和价格和切割框架来解决的。 还实现了一个简单的本地搜索启发式。 我们对不同类型的实例进行计算实验，这些实例通常来自 TSPLib。 事实证明，不同方法的行为因实例类型而异； 然而，在 Cplex 中实施的分支定界和切割方法似乎总体上效果最好。