Динамическая генерация ограничений на устранение подземных условий в AMPL для PVRP

Question

Я пытаюсь закодировать периодическую проблему маршрутизации транспортных средств с некоторыми ограничениями запасов в AMPL.Я хотел бы динамически добавлять ограничения подуровня.Для того, чтобы сделать это, я был вдохновлен этой формулировкой для 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];

Я не уверен, применимо ли вышеуказанное к моей проблеме с несколькими транспортными средствами и несколькими периодами времени.Я попытался определить v и t в let EXTEND, при этом необходимо использовать H, но я не уверен, что это правильный метод.Мои модели запускаются, если сформулированы, как указано выше, однако это не устраняет допуски.Ребята, есть ли у вас какие-либо предложения на этот счет?

---

ДОБАВЛЕННЫЙ ВОПРОС:

Я нашел вдохновение в этой модели, сформулированной в SAS / OR: (Немного обширно для чтения и не нужнодля моих вопросов)

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

Он динамически устраняет обходы в течение d дней, и я подумал, что это может быть связано с моей проблемой с несколькими транспортными средствами и несколькими периодами (днями).

Чтобы немного уточнить мою проблему.Узел может быть посещен только одним транспортным средством один раз за период времени.Не нужно посещать все узлы в каждый период времени, что является основным отличием от формулировки 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);

Я получаю много «недопустимого индекса» при запускемодель:

Ошибка в _cmdno 43 при выполнении команды «if» (файл amplin, строка 229, смещение 5372): набор обработки ошибок COMPONENT: недопустимый нижний индекс COMPONENT [4] отброшен.Ошибка в _cmdno 63 при выполнении команды «for» (файл amplin, строка 245, смещение 5951): набор обработки ошибок 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 не в P_TEMP.Например, когда P_TEMP является набором, состоящим из узлов «1 3 4 5», тогда я получаю «сброшен неверный индекс» для component_id [2] и COMPONENT [2].Я предполагаю, что нечто подобное случается позже в заявлении IF-ELSE.

Как мне избежать этого?

Спасибо, Кристиан

Answer 1

(предыдущий текст ответа удален, потому что я неправильно понял реализацию)

Я не уверен, что это полностью объясняет вашу проблему, но я думаю, что есть несколько проблем с тем, как вы определяете подпрограммы.

 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;
 };

Что это делает:

• решает проблему
• устанавливает NEWSUB как пустое
• случайным образом выбирает один узел из P в качестве начальной точкидля EXTEND и добавляет его в NEWSUB
• ищет любые узлы , а не , находящиеся в настоящее время в NEWSUB, которые подключены к узлу в NEWSUB любым транспортным средством в любой день , идобавляет их в NEWSUB
• , повторяет этот процесс до тех пор, пока не останется больше добавить (т. е. либо NEWSUB равен P, весь набор узлов, либо пока не будет нет поездок между NEWSUB и не-NEWSUB notedes)
• проверяет, меньше ли NEWSUB, чем P (в этом случае он идентифицирует NEWSUB как новый подпункт, добавляет его в SUB и возвращается к началу).
• , если NEWSUB имееттот же сиЗе как Р (то есть равен Р), то он останавливается.

Это должно работать для проблемы с одним транспортным средством только с одним днем, но я не думаю, что это сработает для вашегопроблема.Для этого есть две причины:

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, маршруты первого дня соединяют его со всеми остальными узлами, поэтому вы получите карту (NEWSUB) = карта (P).Он не замечает, что у Дня 2 есть подземный ход, поэтому он примет это решение.

Я не уверен, допускает ли ваша проблема, что несколько транспортных средств посещают один и тот же узел в один и тот же день.Если это произойдет, то вы столкнетесь с такой же проблемой там, где подземный ход для транспортного средства 1 не определен, поскольку транспортное средство 2 связывает этот подземный ход с остальной частью P.

Некоторые из этихможно исправить, выполнив проверку подземных ходов отдельно для каждого дня и для каждого транспортного средства.Но для проблемы, как вы ее описали, есть еще одна проблема ...

После того, как программа определила закрытый маршрут (т. Е. Набор узлов, которые все связаны друг с другом, а не с любыми другими узлами), необходимо выяснить, следует ли запрещать этот подземный ход.

Для основного TSP это просто.У нас есть одно транспортное средство, которое должно посещать каждый узел - следовательно, если мощность подтипа меньше мощности всех узлов, то у нас есть недопустимый подтип.Это обрабатывается if card(NEWSUB) < card(P).

Тем не менее, вы заявляете:

моя проблема в отличие от TSP не требует посещать все узлы в каждый период времени

Предположим, что транспортное средство 1 перемещается ABCA, а транспортное средство 2 - DEFD.В этом случае эти маршруты будут выглядеть как недопустимые подпроцессы, потому что каждый ABC и DEF меньше, чем ABCDEF, и нет маршрутов, которые связывают их.Если вы используете if card(NEWSUB) < card(P) в качестве критерия для запрещенного цикла, вы в конечном итоге заставите каждое транспортное средство посещать все узлы, что хорошо для базового TSP, но не то, что вы хотите здесь.

Этоэто можно исправить, определив, сколько узлов v посещает транспортное средство в день t, а затем сравнив длину подземного пути с этой суммой: например, если имеется всего 10 городов, транспортное средство 1 посещает только 6 из них в первый день, и "subtour "для транспортного средства 1 посещает 6 городов, тогда это нормально, но если он посещает 8 и имеет subtour, посещающий 6, это означает, что он путешествует по двум непересекающимся суб-циклам, что плохо.

Одна ловушка, которую нужно остерегатьсяздесь:

Предположим, 1-й день требует транспортного средства 1 для посещения ABCDEF.Если мы получим «решение» с транспортным средством 1 ABCA и DEFD в один день, мы можем идентифицировать ABCA как подпроцесс, который следует предотвратить.

Однако, если День 2 имеет другие требования, это может бытьпоездка на автомобиле 1 ABCA (и без других узлов) является законным решением для дня 2. В этом случае вы не хотите запрещать его на день 2 только потому, что это было частью незаконного решения на день 1.

Аналогично, у вас может быть «подчиненный», который является законным решением для одного транспортного средства, но запрещен для другого.

Чтобы избежать этого, вам может потребоваться вести отдельный список запрещенных подчиненных для каждого транспортного средства x деньвместо использования одного списка для всех.К сожалению, это сделает вашу реализацию немного более сложной.