mamut_routing_tools.family.tw_synthesis

Stage-2 (VRPTW) synthesis of service times and time windows (v2, Stream 12').

The single implementation of the family's name-seeded synthesis (language-boundary tier 2). One service-time set exists per base, shared by every VRPTW instance and TDVRPTW subinstance. Three TW sets exist per base:

• td-shared (the TD-paired set): route-centered over the static free-flow fastest travel times, seeded from the base name, shared verbatim (post build-td repair) by the plain VRPTW instance and every TDVRPTW subinstance. The v1 per-variant, TD-anchored synthesis is retired: anchoring windows on each traffic variant's own arrivals partially cancelled the traffic effect the family is built to measure.
• tight (static-only): same route-centered machinery and hence the same window centers as td-shared, but much narrower widths (a controlled width comparison over identical demand geometry).
• spread (static-only): window centers drawn uniformly over each customer's individually feasible interval, destroying the route structure (Solomon R-class flavor); widths follow the td-shared distribution.

The static-only sets are never audited under traffic and are not the TDVRPTW windows; they exist to widen the static VRPTW layer of the family.

Values are integer seconds (exact in binary64). Feasibility bounds at free flow: a window [e, l] guarantees l >= t_0i (a vehicle leaving the depot at the horizon start reaches the customer by l) and l + s_i + t_i0 <= horizon end (starting service at l returns in time). For td-shared, stage 3 (build-td) then certifies the complete anchor routes under every traffic overlay and applies minimal shared deadline lifts. The static-only sets are feasible by construction under the free-flow fastest matrix (route-centered: the deterministic multi-route anchor serves everyone in-window; spread: every customer is individually serveable, so singleton routes fit the horizon) and receive no repair.

All randomness comes from random.Random seeded per base and TW set; the windows are shipped data, never re-derived at load time.

synthesize_service_times

synthesize_service_times(
    rng: Random, num_customers: int
) -> list[int]

Gaussian integer service times, mean ~1% of the horizon.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/family/tw_synthesis.py

def synthesize_service_times(rng: Random, num_customers: int) -> list[int]:
    """Gaussian integer service times, mean ~1% of the horizon."""
    horizon = HORIZON_END - HORIZON_START
    mean_ratio = _clamp(rng.gauss(0.0, 1.0) * SERVICE_MEAN_RATIO_STD + SERVICE_MEAN_RATIO, 0.001, 0.2)
    mean_service = horizon * mean_ratio
    upper = max(1, int(mean_service * 2))
    service_times = [0]
    for _ in range(num_customers):
        sampled = rng.gauss(0.0, 1.0) * (mean_service / 2.0) + mean_service
        service_times.append(int(_clamp(float(round(sampled)), 1.0, float(upper))))
    return service_times

construct_anchor_routes

construct_anchor_routes(
    fastest: list[list[float]],
    demands: list[int],
    capacity: int,
    service_times: list[int],
) -> tuple[list[list[int]], list[float]]

Build deterministic capacity-and-horizon-feasible TW anchor routes.

Every route starts at the depot at the horizon start. The next customer is the nearest unserved customer that respects capacity and still permits a direct return to the depot within the horizon. Ties break on customer index. The returned visit times are the free-flow arrivals independently simulated on those routes.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/family/tw_synthesis.py

def construct_anchor_routes(
    fastest: list[list[float]],
    demands: list[int],
    capacity: int,
    service_times: list[int],
) -> tuple[list[list[int]], list[float]]:
    """Build deterministic capacity-and-horizon-feasible TW anchor routes.

    Every route starts at the depot at the horizon start. The next customer
    is the nearest unserved customer that respects capacity and still permits
    a direct return to the depot within the horizon. Ties break on customer
    index. The returned visit times are the free-flow arrivals independently
    simulated on those routes.
    """
    num_nodes = len(fastest)
    if len(demands) != num_nodes or len(service_times) != num_nodes:
        raise ValueError("fastest, demands and service_times must have identical dimensions")
    if capacity <= 0:
        raise ValueError("vehicle capacity must be positive")

    unserved = set(range(1, num_nodes))
    arrivals = [HORIZON_START] * num_nodes
    routes: list[list[int]] = []
    while unserved:
        route: list[int] = []
        current = 0
        load = 0
        clock = HORIZON_START
        while True:
            feasible: list[tuple[float, int, float]] = []
            for customer in unserved:
                demand = demands[customer]
                arrival = clock + fastest[current][customer]
                completion = arrival + service_times[customer]
                if load + demand <= capacity and completion + fastest[customer][0] <= HORIZON_END:
                    feasible.append((fastest[current][customer], customer, arrival))
            if not feasible:
                break
            _, customer, arrival = min(feasible, key=lambda item: (item[0], item[1]))
            route.append(customer)
            unserved.remove(customer)
            arrivals[customer] = arrival
            load += demands[customer]
            clock = arrival + service_times[customer]
            current = customer
        if not route:
            customer = min(unserved)
            raise ValueError(
                f"customer {customer} cannot start a capacity-and-horizon-feasible anchor route"
            )
        routes.append(route)
    return routes, arrivals

validate_static_anchor

validate_static_anchor(
    routes: list[list[int]],
    fastest: list[list[float]],
    demands: list[int],
    capacity: int,
    service_times: list[int],
    time_windows: list[tuple[int, int]],
) -> None

Hard-check a static anchor certificate against its generated windows.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/family/tw_synthesis.py

def validate_static_anchor(
    routes: list[list[int]],
    fastest: list[list[float]],
    demands: list[int],
    capacity: int,
    service_times: list[int],
    time_windows: list[tuple[int, int]],
) -> None:
    """Hard-check a static anchor certificate against its generated windows."""
    expected = set(range(1, len(fastest)))
    visited = [customer for route in routes for customer in route]
    if len(visited) != len(expected) or set(visited) != expected:
        raise AssertionError("anchor routes must cover every customer exactly once")
    for route in routes:
        load = sum(demands[customer] for customer in route)
        if load > capacity:
            raise AssertionError(f"anchor route load {load} exceeds capacity {capacity}")
        clock = HORIZON_START
        previous = 0
        for customer in route:
            arrival = clock + fastest[previous][customer]
            earliest, latest = time_windows[customer]
            clock = max(arrival, earliest)
            if clock > latest:
                raise AssertionError(
                    f"anchor route reaches customer {customer} at {clock} after deadline {latest}"
                )
            clock += service_times[customer]
            previous = customer
        if clock + fastest[previous][0] > HORIZON_END:
            raise AssertionError("anchor route returns after the horizon end")

synthesize_time_windows

synthesize_time_windows(
    rng: Random,
    fastest: list[list[float]],
    service_times: list[int],
    visit_times: list[float],
    *,
    width_ratio_mean: float = TW_WIDTH_RATIO_MEAN,
    width_ratio_std: float = TW_WIDTH_RATIO_STD,
    width_ratio_min: float = TW_WIDTH_RATIO_MIN,
    width_ratio_max: float = TW_WIDTH_RATIO_MAX,
) -> list[tuple[int, int]]

Route-centered integer windows clamped to the free-flow feasibility bounds.

Defaults reproduce the td-shared set byte-for-byte; the tight set passes the TIGHT_TW_WIDTH_RATIO_* parameters (same rng call sequence, so identical seeds with identical widths give identical windows).

Source code in MAMUT-routing-tools/src/mamut_routing_tools/family/tw_synthesis.py

def synthesize_time_windows(
    rng: Random,
    fastest: list[list[float]],
    service_times: list[int],
    visit_times: list[float],
    *,
    width_ratio_mean: float = TW_WIDTH_RATIO_MEAN,
    width_ratio_std: float = TW_WIDTH_RATIO_STD,
    width_ratio_min: float = TW_WIDTH_RATIO_MIN,
    width_ratio_max: float = TW_WIDTH_RATIO_MAX,
) -> list[tuple[int, int]]:
    """Route-centered integer windows clamped to the free-flow feasibility bounds.

    Defaults reproduce the ``td-shared`` set byte-for-byte; the ``tight`` set
    passes the ``TIGHT_TW_WIDTH_RATIO_*`` parameters (same rng call sequence,
    so identical seeds with identical widths give identical windows).
    """
    horizon = HORIZON_END - HORIZON_START
    num_nodes = len(fastest)
    windows: list[tuple[int, int]] = [(int(HORIZON_START), int(HORIZON_END))]
    for i in range(1, num_nodes):
        lo, hi = _feasible_bounds(fastest, service_times, i)
        width_ratio = _clamp(
            rng.gauss(0.0, 1.0) * width_ratio_std + width_ratio_mean,
            width_ratio_min,
            width_ratio_max,
        )
        width = max(1.0, float(round(horizon * width_ratio)))
        center = visit_times[i]
        latest = int(_clamp(float(round(center + width / 2.0)), float(lo), float(hi)))
        earliest = int(_clamp(float(round(center - width / 2.0)), HORIZON_START, float(latest)))
        windows.append((earliest, latest))
    return windows

synthesize_time_windows_spread

synthesize_time_windows_spread(
    rng: Random,
    fastest: list[list[float]],
    service_times: list[int],
) -> list[tuple[int, int]]

Uniform-center integer windows (the static-only spread set).

Per customer, the width is drawn from the td-shared distribution and the center uniformly over the customer's feasible interval (width first, then center: the rng call order is part of the frozen policy). Clamping is identical to the route-centered synthesis, so every window satisfies the individual free-flow feasibility bounds by construction.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/family/tw_synthesis.py

def synthesize_time_windows_spread(
    rng: Random,
    fastest: list[list[float]],
    service_times: list[int],
) -> list[tuple[int, int]]:
    """Uniform-center integer windows (the static-only ``spread`` set).

    Per customer, the width is drawn from the ``td-shared`` distribution and
    the center uniformly over the customer's feasible interval (width first,
    then center: the rng call order is part of the frozen policy). Clamping
    is identical to the route-centered synthesis, so every window satisfies
    the individual free-flow feasibility bounds by construction.
    """
    horizon = HORIZON_END - HORIZON_START
    num_nodes = len(fastest)
    windows: list[tuple[int, int]] = [(int(HORIZON_START), int(HORIZON_END))]
    for i in range(1, num_nodes):
        lo, hi = _feasible_bounds(fastest, service_times, i)
        width_ratio = _clamp(
            rng.gauss(0.0, 1.0) * TW_WIDTH_RATIO_STD + TW_WIDTH_RATIO_MEAN,
            TW_WIDTH_RATIO_MIN,
            TW_WIDTH_RATIO_MAX,
        )
        width = max(1.0, float(round(horizon * width_ratio)))
        center = rng.uniform(float(lo), float(hi))
        latest = int(_clamp(float(round(center + width / 2.0)), float(lo), float(hi)))
        earliest = int(_clamp(float(round(center - width / 2.0)), HORIZON_START, float(latest)))
        windows.append((earliest, latest))
    return windows