车辆路径的线性规划
Linear programming of vehicle routing
需要有关车辆路径问题线性规划的帮助。
在车辆路径问题 (VRP) 中，车辆将服务于一组节点，以使总行驶成本最小化。
如果在节点 i 之后访问节点 j，我的决策变量 is:Xij=1。
参数 dij 是节点 i 和 j 之间的距离。所以，模型如下：
请注意，车辆从仓库（节点号 0）开始游览，最后 returns 到仓库（约束 11 和 12）。应该访问所有节点（约束 13），并且当进入一个节点时，它应该离开该节点（约束 14）。
但是，当我在 cplex 中为大量节点解决这个问题时，有时解决方案会因为这样的循环而无效：
在这个解决方案的情况下，所有的约束都得到满足，但是这个解决方案是无效的，因为路由没有连接。
现在，我的问题是我应该添加什么约束来完成模型。
如@Erwin 所述，您需要添加 subtour 消除约束。简要地说：
- 解决问题。
- 分析解决方案。如果没有子路线，则解决方案是最佳的。否则，在您对原始问题的子旅行中添加约束（在您的示例中，x_01+x_12+x_20 <= 2 和 x_34+x_45+x_53 <= 2).转到 1.
在CPLEX_Studio128\opl\examples\opl\models\TravelingSalesmanProblem
你可以找到一个你需要的小例子，这是subtour elimination。
感谢您的回答。我发现 Tucker 公式消除亚巡赛效果很好。
Ui-Uj+nXij<=n-1.
虽然这个问题很老了，但@alex 的回答中有一个重要的细节需要强调一下。他的 link 中的 subtour elimination (SE) 是通过惰性约束回调动态实现的。记住这一点很重要，因为在更大的例子中，创建所有 SE 约束可能是不可能的，最好懒惰地评估它们。
需要有关车辆路径问题线性规划的帮助。 在车辆路径问题 (VRP) 中，车辆将服务于一组节点，以使总行驶成本最小化。 如果在节点 i 之后访问节点 j，我的决策变量 is:Xij=1。 参数 dij 是节点 i 和 j 之间的距离。所以，模型如下：
请注意，车辆从仓库（节点号 0）开始游览，最后 returns 到仓库（约束 11 和 12）。应该访问所有节点（约束 13），并且当进入一个节点时，它应该离开该节点（约束 14）。 但是，当我在 cplex 中为大量节点解决这个问题时，有时解决方案会因为这样的循环而无效：
在这个解决方案的情况下，所有的约束都得到满足，但是这个解决方案是无效的，因为路由没有连接。 现在，我的问题是我应该添加什么约束来完成模型。
如@Erwin 所述，您需要添加 subtour 消除约束。简要地说：
- 解决问题。
- 分析解决方案。如果没有子路线，则解决方案是最佳的。否则，在您对原始问题的子旅行中添加约束（在您的示例中，x_01+x_12+x_20 <= 2 和 x_34+x_45+x_53 <= 2).转到 1.
在CPLEX_Studio128\opl\examples\opl\models\TravelingSalesmanProblem
你可以找到一个你需要的小例子，这是subtour elimination。
感谢您的回答。我发现 Tucker 公式消除亚巡赛效果很好。
Ui-Uj+nXij<=n-1.
虽然这个问题很老了，但@alex 的回答中有一个重要的细节需要强调一下。他的 link 中的 subtour elimination (SE) 是通过惰性约束回调动态实现的。记住这一点很重要，因为在更大的例子中，创建所有 SE 约束可能是不可能的，最好懒惰地评估它们。