Or-tools: Homogenous fleet: SetArcCostForVehicle() vs SetArcCostForAllVehicles()

[bujol12]

Hi!

I'm trying to use the or-tools for a Vehicle Routing Problem. I have a fleet of 5 vehicles of the same properties. What I found surprising that using SetArcCostForVehicle() yields worse results than SetArcCostForAllVehicles(). Am I doing something wrong? Is there any way to fix it?

Here are the code samples:

if num_locations > 0:
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    dist_between_locations = CreateDistanceCallback(locations)
    dist_callback = dist_between_locations.Distance

    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

    demands_at_locations = CreateDemandCallback(demands)
    demands_callback = demands_at_locations.Demand

    slack_max = 0
    vehicle_capacity = 100
    fix_start_cumul_to_zero = True
    demand = "Demand"
    routing.AddDimension(demands_callback, slack_max, vehicle_capacity,
                         fix_start_cumul_to_zero, demand)

    time = "Time"
    time_callback = dist_between_locations.Time
    time_horizon = 24*3600
    routing.AddDimension(time_callback, time_horizon, time_horizon, not fix_start_cumul_to_zero, time)
    time_dimension = routing.GetDimensionOrDie(time)

    for location in range(0, num_locations):
        start = 18000
        end = 24*3600 - 1
        time_dimension.CumulVar(location).SetRange(start, end)


    assignment = routing.SolveWithParameters(search_parameters)
 ```  

if num_locations > 0:
routing1 = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters1 = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters1.time_limit_ms = 5000
search_parameters1.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

dist_between_locations1 = CreateDistanceCallback(locations)
dist_callback1 = dist_between_locations1.Distance

for i in range(0, num_vehicles):
    routing1.SetArcCostEvaluatorOfVehicle(deepcopy(dist_callback1), i)

demands_at_locations1 = CreateDemandCallback(demands)
demands_callback1 = demands_at_locations1.Demand

slack_max1 = 0
vehicle_capacity1 = [100] * num_vehicles
fix_start_cumul_to_zero1 = True
demand1 = "Demand"
routing1.AddDimensionWithVehicleCapacity(demands_callback1, slack_max1, vehicle_capacity1, fix_start_cumul_to_zero1, demand1)

time1 = "Time"
time_callback1 = dist_between_locations1.Time
vehicle_total_time_callbacks1 = [time_callback1] * num_vehicles
time_horizon1 = 24*3600
routing1.AddDimensionWithVehicleTransits(vehicle_total_time_callbacks1, time_horizon1, time_horizon1, not fix_start_cumul_to_zero1, time1)
time_dimension1 = routing1.GetDimensionOrDie(time1)

for location in range(0, num_locations):
    start = 18000
    end = 24*3600 - 1
    time_dimension1.CumulVar(location).SetRange(start, end)


assignment1 = routing1.SolveWithParameters(search_parameters1)

We use the following data:

num_vehicles = 5
locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58, 30], [84, 39],
[14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], [1, 65],
[88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42], [42, 9],
[61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60], [98, 5]]

demands = [0, 19, 21, 6, 19, 7, 12, 16, 6, 16, 8, 14, 21, 16, 3, 22, 18,
19, 1, 24, 8, 12, 4, 8, 24, 24, 2, 20, 15, 2, 14, 9]
```

The results we get:
SetArcCostForAllVehicles(): 970
SetArcCostForVehicle(): 2752

I use the Manhattan distance.

Is there any chance of getting results which will be quite close to each other?

[furnon]

This is surprising, we will investigate as both results should be the same.

On Wed, Sep 13, 2017 at 11:19 AM, bujol12 [e-mail] wrote:

Hi!

I'm trying to use the or-tools for a Vehicle Routing Problem. I have a
fleet of 5 vehicles of the same properties. What I found surprising that
using SetArcCostForVehicle() yields worse results than
SetArcCostForAllVehicles(). Am I doing something wrong? Is there any way
to fix it?

Here are the code samples:

`if num_locations > 0:
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

dist_between_locations = CreateDistanceCallback(locations)
dist_callback = dist_between_locations.Distance

routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand

slack_max = 0
vehicle_capacity = 100
fix_start_cumul_to_zero = True
demand = "Demand"
routing.AddDimension(demands_callback, slack_max, vehicle_capacity,
fix_start_cumul_to_zero, demand)

time = "Time"
time_callback = dist_between_locations.Time
time_horizon = 24*3600
routing.AddDimension(time_callback, time_horizon, time_horizon, not fix_start_cumul_to_zero, time)
time_dimension = routing.GetDimensionOrDie(time)

for location in range(0, num_locations):
start = 18000
end = 24*3600 - 1
time_dimension.CumulVar(location).SetRange(start, end)

assignment = routing.SolveWithParameters(search_parameters)
`

