PVRP中AMPL中次目标消除约束的动态生成

Question

我试图在AMPL中编写一个带有库存约束的周期性车辆路径问题。我想动态添加subour约束。为了做到这一点，我受到了TSP公式的启发：

https://groups.google.com/d/msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ

然而，我无法在我的模型中消除副标题。我在模型文件中使用了以下内容。

param T;            # Number of time-periods
param V;            # Number of vehicles
param F;            # Number of fuel types

set P ordered;      # Number of gas stations
param hpos {P} >= 0;
param vpos {P} >= 0;

set PAIRS := {p in P, j in P};

param dist {(p,j) in PAIRS}
    := sqrt((hpos[j]-hpos[p])**2 + (vpos[j]-vpos[p])**2);

# A binary variable to determine if an arc is traversed.

    var H{(p,j) in PAIRS, v in 1..V, t in 1..T} binary;

# A binary variable to determine if a delivery of fuel is made to a station in a given time period.

     var StationUsed{p in P, f in 1..F, v in 1..V, t in 1..T} binary;

minimize TransportationCost: 
    sum {(p,j) in PAIRS} sum {v in 1..V, t in 1..T} dist[p,j] * H[p,j,v,t];

param nSubtours >= 0 integer;
set SUB {1..nSubtours} within P;
subject to Subtour_Elimination {k in 1..nSubtours, m in SUB[k], v in 1..V, t in 1..T, f in 1..F}:
    sum {p in SUB[k], j in P diff SUB[k]} 
    if (p,j) in PAIRS then H[p,j,v,t] else H[j,p,v,t]  >=2 * StationUsed[m,f,v,t] ;

我添加了StationUsed变量，因为我的问题与TSP不同，不必在每个时间段访问所有节点。H是我的二元决策变量，用于声明车辆是否在一段时间内通过圆弧（p，j）。

然后我在运行文件中使用了一个类似于TSP的公式：

     set NEWSUB;
     set EXTEND;
     let nSubtours := 0;

     repeat {
     solve;

     let NEWSUB := {};
     let EXTEND := {member(ceil(Uniform(0,card(P))),P)};

     repeat {
     let NEWSUB := NEWSUB union EXTEND;
     let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in 1..V, t in 1..T}
        ((p,j) in PAIRS and H[p,j,v,t] = 1 or (j,p) in PAIRS and H[j,p,v,t] = 1)};
     } until card(EXTEND) = 0;

     if card(NEWSUB) < card(P) then {
     let nSubtours := nSubtours + 1;
     let SUB[nSubtours] := NEWSUB;
     display SUB;
     } else break;
     };

# Display the routes
display {t in 1..T, v in 1..V}: {(p,j) in PAIRS} H[p,j,v,t];

我不确定上述内容是否适用于我的多辆车和多个时间段的问题。我曾尝试在let EXTEND中定义v和t，因为需要使用H，但我不确定这是否是正确的方法。我的模型运行时，如上面所述，但它并没有消除子目标。在这方面你们有什么建议吗？

补充问题：

我在SAS/OR中制定的模型中找到了一些灵感：（阅读范围有点广，我的问题不需要）

http://support.sas.com/documentation/cdl/en/ormpex/67518/HTML/default/viewer.htm#ormpex_ex23_sect009.htm

它可以在d天内动态消除子任务，我认为这可以转化为我的多辆车和多个时段（天）的问题。

详细说明一下我的问题。一个节点在一个时间段内只能被一辆车访问一次。不必在每个时间段访问所有节点，这与TSP公式的主要区别在于，TSP公式中的所有节点都在循环中。

我尝试了以下方法：

模型文件中的约束与之前相同。

set P ordered;  # Number of nodes
set PAIRS := {p in P, j in P: ord(p) != ord(j)};

param nSubtours >= 0 integer;
param iter >= 0 integer;
set SUB {1..nSubtours} within P;

