Как получить только один путь, начинающийся и заканчивающийся в одном узле?

Я пытаюсь запустить эту модель в 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];

}

Спасибо!


linear-programming cplex ilog
person user1123417    schedule 25.12.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы решаете вариант задачи коммивояжера. В частности, то, что вы получаете, называется субтуром, который представляет собой замкнутый путь, который включает меньше, чем все узлы (в вашем случае магазины).

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

Отборочный тур

Вот идея, как исключить подтур S, который включает s магазинов (s ‹num_stores):

На английском языке: мы начинаем с разделения набора узлов (магазинов) на две группы S и T. Пусть S будет набором магазинов в субтур. Пусть 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

Реализация набора ограничений для исключения текущего субтура

Для каждого субтура («острова») вы должны сначала создать набор из 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

Как определить субтуры

Вы проверите наличие субтур вне 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
person Ram Narasimhan    schedule 25.12.2013
comment
Привет, Рам, спасибо! объяснение очень ясное. Я попытаюсь реализовать это, но как мне узнать, какие субтуры, которые я дал на выходе, представляют собой матрицу двоичных элементов Y12 = 1, Y23 = 0, Y27 = 1 и т. Д.? другими словами, как мне создать shopping_in_subtour и shopping_not_in_subtour? . Между прочим, моя проблема включает 50 магазинов, это будет проблемой во время выполнения, реализующем это ограничение? - person user1123417; 26.12.2013
comment
Между прочим - мне не нужно обходить все магазины - я посещаю только те магазины, в которых я решаю покупать продукты (с учетом компромисса между расстоянием и ценой) из моего списка продуктов, поэтому я не обязательно хочу пройти через shopping_not_in_tour, а лучше создать только один закрытый путь с магазинами, в которых я хочу посетить. - person user1123417; 26.12.2013
comment
Я добавил объяснение того, как вы обнаружите shop_in_subtour. Обратите внимание, что вы можете начать с любой переменной Yij и проследить ее до конца, чтобы увидеть, повторяется ли магазин. И 50 магазинов - это достаточно мало, чтобы вы могли решить эту проблему с добавленными ограничениями субтур. - person Ram Narasimhan; 26.12.2013