0

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!!

1 Answer 1

1

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 sums. 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

  1. Take a solution returned by the solver that is wrong.
  2. Find the constraint that this solution should violate.
  3. Figure out why the solution does not violate that particular constraint (or set of constraints). That should tell you what is missing in your model.
1
  • Thank you for answering Daniel! I did not see that yet. Will check into this further!
    – Emma
    Jun 25, 2019 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.