KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version

• Routing terms include TDVRPTW (Time-Dependent Vehicle Routing Problem with Time Windows), DM-TDVRPTW (Duration-Minimization TDVRPTW), and VRPTW (Vehicle Routing Problem with Time Windows).Source: Glossary · p. 5
• Algorithm abbreviations include B&P for Branch & Price, BBT for Balanced Binary Tree, ILS for Iterated Local Search, and LNS for Large Neighborhood Search.Source: Glossary · p. 5
• Function abbreviations include ATF for Arrival Time Function, TTF for Travel Time Function, RDF for Route Duration Function, and NDLCF for Non-Decreasing Left-Continuous PieceWise Linear Function.Source: Glossary · p. 5

Table of Symbols

• Calligraphic letters denote input sets, bold lowercase letters vertex sequences, and plain lowercase letters scalars or set elements; symbols receive domains at first use.Source: Table of Symbols · p. 6

Graph and instance data

• The instance graph G = (V, A) contains customers and duplicated depot vertices, with K bounding route count, Q denoting homogeneous vehicle capacity, and p bounding arc-function breakpoints.Source: Graph and instance data · p. 6

Paths, routes and solutions

• A route is an origin-to-destination path serving customers, and a solution is a feasible route set partitioning the customers with at most K routes.Source: Paths, routes and solutions · p. 6

Objectives and anytime evaluation

• The reference z* need not be optimal; the normalized signed primal integral Λ(Γ) averages the squeezed gap over the runtime horizon, with lower scores better.Source: Objectives and anytime evaluation · pp. 6–7

Time-dependent function taxonomy

• Arc arrival-time and ready-time functions compose into route ready-time functions, while the route duration function Δr(t) = δr(t) − t may be non-monotone.Source: Time-dependent function taxonomy · pp. 7–8

Time warp (penalty-tolerant squeeze)

• The warp-tolerant route duration is penalized by accumulated time warp: Ψr = ˜Δr + ηWr, where η > 0 is the penalty weight.Source: Time warp (penalty-tolerant squeeze) · p. 8

Recurring decorations and conventions

• A star marks a curated reference or best-found value, while a tilde marks a clamped or relaxed variant; angle brackets denote arcs and vertex sequences.Source: Recurring decorations and conventions · p. 8

1.1 Contributions

• KAYROS is an open-source solver for duration-minimization TDVRPTW that returns improving solutions and includes an exact branch-price-and-cut component.Source: §1.1 · pp. 10–11
• The paper extends composition to left-continuous functions needed by stepwise benchmarks, proves the checker routine exact, and analyzes IEEE-754 evaluation and breakpoint-normalization exactness.Source: §1.1 · p. 10
• Re-deriving instance distances at full precision makes 11 published solutions infeasible, motivating byte-exact canonical benchmark data rather than re-derivation recipes.Source: §1.1 · p. 10
• The anytime evaluation uses a normalized signed primal integral against a published reference, with panel-equal weighting and a confirmatory design pre-committed before campaign records existed.Source: §1.1 · pp. 10–11
• The exact component publishes 704 optimality certificates over 2,072 instances as conditional computational claims under a four-run publication protocol, not proof objects.Source: §1.1 · p. 11
• 63.3% lower pooled anytime score than the strongest available contender, with all three pre-committed contrasts significant under Holm correction.Source: §1.1 · p. 11
• KAYROS improves all 30 high-effort Blauth et al. references at unchanged route count and establishes 10 values below references left unproven by the exact literature.Source: §1.1 · p. 11

1.2 Outline

• Sections 2–3 establish composition and arithmetic, section 4 builds the solver, section 5 reports the comparison, and appendices supply records, proofs, internals, and protocol details.Source: §1.2 · p. 11

2.1 Time-Dependent Literature

• KAYROS uses route trees to rank candidate moves but recomputes accounted costs exactly; it specifies composition for discontinuous stepwise functions, including edge cases and floating-point behavior.Prior descriptions covered continuous functions at proof or proposition level, but not an algorithm for stepwise benchmarks.Source: §2.1 · p. 12

2.2 Exact Methods

• KAYROS builds its exact component on branch-price-and-cut, following Lera-Romero et al., and reports conditional computational claims rather than independently checkable proof objects.The cited lineage uses column generation with pricing and branch-and-bound; its reported conditions include arithmetic, tolerances, and search assumptions.Source: §2.2 · p. 13

2.3 Heuristic Methods

• KAYROS’s anytime layer uses granular first-improvement time-dependent descent with ruin-and-recreate kicks and late acceptance, while fleet-aware descent targets route count under fleet-cost objectives.The high-effort references of Blauth et al. use such an objective.Source: §2.3 · p. 14

2.4 Relaxations, Approximations and Matheuristics

• Unlike approximation and heuristic-pricing approaches, KAYROS keeps composition exact and un-normalized and its exact mode prices with valid relaxations, using full elementarity and capacity.An ng-route level was added to the vendored solver but is dormant by default.Source: §2.4 · p. 14

