随时间 windows 的多行程 VRP：解决方案中的 CPLEX 错误

Question

我在写我的硕士论文时遇到了 MT-VRP-TW 解决方案中的一个问题，从 1 号机库到 112 号航班的餐饮航班。有 11 辆车可用，所以我正在寻找 11 辆车的最佳游览。我的车辆进行旅行，但例如从 1-4、从 1-5、从 1-6 并且不进行旅行 and/or 在车站加油...

尝试过一一添加约束，删除约束。增量决策变量是可选的，如果航班外包则为 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）也被一些卡车用来重新装满。

谢谢！！

Answer 1

有很多地方可能是错误的。我建议您仔细检查所有约束并 double-check 它们。例如，这看起来很可疑：

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 和 sum 中都有一个变量 i。我认为变量应该只在 forall 中并且总和应该只超过 j.

为了调试类似的东西，遵循这种方法通常是个好主意

采用求解器返回的错误解。
找到此解决方案应违反的约束条件。
找出解决方案为何不违反该特定约束（或约束集）的原因。那应该告诉您模型中缺少什么。

随时间 windows 的多行程 VRP：解决方案中的 CPLEX 错误

Multi-trip VRP with time windows: CPLEX error in solution

cplex

traveling-salesman

opl

vehicle-routing