I am new to Vehicle Routing Problem. I was going through the tutorial at https://developers.google.com/optimization/routing/cvrptw. For my use case I created the below data model

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    #Obtained from Google Maps Distance Matrix API - Duration Value in Mins
    data['time_matrix'] = [
         [0, 15, 22, 16, 14],
         [14, 0, 15, 7, 7],
         [23, 17, 0, 14, 19],
         [14, 7, 14, 0, 10],
         [13, 7, 17, 10, 0]
    ]
    #Dummy Data 
    data['time_windows'] = [
         (0, 100), #Depot
         (25, 70), #Loc1
         (25, 60), #Loc2
         (80, 120),#Loc3
         (0, 60),  #Loc4
    ]
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

My time dimension is:

time = 'Time'
routing.AddDimension(
    transit_callback_index,
    30,  # allow waiting time
    100,  # maximum time per vehicle
    False,  # Don't force start cumul to zero.
    time)

When I run the above program I get the below output:

Route for vehicle 0:  0 Time(0,0) -> 4 Time(14,38) -> 1 Time(25,45) -> 2 Time(40,60) -> 3 Time(80,80) -> 0 Time(94,94) Time of the route: 94min

Total time of all routes: 94min

Here I have three questions:

  1. I am having trouble in understanding the output. At location 4, Time(14,38) is the solution window. As said in the tutorial link - It means the vehicle must arrive there between times 14 and 38 to stay on schedule. The solution window starts at time 14 because it takes 14 units of time (the 0, 4 entry of the time matrix) to get from the depot to location 4. However why the end time is 38? I am unclear of all the end times shown in output. How is end time derived?
  2. As shown in my data model I am trying to solve a problem where a person from depot needs to reach Locations 1 through 4 within certain time limit.However what should be the value of 'time_windows' for the below case. Service time in each stop is 45 mins.

    Depot - Time Window (4:30 AM to 9:30 AM)
    Loc1 - Time Window (5:00 AM to 9:00 AM)
    Loc2 - Time Window (5:00 AM to 7:00 AM)
    Loc2 - Time Window (5:00 AM to 7:00 AM)
    Loc4 - Time Window (5:00 AM to 6:00 AM)

  3. I am also unclear of AddDimension's allow waiting time value.

Thanks!!

0 Answers