Adding time window constraints on VRP gets an unexpected result

回答済み

Daisuke Asaki

2022年02月23日 08:54 編集済み

• 
• 
• 

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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:43

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Maliheh Aramon

  • Gurobi Staff

  2022年03月02日 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

投稿コメントは受け付けていません。