Program crashes for Routing Solver (Pickups and Deliveries) #4477
Description
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:
- 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):
data["pickups_deliveries"]contains 5 or more items.- Instead of calling
RoutingIndexManager()withdata["depot"]as the start and end point for all vehicles, usedata["starts"]anddata["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!