mamut_routing_tools.campaign.descriptors

Descriptive features of a CVRP instance.

Everywhere else in this project "metric" means an arc-cost metric variant (euclidean / shortest / fastest). This module is the other kind: the statistics that say what an instance is like -- how clustered its customers are, how uneven its demands are, how far off-centre its depot sits, how many customers a vehicle can carry. They exist so a campaign can choose instances that span the feature space instead of hoping a parameter grid happens to.

Two blocks, split by what they cost:

:class:InstanceDescriptors needs only coordinates, demands and capacity, so it can be computed for a large candidate pool before committing to any shortest path computation. That is what makes over-generate-then-select affordable.

:class:MetricDivergence needs the three materialized arc-cost matrices and is therefore computed after generation. It measures how far an instance departs from the Euclidean assumption -- the independent variable of the metric study.

Degenerate inputs (collinear customers, a constant demand vector) leave some features undefined; those fields come back as NaN rather than a guessed value, and the selector drops non-finite candidates.

InstanceDescriptors dataclass

InstanceDescriptors(
    n: int,
    extent_m: float,
    clark_evans_r: float,
    nnd_cv: float,
    radial_dispersion: float,
    depot_centrality: float,
    depot_eccentricity: float,
    demand_cv: float,
    demand_gini: float,
    demand_max_over_mean: float,
    demand_moran_i: float,
    lb_cap: int,
    route_size: float,
    capacity_slack: float,
)

What an instance looks like, from coordinates and demands alone.

MetricDivergence dataclass

MetricDivergence(
    detour_mean: float,
    detour_p90: float,
    asymmetry_shortest: float,
    asymmetry_fastest: float,
    rank_tau_eucl_short: float,
    rank_tau_eucl_fast: float,
    rank_tau_short_fast: float,
)

How far an instance's road metrics depart from its Euclidean one.

selection_features

selection_features(
    descriptors: InstanceDescriptors,
) -> list[float]

Where this instance sits in feature space, for the selector.

Not the same thing as the descriptors themselves. A statistic can be formally undefined while the instance still has a perfectly definite position on that axis, and conflating the two silently deletes instances:

demand_moran_i is undefined when every demand is equal, because there is no variance to correlate. But "are big demands next to big demands?" has an unambiguous answer for a constant field -- no, there is no such pattern -- and 0 is exactly where such an instance belongs on the autocorrelation axis. Leaving it NaN made every unit-demand instance unusable, which quietly removed one of the seven demand distributions from the whole benchmark.

Only that case is imputed. A NaN from a degenerate geometry (clark_evans_r on collinear customers) is a genuinely unusable instance and stays NaN, so :meth:EvaluatedCandidate.is_usable still rejects it.

Two features are taken in logs, because they are ratios spanning an order of magnitude and the selector z-scores whatever it is handed. On a linear scale the step from 50 to 200 customers per route counts eleven times the step from 3 to 16, so a max-min spread objective buys most of its score at one end of the axis and parks instances there. In v2 that put 39 of 100 instances in the longest route-size band against a quota floor of 7 -- the selector was not ignoring the axis, it was being paid to sit on its edge. A log scale prices the two ends the same way a reader does, in ratios.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/campaign/descriptors.py

def selection_features(descriptors: InstanceDescriptors) -> list[float]:
    """Where this instance sits in feature space, for the selector.

    Not the same thing as the descriptors themselves. A statistic can be
    formally undefined while the instance still has a perfectly definite
    position on that axis, and conflating the two silently deletes instances:

    ``demand_moran_i`` is undefined when every demand is equal, because there is
    no variance to correlate. But "are big demands next to big demands?" has an
    unambiguous answer for a constant field -- no, there is no such pattern --
    and 0 is exactly where such an instance belongs on the autocorrelation axis.
    Leaving it NaN made every unit-demand instance unusable, which quietly
    removed one of the seven demand distributions from the whole benchmark.

    Only that case is imputed. A NaN from a degenerate *geometry*
    (``clark_evans_r`` on collinear customers) is a genuinely unusable instance
    and stays NaN, so :meth:`EvaluatedCandidate.is_usable` still rejects it.

    Two features are taken in logs, because they are ratios spanning an order of
    magnitude and the selector z-scores whatever it is handed. On a linear scale
    the step from 50 to 200 customers per route counts eleven times the step from
    3 to 16, so a max-min spread objective buys most of its score at one end of
    the axis and parks instances there. In v2 that put 39 of 100 instances in the
    longest route-size band against a quota floor of 7 -- the selector was not
    ignoring the axis, it was being paid to sit on its edge. A log scale prices
    the two ends the same way a reader does, in ratios.
    """
    return [
        math.log(value) if name in LOG_SCALED_FEATURES and value > 0 else value
        for name, value in zip(SELECTION_FEATURES, descriptor_values(descriptors))
    ]

