Repair operators¶
The pyvrp.repair
module provides operators that are responsible for repairing a Solution
after destruction in a large neighbourhood search (LNS) setting.
- greedy_repair(solution: Solution, unplanned: list[int], data: ProblemData, cost_evaluator: CostEvaluator) Solution ¶
- greedy_repair(routes: list[Route], unplanned: list[int], data: ProblemData, cost_evaluator: CostEvaluator) Solution
Greedy repair operator. This operator inserts each client in the list of unplanned clients into the solution. It does so by evaluating all possible moves and applying the best one for each client, resulting in a quadratic runtime.
- Raises:
ValueError: When the solution is empty but the list of unplanned clients is not.
- nearest_route_insert(routes: list[Route], unplanned: list[int], data: ProblemData, cost_evaluator: CostEvaluator) Solution ¶
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.- 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 repaired solution.
- Return type:
- Raises:
ValueError – When the list of routes is empty but the list of unplanned clients is not.