mamut_routing_lib.checker

The static solution checker: the authority on what a CVRP/VRPTW solution costs.

check_solution validates a solution against an embedded-matrix instance (customer indices, single service, capacity, time windows with waiting at ready and hard due dates, fleet size) and prices it by summing the instance's arc_costs along each route, depot to depot, in plain Python arithmetic (ints stay ints, floats accumulate left to right). Every stored BKS cost is this value. Slim collection instances must be hydrated first (artifacts.hydrate_collection_instance); time-dependent instances use mamut_routing_lib.td.checker.

is_better_solution defines the order of each objective: MonoCost, Duration and FleetCostDuration compare the cost alone, HierarchicalVehicleCost compares the route count first.

SolutionCheckStatus

Bases: str, Enum

Outcome of a check: valid or the first violation met, in route order.

The checker stops at the first violation, so a solution with several defects reports only one. route_timing_infeasible is reserved for the time-dependent checker.

VALID class-attribute instance-attribute

VALID = 'valid'

INVALID_CUSTOMER_INDEX class-attribute instance-attribute

INVALID_CUSTOMER_INDEX = 'invalid_customer_index'

CUSTOMER_SERVED_MULTIPLE_TIMES class-attribute instance-attribute

CUSTOMER_SERVED_MULTIPLE_TIMES = (
    "customer_served_multiple_times"
)

VEHICLE_CAPACITY_EXCEEDED class-attribute instance-attribute

VEHICLE_CAPACITY_EXCEEDED = 'vehicle_capacity_exceeded'

TIME_WINDOW_VIOLATED class-attribute instance-attribute

TIME_WINDOW_VIOLATED = 'time_window_violated'

NOT_ALL_CUSTOMERS_SERVED class-attribute instance-attribute

NOT_ALL_CUSTOMERS_SERVED = 'not_all_customers_served'

TOO_MANY_VEHICLES_USED class-attribute instance-attribute

TOO_MANY_VEHICLES_USED = 'too_many_vehicles_used'

OBJECTIVE_VALUE_MISMATCH class-attribute instance-attribute

OBJECTIVE_VALUE_MISMATCH = 'objective_value_mismatch'

ROUTE_TIMING_INFEASIBLE class-attribute instance-attribute

ROUTE_TIMING_INFEASIBLE = 'route_timing_infeasible'

SolutionCheckResult

Bases: BaseModel

Status plus, when valid, the priced routing_cost and num_routes; error_message explains a rejection.

status instance-attribute

status: SolutionCheckStatus

routing_cost instance-attribute

routing_cost: int | float | None

num_routes instance-attribute

num_routes: int | None

error_message class-attribute instance-attribute

error_message: str = ''

is_valid

is_valid() -> bool

True when the status is valid.

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def is_valid(self) -> bool:
    """True when the status is ``valid``."""
    return self.status == SolutionCheckStatus.VALID

make_invalid classmethod

make_invalid(
    status: SolutionCheckStatus, error_message: str
) -> "SolutionCheckResult"

A rejection with status and a human-readable error_message.

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

@classmethod
def make_invalid(cls, status: SolutionCheckStatus, error_message: str) -> "SolutionCheckResult":
    """A rejection with ``status`` and a human-readable ``error_message``."""
    return cls(status=status, routing_cost=None, num_routes=None, error_message=error_message)

make_valid classmethod

make_valid(
    routing_cost: int | float, num_routes: int
) -> "SolutionCheckResult"

A valid result carrying the priced cost and route count.

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

@classmethod
def make_valid(cls, routing_cost: int | float, num_routes: int) -> "SolutionCheckResult":
    """A ``valid`` result carrying the priced cost and route count."""
    return cls(status=SolutionCheckStatus.VALID, routing_cost=routing_cost, num_routes=num_routes)

compute_route_cost

compute_route_cost(
    instance: AnyBenchmarkInstance, route: list[int]
) -> int | float

Cost of one route: depot -> route[0] -> ... -> route[-1] -> depot over instance.arc_costs (no feasibility check).

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def compute_route_cost(instance: AnyBenchmarkInstance, route: list[int]) -> int | float:
    """Cost of one route: ``depot -> route[0] -> ... -> route[-1] -> depot`` over ``instance.arc_costs`` (no feasibility check)."""
    total_cost: int | float = 0
    previous_node = instance.depot
    for customer in route:
        total_cost += instance.arc_costs[previous_node][customer]
        previous_node = customer
    total_cost += instance.arc_costs[previous_node][instance.depot]
    return total_cost

compute_solution_cost

compute_solution_cost(
    instance: AnyBenchmarkInstance,
    solution_or_routes: BenchmarkSolution
    | BenchmarkBKS
    | list[list[int]],
) -> int | float