2.5 Numerical Exactness and Data Provenance

• KAYROS specifies composition arithmetic and analyzes when evaluation and breakpoint normalization are exact in IEEE-754 double precision; its epsilon-free checker defines the objective and recomputes published routes.Instances are distributed as byte-exact canonical data with checksums rather than re-derivation recipes.Source: §2.5 · p. 15
• Re-deriving benchmark distances at full precision makes some of the 146 published best-known solutions of Lera-Romero et al. infeasible, while those solutions remain correct on canonical instances.The published Dabia2013 preprocessing scales Solomon quantities by 10 and floor-truncates arc distances to integers.Source: §2.5 · p. 15

2.6 Anytime Resolution and its Evaluation

• The primal integral evaluates an anytime solver’s trajectory by combining how long it takes to become useful with incumbent quality, unlike a final-value-only comparison.Its reference is the best value known at analysis time, updated when a run improves it.Source: §2.6 · p. 16
• The proposed score is bounded, threshold-free, signed, and reference-based, preserving improvements beyond a frozen published reference and assigning a finite value before the first incumbent.The evaluation also requires timestamped incumbents on a common clock and an external evaluator that recomputes candidate objectives.Source: §2.6 · p. 17
• To the authors’ knowledge, no cross-solver anytime comparison had been reported for the TDVRPTW; the paper applies the established measurement lineage to this problem class.The choice of a frozen published reference has stated costs, while measurement choices and their effects are treated in a companion paper [Ras26b].Source: §2.6 · p. 17

2.7 The Available-Solver Landscape

• A solver qualifies for comparison if it models time-dependent travel, exposes an interface for instances and solution streams, and can be obtained and run with its license.This availability standard excludes unreleased codes; the campaign compares against Timefold, Hexaly, and jsprit, the solvers the authors identify as obtainable and runnable for this problem class.Source: §2.7 · pp. 17–18
• Timefold accepts rich per-arc travel-time functions and is the strongest contender; jsprit fixes routes at earliest feasible departure, while Hexaly offers rich and time-sliced model tiers.PyVRP is a strong VRPTW reference but targets the static problem family, and the open branch-price-and-cut solver is excluded because it is KAYROS’s own exact component.Source: §2.7 · pp. 17–18

3.3 A taxonomy of travel-time-related functions

• The model uses FIFO arc travel times, whose arrival-time functions are non-decreasing, while allowing stepwise travel-time jumps represented by left-continuous functions.A chain represents a function by breakpoints; at a jump abscissa, the selected function takes the smallest ordinate, making the represented function left-continuous.Source: §3.1 · p. 19, §3.3 · p. 22

3.1 Formal definition of the DM-TDVRPTW

• A path's ready-time function is recursively composed from arc arrival-time and vertex service functions, with feasible departures restricted by arc domains and time-window deadlines.The route starts from the depot departure window, and arrival at the destination must meet its due date.Source: §3.1 · p. 20
• Feasible solutions partition customers among at most K feasible routes, minimizing total route duration or, under FleetCostDuration, duration plus a fixed cost per route.Each route's cost is its minimum duration over feasible departure times; the exact component does not support FleetCostDuration.Source: §3.1 · p. 20

3.2 Set-partitioning formulation and pricing

• The route-based Dantzig-Wolfe formulation uses column generation over an exponential route set, labeling dynamic programming for pricing, and branching with cutting planes to restore integrality.The time-dependent pricing problem is NP-hard.Source: §3.2 · p. 21

3.3 A taxonomy of travel-time-related functions

• Chains can contain redundant breakpoints, so normalization is optional rather than a class invariant, and canonical cost semantics keeps compositions un-normalized.Breakpoint counts include duplicate abscissae and do not assume normalization.Source: §3.3 · pp. 22–23
• For non-decreasing left-continuous piecewise-linear functions, composition is pointwise and associative, with its domain restricted to inputs whose inner-function values lie in the outer function's domain.The route algebra's stated hypothesis is that the outer function's domain does not start strictly above the inner function's first value.Source: §3.3 · p. 23
• For functions satisfying (H), composition remains in the nondecreasing left-continuous class, and the event merge represents it in O(ϕf + ϕg) operations.For the temporal function classes used in route evaluation, every bracketing satisfies (H), represents the same partial function, and needs no continuity assumption.Source: §3.3 · pp. 23–24

Arc Travel Time Function (TTF)

• Arc TTFs are left-continuous piecewise-linear duration functions that may be nonmonotone, while their associated arrival functions are FIFO exactly when nondecreasing.FIFO bounds the TTF slope below by −1.Source: Arc Travel Time Function (TTF) · pp. 24, 26

Arc Arrival Time Function (ATF)

