mamut_routing_tools.campaign.design

The candidate pool: what to consider generating, and what each one would be.

A campaign that wants measured diversity cannot pick parameters and hope. It enumerates far more candidates than it needs, works out what each one would look like without paying for it, and lets :mod:~.select keep the spread.

:class:CandidateSpec is a complete, deterministic recipe for one instance -- everything needed to rebuild it byte for byte later, which is what makes the "propose" and "generate" phases separable.

:func:evaluate_candidates is the cheap half of generation: it builds the customer selection and draws the demands exactly as the real generator will, then stops. No distance matrix is computed, which is the whole point -- the Dijkstra passes are what cost hours, and they are only spent on winners.

CandidateSpec dataclass

CandidateSpec(city: str, osm_path: Path, n: int, method: str, demand_type: int, avg_route_size: int, depot_mode: str, customer_mode: str, cluster_seeds: int, cluster_decay_meters: float, hybrid_poi_share: float, poi_attach_mode: str = CAMPAIGN_POI_ATTACH_MODE, categories: tuple[str, ...] = CAMPAIGN_POI_CATEGORIES, distortion_stratum: str | None = None, tier: str = 'main', rung_key: str = '')

A complete, deterministic recipe for one base instance.

EvaluatedCandidate dataclass

EvaluatedCandidate(spec: CandidateSpec, descriptors: InstanceDescriptors, resolved_n: int, effective_method: str = '', poi_fraction: float = 0.0)

A candidate together with what it would look like if generated.

is_usable

is_usable() -> bool

Servable at the requested size, a genuine VRP, and fully described.

The size check is not pedantry. A city whose amenities are sparse serves a POI request short -- Nairobi's extract has 27 amenities in total -- and the generator only warns. Accepting the short instance would put a candidate selected for the 701-1000 bucket into the tree at n=198, which is exactly the kind of silent drift a designed benchmark must not have.

Neither is the route-count check. This gate read lb_cap >= 2 in v2 -- "not a TSP" -- and 22 of the 110 published bases cleared it while still being trivially partitioned, 19 of them into exactly two routes. Two is not a fleet. The band admissibility rule in :mod:~.ladder is what makes the guarantee hold by construction; this is the backstop that catches the one case it cannot, where Q = ceil(r * mean demand) rounds up far enough to cost a route at the very edge of a band.

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

def is_usable(self) -> bool:
    """Servable at the requested size, a genuine VRP, and fully described.

    The size check is not pedantry. A city whose amenities are sparse serves
    a POI request short -- Nairobi's extract has 27 amenities in total -- and
    the generator only warns. Accepting the short instance would put a
    candidate selected for the 701-1000 bucket into the tree at n=198, which
    is exactly the kind of silent drift a designed benchmark must not have.

    Neither is the route-count check. This gate read ``lb_cap >= 2`` in v2 --
    "not a TSP" -- and 22 of the 110 published bases cleared it while still
    being trivially partitioned, 19 of them into exactly two routes. Two is
    not a fleet. The band admissibility rule in :mod:`~.ladder` is what makes
    the guarantee hold by construction; this is the backstop that catches the
    one case it cannot, where ``Q = ceil(r * mean demand)`` rounds up far
    enough to cost a route at the very edge of a band.
    """
    return (
        self.resolved_n >= self.spec.n
        and self.descriptors.lb_cap >= CAMPAIGN_MIN_ROUTES
        and all(isfinite(v) for v in self.feature_vector())
    )

stable_seed

stable_seed(*parts: Any) -> int

A seed derived from what the instance is, never from a counter.

Mirrors family.family._stable_seed: re-running the campaign, or regenerating one instance on its own, must land on the same draw.

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

def stable_seed(*parts: Any) -> int:
    """A seed derived from what the instance *is*, never from a counter.

    Mirrors ``family.family._stable_seed``: re-running the campaign, or
    regenerating one instance on its own, must land on the same draw.
    """
    return zlib.crc32("|".join(str(part) for part in parts).encode("utf-8"))

enumerate_for_rungs

enumerate_for_rungs(assignments: Sequence[Any], *, osm_dir: str | Path = 'osmdata', per_rung: int = 6, base_seed: int = 0, tier: str = 'main', categories: Sequence[str] = CAMPAIGN_POI_CATEGORIES, poi_attach_mode: str = CAMPAIGN_POI_ATTACH_MODE) -> list[CandidateSpec]

per_rung candidates for each ladder position.

The counterpart of :func:enumerate_candidates for a campaign that has already decided what each instance is -- city, size and sourcing method come from a :class:~.ladder.RungAssignment and are not up for negotiation here. What is still free is what the instance is like: how demand is distributed, how tightly the vehicles are loaded, where the depot sits and whether the customers cluster. Those are drawn as balanced columns across the whole pool exactly as before, so the selector still gets a spread to choose from on every axis it can still move.

