VRPTW Multiple Depots with different departure at each depot

134 views
Skip to first unread message

Heather Orange

unread,
Apr 5, 2020, 2:29:02 AM4/5/20
to or-tools-discuss
Im using or-tools in python for a VRPTW problem. I have 9 depots that open at different time. Ive set time windows for each depots, but all vehicles departing from different depots seem to use the start time for only the first depot. 

data['time_windows'] = [
     
(150, 840), #0 Depot
     
(537,1227), #1 Depot
     
(120, 810), #2 Depot
     
(180, 870), #3 Depot
     
(120, 810), #4 Depot
     
(180, 870), #5 Depot
     
(360, 1050), #6 Depot
     
(60, 750), #7 Depot
     
(0, 690), #8 Depot
     
...all other delivery point time windows...
]


Route output has all vehicles leaving at the same time

Route for vehicle 1:
0 Time(150,150) ->
Route for vehicle 2:
1 Time(150,150) ->
...
Route for vehicle 9:
8 Time(150,150) ->


Im currently using a work around, starting all depots at 0 and modifying the time matrix to add the depot delayed start time to the time for each depot to delivery location. However I think this is affect the solvers ability to find the best solution. I also run into issues setting the max route time using the work around since its not a true max route time due to having the added time for delayed start at certain depots.

Is there a way to get the solver to have different departure times for each depot? 

Heather Orange

unread,
Apr 5, 2020, 8:21:45 PM4/5/20
to or-tools...@googlegroups.com
I was able to set the time window constraint for each vehicle using a conditional statement. I have 20 vehicles for each route... so heres what I used. You could probably set them individually as well. Im sure there are much more elegant ways to handle this, but this works for me. 
 # Add time window constraints for each vehicle start node.
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        #sets time window for each depot
        if vehicle_id < 20:
            time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],data['time_windows'][0][1])
        elif vehicle_id < 40:   
            time_dimension.CumulVar(index).SetRange(data['time_windows'][1][0],data['time_windows'][1][1])
        ... continue conditional statements for all vehicles ids....

        #set maximum travel time for the vehicle (does not include the time for starting at a non 0 time), 720 minutes in this case
        time_dimension.SetSpanUpperBoundForVehicle(720, vehicle_id) 

Now I have run into another issue... 

How can I set the cumulative route time to exclude the time for starting later at the depot?

Say depot one starts at 100 minutes. This is included in the total route time, also if one of the vehicles is not utilized, it starts and ends at the depot, which adds 100 minutes to the total route time. 



Reply all
Reply to author
Forward
Message has been deleted
0 new messages