descriptor_values

descriptor_values(
    descriptors: InstanceDescriptors,
) -> list[float]

The selection descriptors in their own units, imputation applied.

Split from :func:selection_features because the two answer different questions and confusing them misreports the collection. The selector wants the transformed space; a reader wants customers per route to be a number of customers. Reporting the transformed value under the descriptor's own name published a route size of "1.097" for a set whose shortest routes hold three customers.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/campaign/descriptors.py

def descriptor_values(descriptors: InstanceDescriptors) -> list[float]:
    """The selection descriptors in their own units, imputation applied.

    Split from :func:`selection_features` because the two answer different
    questions and confusing them misreports the collection. The selector wants
    the transformed space; a *reader* wants customers per route to be a number
    of customers. Reporting the transformed value under the descriptor's own
    name published a route size of "1.097" for a set whose shortest routes hold
    three customers.
    """
    values: list[float] = []
    for name in SELECTION_FEATURES:
        value = getattr(descriptors, name)
        if (
            name == "demand_moran_i"
            and math.isnan(value)
            and descriptors.demand_cv == 0.0
        ):
            value = 0.0
        values.append(float(value))
    return values

compute_descriptors

compute_descriptors(
    coordinates: Sequence[Sequence[float]],
    demands: Sequence[int],
    capacity: int,
) -> InstanceDescriptors

Descriptors of one instance. Index 0 is the depot, in both sequences.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/campaign/descriptors.py

def compute_descriptors(
    coordinates: Sequence[Sequence[float]],
    demands: Sequence[int],
    capacity: int,
) -> InstanceDescriptors:
    """Descriptors of one instance. Index 0 is the depot, in both sequences."""
    points = np.asarray(coordinates, dtype=float)
    if points.ndim != 2 or points.shape[1] != 2:
        raise ValueError("coordinates must be a sequence of (x, y) pairs")
    if len(points) != len(demands):
        raise ValueError("coordinates and demands must have the same length")
    if capacity <= 0:
        raise ValueError("capacity must be positive")

    depot = points[0]
    customers = points[1:]
    n = len(customers)
    if n < 2:
        raise ValueError("at least 2 customers are required")

    quantities = np.asarray(demands[1:], dtype=float)
    if (quantities < 0).any():
        raise ValueError("customer demands must be non-negative")

    # --- spatial -----------------------------------------------------------
    area = _point_area(customers)
    distances, _ = cKDTree(customers).query(customers, k=2)
    nnd = distances[:, 1]
    mean_nnd = float(nnd.mean())
    if area > 0.0:
        expected_nnd = 0.5 * math.sqrt(area / n)
        clark_evans_r = mean_nnd / expected_nnd if expected_nnd > 0.0 else float("nan")
    else:
        clark_evans_r = float("nan")
    nnd_cv = float(nnd.std() / mean_nnd) if mean_nnd > 0.0 else float("nan")

    centroid = customers.mean(axis=0)
    radii = np.linalg.norm(customers - centroid, axis=1)
    mean_radius = float(radii.mean())
    radial_dispersion = float(radii.std() / mean_radius) if mean_radius > 0.0 else float("nan")
    depot_offset = float(np.linalg.norm(depot - centroid))
    depot_centrality = depot_offset / mean_radius if mean_radius > 0.0 else float("nan")

    # Where the depot sits in the instance's own "how remote is this point"
    # ordering. Scale-free and shape-free, unlike a raw distance.
    mean_to_customers = _mean_distance_to(points, customers)
    depot_eccentricity = float((mean_to_customers < mean_to_customers[0]).sum()) / n

    # --- demand ------------------------------------------------------------
    mean_demand = float(quantities.mean())
    if mean_demand > 0.0:
        demand_cv = float(quantities.std() / mean_demand)
        demand_max_over_mean = float(quantities.max() / mean_demand)
    else:
        demand_cv = float("nan")
        demand_max_over_mean = float("nan")
    demand_gini = _gini(quantities)
    demand_moran_i = _moran_i(customers, quantities, MORAN_NEIGHBOURS)

    # --- capacity ----------------------------------------------------------
    total_demand = float(quantities.sum())
    lb_cap = int(math.ceil(total_demand / capacity)) if total_demand > 0 else 0
    route_size = n / lb_cap if lb_cap > 0 else float("nan")
    capacity_slack = 1.0 - total_demand / (lb_cap * capacity) if lb_cap > 0 else float("nan")

    return InstanceDescriptors(
        n=n,
        extent_m=math.sqrt(area),
        clark_evans_r=clark_evans_r,
        nnd_cv=nnd_cv,
        radial_dispersion=radial_dispersion,
        depot_centrality=depot_centrality,
        depot_eccentricity=depot_eccentricity,
        demand_cv=demand_cv,
        demand_gini=demand_gini,
        demand_max_over_mean=demand_max_over_mean,
        demand_moran_i=demand_moran_i,
        lb_cap=lb_cap,
        route_size=route_size,
        capacity_slack=capacity_slack,
    )