subject to Subtour_Elimination {s in 1..nSubtours, k in SUB[s], f in F, v in V, t in T}:
sum {p in SUB[s], j in P diff SUB[s]} 
      if (p,j) in PAIRS then H[p,j,v,t] else H[j,p,v,t]  >= 2 * StationUsed[k,f,v,t];

我的跑步文件如下所示：

let nSubtours := 0;
let iter := 0;
param num_components {V, T};
set P_TEMP;
set PAIRS_SOL {1..iter, V, T} within PAIRS;
param component_id {P_TEMP};
set COMPONENT_IDS;
set COMPONENT {COMPONENT_IDS};
param cp;
param cj;

# loop until each day and each vehicles support graph is connected

repeat {
    let iter := iter + 1;

    solve;
    # Find connected components for each day

    for {v in V, t in T} {
        let P_TEMP := {p in P: exists {f in F} StationUsed[p,f,v,t] > 0.5};
        let PAIRS_SOL[iter, v, t] := {(p,j) in PAIRS: H[p, j, v, t] > 0.5};

        # Set each node to its own component

        let COMPONENT_IDS := P_TEMP;
        let num_components[v, t] := card(P_TEMP);
            for {p in P_TEMP} {
                let component_id[p] := p;
                let COMPONENT[p] := {p};
            };

        # If p and j are in different components, merge the two component

        for {(p,j) in PAIRS_SOL[iter, v, t]} {
            let cp := component_id[p];
            let cj := component_id[j];
            if cp != cj then {

                # update smaller component

                if card(COMPONENT[cp])  < card(COMPONENT[cj]) then {
                    for {k in COMPONENT[cp]} let component_id[k] := cj;
                    let COMPONENT[cj] := COMPONENT[cj] union COMPONENT[cp];
                    let COMPONENT_IDS := COMPONENT_IDS diff {cp};
                } else {
                    for {k in COMPONENT[cj]} let component_id[k] := cp;
                    let COMPONENT[cp] := COMPONENT[cp] union COMPONENT[cj];
                    let COMPONENT_IDS := COMPONENT_IDS diff {cj};   
                };
            };
        };
        let num_components[v, t] := card(COMPONENT_IDS);
        display num_components[v, t];

        # create subtour from each component not containing depot node

        for {k in COMPONENT_IDS: 1 not in COMPONENT[k]} { . #***
            let nSubtours := nSubtours + 1;
            let SUB[nSubtours] := COMPONENT[k];
            display SUB[nSubtours];
        };
    };
    display num_components;
} until (forall {v in V, t in T} num_components[v,t] = 1);

在运行模型时，我得到了很多“丢弃的无效下标”：

执行“if”命令（文件扩增，第229行，偏移量5372）时_cmdno43出错：错误处理集COMPONENT：无效下标COMPONENT[4]丢弃。执行“for”命令（文件扩增，第245行，偏移量5951）时_cmdno63出错：错误处理集COMPONENT：无效下标COMPONENT[3]丢弃。

(...) 在10次警告后进行救援。

我认为脚本正在执行我正在寻找的操作，但当它丢弃10个无效下标时，它会停止。

当尝试调试时，我测试了第二个for循环。

for {p in P_TEMP} {

        let component_id[p] := p;
    let COMPONENT[p] := {p};        
    display component_id[p];
    display COMPONENT[p];   
};

这显示的是正确的，但不是在出现“无效下标已丢弃”的几个错误之前。似乎p穿过一些不在p\U温度中的p。例如，当P\u TEMP是一个由节点“1 3 4 5”组成的集时，我得到了component\u id[2]和component[2]的“invalid subscript discarded”。我的猜测是，类似的事情稍后在IF-ELSE语句中再次发生。

如何避免这种情况？

谢谢你克里斯蒂安

Answer 1

（由于我误解了实施，删除了之前的答案文本）

