Routing solver 9.2 returning infeasible solution (time windows violated) | Python

[vilumaa]

Version: 9.2.9972 Language: Python 3.9.7 Routing solver Windows 10

Runnable python script:

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

def compile_solution(data, manager, routing, assignment):
    """Compiles solution"""
    solution = {}
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    all_nodes = set(range(len(data["time_matrix"])))
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        while not routing.IsEnd(index):
            if vehicle_id not in solution.keys():
                solution[vehicle_id] = []
            time_var = time_dimension.CumulVar(index)
            solution[vehicle_id].append(
                (
                    manager.IndexToNode(index),
                    assignment.Min(time_var),
                    assignment.Max(time_var),
                )
            )
            if manager.IndexToNode(index) in all_nodes:
                all_nodes.remove(manager.IndexToNode(index))
            index = assignment.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        total_time += assignment.Min(time_var)
    solution["unperformed"] = [(node, None, None) for node in list(all_nodes)]
    return solution

def optimize(data):
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]), data["num_vehicles"], data["starts"], data["ends"]
    )
    routing = pywrapcp.RoutingModel(manager)

    # [objective]
    def time_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 data["time_matrix"][from_node][to_node]

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

    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        data["allowed_waiting_time"],  # allow waiting time
        data["max_time_per_vehicle"],  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time,
    )
    time_dimension = routing.GetDimensionOrDie(time)

    counter = "Counter"
    routing.AddConstantDimension(
        1,  # increment by one every time
        data["max_nodes_per_vehicle"],  # a max number of nodes a vehicle can visit
        True,  # force starting count to zero
        counter,
    )
    counter_dimension = routing.GetDimensionOrDie(counter)
    counter_dimension.SetGlobalSpanCostCoefficient(data["span_cost"])

    # [start_end_objective]
    for i in range(data["num_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i))
        )
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

    # [disjunction]
    for node in range(1, len(data["time_matrix"])):
        routing.AddDisjunction([manager.NodeToIndex(node)], data["penalty_cost"])

    # the objective function:
    # + 1000 for every dropped node [disjunctions]
    # + sum of time_matrix entries that we choose [SetArcCostEvaluatorOfAllVehicles]
    # + start and end time of every vehicle [AddVariableMinimizedByFinalizer]
    # + 100 * (max(end_time_of_vehicles) - min(start_time_of_vehicles)) [span]

    # [time_windows]
    for location_idx, time_window in data["time_windows"].items():
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

    # [pickups_deliveries]
    for pickup, dropoff in data["pickups_deliveries"]:
        pickup_index = manager.NodeToIndex(pickup)
        dropoff_index = manager.NodeToIndex(dropoff)
        routing.AddPickupAndDelivery(pickup_index, dropoff_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(dropoff_index)
        )
        routing.solver().Add(
            time_dimension.CumulVar(pickup_index)
            <= time_dimension.CumulVar(dropoff_index)
        )

    # [max_time_in_vehicle]
    for pickup_node, dropoff_node in data["pickups_deliveries"]:
        pickup_index = manager.NodeToIndex(pickup_node)
        dropoff_index = manager.NodeToIndex(dropoff_node)
        routing.solver().Add(
            time_dimension.CumulVar(pickup_index) + data["max_time_in_vehicle"]
            >= time_dimension.CumulVar(dropoff_index)
        )

    # [capacity]
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

    # [solver_operations]
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
    )

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.seconds = data["max_iteration_time"]
    search_parameters.log_search = True

    assignment = routing.SolveWithParameters(search_parameters)
    if assignment:
        print(
            "Objective from assignment.ObjectiveValue(): %s"
            % assignment.ObjectiveValue()
        )
        return (
            compile_solution(data, manager, routing, assignment),
            assignment.ObjectiveValue(),
        )
    else:
        return {}, float("inf")

def main():
    data = {
        "time_matrix": [
            [0, 187, 60, 187, 60],
            [186, 0, 154, 150, 154],
            [60, 153, 0, 153, 150],
            [186, 150, 154, 0, 154],
            [60, 153, 150, 153, 0],
        ],
        "pickups_deliveries": [[1, 2], [3, 4]],
        "time_windows": {2: [1015, 1030], 4: [1015, 1030]},
        "num_vehicles": 1,
        "demands": {1: 1, 2: -1, 3: 1, 4: -1},
        "starts": [0],
        "ends": [0],
        "vehicle_capacities": [7],
        "pairs": {1: 2, 2: 1, 3: 4, 4: 3},
        "allowed_waiting_time": 3000,
        "max_time_per_vehicle": 50000,
        "max_nodes_per_vehicle": 29,
        "span_cost": 100,
        "penalty_cost": 10000,
        "max_time_in_vehicle": 45,
        "max_iteration_time": 25,
    }
    solution, _ = optimize(data)

    print(solution)

if __name__ == "__main__":
    main()

Expect no solution since max_time_in_vehicle=45 but each pickup/dropoff pair in time_matrix > 45.

Instead, I get a "feasible" solution that clearly violates travel time: {0: [(0, 0, 0), (3, 970, 1015), (1, 970, 1015), (4, 1015, 1015), (2, 1015, 1015)], 'unperformed': []} Where dict key is vehicle (0), and tuples are (node_id, time_var.Min(), time_var.Max()).

Am I wrong in expecting that if assignment: will only trigger when there is a feasible solution?

[lperron]

the max_time_in_vehicle is the max waiting time not including transit between 2 visits

see: https://developers.google.com/optimization/routing/dimensions

[vilumaa]

Are you saying that the "each parcel can only spend at most 45 minutes in a vehicle (max_time_in_vehicle)" constraint implementation is incorrect? I believe I have seen this in the forums before, including here

Nevertheless, even commenting out that constraint, I still get a solution: {0: [(0, 0, 0), (3, 0, 1015), (1, 0, 1015), (4, 1015, 1015), (2, 1015, 1015)], 'unperformed': []} Implying the driving time between nodes 4 and 2 is 0, yet when I look at the time_matrix it's 150. Or am I misinterpreting the output time windows obtained by assignment.Max(time_var)?

Moreover, by adding a solution callback, and recording the best objective found during the search, I can see that the solution callback has never been triggered. Yet, it does return a "feasible" solution...

class SolutionCallback:
    """Solution callback for debugging"""

    def __init__(self, model):
        self.model = model
        self.best_objective = float("inf")

    def __call__(self):
        if self.model.CostVar().Max() < self.best_objective:
            self.best_objective = self.model.CostVar().Max()

solution_callback = SolutionCallback(routing)
routing.AddAtSolutionCallback(solution_callback)

Output:

Objective from assignment.ObjectiveValue(): 500
Objective from callback = inf
{0: [(0, 0, 0), (3, 0, 1015), (1, 0, 1015), (4, 1015, 1015), (2, 1015, 1015)], 'unperformed': []}

[lperron]

the code uses max_time_PER_vehicle, which is 50k.