Динамическая генерация ограничений на удаление субтура в AMPL для PVRP
Я пытаюсь закодировать периодическую проблему маршрутизации транспортных средств с некоторыми ограничениями запасов в 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
Он динамически устраняет обходы в течение 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.
Как мне избежать этого?
Спасибо кристиан
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)
- проверяет, меньше ли NEWSUB, чем P (в этом случае он идентифицирует NEWSUB как новый подпоток, добавляет его в SUB и возвращается к началу).
- если NEWSUB имеет тот же размер, что и P (то есть равен P), то он останавливается.
Это должно работать на проблему с одним транспортным средством только с одним днем, но я не думаю, что это сработает для вашей проблемы. Для этого есть две причины:
- Если ваше решение имеет разные подпрограммы в разные дни, оно может не распознать их как подпрограммы.
Например, рассмотрим проблему с одним транспортным средством в течение двух дней, когда ваши города 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 для посещения ABCDEF Если мы получим "решение" с транспортным средством 1 ABCA и DEFD в один день, мы можем определить ABCA как подпроцесс, который следует предотвратить.
Тем не менее, если ко Дню 2 предъявляются другие требования, может случиться так, что наличие транспортного средства 1 в пути ABCA (и без других узлов) является законным решением для дня 2. В этом случае вы не хотите запрещать его на день 2 только потому, что оно был частью незаконного решения в течение первого дня.
Точно так же у вас может быть "подчиненный", который является законным решением для одного транспортного средства, но незаконным для другого.
Чтобы избежать этого, вам может потребоваться вести отдельный список запрещенных маршрутов для каждого транспортного средства x день вместо использования одного списка для всех. К сожалению, это сделает вашу реализацию немного более сложной.