我不确定这是否充分解释了您的问题，但我认为您在如何确定子项方面存在一些问题。

 repeat {
 solve;

 let NEWSUB := {};
 let EXTEND := {member(ceil(Uniform(0,card(P))),P)};

 repeat {
 let NEWSUB := NEWSUB unhtml" target="_blank">ion EXTEND;
 let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in 1..V, t in 1..T}
    ((p,j) in PAIRS and H[p,j,v,t] = 1 or (j,p) in PAIRS and H[j,p,v,t] = 1)};
 } until card(EXTEND) = 0;

 if card(NEWSUB) < card(P) then {
 let nSubtours := nSubtours + 1;
 let SUB[nSubtours] := NEWSUB;
 display SUB;
 } else break;
 };

其作用：

• 解决问题
• 将NEWSUB设置为空
• 从P中随机选择一个节点作为扩展的起点，并将其添加到NEWSUB
• 查找当前不在NEWSUB中的任何节点，这些节点通过任何一天的任何车辆行程连接到NEWSUB中的节点，并将它们添加到NEWSUB
• 重复此过程，直到没有更多要添加的内容（即NEWSUB等于P，即整个节点集，或者直到NEWSUB和非NEWSUB notedes之间没有行程）
• 检查NEWSUB是否小于P（在这种情况下，它将NEWSUB标识为新的subtour，将其附加到SUB，然后返回开始）
• 如果NEWSUB的大小与P相同（即等于P），则它将停止

这应该可以在一天内解决一辆车的问题，但我不认为它可以解决你的问题。这有两个原因：

1. 如果您的解决方案在不同的日子有不同的子旅行，它可能无法将它们识别为子旅行。

例如，考虑一个为期两天的单车问题，其中您所在的城市是a、B、C、D、E、F。

假设第1天溶液选择AB、BC、CD、DE、EF、FA，第2天溶液选择AB、BC、CA、DE、EF、FD。第1天没有子行程，但第2天有两个长度为3的子行程，所以这不应该是一个合法的解决方案。

但是，您的实现不会识别这一点。无论您选择哪个节点作为NEWSUB的起点，第一天的路由都会将其连接到所有其他节点，因此最终的结果是card（NEWSUB）=card（P）。它没有注意到第2天有一个subtour，所以它会接受这个解决方案。

我不确定您的问题是否允许多辆车在同一天访问同一节点。如果是这样的话，那么您将遇到同样的问题，因为车辆2将该次主题链接到P的其余部分，所以无法识别车辆1的次主题。

其中一些问题可以通过每天和每辆车分别进行小计检查来解决。但对于你所描述的问题，还有另一个问题。。。

对于基本的TSP，这很简单。我们有一个车辆需要访问每个节点——因此，如果子游的基数小于所有节点的基数，那么我们就有一个非法的子游。这由if card（NEWSUB）处理

但是，您声明：

我的问题与TSP不同，不必在每个时间段访问所有节点

假设车辆1行驶A-B-C-A，车辆2行驶D-E-F-D。在这种情况下，这些路线看起来像非法的小计，因为ABC和DEF都小于ABCDEF，并且没有连接它们的路线。如果您使用If卡（NEWSUB）

可以通过确定车辆v在第t天访问了多少节点，然后将子路径的长度与该总路径的长度进行比较来解决这一问题：例如，如果总共有10个城市，车辆1在第1天只访问了其中的6个，车辆1的“子路径”访问了6个城市，那么这很好，但如果它访问了8个节点，并且有一个子路径访问了6个节点，这意味着它正在运行两个不相交的子路径，这很糟糕。

这里需要注意一个陷阱：

假设第一天需要车辆1访问ABCDEF。如果我们得到一个“解决方案”，有一天有车辆1 ABCA和DEFD，我们可能会将ABCA确定为一个应该阻止的子旅行。

但是，如果第2天有不同的要求，那么让车辆1行驶ABCA（而没有其他节点）可能是第2天的合法解决方案。在这种情况下，您不想仅仅因为它是第1天非法解决方案的一部分而在第2天禁止它。

类似地，您可能有一个“子例程”，它对一辆车是合法的解决方案，但对另一辆车是非法的。

为了避免这种情况，您可能需要为每个车辆x天维护不同的禁止子路线列表，而不是为所有车辆使用一个列表。不幸的是，这会使您的实现更加复杂。