CODEWITHSUNDEEP
pythonor-tools
Doggy Face
Doggy Face

Reputation: 409

Vehicle Routing with Different Vehicle Speed (Google OR Tools)

Currently, I am working on the vehicle routing problems with different vehicle speeds. My approach is using speed adjustment ratio for each vehicle (which mean I have default speed), to build the time constraint I used the code: (data['travel_service'] is time matrix + service time and data['travel_service'] is service time only)

data['vehicle_speed_adjustment'] = [1.5, 1.3, 1.2, 1]
def create_vehicle_travel_service_time_callback(travel_service_matrix, service_time, speed_adjust_ratio):
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes + the service time of starting node."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        if travel_service_matrix[from_node][to_node] == sys.maxsize or travel_service_matrix[from_node][to_node] == service_time[from_node]:
            return travel_service_matrix[from_node][to_node]
        else:
            return int((travel_service_matrix[from_node][to_node]-service_time[from_node])/speed_adjust_ratio) + service_time[from_node]
    return time_callback

# time_callback_index = []
for vehicle_id in range(data['num_vehicles']):
    time_callback = create_vehicle_travel_service_time_callback(data['travel_service'], data['service_time'], data['vehicle_speed_adjustment'][vehicle_id])
    time_callback_index = routing.RegisterTransitCallback(time_callback)
    print(time_callback_index)
    routing.AddDimension(
        time_callback_index,
        max_waiting_time,  # allow waiting time
        max_operation_time,  # maximum time per vehicle
        False,  
        'Time')
    
time_dimension = routing.GetDimensionOrDie('Time')

The problem is, when I try to run the program, the program only recognize the first value of the data['vehicle_speed_adjustment'] list which is 1.5 and applied it into every vehicle.

Can someone explain why this happens?

data['travel_service'] = [[0, 4, 22, 21, 48, 28, 8, 23, 16, 14, 23, 37], [59, 0, 79, 78, 104, 84, 63, 76, 68, 66, 78, 91], [32, 34, 0, 12, 38, 32, 31, 14, 41, 40, 41, 52], [27, 29, 8, 0, 35, 28, 27, 11, 36, 35, 37, 47], [58, 59, 38, 39, 0, 39, 52, 41, 62, 61, 60, 60], [36, 37, 30, 30, 37, 0, 32, 30, 41, 40, 39, 34], [18, 18, 31, 31, 52, 34, 0, 32, 20, 19, 22, 39], [33, 31, 14, 15, 41, 32, 32, 0, 42, 41, 43, 54], [44, 41, 59, 58, 80, 61, 38, 60, 0, 31, 36, 53], [69, 66, 85, 84, 106, 87, 64, 86, 58, 0, 65, 83], [33, 33, 41, 41, 60, 41, 22, 43, 18, 20, 0, 31], [45, 44, 50, 49, 58, 34, 37, 52, 33, 36, 29, 0]]

data['travel_service'] = [0, 55, 10, 6, 10, 8, 10, 10, 28, 55, 10, 8]

data['num_vehicles'] = 4

Upvotes: 2

Views: 1669

Answers (1)

Mizux
Mizux

Reputation: 9281

nearly good, you just need to create an array of callback index then pass the array to AddDimension...
note: array length MUST be equal to the vehicle number.
note2: you can reuse the same registered callback index for few vehicles
e.g. you have two bikes, and three cars in this order you could pass an array [1, 1, 2, 2, 2] supposing RegisterTransitCallback() returned 1 and 2...

ref: https://github.com/google/or-tools/blob/45770b833997f827d322e929b1ed4781c4e60d44/ortools/constraint_solver/routing.h#L416-L418

time_callback_indices = []
for vehicle_id in range(data['num_vehicles']):
    time_callback = create_vehicle_travel_service_time_callback(data['travel_service'], data['service_time'], data['vehicle_speed_adjustment'][vehicle_id])
    time_callback_indices.append(routing.RegisterTransitCallback(time_callback))
    #print(time_callback_index)

routing.AddDimensionWithVehicleTransits(
    time_callback_indices,
    max_waiting_time,  # allow waiting time
    max_operation_time,  # maximum time per vehicle
    False,  
    'Time')

Upvotes: 3

Related Questions