Adding time window constraints on VRP gets an unexpected result

Answered

Daisuke Asaki

February 23, 2022 08:54 Edited

• 
• 
• 

Hello, I'm using gurobipy to solve CVRPTW.

The problem is when I add constraints of time windows, the solution becomes unexpected regarding an arrival time, which means the solution's arrival time doesn't meet the time window constraints.

Here is the code for adding the constraint.

arrTime = model.addVars(n, vtype=GRB.CONTINUOUS)

.........some code

# time window(supposed to start at 9:00 am)
for i in range(0,n):
    # arrival time at depot should be 0 which means a tour starts at 9:00 am
    if i == 0:
        model.addConstr(arrTime[i] == 0)
    # arrival time should be after start time of timewindows
    model.addConstr(arrTime[i] >= (start_time[i] - 9) * 60)
    # arrival time should be before end time of timewindows
    model.addConstr(arrTime[i] <= (end_time[i] - 9) * 60)
    # arrival time should be after previous node arrival time + travel time
    model.addConstrs(arrTime[i] - arrTime[j] - dist_matrix[j, i] >= inf * (egdes[j, i] - 1) for j in range(n))

egdes[j, I] is 1 if a driver visits node i from node j. This edges is also a variable.

So, for instance, if a driver arrives at node j at 10:00 AM and he/she visits node i after node j, the arrival time of node i should be later than 10:00 + distance[j,i]. The arrival time of node i should also be within node i's time window.

Here is what I got as a solution, meaning each two elements in the list are edges [from node id, to node id]. The second list is the arrival times (minutes after the start depot) of each node.

[[0, 1], [0, 8], [1, 5], [2, 3], [3, 0], [4, 6], [5, 2], [6, 0], [7, 4], [8, 9], [9, 7]]
[  0.   0.  60.  60. 180.  60.  60.   0.  60.   0.]

In the above result, the driver visits node 1 after node 0. So the arrival time at node 1 should be 3.35 since dist_matrix[0, 1] is 3.35, but it is 0., which means the solution doesn't meet the constraint.

Do I set this constraint incorrectly?
Thank you very much for your help.

0

• 

  Maliheh Aramon

  • Gurobi Staff

  March 02, 2022 01:51

  Hi Daisuke, 

  The issue is likely happening because of the very big M value \(\texttt{numpy.inf}\) you are using in the RHS of the arrival time constraints. 

  The arrival time constraints ensure 

  if edges[j, i] = 1, then arrTime[i] >= arrTime[j] + dist_matrix[j, i]

  I would suggest to use the Gurobi API for indicator constraints and implement them as below:

  model.addConstrs(
       (
          (edges[j, i] == 1) >> (arrTime[i] >= arrTime[j] + dist_matrix[j][i]) 
          for i in range(n)
          for j in range(n)
       ),
  name="arrival_time",
  )

  Best regards,

  Maliheh

  0

Please sign in to leave a comment.