Arrival Time VRPTW Need Help

Answered

Maura Nurinda

July 16, 2023 23:52

• 
• 
• 

Hi I'm am working on my undergraduate thesis on multi period VRP with time windows in collection pickup scheduling and routing. My code work well unless the decision variable start time of pickup in each node.

Parameters:

• s[i,j,k] = start pickup time for vehicle i, in node j, at period k
• s[i,l,k] = start pickup time for vehicle i in node l at period k
• grid [j,l] = matrix time travel from node j to l
• z[i,j,l,k] = routing decision for vehicle i, from node j to node l, at period k
• sd [j] = service time at node j

it used j+1 and l+1 because we want to start from 1 in range n (there's no problem with this because it works well). 

The concept is that i want to make sure that vehicle depart right after the service time is finished in node, which led to s[i,l,k] = s[i,j,k] + service time j + time travel from j to l

So this is my code that I used to use:

 for i in range(m):
        for k in range(t):
            for j in range(n):
                for l in range(n):
                    '''constraint 5.17. scheduling constraint'''
                    M.addConstr((s[i, j+1, k] + (sd[j+1] + grid[j+1, l+1]) * z[i, j+1, l+1, k] <= s[i, l+1, k] + bigM * (1 - z[i, j+1, l+1, k])), name="5.17")
  M.update()

With that code, the code works but doesn't satisfy what I want. I have constraint where total service time + total time travel <= 360. What I mean is that the start time in l - start time will j of course will be far less than 360, but it's not.

Example: s[i,j,k] is 141 but s[i,l,k] is 544. The vehicle doesn't depart right after it finishes in node j, it delays and depart in l at 544. I don't want this to happen.

So I try to modify the code to:

   for i in range(m):
        for k in range(t):
            for j in range(n):
                for l in range(n):
                    '''constraint 5.17. scheduling constraint'''
                    M.addConstr((s[i, j+1, k] + (sd[j+1] + grid[j+1, l+1]) * z[i, j+1, l+1, k] == s[i, l+1, k] + bigM * (1 - z[i, j+1, l+1, k])), name="5.17")
    M.update()

And it shows error:

I need to do this constraint:

Could you please help me to create the logic to define s[i,l,k]? Thank you very much

Related to

• VRP

0

• 

  Mario Ruthmair

  • Gurobi Staff

  July 25, 2023 13:46

  Hi Maura,

  VRPs with time windows in general have solutions where the vehicles need to wait at some customer locations until the time window starts. So, even in an optimal solution, there could be waiting times at customers. Additionally, there are usually multiple optimal solutions that basically describe the same vehicle routes but differ in the waiting times at the customers (for the objective of minimizing the route distances or minimizing the travel times, it does not matter where the vehicles wait and how long).

  What people usually do is leave some freedom in the model with respect to the service start times. Optimal solutions will not be affected by this. In a postprocessing step, you can trace through each vehicle route and move the service start times to the earliest possible values.

  To your two modeling variants:

  1. You can easily put an upper variable bound of 360 to all your s[i,j,k] variables. Then, the value cannot be 544 anymore. If the vehicles should be at the depot again before time 360, you might need some additional constraints similar to: s[i,j,k] + (sd_j + w_j0)* z[i,j,0,k] <= 360 (provided that the depot is 0).
  2. Since you set the BigM constraint to be an equality, the model is most probably infeasible, and it returns a subset of the model that is already infeasible (which is clearly the case when you look at it).

  Best regards,
  Mario

  0

Please sign in to leave a comment.