• Arc arrival maps αij(t)=t+τij(t) are nondecreasing FIFO maps with αij(t)≥t, while customer ready-time maps encode time windows and service duration.Both depot maps are identities: the origin restricts feasible departure times by its domain, and the destination clamps arrival to its deadline.Source: Arc Arrival Time Function (ATF) · p. 26

Arc Ready Time Function (arc RTF)

• An arc RTF composes the arrival map with the destination's ready-time map, restricting its domain to departures that meet the destination deadline.An empty domain means the arc is infeasible and is removed in preprocessing; all arc RTFs can be precomputed in O(n2p) time and memory.Source: Arc Ready Time Function (arc RTF) · p. 27
• A route RTF composes arc RTFs over feasible depot departures; its domain is nonempty exactly when the route is feasible, and a BBT computes it in O(mp log2(m)) time and memory.The resulting path representation has O(mp) breakpoints.Source: Arc Ready Time Function (arc RTF) · pp. 27–28

Route Duration Function (RDF)

• The route duration function is the route's arrival time minus departure time; it may be nonmonotone, and its minimum and earliest minimizer give optimal duration and dispatch time.Both are read from the route RTF chain in O(mp) time.Source: Route Duration Function (RDF) · p. 28

3.4 Exact composition of NDLCFs

• The section gives a complete pseudocode-level composition algorithm for left-continuous functions, proves equivalence to pointwise composition, and analyzes when evaluation is exact in IEEE-754 double precision.The listing is the one shipped in KAYROS and its canonical checker.Source: §3.4 · pp. 28–29
• The merge sweeps the inner function’s value band, gathering f’s ordinates and g’s abscissae at each event and interpolating whichever side lacks a breakpoint.It then emits the bottom and right edges of the resulting rectangle.Source: §3.4 · p. 29
• The left-continuous extension changes the sweep at a double tie: across a g plateau, h=f(ev), then jumps to f(ev+) at its right end.The merge emits the plateau’s bottom edge followed by the jump’s right edge.Source: §3.4 · p. 29
• Each event consumes at least one input point and emits at most as many; the closed value band includes exact boundary ties without a special step.Source: §3.4 · p. 30
• Unnormalized composition is canonical cost semantics: dropping points on flat or vertical runs is value-neutral, but dropping sloped-piece points can change interpolation results.For ATFs with vertical steps, measured deviations reached full step heights; solver and checker remain bit-identical by construction.Source: §3.4 · p. 30
• Validation uncovered silent index-out-of-bounds errors in, exact floating-point boundary ties, and benchmark-data provenance defects.The paper attributes the boundary ties to optimal-duration solutions and says random testing cannot reach them.Source: §3.4 · p. 30
• These findings motivate rules that the checker defines the objective and instances ship as byte-exact canonical data.The paper points to section 5.1 for the count of published BKS that full-precision Dabia2013 reading flips to infeasible.Source: §3.4 · p. 30

4.1 Architecture and the Checker as Referee

• KAYROS publishes only checker-recomputed objective values, rejecting bitwise mismatches; search uses a 10^-9 screening threshold, but accounted values are never compared with a tolerance.The checker uses IEEE-754 double precision, exact comparisons, and a fixed route order for reproducible totals.Source: §4.1 · p. 31

4.2 Exact Route Folding and Balanced Route Trees

• Because floating-point interpolation is non-associative, tree-ranked moves are committed only after changed routes are rebuilt and repriced by the sequential checker-identical fold.Different bracketings can differ by units in the last place and, on stepwise instances, by a full step height.Source: §4.2 · p. 33
• Route-tree move evaluation is 2× faster at mean route length about 6 and up to 17× faster at about 50 than naive recomposition.The study found no route size at which the sequential fold overtook the tree structures.Source: §4.2 · p. 33

4.3 The Anytime Stack

• The anytime stack publishes a greedy feasible seed before descent, then uses first-improvement descent and iterated local search while keeping published incumbents strictly decreasing.The descent cycles inter-route relocate, intra-route relocate, swap, and 2-opt*; accepted moves strictly reduce the repriced total.Source: §4.3 · p. 34
• On 1000-customer instances, granular enumeration accelerates a full descent by about 13× for a quality gap of 0.4 to 1.0%.The search uses proximity-based candidate lists and an exhaustive sentinel restores complete enumeration.Source: §4.3 · p. 34

4.4 Fleet-Aware Search under FleetCostDuration

• Under FleetCostDuration, KAYROS prices routes in acceptance and credits singleton-route removal, while only the kick can add routes and the fleet bound is an upper bound.The seed-splitting device is disabled for this objective.Source: §4.4 · p. 35
• Fleet descent attempts to eliminate one route through a two-rung insertion-and-ejection ladder, restoring the original solution on failure.It runs at restart-to-best triggers and by default on a work-based period; it has no singleton fallback, and its budgets use work units rather than wall-clock time. The phase does not support FleetCostDuration in the exact component, so it carries no optimality claim.Source: §4.4 · p. 37
• Fleet descent is decisive at n = 500 but hits a hard ceiling at n ≥1000.The bounded penalty-tolerant squeeze is inert by default because the two readings point in opposite directions at n = 1000 and n = 500.Source: §4.4 · p. 37

