1

我正在尝试在 Cplex/OPL 中运行此模型，以找到给定商店距离的最佳路径，以及每个商店中不同产品的数量+价格。问题是我得到了脱节路径的结果 - “岛屿”。我需要添加什么约束才能只获得一个在节点 1 开始和结束的封闭路径？这是模型：

 dvar float+ x[products,stores];
 dvar boolean y[stores,stores];


 minimize ((sum(i in products, j in stores) prices[i,j]*x[i,j]) + (sum(j in stores, k     
 in stores) gas*distance[j,k]*y[j,k]));

  subject to {
    sum(k in stores) y[1,k] == 1;
    sum(j in stores) y[j,1] == 1;
    forall(j in stores) 
        sum(i in products) x[i,j] <= M*sum(k in stores) y[j,k];
    forall(j in stores)
        sum(i in products) x[i,j] <= M*sum(k in stores) y[k,j];
    forall(i in products) sum(j in stores) x[i,j] == demand[i];
    forall(i in products, j in stores) x[i,j] <= quantity[i,j];
    forall(j in stores, k in stores) y[j,k] + y[k,j] <= 1;
    forall(j in stores) sum(k in stores) y[j,k] == sum(k in stores) y[k,j];

}

谢谢！

4

1 回答 1

3

您要解决的是旅行商问题的变体。具体来说，您所得到的称为subtours，这是一条封闭路径，涉及的节点少于所有节点（在您的情况下为商店。）

对于给定的一组节点，有指数数量的子路径。围绕子旅游消除约束存在大量文献。幸运的是，对于实践中的小问题，我们可以根据需要添加 subtour 消除约束。

次旅游消除

以下是如何消除涉及s个商店 (s < num_stores)的子旅游S的想法：

In Chinese：我们首先将节点（商店）的集合划分为两组 S 和 T。让 S 是 subtour 中的商店集合。令 T为 S之外的商店集合，即所有其他商店。我们想打破只涉及 S 中商店的单循环路径。

伪代码

Do while:
    Solve the current problem 
    If you don't find any subtours, you are done. Exit.
    If there are subtours, add the subtour elimination constraints (see details below)
    Continue

实施一组约束以消除当前的子旅游

对于每个 subtour（“岛”），您必须首先创建一组shops_in_subtour. 所有其他节点（商店）进入另一个集合（T）shops_not_in_subtour

将以下内容添加到您的约束集中：

forall(s in shops_in_subtour)
  forall(t in shops_not_in_subtour)
    sum y[s,t] > = 1; // at least one edge must leave S and go to T
    sum y[t,s] > = 1; // at least one edge must enter the set S from T

如果您的问题很小，您会发现添加一些这样的约束集就足够了。希望能帮助你前进。

根据OP的后续问题更新

如何检测 Subtours

您将检查是否存在CPLEX/Solver之外的子游览

英文理念：您从原点商店开始，遍历路径，跟踪每个visited商店。如果你回到原点，仍然有一些二进制 Y 变量，你有一个或多个子旅游。（从技术上讲，您可以从任何商店开始，但从一个商店开始更容易理解。）

Initialize visited_shop = NULL; 
Find the Yij that is 1. (Starting edge for the path)
Do while (There are more Y variables = 1 remaining)
  Add the destination of the new binary variable to list of visited_shops
  Check if you are done (are you back at shop 1):
    if Yes: 
       If no more binary variables left, you are done. Exit.
       If there are some more non-zero binary variables, subtour detected
    if No: 
       pick the next Y variable whose origin is current Y_variable's destination
  Continue
于 2013-12-25T22:34:21.503 回答