Program crashes for Routing Solver (Pickups and Deliveries)

[jpconde]

What version of OR-Tools and what language are you using?
Version: v9.11 (lower versions don't work either. At least 9.9, 9.5 and 9.2)
Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing solver

What operating system (Linux, Windows, ...) and version?
Colab Jupyter Notebook, MacOS

What did you do?
Steps to reproduce the behavior:

1. Run the following program:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["time_matrix"] = [
        # fmt: off
        [0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 0],
        [1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5, 0],
        [2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4, 0], 
        [3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3, 0],
        [1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 0], 
        [2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 0], 
        [3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 0],
        [4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 0],
        [2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 0],
        [3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 0], 
        [4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 0], 
        [5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 0], 
        [3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 0], 
        [4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 0], 
        [5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 0], 
        [6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        # fmt: on
    ]
    data["pickups_deliveries"] = [
        [1, 3], 
        [2, 5],
        [4, 14], 
        [6, 14], 
        [7, 3], 
        #[8, 3], 
        #[9, 14], 
        #[10, 5], 
        #[12, 14], 
        #[13, 3],
        #[15, 14], 
    ]
    data["num_vehicles"] = 4
    data["depot"] = 0
    data["starts"] = [0, 11]
    data["ends"] = [16, 16] # End location is not relevant, so using dummy one.
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    total_distance = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += f" {manager.IndexToNode(index)} -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f"{manager.IndexToNode(index)}\n"
        plan_output += f"Time for the route: {route_distance}m\n"
        print(plan_output)
        total_distance += route_distance
    print(f"Total time for all routes: {total_distance}m")


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]), data["num_vehicles"], data["depot"] #, data["starts"], data["ends"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    # Define cost of each arc.
    def time_callback(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["time_matrix"][from_node][to_node]

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

    # Add Distance constraint.
    dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        False,  # start cumul to zero
        dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(dimension_name)
    time_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.
    for request in data["pickups_deliveries"]:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index)
        )
        routing.solver().Add(
            time_dimension.CumulVar(pickup_index)
            <= time_dimension.CumulVar(delivery_index)
        )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.FromSeconds(1)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution")


if __name__ == "__main__":
    main()

What did you expect to see
I expected the solver to return either a valid solution or no solution.

What did you see instead?
The program crashes after calling routing.SolveWithParameters(search_parameters).

Error message (when run locally):

libc++abi: terminating due to uncaught exception of type std::__1::bad_function_call: std::exception

For the Colab Jupyter Notebook, the error information is not available, but I assume it is the same.

Anything else we should know about your project / environment
Conditions that make it crash (any):

1. data["pickups_deliveries"] contains 5 or more items.
2. Instead of calling RoutingIndexManager() with data["depot"] as the start and end point for all vehicles, use data["starts"] and data["ends"] as start and end points.

Other comments:

• Most code has been copied from the Vehicle Routing with Pickups and Deliveries example code. Distance concept has been replaced with Time.
• search_parameters.first_solution_strategy has been changed to PATH_CHEAPEST_ARC. However, it does not work with PARALLEL_CHEAPEST_INSERTION either. Removing GUIDED_LOCAL_SEARCH doesn't help either.
• A dummy location with zero distance to/from all nodes has been added, as it can be seen in the time matrix.

Thanks!

[lperron]

you cannot reuse the same node in two P&D pairs.

[jpconde]

Hi @lperron,

thanks for your reply.

The documentation is not clear about this precondition, but I guess I can get away by using dummy points.

However, the program still crashes when I use data["starts"] and data["ends"] for start and end points for the vehicles instead of just data["depot"] for everything. No matter if the P&D pairs don't repeat nodes, if there is just one pair, or if there are no pairs at all.

Thanks.

[Mizux]

However, the program still crashes when I use data["starts"] and data["ends"] for start and end points for the vehicles instead of just data["depot"] for everything. No matter if the P&D pairs don't repeat nodes, if there is just one pair, or if there are no pairs at all.

Since you set VehcileNumber to 4, your starts and ends arrays must be of length 4.
note: for start/ends you can reuse several time the same index.
e.g. 2 vehicles at both starts: data["starts"] = [0, 0, 11, 11] and sames for ends...

[jpconde]

Thanks, @Mizux. It works now.

[lperron]

you cannot have start and ends being P&D nodes. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le dim. 22 déc. 2024 à 20:45, Juan Pablo Conde ***@***.***> a écrit :

…

Hi @lperron <https://github.com/lperron>, thanks for your reply. The documentation is not clear about this precondition, but I guess I can get away by using dummy points. However, the program still crashes when I use data["starts"] and data["ends"] for start and end points for the vehicles instead of just data["depot"] for everything. No matter if the P&D pairs don't repeat nodes, if there is just one pair, or if there are no pairs at all. Thanks. — Reply to this email directly, view it on GitHub <#4477 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3L6TNYEQMHYSGVY7ID2G4JFRAVCNFSM6AAAAABUALADNOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKNJYGU3TIMRWGQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[jpconde]

Even if I remove all P&D pairs, it still crashes.