routing - 车辆路线的线性规划

Question

车辆路线问题的线性规划需要帮助。在车辆路径问题 (VRP) 中，车辆将服务于一组节点，从而使总行驶成本最小化。如果在节点 i 之后访问节点 j，我的决策变量是：Xij=1。参数 dij 是节点 i 和 j 之间的距离。所以，模型如下：

请注意，车辆从仓库（节点号 0）开始旅行，最后返回仓库（约束 11 和 12）。应该访问所有节点（约束 13），当进入一个节点时，它应该离开那个节点（约束 14）。但是，当我在 cplex 中为大量节点解决这个问题时，有时解决方案是无效的，因为像这样的循环：

在此解决方案的情况下，所有约束都得到满足，但此解决方案无效，因为路径未连接。现在，我的问题是我应该添加什么约束来完成模型。

Answer 1

正如@Erwin 提到的，您需要添加子旅游消除约束。简要地：

1. 解决这个问题。
2. 分析解决方案。如果没有 subtours，则解决方案是最佳的。否则，对原始问题的子路径添加约束（在您的示例中，x_01+x_12+x_20 <= 2 和 x_34+x_45+x_53 <= 2）。转到 1。

Answer 2

尽管这个问题很老，但@alex 答案中有一个重要的细节需要强调。他的链接中的 subtour 消除 (SE)是通过惰性约束回调动态实现的。记住这一点很重要，因为在更大的示例中，创建所有 SE 约束可能是不可能的，最好懒惰地评估它们。

Answer 3

谢谢你的回答。我发现用于消除子巡演的 Tucker 公式效果很好。

Ui-Uj+nXij<=n-1.

Answer 4

在CPLEX_Studio128\opl\examples\opl\models\TravelingSalesmanProblem 您可以找到您需要的一个小示例，即 subtour 消除。