compute_divergence

compute_divergence(
    euclidean: Sequence[Sequence[float]],
    shortest: Sequence[Sequence[float]],
    fastest: Sequence[Sequence[float]],
    *,
    seed: int = 0,
) -> MetricDivergence

How much the road metrics of one instance disagree with its Euclidean one.

seed fixes the pair subsample used for the rank correlations, so the reported values are reproducible for a given instance.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/campaign/descriptors.py

def compute_divergence(
    euclidean: Sequence[Sequence[float]],
    shortest: Sequence[Sequence[float]],
    fastest: Sequence[Sequence[float]],
    *,
    seed: int = 0,
) -> MetricDivergence:
    """How much the road metrics of one instance disagree with its Euclidean one.

    ``seed`` fixes the pair subsample used for the rank correlations, so the
    reported values are reproducible for a given instance.
    """
    d_eucl = np.asarray(euclidean, dtype=float)
    d_short = np.asarray(shortest, dtype=float)
    d_fast = np.asarray(fastest, dtype=float)
    if not (d_eucl.shape == d_short.shape == d_fast.shape):
        raise ValueError("the three matrices must have the same shape")
    if d_eucl.ndim != 2 or d_eucl.shape[0] != d_eucl.shape[1]:
        raise ValueError("matrices must be square")

    flat_eucl = _offdiagonal(d_eucl)
    flat_short = _offdiagonal(d_short)
    flat_fast = _offdiagonal(d_fast)

    positive = flat_eucl > 0.0
    if positive.any():
        detour = flat_short[positive] / flat_eucl[positive]
        detour_mean = float(detour.mean())
        detour_p90 = float(np.percentile(detour, 90))
    else:
        detour_mean = detour_p90 = float("nan")

    # One generator, drawn from in a fixed order: the three correlations use
    # different subsamples, and re-running with the same seed reproduces them.
    rng = np.random.default_rng(seed)
    return MetricDivergence(
        detour_mean=detour_mean,
        detour_p90=detour_p90,
        asymmetry_shortest=_asymmetry(d_short),
        asymmetry_fastest=_asymmetry(d_fast),
        rank_tau_eucl_short=_sampled_tau(flat_eucl, flat_short, rng),
        rank_tau_eucl_fast=_sampled_tau(flat_eucl, flat_fast, rng),
        rank_tau_short_fast=_sampled_tau(flat_short, flat_fast, rng),
    )