`
if num_locations > 0:
routing1 = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters1 = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters1.time_limit_ms = 5000
search_parameters1.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

dist_between_locations1 = CreateDistanceCallback(locations)
dist_callback1 = dist_between_locations1.Distance

for i in range(0, num_vehicles):
routing1.SetArcCostEvaluatorOfVehicle(deepcopy(dist_callback1), i)

demands_at_locations1 = CreateDemandCallback(demands)
demands_callback1 = demands_at_locations1.Demand

slack_max1 = 0
vehicle_capacity1 = [100] * num_vehicles
fix_start_cumul_to_zero1 = True
demand1 = "Demand"
routing1.AddDimensionWithVehicleCapacity(demands_callback1, slack_max1, vehicle_capacity1, fix_start_cumul_to_zero1, demand1)

time1 = "Time"
time_callback1 = dist_between_locations1.Time
vehicle_total_time_callbacks1 = [time_callback1] * num_vehicles
time_horizon1 = 24*3600
routing1.AddDimensionWithVehicleTransits(vehicle_total_time_callbacks1, time_horizon1, time_horizon1, not fix_start_cumul_to_zero1, time1)
time_dimension1 = routing1.GetDimensionOrDie(time1)

for location in range(0, num_locations):
start = 18000
end = 24*3600 - 1
time_dimension1.CumulVar(location).SetRange(start, end)

assignment1 = routing1.SolveWithParameters(search_parameters1)

`

We use the following data:

`num_vehicles = 5
locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58,
30], [84, 39],
[14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], [1,
65],
[88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42], [42, 9],
[61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60], [98,
5]]

demands = [0, 19, 21, 6, 19, 7, 12, 16, 6, 16, 8, 14, 21, 16, 3, 22, 18,
19, 1, 24, 8, 12, 4, 8, 24, 24, 2, 20, 15, 2, 14, 9]
`

The results we get:
SetArcCostForAllVehicles(): 970
SetArcCostForVehicle(): 2752

I use the Manhattan distance.

Is there any chance of getting results which will be quite close to each
other?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/479, or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUvO7u-VgIQO1Gr7HFZjjACKlE7U1ks5sh54RgaJpZM4PV0Eo
.

[bujol12]

Hey furnon,

Would you mind telling me the approximate time in which you would be able to do that?

[furnon]

I looked into this. The culprit is related to the deepcopy you do when
passing callbacks. Passing the distance callback directly to
SetArcCostEvaluatorOfVehicle
I get the same cost in both cases (970).
Explanation: You must explicitly keep a reference to the callbacks you
create (python is not aware of what's happening on the C++ side and will
clean up unused objects).
Possible fixes:
1) Don't do a copy (actually not needed)
2) Keep a reference to your callback:

dist_callback1s = []
for i in range(0, num_vehicles):
dist_callback1s.append(deepcopy(dist_callback1))
routing1.SetArcCostEvaluatorOfVehicle(dist_callback1s[-1], i)
I hope this helps.

On Mon, Oct 2, 2017 at 10:21 PM, bujol12 [e-mail] wrote:

Hey furnon,

Would you mind telling me the approximate time in which you would be able
to do that?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/479#issuecomment-333653207,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUvxLBHucftCEazklvMrwK2H8SHhYks5soUXTgaJpZM4PV0Eo
.

[bujol12]

Thank you very much! Didn't make this mistake in the original code, but a very similar one. However, the fix to it is the same.

Once again, thank you!

[lihuiknight]

@furnon @bujol12

In my program, I also need to invoke SetArcCostEvaluatorOfVehicle, because each vehicle has its own distance_matrix. Do you have any example for this function?

I implement my code as following:

for vehicle_id in range(data['num_vehicles']):
    def distance_callback_vehicle(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][vehicle_id][from_node][to_node]

    callback = distance_callback_vehicle
    transit_callback_index = routing.RegisterTransitCallback(callback)
    routing.SetArcCostEvaluatorOfVehicle(distance_callback_vehicle, vehicle_id)

However, I meet the following error

File "/usr/local/lib/python3.6/dist-packages/ortools/constraint_solver/pywrapcp.py", line 3332, in SetArcCostEvaluatorOfVehicle
    return _pywrapcp.RoutingModel_SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
TypeError: in method 'RoutingModel_SetArcCostEvaluatorOfVehicle', argument 2 of type 'int'

[Mizux]

Please see https://github.com/google/or-tools/issues/1032#issuecomment-459421223

