Многопутевый VRP с временными окнами: ошибка CPLEX в решении

Я пишу свою магистерскую диссертацию по поводу проблемы в решении MT-VRP-TW с рейсами с питанием от депо 1 до 112 рейсов. Доступно 11 автомобилей, поэтому я ищу оптимальный тур для 11 автомобилей. Мои машины ходят, но, например, едут с 1 по 4, с 1 по 5, с 1 по 6 и не совершают поездок и / или не заправляются в депо ...

Пробовали добавлять ограничения одно за другим, удаляя ограничения. Переменная дельта-решения является необязательной и равна 1, если рейс передан на аутсорсинг, и 0, если нет.

Это полный код, который у меня есть сейчас:

int trucks = ...;
range S = 1..trucks; // Trucks k in S
int nodes = ...;
range N = 1..nodes; // Nodes i,j in N
int arcs = ...;
range A = 1..arcs; // Arcs i,j in A
int T[N][N] = ...; // Travel time from aircraft i to aircraft j
int d[N] = ...; // Demand aircraft i in N 
int Qmax = ...; // Max capacity of truck
int e[N] = ...; // Time window opens
int l[N] = ...;
int T0 = ...; // Start of shift (5:00 AM)
int Th = ...; // End of shift, length of planning horizon (22:30PM)


dvar boolean x[N][N][S]; // x[i][j][k] yes or no
dvar boolean xi[N][N][S]; // If visited with stop in between depot 0
dvar int+ q[N][S]; // Quantity aboard truck k in S
//dvar int+ r[N]; // Arrival time at aircraft i in N
dvar int+ u[N][S]; // Position of i in N on the tour
// dvar boolean delta[N]; // Boolean 0 when aircraft is served, 1 if outsourced



minimize sum (i,j in N, k in S) T[i][j] * x[i][j][k];

subject to{

forall (i in N)
  sum (j in N, k in S) x[i][j][k] == 1; // Tour must leave in city i

forall (j in N)
  sum (i in N, k in S) x[i][j][k] == 1; // Tour must enter in city j

forall (i in N : i != 1)
  sum (j in N, k in S) x[i][j][k] == 1; // Assignment constraint TSP

forall (i in N)
  sum (i,j in N, k in S) x[i][j][k] == sum (i,j in N, k in S) x[j][i][k]; // Flow conservation

forall (k in S)
  sum (j in N) x[1][j][k] == sum (j in N) x[j][1][k]; // No of arcs entering depot == leaving depot

forall (i in N, k in S)
  sum (j in N : i != 1) q[i][k] >= d[i]; // Demand constraint

forall (k in S)
  sum (i in N) q[i][k] <= Qmax; // Capacity constraint

forall (i,j in N : i != j && j != 1, k in S)
  u[i][k] + 1 <= u[j][k] + nodes * (1 - x[i][j][k]); // Decide positions along tour

forall (i in N, k in S)
  x[i][i][k] == 0; // Eliminate subtours  

forall (i,j in N, k in S)
  q[i][k] + d[i] <= q[j][k] + Qmax * (1 - x[i][j][k]); // Eliminate subtours, allows to count trolleys

forall (i in N, j in N : i != 1, k in S)
  u[i][k] + T[i][j] <= u[i][k] + M * (1 - xi[i][j][k]); // Arrival time at i + time i --> j has <= arrival time at j

forall (i,j in N, k in S)
  u[i][k] + (T[i][1] + T[1][j]) <= u[j][k] + M * (1 - xi[i][j][k]); // Each truck can make multiple trips

forall (i in N, k in S)
  T[1][i] <= u[i][k]; 

forall (i in N, k in S)
  u[i][k] <= Th - T0; // Arrival at j cannot be smaller than traveltime depot to j

forall (i in N, k in S)
  sum (j in N) xi[i][j][k] <= x[i][1][k]; // Connect variables to return to depot

forall (j in N, k in S)
  sum (i in N) xi[i][j][k] <= x[1][j][k]; // Connect variables to return to depot

forall (i,j in N, k in S)
  e[i] >= u[i][k]; // Arrival time cannot be smaller than earliest time window

forall (i,j in N, k in S)
  u[i][k] <= l[i]; // Arrival time cannot be greater than latest time window

}

В настоящее время сообщений об ошибках нет, но ожидается, что рейсы строятся для каждого грузовика, и эта переменная xi (переход от самолета i к самолету j через депо 0) также используется некоторыми грузовиками для пополнения.

Спасибо!!


person Emma    schedule 21.06.2019    source источник


Ответы (1)


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

forall (i in N)
  sum (i,j in N, k in S) x[i][j][k] == sum (i,j in N, k in S) x[j][i][k]; // Flow conservation

У вас есть переменная i как в forall, так и в sums. Я думаю, что эта переменная должна быть только в forall, а суммы должны быть не больше j.

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

  1. Возьмите решение, возвращенное решающей программой, которое неверно.
  2. Найдите ограничение, которое должно нарушаться этим решением.
  3. Выясните, почему решение не нарушает это конкретное ограничение (или набор ограничений). Это должно сказать вам, чего не хватает в вашей модели.
person Daniel Junglas    schedule 24.06.2019
comment
Спасибо за ответ, Даниэль! Я этого еще не видел. Проверим дальше! - person Emma; 25.06.2019