4.5 The Exact Component and Optimality Certificates

• KAYROS vendors the branch-price-and-cut solver of Lera-Romero et al., adding HiGHS, deadline compliance, warm starts, and checker-consistent binary64 route costs.Production pricing uses an exact value-jump path for stepwise instances; LP bounds retain the backend’s stated tolerances.Source: §4.5 · pp. 37–38
• Certificates claim optimality under checker-exact route costs and standard LP/pricing tolerances, with pricing completeness modulo Lera epsilon dominance.They are not formal proofs or portable artifacts, and do not establish exact real arithmetic or rigorous LP bounds.Source: §4.5 · p. 38
• A certificate requires four runs across cold/warm starts and bidirectional labeling modes to prove optimality at one agreeing checker-evaluated value.All runs must meet the stored-reference bound, include an audited exact-pricing iteration, and use checker-repriced routes; shared deterministic errors remain possible, so certificates are falsifiable and retractable.Source: §4.5 · pp. 38–39

5.1 Benchmarks and Protocol

• Lera2026 and Poryos2026 extend the benchmark to n = 1000, with Poryos2026 introducing a road-network family across five cities.Dabia2013’s canonical preprocessing floor-truncates arc distances; the resulting instances are an outer approximation, and 11 of 146 published BKS lose feasibility under a full-precision reading. KAYROS distributes byte-exact canonical data.Source: §5.1 · pp. 39–40
• The comparison fixes 212 instances in 10 panels and gives five solver arms one single-threaded hour per cell, rescoring incumbents with a common external checker.Four arms use exact per-arc travel-time functions; the fifth is a time-sliced Hexaly approximation reported separately from Tier-1 results.Source: §5.1 · pp. 40–41

5.2 Metrics and Confirmatory Design

• The normalized signed primal integral Λ scores the full incumbent trajectory, while final gap gΓ measures end-of-budget quality; pooled means weight the 10 panels equally.No-incumbent runs remain in the aggregates, scored at the upper bound rather than excluded.Source: §5.2 · p. 43
• The pre-committed design tests three pooled Λ contrasts at one hour using paired instance-level bootstrap resampling and Holm correction at 5%.The design was frozen before any pilot or campaign record; the bootstrap uses 10,000 resamples, and the seed-subset check preserved the arm ordering, panel winners, and Holm verdicts.Source: §5.2 · p. 44

5.3 Contender Comparison

• KAYROS’s pooled anytime score Λ was 0.008368 versus 0.02282 for Timefold, 63.3% lower; all three Tier-1 contrasts were Holm-significant.The pooled final gap gΓ was 0.84% for KAYROS, versus 2.37% for Timefold, 7.42% for Hexaly, and 51.3% for jsprit—a 64.6% reduction against Timefold.Source: §5.3 · p. 44
• All three paired final-gap contrasts favor KAYROS, and the two metrics rank the Tier-1 arms identically; KAYROS leads on 7 of 10 panels.On the other three panels, Timefold leads, but the paired difference intervals straddle zero and do not establish equivalence. On the 27 remaining panel contrasts, the difference is negative with an interval clear of zero.Source: §5.3 · pp. 44–45, Table 5 · p. 45

5.4.1 NDCPWLF compositions

• Visser+nor+tree is the fastest composition variant overall, while sequential visser+nor is about twice as fast as the other algorithms and 69 times faster than visser2020.Alternative uses the least memory; visser+nor is only 0.1% above it, making either visser+nor form the authors’ implementation choice. The stress benchmark uses chains up to 1,000 compositions, a regime relevant to road-network ATFs but beyond canonical TD instances.Source: §5.4.1 · p. 50

5.4.2 Search strategy head-to-head

• Across 6,936 paired cells, iterated local search wins 5,714 and improves final cost by 2.52% on average, rising to 5.44% at n = 1000.At the tested fixed half-budget allocation, a colony warm start did not improve final quality over ILS alone. This historical comparison fixed the default at release 0.4.0, not in a same-version ablation on the 212-instance benchmark.Source: §5.4.2 · p. 50

5.4.4 Fleet descent and penalty-tolerant squeeze

• At n = 500, fleet descent won route count 23 times versus 0 in 80 paired cells and produced the first improvements on Blauth et al. references.At n ≥ 1000, the reference route count was reached in only 0.1% of 3,000 cells; matched-route duration gaps were just 0.3%–1.0%. Penalty-tolerant squeeze reached the reference fleet in 4 of 30 n = 1000 pairs versus 0 of 30 for the default, but failed its pre-committed acceptance gate at n = 500.Source: §5.4.4 · p. 52

5.5 Best-Known Solutions and Certificates

