有点扭曲的 TSP

TSP with a twist

我遇到了一个与旅行商问题非常相似的问题，只是有一些不同之处：

当然，这个问题是 NP 完全问题，因为这是 TSP 的一个变体，但我想知道是否有任何算法是为常规 TSP 设计的，可以很容易地修改以适应这个特定的问题有问题吗？

听起来您所描述的是 图形化的非对称 TSP。要分解您描述的约束条件，

3是非对称TSP（ATSP），即有向图上的TSP。这比一般的 TSP 难得多，但它是一个经过充分研究的问题。在我的脑海中，Lin-Kernighan-Helsgaun (LKH) 启发式算法是一种 TSP 启发式算法，它在 ATSP 上也表现出色，我相信还有其他的。

1 是图形化的TSP，即可以多次访问节点的TSP。我不会确切地称这个问题得到充分研究。有很多关于它的工作，但其中大部分是在可以为标准 TSP 挖掘的结果的背景下进行的。

约束 2 让我很困惑，但我认为这是一个转移注意力的问题，因为图形 TSP 已经暗示了它。考虑图形 TSP 的另一种方法是，您需要原始图的连通子图，其中每个节点的度数至少为二，而在 TSP 中，度数等于二。因此，我们只承担一次访问边缘的成本。

因此，将此与您的问题联系起来！如果我必须使用 TSP 方法中的 "easily modified" 算法，我会：

-使用 LKH 计算起始 ATSP 巡回，因为这样的巡回对于您的问题是可行的，所以它提供了一个上限。

-在商业整数规划求解器（如 CPLEX 或 Gurobi）中编写图形 ATSP 的公式。我会为 ATSP 使用 Held-Karp 松弛，并更改度方程以允许多次访问给定城市。

-为 IP 求解器编写回调以添加连接约束，如果它 returns 是断开连接的解决方案。

-将 LKH 游览作为暖 start/numerical 上限传递给 IP 求解器。

然后祝一切顺利！基本上，这将是基于切割平面的 TSP 求解器的简化版本，适用于您的问题。我不会指望它来解决大规模实例，但我认为这将是一次值得尊敬的尝试。