VRP с несколькими отключениями и временными окнами: ошибка CPLEX в решении - PullRequest
Новая
       47

VRP с несколькими отключениями и временными окнами: ошибка CPLEX в решении

0 голосов
/ 21 июня 2019

Я пишу магистерскую диссертацию, где столкнулся с проблемой в решении 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) также используется некоторыми грузовиками для пополнения запасов.

Спасибо !!

1 Ответ

1 голос
/ 24 июня 2019

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

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 и sum s. Я думаю, что переменная должна быть только в forall, а суммы должны превышать j.

Для того, чтобы отлаживать подобные вещи, обычно хорошей идеей является использование этого подхода

  1. Возьмите решение, возвращенное неверным решателем.
  2. Найдите ограничение, которое это решение должно нарушать.
  3. Выясните, почему решение не нарушает это конкретное ограничение (или набор ограничений). Это должно сказать вам, что отсутствует в вашей модели.
...