Splitting it this way is what stops the two decisions from fighting. Drawn together, a size the city could not serve was silently downgraded; drawn in order, the size is guaranteed feasible before any descriptor is computed.

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

def enumerate_for_rungs(
    assignments: Sequence[Any],
    *,
    osm_dir: str | Path = "osmdata",
    per_rung: int = 6,
    base_seed: int = 0,
    tier: str = "main",
    categories: Sequence[str] = CAMPAIGN_POI_CATEGORIES,
    poi_attach_mode: str = CAMPAIGN_POI_ATTACH_MODE,
) -> list[CandidateSpec]:
    """``per_rung`` candidates for each ladder position.

    The counterpart of :func:`enumerate_candidates` for a campaign that has
    already decided *what* each instance is -- city, size and sourcing method
    come from a :class:`~.ladder.RungAssignment` and are not up for negotiation
    here. What is still free is what the instance is *like*: how demand is
    distributed, how tightly the vehicles are loaded, where the depot sits and
    whether the customers cluster. Those are drawn as balanced columns across
    the whole pool exactly as before, so the selector still gets a spread to
    choose from on every axis it can still move.

    Splitting it this way is what stops the two decisions from fighting. Drawn
    together, a size the city could not serve was silently downgraded; drawn in
    order, the size is guaranteed feasible before any descriptor is computed.
    """
    if per_rung < 1:
        raise ValueError("per_rung must be >= 1")
    if not assignments:
        return []

    # A RungAssignment carries the extract's *file name*, not its path: capacity
    # measurements are shared across checkouts and an absolute path would not
    # survive the trip. The directory is supplied here instead.
    root = Path(osm_dir)
    total = per_rung * len(assignments)
    rng = np.random.default_rng(
        stable_seed("rungs", tier, base_seed, len(assignments), per_rung)
    )
    # ``avg_route_size`` is absent from this table on purpose. Which bands keep an
    # instance a genuine VRP depends on ``n``, so the band comes from the rung
    # alongside the city and the size; drawing it here as a balanced column over
    # all seven levels is precisely what put a 50-200 customer route target on a
    # hundred-customer instance in v2.
    columns = {
        "demand_type": _balanced_column(DEMAND_TYPES, total, rng),
        "depot_mode": _balanced_column(DEPOT_MODES, total, rng),
        "customer_mode": _balanced_column(CUSTOMER_MODES, total, rng),
        "cluster_seeds": _balanced_column(CLUSTER_SEEDS, total, rng),
        "cluster_decay_meters": _balanced_column(CLUSTER_DECAY_METERS, total, rng),
        "hybrid_poi_share": _balanced_column(HYBRID_POI_SHARES, total, rng),
    }

    specs: list[CandidateSpec] = []
    for index in range(total):
        rung = assignments[index // per_rung]
        specs.append(
            CandidateSpec(
                city=rung.city,
                osm_path=root / rung.osm_file,
                n=int(rung.n),
                method=str(rung.method),
                demand_type=int(columns["demand_type"][index]),
                avg_route_size=int(rung.avg_route_size),
                depot_mode=str(columns["depot_mode"][index]),
                customer_mode=str(columns["customer_mode"][index]),
                cluster_seeds=int(columns["cluster_seeds"][index]),
                cluster_decay_meters=float(columns["cluster_decay_meters"][index]),
                hybrid_poi_share=float(columns["hybrid_poi_share"][index]),
                poi_attach_mode=poi_attach_mode,
                categories=tuple(categories),
                distortion_stratum=rung.distortion_stratum,
                tier=tier,
                rung_key=rung.rung_key,
            )
        )
    return specs

enumerate_candidates

enumerate_candidates(cities: Sequence[tuple[str, Path]], profiles: Sequence[CityProfile] = (), *, per_city: int = 8, size_grid: Sequence[int] = MAIN_SIZE_GRID, methods: Sequence[str] = METHODS, size_ceiling: Mapping[str, int] | None = None, tier: str = 'main', base_seed: int = 0) -> list[CandidateSpec]

per_city candidates for every city, balanced on every design axis.

methods narrows the sourcing axis. The POI-only tier passes a single method because "every customer is a real amenity" is the point of that tier, not one option among three.

size_ceiling caps n per city. Sizes are drawn from a grid that knows nothing about how many customers a given city can actually serve, so without it a POI-only tier proposes n = 5000 in a city holding 1800 amenities and discovers the shortfall only after paying for the evaluation. The cap replaces an over-large draw with the largest grid size that still fits, and drops the candidate when even the smallest does not.

The route-size band is drawn as a balanced column and then repaired against the size, because which bands leave a real fleet depends on n: a target of 50-200 customers per route is an ordinary instance at n = 4000 and a two-route degenerate at n = 272. A draw the size cannot support falls back to the largest admissible band, which keeps the column's ordering -- longer draws still get longer routes -- without letting it off the end.

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

def enumerate_candidates(
    cities: Sequence[tuple[str, Path]],
    profiles: Sequence[CityProfile] = (),
    *,
    per_city: int = 8,
    size_grid: Sequence[int] = MAIN_SIZE_GRID,
    methods: Sequence[str] = METHODS,
    size_ceiling: Mapping[str, int] | None = None,
    tier: str = "main",
    base_seed: int = 0,
) -> list[CandidateSpec]:
    """``per_city`` candidates for every city, balanced on every design axis.

    ``methods`` narrows the sourcing axis. The POI-only tier passes a single
    method because "every customer is a real amenity" is the point of that tier,
    not one option among three.

    ``size_ceiling`` caps ``n`` per city. Sizes are drawn from a grid that knows
    nothing about how many customers a given city can actually serve, so without
    it a POI-only tier proposes n = 5000 in a city holding 1800 amenities and
    discovers the shortfall only after paying for the evaluation. The cap
    replaces an over-large draw with the largest grid size that still fits, and
    drops the candidate when even the smallest does not.

    The route-size band is drawn as a balanced column and then *repaired against
    the size*, because which bands leave a real fleet depends on ``n``: a target
    of 50-200 customers per route is an ordinary instance at n = 4000 and a
    two-route degenerate at n = 272. A draw the size cannot support falls back to
    the largest admissible band, which keeps the column's ordering -- longer
    draws still get longer routes -- without letting it off the end.
    """
    if per_city < 1:
        raise ValueError("per_city must be >= 1")
    if not cities:
        return []
    if not methods:
        raise ValueError("methods must not be empty")

    stratum_of = {profile.city: profile.distortion_stratum for profile in profiles}
    total = per_city * len(cities)
    rng = np.random.default_rng(stable_seed("enumerate", tier, base_seed, len(cities), per_city))

    columns = {
        "n": _balanced_column(size_grid, total, rng),
        "method": _balanced_column(methods, total, rng),
        "demand_type": _balanced_column(DEMAND_TYPES, total, rng),
        "avg_route_size": _balanced_column(AVG_ROUTE_SIZES, total, rng),
        "depot_mode": _balanced_column(DEPOT_MODES, total, rng),
        "customer_mode": _balanced_column(CUSTOMER_MODES, total, rng),
        "cluster_seeds": _balanced_column(CLUSTER_SEEDS, total, rng),
        "cluster_decay_meters": _balanced_column(CLUSTER_DECAY_METERS, total, rng),
        "hybrid_poi_share": _balanced_column(HYBRID_POI_SHARES, total, rng),
    }

    ordered_sizes = sorted(size_grid)
    specs: list[CandidateSpec] = []
    for index in range(total):
        city, osm_path = cities[index // per_city]
        n = int(columns["n"][index])
        if size_ceiling is not None:
            ceiling = int(size_ceiling.get(city, 0))
            if n > ceiling:
                fitting = [size for size in ordered_sizes if size <= ceiling]
                if not fitting:
                    continue
                n = fitting[-1]
        specs.append(
            CandidateSpec(
                city=city,
                osm_path=Path(osm_path),
                n=n,
                method=str(columns["method"][index]),
                demand_type=int(columns["demand_type"][index]),
                avg_route_size=_admissible_band(int(columns["avg_route_size"][index]), n),
                depot_mode=str(columns["depot_mode"][index]),
                customer_mode=str(columns["customer_mode"][index]),
                cluster_seeds=int(columns["cluster_seeds"][index]),
                cluster_decay_meters=float(columns["cluster_decay_meters"][index]),
                hybrid_poi_share=float(columns["hybrid_poi_share"][index]),
                distortion_stratum=stratum_of.get(city),
                tier=tier,
            )
        )
    return specs

evaluate_candidate

evaluate_candidate(spec: CandidateSpec) -> EvaluatedCandidate

What this candidate would be, short of its distance matrices.

Rebuilds the customer selection and draws the demands through exactly the calls generate_single_instance makes, from exactly the same seed, so the descriptors describe the instance that generation will actually produce.

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

def evaluate_candidate(spec: CandidateSpec) -> EvaluatedCandidate:
    """What this candidate would be, short of its distance matrices.

    Rebuilds the customer selection and draws the demands through exactly the
    calls ``generate_single_instance`` makes, from exactly the same seed, so the
    descriptors describe the instance that generation will actually produce.
    """
    selection = build_generation_selection(spec.to_request())
    graph = selection.graph
    coordinates = [graph.node_enu[graph.node_of[v]][:2] for v in selection.vertices]

    customer_ll = list(zip(selection.poi_lats[1:], selection.poi_lons[1:]))
    demand_values, _total, _maximum, route_target = generate_demands(
        random.Random(spec.seed), customer_ll, spec.demand_type, spec.avg_route_size
    )
    capacity = capacity_from_avg_route_size(route_target, demand_values)

    customer_tags = selection.source_tags[1:]
    poi_count = sum(1 for tag in customer_tags if is_poi_source_tag(tag))
    return EvaluatedCandidate(
        spec=spec,
        descriptors=compute_descriptors(coordinates, [0, *demand_values], capacity),
        resolved_n=len(selection.vertices) - 1,
        effective_method=str(selection.params["method"]),
        poi_fraction=poi_count / len(customer_tags) if customer_tags else 0.0,
    )

evaluate_candidates

evaluate_candidates(specs: Sequence[CandidateSpec], *, jobs: int = 1, drop_unusable: bool = True, on_progress: Callable[[str, int, int], None] | None = None) -> list[EvaluatedCandidate]

Evaluate a whole pool, one process per city.

drop_unusable=False returns everything that evaluated, letting the caller apply :meth:EvaluatedCandidate.is_usable itself. That is what a campaign wants for its saved pool: usability depends on the feature space, and re-deciding it must not cost another pass over every OSM extract.

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

def evaluate_candidates(
    specs: Sequence[CandidateSpec],
    *,
    jobs: int = 1,
    drop_unusable: bool = True,
    on_progress: Callable[[str, int, int], None] | None = None,
) -> list[EvaluatedCandidate]:
    """Evaluate a whole pool, one process per city.

    ``drop_unusable=False`` returns everything that evaluated, letting the
    caller apply :meth:`EvaluatedCandidate.is_usable` itself. That is what a
    campaign wants for its saved pool: usability depends on the feature space,
    and re-deciding it must not cost another pass over every OSM extract.
    """
    by_city: dict[str, list[CandidateSpec]] = {}
    for spec in specs:
        by_city.setdefault(spec.city, []).append(spec)
    groups = list(by_city.items())

    evaluated: list[EvaluatedCandidate] = []
    if jobs <= 1:
        for index, (city, city_specs) in enumerate(groups, start=1):
            if on_progress is not None:
                on_progress(city, index, len(groups))
            evaluated.extend(_evaluate_city(city_specs))
    else:
        with ProcessPoolExecutor(max_workers=jobs) as pool:
            futures = {
                pool.submit(_evaluate_city, city_specs): city for city, city_specs in groups
            }
            for index, (future, city) in enumerate(futures.items(), start=1):
                if on_progress is not None:
                    on_progress(city, index, len(groups))
                evaluated.extend(future.result())

    if not drop_unusable:
        return evaluated

    usable = [candidate for candidate in evaluated if candidate.is_usable()]
    dropped = len(evaluated) - len(usable)
    if dropped:
        short = sum(1 for c in evaluated if c.resolved_n < c.spec.n)
        warnings.warn(
            f"dropped {dropped} candidate(s): {short} could not be served at the requested "
            f"size, {dropped - short} had LB_cap < {CAMPAIGN_MIN_ROUTES} or an "
            "undefined descriptor",
            stacklevel=2,
        )
    return usable

resolve_cities

resolve_cities(osm_dir: str | Path, names: Iterable[str] | None = None) -> list[tuple[str, Path]]

(city_slug, osm_path) for the extracts on disk, slugged like the tree.

Aix-en-Provence.osm becomes aix_en_provence, matching the place slugs the benchmark tree and the website already use.

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

def resolve_cities(osm_dir: str | Path, names: Iterable[str] | None = None) -> list[tuple[str, Path]]:
    """``(city_slug, osm_path)`` for the extracts on disk, slugged like the tree.

    ``Aix-en-Provence.osm`` becomes ``aix_en_provence``, matching the place slugs
    the benchmark tree and the website already use.
    """
    directory = Path(osm_dir)
    wanted = {slugify(name) for name in names} if names else None
    cities: list[tuple[str, Path]] = []
    for path in sorted(directory.glob("*.osm")):
        slug = slugify(path.stem)
        if wanted is None or slug in wanted:
            cities.append((slug, path))
    if wanted is not None:
        missing = wanted - {slug for slug, _ in cities}
        if missing:
            raise FileNotFoundError(f"no OSM extract for: {', '.join(sorted(missing))}")
    return cities