• Against the re-priced literature solutions, KAYROS holds 114 optimality certificates: 103 reproduce published proven optima, while 10 beat unproven references by 0.06%–2.15%.No certificate contradicts a published proven optimum; one other instance differs only through checker re-evaluation of published routes, by less than 10^-9 relatively and below the reporting threshold. The comparison uses canonical re-pricing of 146 published solutions, the stated well-posed basis for comparison.Source: §5.5 · p. 52
• Long-budget KAYROS searches improve all 30 Blauth2024 high-effort references without changing route counts, by 0.032%–1.314% (mean 0.254%).These chained, warm-started best-effort searches move strong reference solutions by fractions of a percent; the reported margin shrinks as instance size grows.Source: §5.5 · pp. 52–53
• 704 computational optimality certificates cover 2,072 instances: 466 legacy instances and 238 time-dependent Poryos2026 instances.The legacy certificates cover 1,352 instances across four families and both problem variants; the Poryos2026 certificates cover 720 instances.Source: §5.5 · p. 53
• Certificate coverage varies sharply by family and size: 165 of 168 Vu2020 TDVRPTW instances certify, but only 6 Poryos2026 TDVRPTW instances certify at n = 50 and none above.Poryos2026 mostly certifies at n ≤ 25; removing time windows weakens pruning on Vu2020, and no certificates are claimed for Lera2026 or Blauth2024.Source: §5.5 · p. 53
• Of the certificates, 173 improved a stored best-known solution, while certificate sets were withdrawn after a representation defect and protocol reruns re-derived 466 legacy certificates.The 173 improvements mostly concern KAYROS heuristic solutions; open or resource-limited runs remain explicitly unclaimed rather than being downgraded to weaker claims.Source: §5.5 · p. 53

What the fleet-cost comparison licenses

• Fleet-cost improvements compare long searches with reference solutions whose budgets and trajectories are unknown, supporting final-quality comparison only.The authors say an anytime or equal-budget comparison would require the other side’s traces or code.Source: §6 · p. 53

The time-sliced tier has no causal reading

• The time-sliced tier cannot isolate representation effects from search because KAYROS was not run on the sliced instances.Its checker-invalid final solutions reflect optimizing an approximation and scoring against the truth, not the approximation’s worth.Source: §6 · pp. 53–54

Benchmark surface

• The pooled benchmark gives two thesis-built families two of five family slots and two fifths of the aggregate.The protocol fixed these shares before campaign records existed, and results are published per panel.Source: §6 · p. 54

The single-core convention

• The single-core campaign does not establish multi-threaded behavior; KAYROS is single-threaded by design, while one contender’s time-sliced encoding scales with threads.A multi-core comparison would be a different experiment and trade-off.Source: §6 · p. 54

An earlier decision, honestly dated

• The ILS-versus-ant-colony decision was measured at an earlier release on a different instance design, not as an ablation of the evaluated build.It informs the solver’s history, not a general comparison of the two metaheuristic families.Source: §6 · p. 54

Evidence and reproducibility

• Every reported number is regenerated from the frozen campaign artifacts, while the companion report and public artifacts provide further detail.The discussion states that its claims do not depend on an unchecked document.Source: §6 · p. 54

KAYROS and the objective

• The checker’s epsilon-free recomputation defines the objective for every value the solver publishes.The solver is released as an anytime and exact duration-minimization TDVRPTW solver.Source: §7 · p. 54

Composition and arithmetic

• Algorithm 1 gives exact composition for non-decreasing left-continuous piecewise-linear functions under a domain hypothesis route evaluation satisfies.It covers floating-point breakpoint normalization and recovers the continuous case when there are no jumps.Source: §7 · p. 55

Contributions and results

• 63.3% lower pooled anytime score than the strongest available contender, with all three contrasts Holm-significant; KAYROS also publishes 704 conditional optimality certificates.The evaluation aggregates a normalized signed primal integral against a frozen published reference under panel-equal weighting and a pre-committed design.Source: §7 · p. 55

Exact component and certificates

• Ten certificates establish values 0.06% to 2.15% below published references that earlier work left unproven.The paper also reports that no certificate contradicts a published proven optimum.Source: §7 · p. 55

Fleet-cost objective

• KAYROS improves all 30 high-effort Blauth et al. reference solutions under the fleet-cost objective at an unchanged route count.The fleet-aware descent addresses those references.Source: §7 · p. 55

Future verification

• Independently verified safe bounds would make certificates checkable without rerunning the solver.The paper names interval arithmetic or rational certification of the final relaxation as possible approaches.Source: §7 · p. 55

Perspectives

• The engine and anytime layer could be ported to single-vehicle time-dependent problems, and the exact component could integrate DDD.Other proposed directions include hardening published best-known solutions and testing whether coarse time-sliced representations repay their loss of fidelity.Source: §7 · p. 55

Public artifacts

• The solver, benchmark instances, solution store, and campaign data are public.The authors present public release as the condition for contesting the reported findings.Source: §7 · p. 55

Solver release

