bugs? routing.GetArcCostForVehicle(previous_index, index, vehicle_id)

[KK666-AI]

Dear Authors,

It seems that there is a bug in https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/vrp_pickup_delivery.py.

In the print_solution function, it seems that the underlying program has encoded each original node id into a new index, which can transfer them by manager.IndexToNode(index) or manager.NodeToIndex(raw_node_id).

In the program, when we invoke index = assignment.Value(routing.NextVar(index)) the returned index could be larger than the max original node_id. I think it is reasonable because the underlying logic in or-tools may reindex each node.

Despite that, I think a right logic should be maintain the following conclusion, however in my data, it doesn't. So I think there is a potential bug in the logic. Note that, in the example data, this bug doesn't occur.

pre_node = manager.IndexToNode(previous_index)
cur_node = manager.IndexToNode(index)
distance_1 = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
distance_2 = data['distance_matrix'][pre_node][cur_node]
assert distance_1 == distance_2

[Mizux]

1) Yes, solver need a specific index for each start/end vehicle node, so solver may add new index as needed and the manager is use to do the transform...

How did you define your transit callback, register it, and setup it ? I mean you may have something like this:

def distance_callback(previous_index, index):
        """Returns the manhattan distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        pre_node = manager.IndexToNode(previous_index)
        cur_node = manager.IndexToNode(index)
        return data['distance_matrix'][pre_node][cur_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

routing.GetArcCostForVehicle(previous_index, index, vehicle_id) is just calling your callback...

[KK666-AI]

Yes. I code my program according to your example.

# [START solution_printer]
def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    print('Objective: {}'.format(assignment.ObjectiveValue()))
    total_distance = 0
    city_names = data['city_names']
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        cur_city = city_names[manager.IndexToNode(index)]
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        hop = 0
        prefix_city = ''
        while not routing.IsEnd(index):
            if cur_city != prefix_city:
                plan_output += ' {} -> '.format(cur_city)
                hop += 1

            previous_index = index
            prefix_city = cur_city
            index = assignment.Value(routing.NextVar(index))
            cur_city = city_names[manager.IndexToNode(index)]
            pre_node = manager.IndexToNode(previous_index)
            cur_node = manager.IndexToNode(index)
            # dist = routing.GetArcCostForVehicle(previous_index, index, vehicle_id) # bug
            dist = data['distance_matrix'][pre_node][cur_node]
            route_distance += dist
            if vehicle_id == 14:
                # tmp_dist = data['distance_matrix'][previous_index][index]
                pre_loc = data['locations'][manager.IndexToNode(previous_index)]
                cur_loc = data['locations'][manager.IndexToNode(index)]
                pre_node = manager.IndexToNode(previous_index)
                cur_node = manager.IndexToNode(index)
                print('%s->%s %.9f pre_index=%d, cur_index=%d, pre_node=%d, cur_node=%d, pre_loc=%s, cur_loc=%s' %
                      (prefix_city, cur_city, dist,
                       previous_index, index,
                       pre_node, cur_node,
                       pre_loc, cur_loc))

        # plan_output += '{}\n'.format(manager.IndexToNode(index))
        cur_city = city_names[manager.IndexToNode(index)]
        if cur_city != prefix_city:
            hop += 1
            plan_output += '{}\n'.format(cur_city)
            plan_output += 'Distance of the route: {}km\n'.format(route_distance * DISTANCE_SCALE)
        if hop > 1:
            print(plan_output)
        total_distance += route_distance
    print('Total Distance of all routes: {} km'.format(total_distance * DISTANCE_SCALE))
    # [END solution_printer]

The part of my output would be:

YT->YT 0.000000000 pre_index=14, cur_index=62, pre_node=14, cur_node=62, pre_loc=(37.464541, 121.450393), cur_loc=(37.464541, 121.450393)
YT->WH 0.597659010 pre_index=62, cur_index=63, pre_node=62, cur_node=63, pre_loc=(37.464541, 121.450393), cur_loc=(37.517347, 122.122946)
WH->YT 0.597659010 pre_index=63, cur_index=116, pre_node=63, cur_node=14, pre_loc=(37.517347, 122.122946), cur_loc=(37.464541, 121.450393)
Route for vehicle 14:
 YT ->  WH -> YT
Distance of the route: 119.53180206117398km

When I use dist = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)

it would be:

YT->YT 0.000000000 pre_index=14, cur_index=62, pre_node=14, cur_node=62, pre_loc=(37.464541, 121.450393), cur_loc=(37.464541, 121.450393)
YT->WH 0.000000000 pre_index=62, cur_index=63, pre_node=62, cur_node=63, pre_loc=(37.464541, 121.450393), cur_loc=(37.517347, 122.122946)
WH->YT 0.000000000 pre_index=63, cur_index=116, pre_node=63, cur_node=14, pre_loc=(37.517347, 122.122946), cur_loc=(37.464541, 121.450393)
Route for vehicle 14:
 YT ->  WH -> YT
Distance of the route: 0.0km

[Mizux]

Can you add a "print" to check if your callback is call in the second test ?

Also currently, the SWIG wraping doesn't keep alive the callback, so if python gc.collect() is call...., you could try to keep a reference to the callback directly

def distance_callback(previous_index, index):
        """Returns the manhattan distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        pre_node = manager.IndexToNode(previous_index)
        cur_node = manager.IndexToNode(index)
        return data['distance_matrix'][pre_node][cur_node]

