0

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

试过一一添加约束，去掉约束。delta 决策变量是可选的，如果航班外包则为 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 经仓库 0 到飞机 j）也被一些卡车带走以重新装满。

谢谢！！

4

1 回答 1

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您在 theforall和sums中都有一个变量。我认为该变量应该只在 中，forall而总和应该只在j.

为了调试这样的事情，遵循这种方法通常是个好主意

  1. 采用解算器返回的错误解。
  2. 找出这个解决方案应该违反的约束。
  3. 找出解决方案不违反特定约束（或一组约束）的原因。这应该告诉您模型中缺少什么。
于 2019-06-24T14:09:09.917 回答