• KAYROS 1.6.0 is open source under the MIT license, available on PyPI as kayros, and archived by Software Heritage.Source: Data Availability · p. 56

Benchmark and solution artifacts

• Benchmark instances, the canonical checker, and the versioned solution store with certificates are published by the MAMUT-routing platform.Source: Data Availability · p. 56

Campaign data

• The campaign archive and analysis code are released, alongside 2,010 thread-scaling runs deposited separately.The campaign archive contains 8,800 solver runs; both run archives are under CC BY 4.0.Source: Data Availability · pp. 56–57

Declaration

• Generative AI tools were used throughout preparation of the work.Source: Declaration of AI Use · p. 57

Contributions

• The tools contributed to solver and benchmark tooling, experiment orchestration and analysis, and drafting.Source: Declaration of AI Use · p. 57

Review and responsibility

• Florian Rascoussier reviewed and revised all tool outputs and takes full responsibility for their use in the final content.Source: Declaration of AI Use · p. 57

• Every published BKS is feasible and reproduced exactly on canonical data, while the same routes under full-precision distances average +0.40 per arc and 11 miss deadlines by 0.94 to 4.8 time units.Source: A Per-Instance Best-Known-Solution… · p. 66
• The full-precision feasibility differences reflect evaluation convention, not an error on either side, so the convention must be fixed for reproducible comparison.Source: A Per-Instance Best-Known-Solution… · p. 66
• RC105_100 departs 10−5 before its duration-minimizing breakpoint, making its published duration improvable by 10−5 under the original ε = 10−5 tolerance.Source: A Per-Instance Best-Known-Solution… · p. 66
• 10 Dabia2013 instances have KAYROS-certified optima 0.06% to 2.15% below published references that earlier work left unproven.Source: Table 8 · p. 67
• 30 high-effort BonnTour references are improved by long-budget KAYROS searches at unchanged route count under FleetCostDuration.Source: Table 9 · p. 67

• Per-panel results are descriptive and exploratory; the confirmatory family is the three pooled contrasts, and the per-panel contrasts have no multiplicity correction.Source: B Per-Panel Statistics · p. 68, Table 10 · p. 68, Table 11 · p. 70
• 27 of 30 per-panel paired-difference intervals lie entirely below zero, favoring KAYROS.Source: Table 11 · p. 70
• The three per-panel intervals containing zero are all comparisons against Timefold.Source: Table 11 · p. 70

C NDCPWLF Composition Benchmark Grid

• The four composition algorithms are tested sequentially and with tree variants that compose in log2(k) levels rather than along the full chain.Source: C NDCPWLF Composition Benchmark Grid · p. 71
• The tree variant of visser2020 recovers most of the time lost by its sequential form relative to visser+nor, but not the memory savings from normalization.Source: C NDCPWLF Composition Benchmark Grid · p. 71
• At k = 1000, the four largest-k rows account for 88.5% to 99.2% of each method’s total time, and one cell accounts for 90% of visser2020’s total.Source: C NDCPWLF Composition Benchmark Grid · p. 71

D Function Taxonomy: Properties, Complexity and Exactness

• The arc ready-time function has an explicit domain restriction; an empty domain means the arc is infeasible and is removed during preprocessing.Source: §D.1 · p. 74

D.1 Properties and complexity

• Balanced-tree route-function construction takes O(mp log2(m)) time and memory for a route with m vertices and at most p arc breakpoints.Source: §D.1 · p. 74
• A route’s minimum duration is the minimum of its duration function over feasible departure times, and the earliest minimizing departure can be read from the attaining breakpoint.Source: §D.1 · p. 75

D.2 Chains, closure and the correctness of the event merge

• Chains represent exactly the finite-piece, non-decreasing, left-continuous functions: every such function has a canonical chain, and equivalent chains differ only by redundant points or a trailing vertical.Between consecutive abscissae, the represented function interpolates linearly; at jumps, its value is the smallest ordinate in the group.Source: §D.2 · pp. 75–76
• For any chain representing h, the minimum of h(t) − t is attained and equals the minimum of y_k − x_k over chain points; the earliest minimizing abscissa is chain-invariant.The minimum is attained at a chain abscissa, and the chain’s smallest ordinate there equals h’s value.Source: §D.2 · p. 76
• Under the stated assumptions, composition has a closed initial-segment domain and is non-decreasing, left-continuous, and piecewise linear with finitely many pieces.The domain is empty exactly when g’s starting value exceeds f’s upper endpoint.Source: §D.2 · pp. 76–77
• The event merge produces a chain representing f ◦ g, with output length at most ϕ_f + ϕ_g and total running time O(ϕ_f + ϕ_g).In exact arithmetic, dropping exact duplicates is the only effect of the output step; bitwise identity is not guaranteed across different representations.Source: §D.2 · pp. 77–78
• Different representing chains can yield different output bits while representing the same composition; bitwise identity is guaranteed only when the checker and KAYROS run the same fixed pipeline on the same chains.Source: §D.2 · p. 79
• Without (H), the merge can return a non-empty chain for an empty composition, and re-bracketing can produce different wrong outputs.The counterexample violates (H) because a_f = 8 > g(0) = 0; the true composition is empty.Source: §D.2 · p. 80
• With (H), the composition class is closed and faithfully represented, and route evaluation stays within it; exact-rational tests checked the shipped listing.The tests covered boundary ties, redundant points, trailing verticals, random pairs with and without (H), and random temporal-chain associations.Source: §D.2 · p. 80

