routes - 车辆路径的线性规划

Question

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

请注意，车辆从仓库(节点号 0)开始巡游，最后返回仓库(约束 11 和 12)。所有的节点都应该被访问(约束13)，并且当进入一个节点时，它应该离开该节点(约束14)。 但是，当我在 cplex 中针对大量节点解决这个问题时，有时该解决方案会因为像这样的循环而无效:

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

Answer 1

正如@Erwin提到的，您需要添加子路线消除约束。简而言之:

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