Sum of compute_route_cost over the routes of a solution, BKS or plain route list.

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def compute_solution_cost(
    instance: AnyBenchmarkInstance,
    solution_or_routes: BenchmarkSolution | BenchmarkBKS | list[list[int]],
) -> int | float:
    """Sum of ``compute_route_cost`` over the routes of a solution, BKS or plain route list."""
    return sum(compute_route_cost(instance, route) for route in _iter_routes(solution_or_routes))

check_cvrp_solution

check_cvrp_solution(
    instance: BenchmarkInstanceCVRP,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult

Validate and price a solution on a CVRP instance (capacity, coverage, fleet; no timing).

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def check_cvrp_solution(
    instance: BenchmarkInstanceCVRP,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult:
    """Validate and price a solution on a CVRP instance (capacity, coverage, fleet; no timing)."""
    result = _check_common_route_constraints(instance, solution.routes, validate_time_windows=False)
    if result.is_valid() and solution.cost is not None and solution.cost != result.routing_cost:
        return SolutionCheckResult.make_invalid(
            SolutionCheckStatus.OBJECTIVE_VALUE_MISMATCH,
            "Provided cost does not match computed routing cost.",
        )
    return result

check_vrptw_solution

check_vrptw_solution(
    instance: BenchmarkInstance,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult

Validate and price a solution on a VRPTW instance (capacity, coverage, fleet, time windows with waiting).

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def check_vrptw_solution(
    instance: BenchmarkInstance,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult:
    """Validate and price a solution on a VRPTW instance (capacity, coverage, fleet, time windows with waiting)."""
    result = _check_common_route_constraints(instance, solution.routes, validate_time_windows=True)
    if result.is_valid() and solution.cost is not None and solution.cost != result.routing_cost:
        return SolutionCheckResult.make_invalid(
            SolutionCheckStatus.OBJECTIVE_VALUE_MISMATCH,
            "Provided cost does not match computed routing cost.",
        )
    return result

check_solution

check_solution(
    instance: AnyBenchmarkInstance,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult

Validate and price solution on a static instance; the single entry point.

Dispatches on the instance model. Raises TypeError for time-dependent instances (use mamut_routing_lib.td.check_td_solution) and for slim collection instances (hydrate them first).

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def check_solution(
    instance: AnyBenchmarkInstance,
    solution: BenchmarkSolution | BenchmarkBKS,
) -> SolutionCheckResult:
    """Validate and price ``solution`` on a static instance; the single entry point.

    Dispatches on the instance model. Raises ``TypeError`` for time-dependent
    instances (use ``mamut_routing_lib.td.check_td_solution``) and for slim
    collection instances (hydrate them first).
    """
    if not isinstance(instance, (BenchmarkInstance, BenchmarkInstanceCVRP)):
        raise TypeError(
            "Time-dependent instances require the ATF sidecar; "
            "use mamut_routing_lib.td.check_td_solution instead."
        )
    if isinstance(instance, BenchmarkInstanceCVRP):
        return check_cvrp_solution(instance, solution)
    return check_vrptw_solution(instance, solution)

get_objective_tuple

get_objective_tuple(
    routes: list[list[int]],
    cost: int | float,
    objective_function: ObjectiveFunction,
) -> tuple[int | float, ...]

The comparison key of a solution under objective_function: (cost,) or (num_routes, cost) for the hierarchical objective.

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def get_objective_tuple(
    routes: list[list[int]],
    cost: int | float,
    objective_function: ObjectiveFunction,
) -> tuple[int | float, ...]:
    """The comparison key of a solution under ``objective_function``: ``(cost,)`` or ``(num_routes, cost)`` for the hierarchical objective."""
    if objective_function in (
        ObjectiveFunction.MONO_COST,
        ObjectiveFunction.DURATION,
        ObjectiveFunction.FLEET_COST_DURATION,
    ):
        # Mono-objective: for FleetCostDuration the vehicle count is already
        # priced into the cost (duration + fleet_fixed_cost * num_routes), so
        # there is no lexicographic tier.
        return (cost,)
    return (len(routes), cost)

is_better_solution

is_better_solution(
    candidate_routes: list[list[int]],
    candidate_cost: int | float,
    existing_routes: list[list[int]],
    existing_cost: int | float,
    objective_function: ObjectiveFunction,
) -> bool

True when the candidate strictly precedes the existing solution under objective_function (see get_objective_tuple).

Source code in MAMUT-routing-tools/MAMUT-routing-lib/src/mamut_routing_lib/checker.py

def is_better_solution(
    candidate_routes: list[list[int]],
    candidate_cost: int | float,
    existing_routes: list[list[int]],
    existing_cost: int | float,
    objective_function: ObjectiveFunction,
) -> bool:
    """True when the candidate strictly precedes the existing solution under ``objective_function`` (see ``get_objective_tuple``)."""
    return get_objective_tuple(candidate_routes, candidate_cost, objective_function) < get_objective_tuple(
        existing_routes,
        existing_cost,
        objective_function,
    )