D.3 Exactness of normalization and the three defect families

• Deleting sloped breakpoints can change floating-point evaluations, with deviations reaching full step heights; KAYROS therefore uses un-normalized composition for canonical cost semantics.Removing interior points on exactly horizontal or vertical runs is bit-neutral; this restricted deduplication yields 10–28% fewer stored breakpoints on TW-clamped and step families, at no semantic cost.Source: §D.3 · p. 81
• Random-RTF assessment exposed silent index-out-of-bounds errors in the original composition, which were corrected before benchmarking.The benchmark implementation predates this analysis and inherited epsilon-based comparators from the lera2020 baseline.Source: §D.3 · p. 81
• 72 of 146 published BKS carried exact deadline ties, while an early two-pointer sweep silently collapsed the composed domain on 3 of 898 routes.The 72 solutions span 188 routes; the early implementation remained bit-identical on all other published BKS routes.Source: §D.3 · p. 81
• Using Solomon coordinates instead of floor-truncated canonical ones inflated every arc by +0.40 time units on average and made 11 BKS infeasible; all 11 were among 72 tie-carrying solutions.The checker reproduces all 146 published BKS and finds a strictly better RC105_100 solution; its published departure time on one route is 10^-5 short of the duration-minimizing breakpoint, below the original solver’s ε = 10^-5 comparison tolerance and therefore invisible to its epsilon-based comparisons.Source: §D.3 · pp. 81–82
• The paper makes the canonical, epsilon-free checker the objective authority and distributes benchmark instances as byte-exact data with checksums.These rules avoid silently changing instance sets through re-derivation or tolerance-based comparisons.Source: §D.3 · p. 82

E.1 Move evaluation and the bracketing measurement

• Different floating-point bracketings produced bitwise-identical route ready-time functions in 73% and 71% of comparisons and exactly equal durations in 91% and 89%, with no feasibility disagreements.Most mismatches were about 7 · 10^-12, but on a stepwise instance accumulated rounding dust crossed a step boundary and changed duration by a full step height; accepted moves were therefore repriced by the sequential checker-identical fold with strict inequality and no tolerance.Source: §E.1 · p. 83
• Tree-ranked move evaluation was 2× faster at mean route length about 6 and up to 17× faster at about 50, with identical feasible moves across the compared methods.The LCA-BST led the composition tree by 15%–35%, and no tested size favored the sequential fold.Source: §E.1 · p. 83

E.2 The anytime stack: parameters and screens

• The anytime stack defines proximity from minimum travel duration plus 0.2 times unavoidable waiting, symmetrizes and truncates neighbors to 50 per customer, and uses granular move justifications with staleness-based re-enumeration.Relocations, swaps, and 2-opt* require customer-neighbor links rather than depot reconnections; customers are revisited when their own context or a neighbor’s has changed.Source: §E.2 · p. 84

E.3 Fleet descent and the penalty-tolerant squeeze

• Fleet descent removes a victim route through an all-or-nothing ejection ladder, while the penalty-tolerant squeeze is opt-in and inert by default.The squeeze relaxes only time-window feasibility on a copy, tracks violations separately, and returns only a banked zero-warp state; its default status reflects the failed n = 500 acceptance gate despite gains at n = 1000.Source: §E.3 · p. 85

E.4 The exact component: additions and the four-run gate

• The exact component adds an open HiGHS backend, checker-consistent column costs, and stepwise value-jump pricing, while requiring a four-run gate before issuing a certificate.All four cold/warm-start and bidirectional-labeling runs must prove optimality at an agreeing checker-evaluated value, with audited exact-pricing iterations and checker-repriced routes; refusal is distinct from open and resource-limited outcomes.Source: §E.4 · pp. 86–87

E.5 Fleet descent and squeeze: the full readings

• At n = 500, fleet descent won the route-count comparison 23–0 and reduced the summed fleet from 496 to 471 routes; at n ≥ 1000, it reached the reference count on only 0.1% of runs.At n ≥ 1000, route counts remained one above the reference on 58.0% of runs, two above on 38.2%, and three above on 3.7%; the residual duration gap at a matched route count was 0.3%–1.0%.Source: §E.5 · p. 87
• Across 30 pairs, it removed a net 12 routes and improved paired mean objective by 1.32%; its pre-committed gate failed on n=500 2-hour cells, with 0.277% paired mean cost versus a 0.05% tolerance.Source: §E.5 · p. 87
• 90 of 90 one-vehicle searches failed to attain the reduced fleet within 12 hours, supporting tight record route counts at that budget, but nothing stronger.The negative-result option publishes nothing when a run never attains its cap, rather than reporting an above-cap solution.Source: §E.5 · p. 88