[Akavall]

I am running into the same issue as @lihuiknight, has there been any progress on this issue?

[Mizux]

Please notice while using v7.0 API, SetArcCostEvaluatorOfVehicle() takes a callback index so you must write

routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, vehicle_id)

i.e. it is using an evaluator_index not a "evaluator callback"....
@Akavall Which ortools version did you used (e.g. python -m pip show ortools)?

[Akavall]

@Mizux, I am using version: Version: 7.0.6546, and your suggestion worked for me. Thank You Very Much!

[veer5551]

Hello @Mizux and Team here,

I too have added a different matrix for each vehicle.
But the model seems to take the last appended distance matrix( transit_index) only and all
the routes are designed according to it.
Here is the code I used by referring to:
https://github.com/google/or-tools/issues/1032#issuecomment-459709180

    transit_callback_index_arr = []

    for vehicle_id in range(data['num_vehicles']):
        distance_matrix = data['distance_matrix'][vehicle_id]
        # print('vehicle_id=%d' % vehicle_id)
        # print(distance_matrix)

        def distance_callback_vehicle(from_index, to_index):
            # Convert from routing variable Index to distance matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            to_node = manager.IndexToNode(to_index)
            return distance_matrix[from_node][to_node]

        transit_callback_index = routing.RegisterTransitCallback(distance_callback_vehicle)
        transit_callback_index_arr.append(transit_callback_index)

    for vehicle_id in range(data['num_vehicles']):
        routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_arr[vehicle_id], vehicle_id)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimensionWithVehicleTransits(
        transit_callback_index_arr,  # list of transit callback, one per vehicle
        0,  # no slack
        300000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

where my

data['distance_matrix'] = [ build_dist_matrix() , build_dist_matrix() , build_dist_matrix2() ]

that is data['distance_matrix'] is a 2D array, while the distance_matrix is the same for the first 2 vehicles and different for the third one.

Could you please take a look here!

Any help is greatly appreciated!!
thanks a lot for your help in advance!!

[veer5551]

Hello there @Mizux and Team,

Just a quick update,
When I tried adding the individual callbacks and then appending them together to pass to the add_dimension, it is working fine. Each vehicle is obeying its own distance_matrix.

I am just wondering what is wrong with the loop there, which dynamically adds the distance_matrices according to the number of vehicles.
This is a naive way of writing logic ( hardcoded callbacks), but as of now, it seems to work.

I think is the same problem as mentioned in:
https://github.com/google/or-tools/issues/479#issuecomment-333842943
But I couldn't resolve it there itself in looping.

Can you have a quick look here and let me know what am I missing here?

Below is the code I added individually for each vehicle.

transit_callback_index_arr = []

    ## vehicle 1 --

    dist_mat_1 = data['distance_matrix'][0]
    print("Vehicle 1",dist_mat_1)

    def distance_callback_vehicle1(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return dist_mat_1[from_node][to_node]

    transit_callback_index1 = routing.RegisterTransitCallback(distance_callback_vehicle1)
    transit_callback_index_arr.append(transit_callback_index1)

    ## vehicle 1 end --

    ## vehicle 2 start --

    dist_mat_2 = data['distance_matrix'][1]
    print("Vehicle 2", dist_mat_2)

    def distance_callback_vehicle2(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return dist_mat_2[from_node][to_node]

    transit_callback_index2 = routing.RegisterTransitCallback(distance_callback_vehicle2)
    transit_callback_index_arr.append(transit_callback_index2)

    ## vehicle 2 end --


    ## vehicle 3 start --

    dist_mat_3 = data['distance_matrix'][2]
    print("Vehicle 3", dist_mat_3)

    def distance_callback_vehicle3(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return dist_mat_3[from_node][to_node]

    transit_callback_index3 = routing.RegisterTransitCallback(distance_callback_vehicle3)
    transit_callback_index_arr.append(transit_callback_index3)

    ## vehicle 3 end --


    def distance_callback_vehicle3(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return dist_mat_3[from_node][to_node]

    transit_callback_index3 = routing.RegisterTransitCallback(distance_callback_vehicle3)
    transit_callback_index_arr.append(transit_callback_index3)

Any help is greatly appreciated!!
Thanks a lot in advance!!
Have a nice weekend :) (From India Time here :) )

[Mizux]

in your call:

transit_callback_indexX = routing.RegisterTransitCallback(distance_callback_vehicleX)

here transit_callback_indexX contains a C++ index but the distance_callback_vehicleX function (which depends on dist_matrix_X) has its address stored in C++ but for python gc (Garbage Collector )point of view no one reference it, so it may be possible that python gc decide to reclaim the memory -> crash

You can try to keep the dist_mat_X alive in a list too i.e.

transit_callback_index_arr = []
transit_callback_mat_arr = []
...
transit_callback_indexX = routing.RegisterTransitCallback(distance_callback_vehicleX)
transit_callback_index_arr.append(transit_callback_indexX)
transit_callback_mat_arr.append(dist_mat_X)

[veer5551]

Hey @Mizux,
Thanks for the suggestion.
But the issue is, I do not have control over the number of vehicles to be used. So hardcoding each vehicle call back would not be feasible.

I need to add the number of vehicles dynamically, so I need to have something like the loop mentioned in https://github.com/google/or-tools/issues/479#issuecomment-589572913.
But as mentioned, it takes only the last callback distance_matrix and ignores the others.

Is there any C++ indexing issue as you mentioned here?

https://github.com/google/or-tools/issues/479#issuecomment-589661233 is the work around I used to solve the problem.

Thanks a lot for your help!!

[Mizux]

Two points,

1. Yes, your callback could be garbage collected by python so that's why you should keep it in an array

1. in python, lambda/function capture variable not value so that's why all functions in the loop use the last data matrix value
   e.g.

#!/usr/bin/env python3

functors_bad = []
functors_good = []

for i in range(10):
    def bad():
        return i

    # capture i by value using default parameter trick
    def good(data=i):
        return data

    functors_bad.append(bad)
    functors_good.append(good)

print("bad:")
for f in functors_bad:
    print(f())

print("good:")
for f in functors_good:
    print(f())

so your code, could be:

# keep transit callback alive
transit_callback = []
transit_callback_index_arr = []
for vehicle_id in range(data['num_vehicles']):
    distance_matrix = data['distance_matrix'][vehicle_id]

    # Use default value to capture distance_matrix current value
    def distance_callback_vehicle(from_index, to_index, data=distance_matrix):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data[from_node][to_node]

    transit_callback.append(distance_callback_vehicle)
    transit_callback_index_arr.append(routing.RegisterTransitCallback(transit_callback[-1])

[veer5551]

Thanks once again for the amazing explanation and for sorting the problem out!!
Each vehicle is obeying its own distance matrix now,
and I'm playing out with the model and trying to scale it to a larger scale now.

Thanks once again for the help!!
Really appreciate it !! :)

[Tiantian-py]

Hi, I'm trying to use SetArcCostEvaluatorOfVehicle to set different cost for different vehicle.

def create_vehicle_cost_callback(time_matrix, cost_per_m):
    def distance_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(time_matrix[from_node][to_node]*cost_per_m)
    return distance_callback
#    return routing.RegisterTransitCallback(distance_callback)

cost_callbacks = []
for vehicle_id in range(data['num_vehicles']):
    cost_callbacks.append(create_vehicle_cost_callback(data['time_matrix'], data['vehicle_cost_per_m'][vehicle_id]))
    routing.SetArcCostEvaluatorOfVehicle(routing.RegisterTransitCallback(cost_callbacks[-1]), vehicle_id)

While it can only work if I set data['vehicle_cost_per_m'] = [1]data['num_vehicles'] or [0]data['num_vehicles']. Otherwise, I got errors like:
SystemError: <built-in function RoutingModel_SolveWithParameters> returned a result with an error set

Couldn't find out why T-T

Ohh~~I know why!
In the travel matrix, I set the forbidden edges to sys.maxsize. Therefore, it cannot multiple by a number larger than 1.

[Javyfu]

Two points,

1. Yes, your callback could be garbage collected by python so that's why you should keep it in an array
2. in python, lambda/function capture variable not value so that's why all functions in the loop use the last data matrix value
   e.g.

#!/usr/bin/env python3

functors_bad = []
functors_good = []

for i in range(10):
    def bad():
        return i

    # capture i by value using default parameter trick
    def good(data=i):
        return data

    functors_bad.append(bad)
    functors_good.append(good)

print("bad:")
for f in functors_bad:
    print(f())

print("good:")
for f in functors_good:
    print(f())

so your code, could be:

# keep transit callback alive
transit_callback = []
transit_callback_index_arr = []
for vehicle_id in range(data['num_vehicles']):
    distance_matrix = data['distance_matrix'][vehicle_id]

    # Use default value to capture distance_matrix current value
    def distance_callback_vehicle(from_index, to_index, data=distance_matrix):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data[from_node][to_node]

    transit_callback.append(distance_callback_vehicle)
    transit_callback_index_arr.append(routing.RegisterTransitCallback(transit_callback[-1])

You save my life!!!!! Love you,mua~~~