I am writing my master thesis en encountering a problem in the MT-VRP-TW solution, with catering flights from depot 1 to 112 flights. There are 11 vehicles available so I am looking for an optimal tour for 11 vehicles. My vehicles make trips, but for example go from 1-4, from 1-5, from 1-6 and do not make tours and/or refill at the depot...
Have tried adding constraints one by one, removing constraints. The delta decision variable is optional and is 1 if a flight is outsourced and 0 if not.
This is the full code I have now:
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
}
There are no error messages now, but expected is that trips are constructed per truck, and that variable xi (going from aircraft i to aircraft j via depot 0) is also taken by some trucks to get refilled.
Thank you!!
There are many things that could be wrong. I suggest you carefully go through all your constraints and double-check them. For example, this looks fishy:
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
You have a variable i
in both the forall
and the sum
s. I think that variable should only be in the forall
and the sums should only be over j
.
In order to debug things like that it is usually a good idea to follow this approach