F.1 The canonical preprocessing of Dabia2013

• Dabia2013 instances use scaled Solomon quantities, floor-truncated integer arc distances, and stepwise speed profiles integrated into FIFO travel-time functions; the resulting data match Lera-Romero et al. [LMS20] and are used by Pan et al. [PZL21b].The hidden preprocessing pipeline was hard-coded in Dabia et al.'s original Java solver; the authors supplied it, and its distance truncation is part of the benchmark definition.Source: §F.1 · p. 88
• For Dabia2013, floor-truncated distances are on average ≈0.40 time units shorter per arc, making canonical instances an optimistic outer approximation: full-precision feasibility transfers to canonical instances, but not conversely.Source: §F.1 · p. 89

F.2 The stratified draw of the frozen instance set

• The frozen set includes all 56 Dabia2013 n = 100 and 60 Poryos2026 n = 1000 instances; eight other panels use solver-blind, stratified samples of 12, selected with a deterministic seed-14 generator.Selection ranks instances by a SHA-256 key from their identity in a campaign-specific namespace, with strata based on each family’s available diversity axes.Source: §F.2 · p. 89

F.3 Load fractions

• KAYROS’s largest panel-mean loading fraction was 1.62% of budget (58.4 s) on Poryos2026 n = 1000, while the longest individual load there was 127.9 s (3.552%).Because individual startup costs vary and the individual load can exceed the panel mean, no solver arm receives a warm-up allowance.Source: §F.3 · p. 89

F.4 The metric design, developed

• The bounded signed gap keeps the anytime score defined before a first incumbent and when a solver beats the frozen reference; this campaign folds improvements into its reference.Before any feasible solution, the squeezed gap is scored as 1; after the campaign fold, gaps are nonnegative and matching the latest record scores zero.Source: §F.4 · p. 90
• The final-gap measure has no finite value when a run ends without an incumbent, a case present in the campaign.The design also guards contrasts with fewer than two shared instances and treats any instance-set mismatch as a hard error; neither guard had to fire.Source: §F.4 · p. 90

G.1 Search strategy head-to-head

• ILS beats colony in 5,714/6,936 paired cells, ties 917, loses 305, and improves mean final cost 2.52%, reaching 5.44% at n=1000.The comparison covered both problem variants, five instance families, and sizes from n = 10 to n = 1000.Source: §G.1 · p. 91
• The half-budget colony-to-ILS hybrid loses to pure ILS at scale, by 0.56% at n = 200 and 1.17% at n = 1000.Other budget allocations and switching policies were not tested.Source: §G.1 · p. 91
• On the road-network family, iterated local search wins every paired cell from n = 100 upward; at n = 1000, all its runs end below a 1% gap, while 11% of colony runs do and the colony plateaus above 1.5%.The colony’s best run beat iterated local search on four small, heavily congested instances.Source: §G.1 · p. 91
• The search-strategy comparison fixed ILS as the default at release 0.4.0; it is a historical decision record, not a same-version ablation on the 212-instance set.The evaluated build was version 1.6.0.Source: §G.1 · p. 91

G.2 Thread scaling of the commercial contender

• The 500-run ladder used 10 instances, 10 seeds per cell, one hour per run, and 1, 2, 4, 8, or 16 requested threads in both encodings.Both encodings largely occupied their requested cores; the comparison measures quality gained from width, not core acquisition.Source: §G.2 · pp. 91–92, Table 14 · p. 93
• The external-function encoding’s mean final gap is 5.87% at 1 thread, reaches a shallow optimum of 5.59% at 8, and returns to 5.98% at 16.By contrast, the sliced encoding’s mean final gap falls 23.5% from 1 to 16 threads, and its anytime score falls 25.4%.Source: §G.2 · p. 92
• Across 10 instances, 9 improve with width by 17.8% on their panel-equal mean from 1 to 16 threads, but one 1000-customer instance degrades 25.3%.That single instance cancels the pooled improvement; sliced encoding leads on 6 of 10 instances at one thread and all 10 at 16.Source: §G.2 · p. 92
• At 16 threads, the sliced encoding leads on all 10 instances, with a 4.56% mean final gap against 5.98% for the external-function encoding.At one thread, the encodings are nearly tied: 5.87% for external-function against 5.96% for sliced.Source: §G.2 · p. 92, Table 14 · p. 93
• The gaps use a pre-campaign reference and are not comparable with the main campaign scores; 16 threads also require up to 16 times the nominal core allocation.The gaps are reported on the raw scale gΓ, whereas the companion report uses squeezed gaps.Source: §G.2 · p. 92