callback = distance_callback;
transit_callback_index = routing.RegisterTransitCallback(callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
....
printer_function(...., callback) # keep callback alive
// try to check if the callback is working properly
print("test callback:{}".format(callback(63, 14)))
// test using routing.GetArcCost....
print("test callback:{}".format(routing.GetArcCostForVehicle(63, 116, 0)))

Note: i'm working on C# (done), Java (in progress) and Python (todo) so solve this ownership issue...

[KK666-AI]

I try to keep callback alive in my code as you said. But it doesn't work.

##################################
        # try to check if the callback is working properly
        print("test callback:{}".format(callback(63, 116) * DISTANCE_SCALE))
        # test using routing.GetArcCost....
        print("test GetArcCost:{}".format(routing.GetArcCostForVehicle(63, 116, 14) * DISTANCE_SCALE ))
        # test directly query the distance matrix
        pre_node = manager.IndexToNode(63)
        cur_node = manager.IndexToNode(116)
        print("test distance_matrix:{}".format( data['distance_matrix'][pre_node][cur_node] * DISTANCE_SCALE  ))
        import sys
        sys.exit(1)
##################################

The log will be:

test callback:59.76590103058697
test GetArcCost:0.0
test distance_matrix:59.76590103058697

[Mizux]

one more question, does your distance_matrix is using int ?

Routing Solver is based on top of CP solver which does not support floating point... maybe the convertion from double to int make the callback always returning 0.0

[KK666-AI]

The type of distance_matrix is double, as shown in our above discussion.

[Mizux]

then it's a bug, you must return an int... ref: https://github.com/google/or-tools/blob/14875ce07325344ab989deb3662aabd7be7288ec/ortools/constraint_solver/routing.h#L364 and https://github.com/google/or-tools/blob/14875ce07325344ab989deb3662aabd7be7288ec/ortools/constraint_solver/routing_types.h#L41

[KK666-AI]

OK , I see. Thanks a lot.

[Mizux]

Does this fix your issue ?

[KK666-AI]

Yes, you can close this issue.

[hovjr]

Hi I am getting zero with routing.GetArcCostForVehicle(previous_index, index, vehicle_id).

I changed my distance matrix to integer form however it hasn't resolved the issue.

def print_solution(data, manager, routing, solution):
    total_distance = 0
    total_load = 0
    final_df = pd.DataFrame()
    count = 1

    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        route_distance, route_load = 0, 0
        sequence, load_sequence, dist_from_prev_sequence = [], [], []

        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            sequence.append(node_index)
            node_demand = data['demands'][node_index]
            # print('vid:', vehicle_id, 'node_id', node_index, 'data id: ', data['ids'][node_index])
            # print(node_demand, data['vehicle_seed_id'], index)
            load_sequence.append(node_demand)
            route_load += node_demand

            previous_index = index
            index = solution.Value(routing.NextVar(index))
            print(previous_index, index, vehicle_id)
            route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            print(routing.GetArcCostForVehicle(previous_index, index, vehicle_id))

prints example return:

vid: 2 node_id 12 data id:  28
83.0 [1, 2, 5, 6] 12
12 18 2
0