Repair operators¶

The pyvrp.repair module provides operators that are responsible for repairing a solution after destruction in a large neighbourhood search (LNS) setting. These operators take a given list of routes and insert any unplanned clients into these routes. To allow fine-grained control over the number of routes and vehicles used, no new routes are created: clients are only inserted into the given routes.

greedy_repair(routes: list[Route], unplanned: list[int], data: ProblemData, cost_evaluator: CostEvaluator) → list[Route]¶

Greedy repair operator. This operator inserts each client in the list of unplanned clients into the given routes. It does so by evaluating all possible moves and applying the best one for each client, resulting in a quadratic runtime.

Parameters:

routes: list[Route]¶: List of routes.
unplanned: list[int]¶: Unplanned clients to insert into the routes.
data: ProblemData¶: Problem data instance.
cost_evaluator: CostEvaluator¶: Cost evaluator to use when evaluating insertion moves.

Returns:

The list of repaired routes.

Return type:

list[Route]

Raises:

ValueError – When the list of routes is empty but the list of unplanned clients is not.

nearest_route_insert(routes: list[Route], unplanned: list[int], data: ProblemData, cost_evaluator: CostEvaluator) → list[Route]¶

Nearest route insert operator. This operator inserts each client in the list of unplanned clients into one of the given routes. It does so by first determining which route has a center point closest to the client, and then evaluating all possible insert moves of the client into that closest route. The best move is applied. This operator has a quadratic runtime in the worst case, but is typically much more efficient than greedy_repair(), at the cost of some solution quality.