Paper deep dive
KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering
Florian Rascoussier
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:KAYROS is an open-source solver for duration-minimization time-dependent vehicle routing problems, with or without time windows (TDVRPTW, TDVRP). In these variants, travel times change with departure time, and each route's dispatch time is a decision. To the best of the author's knowledge, it is the first openly available solver that is both anytime, streaming improving solutions from the first seconds, and exact, proving optimality with publicly verifiable certificates, for these problems over rich piecewise-linear travel- time functions rather than a time discretization. It has no proprietary dependency and installs with one command. It builds on the state of the art for time-dependent function composition and exact solving, extending the open-source branch-price-and-cut solver of Lera-Romero, Miranda Bront and Soulignac (2020) with an open LP backend, anytime and warm- start behavior, checker-exact pricing, and exact treatment of stepwise travel times. On the MAMUT-routing benchmark collection, KAYROS stands behind 468 published optimality certificates, each requiring agreement among four independent solves, and five certificates strictly improve published reference values. The report also introduces Poryos2026, a benchmark family designed and generated by the author from real OpenStreetMap city road networks. Its 1,080 paired CVRP, VRPTW, TDVRP and TDVRPTW instances combine real road geometries with controlled synthetic demands, time windows and congestion. Every instance carries a checker-validated best-known solution. This report presents the solver, its certification protocol, the benchmark's generation and feasibility guarantees, and their experimental connection for a broad technical audience. It is also a case study in the intensive human-AI collaboration that made this body of work feasible while keeping its claims independently verifiable.
Tags
Links
- Source: https://arxiv.org/abs/2607.23116v1
- Canonical: https://arxiv.org/abs/2607.23116v1
Trouble viewing inline? Open PDF directly â
Full Text
88,356 characters extracted from source content.
Expand or collapse full text
KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing A Technical Report and a Case Study in HumanâAI Engineering Florian Rascoussier â July 22, 2026 Abstract KAYR O S is an open-source solver for duration-minimization time-dependent vehicle routing problems, with or without time windows (TDVRPTW, TDVRP). Such variants involve travel times that change with the departure time, and in which the dispatch time of every route is itself a decision. To the best of the authorâs knowledge, it is the first openly available solver that is both anytime (streaming improving solutions from the first seconds) and exact (proving optimality with certificates whose every value can be re-verified against a public reference checker) on these problems over rich piecewise-linear travel-time functions rather than a time discretization, with no proprietary dependency and a one-command install. It builds on the state of the art for time-dependent function composition and exact solving, extending the open-source branch-price-and-cut solver of Lera-Romero, Miranda Bront and Soulignac (2020) with an open LP backend, anytime and warm-start behavior, checker-exact pricing, and an exact treatment of stepwise travel times. On the MAMUT-routing benchmark collection, KAYROS stands behind 468 published optimality certificates, each requiring four independent agreeing solves, and five strictly improve published reference values. The report also introduces Poryos2026, a benchmark family designed and generated by the author from real OpenStreetMap city road networks. Its 1,080 paired CVRP, VRPTW, TDVRP and TDVRPTW instances combine real road geometries with controlled synthetic demands, time windows and congestion, and every instance carries a checker-validated best-known solution. This report presents the solver, its certification protocol, the benchmarkâs generation and feasibility guarantees, and their experimental connection for a broad technical audience. It is also a case study in the intensive humanâAI collaboration that made this body of work feasible while keeping its claims independently verifiable. Keywords: Vehicle Routing, Time Dependence, TDVRPTW, TDVRP, Duration minimization, OpenStreetMap, Benchmark Generation, Exact Algorithms, Branch-Price- and-Cut, HiGHS, Iterated Local Search, Anytime Optimization, Open-Source Software, HumanâAI Collaboration, AI-assisted Research, Context-Oriented Programming â IMT Atlantique, Lab-STICC, CNRS, UMR 6285 (ĂŠquipe DECIDE) and INSA Lyon, Inria, CITI, UR3720, 69621 Villeurbanne, France. ORCID: 0009-0005-3253-9814; IdHAL: florian-onyr-rascoussier. 1 arXiv:2607.23116v1 [math.OC] 25 Jul 2026 Contents 1 Introduction4 1.1 Context and claim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Why this report also documents a collaboration . . . . . . . . . . . . . . . . . . 4 1.3 Scope and companion work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Time-dependent routing in a nutshell5 2.1 The problem and the gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Why this gap matters: a decade of unmet demand . . . . . . . . . . . . . . . . . 6 2.3 Travel times as functions: a two-client tour . . . . . . . . . . . . . . . . . . . . . 8 2.4 Representing time dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 The KAYR OS solver11 3.1 Design principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 The NDCPWLF engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 The anytime stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 The exact component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Packaging and availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Certificates, and the day we retracted 160 of them14 4.1 What a certificate is . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 The validation ladder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 The self-refutation and its repair . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Poryos2026: an OpenStreetMap-based modern TD benchmark family16 5.1 A paired design across four routing problems . . . . . . . . . . . . . . . . . . . . 17 5.2 From a city extract to time-dependent instances . . . . . . . . . . . . . . . . . . 19 5.3 Feasibility by construction, then by audit . . . . . . . . . . . . . . . . . . . . . . 20 2 6 Experimental evidence on MAMUT-routing21 6.1 The benchmark collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Optimality certificates in the public store . . . . . . . . . . . . . . . . . . . . . . 21 6.3 Comparing against published results . . . . . . . . . . . . . . . . . . . . . . . . 22 6.4 Complete heuristic coverage of Poryos2026 . . . . . . . . . . . . . . . . . . . . 23 6.5 Choosing the default heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7 The humanâAI collaboration24 7.1 Setting and division of labor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.2 Context-Oriented Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.3 What became feasible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.4 Accountability: the checker is the referee . . . . . . . . . . . . . . . . . . . . . . 26 7.5 Limits of this account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 8 Limitations and outlook27 9 Conclusion28 3 1 Introduction 1.1 Context and claim KAYR O S [Ras26a] is an open-source solver for the duration-minimization time-dependent (TD) vehicle routing problem with time windows (TDVRPTW) and its simpler non-TW variant (TDVRP), released in version 1.1 on PyPI in July 2026 and currently available as version 1.1.3 1 . It combines two solving modes on one exact time-dependent engine: an anytime heuristic that streams improving solutions from the first seconds of a run, and an exact branch-price-and-cut method that proves optimality with certificates whose every value is verifiable against a public reference checker. Their exact semantics are stated in Section 4.1. To the best of the authorâs knowledge, it is the first solver to make the following combination openly available: exact and anytime solving of the duration-minimization TDVRP(TW) over rich piecewise-linear time-dependent travel times (not a time discretization), installable with one command, with no proprietary dependency. It builds deliberately on the state of the art rather than around it: its function-composition engine follows Visser et al. [VS20], its local-search structures follow Blauth et al. [Bla+24], and its exact component extends the open-source branch-price-and-cut solver of Lera-Romero et al. [LMS20]. Run over the MAMUT-routing benchmark collection, it stands behind 468 published optimality certificates, five of which strictly improve published reference values, and none of which contradicts any published proven optimum (Section 6). The claim is deliberately narrow: this report does not claim that KAYROS outperforms existing exact TD solvers (no head-to-head comparison exists, and Section 8 explains why running an honest one is not straightforward), and improvement counts are always qualified by what they are measured against. The reportâs second software-and-data contribution is Poryos2026, a family of 1,080 instances generated from the road networks and points of interest of Lyon, Paris, San Francisco, Hong Kong and Tokyo. The author designed and generated this family as a realism-oriented benchmark with actual city geometry, controlled paired variants and reproducible synthetic traffic. It is published through MAMUT-routing [RP26], a broader platform developed collaboratively with Adrien Pichon as part of the ANR-MAMUT project. This distinction matters: Poryos2026 is the authorâs benchmark, MAMUT-routing is the collaborative catalog and checker infrastructure that distributes it, and OpenStreetMap contributors are the source of the geographic data from which it derives. 1.2 Why this report also documents a collaboration This report has a further purpose, unusual for a solver report. KAYROS was built in an intensive collaboration between its author and an AI agent, Claude Fable 5 (Anthropic), in about two weeks of wall-clock time. The author had previously estimated this exact scope of work at years 1 https://github.com/0nyr/kayros,https://pypi.org/project/kayros/. Version 1.1 designates the v1.1.x release line. The certification campaign of Section 4.2 ran on the v1.1.0 build. 4 of post-doctoral effort. Section 7 documents that collaboration as an engineering methodology: what the division of labor actually was, what practices made the speed compatible with scientific soundness, and what the limits of this single-project account are. The verification protocol of Section 4, which predates and survived the collaborationâs hardest bug, is precisely what makes solver output produced at this speed trustworthy and checkable. Readers interested only in the technical contributions can skip Section 7. Sections 2 to 6 form a self-contained report. Throughout, âthe authorâ designates the human and âweâ the humanâAI collaboration. 1.3 Scope and companion work This document is a technical report, written to be read: it favors precise statements over formal ones and a worked toy example over definitions. It deliberately does not contain the formal model of the duration-minimization TDVRP(TW), the composition algorithms and their proofs, algorithm-level pseudocode, component ablations, or any performance benchmark of the function-composition engine. Those belong to a full-length paper in preparation and to the authorâs PhD thesis, which the report at no point replaces. Section 2 introduces time-dependent routing for readers outside vehicle routing, around a two-client toy tour. Section 3 presents the solverâs design principles and architecture, and Section 4 defines the optimality-certification protocol and recounts a self-refutation episode central to the projectâs credibility. Section 5 then presents the design and generation of Poryos2026, before Section 6 reports the experimental evidence connecting solver, benchmark and public store. Section 7 documents the humanâAI collaboration after the technical results, and Section 8 states limitations and outlook. 2 Time-dependent routing in a nutshell This section assumes no vehicle-routing background: it states the problem, documents the availability gap, and builds every concept the rest of the report needs on a two-client toy tour. 2.1 The problem and the gap The Vehicle Routing Problem with Time Windows (VRPTW) is one of the workhorses of Operations Research (OR): a fleet of capacitated vehicles based at a depot must visit a set of clients, each client specifying a time window during which service may start, and the goal is to find feasible tours of minimum total cost [Sol87]. The problem is NP-hard, ubiquitous in logistics, and has accumulated four decades of competitive algorithmic literature. The classic model assumes that driving fromitojalways takes the same time. Anyone who has commuted through a city knows this is false: the same road takes much longer at rush hours. The Time-Dependent VRPTW (TDVRPTW) drops this assumption and makes the travel time of every arc a function of the departure time [MD92]. The standard way to keep such a model 5 physically sensible is the First-In First-Out (FIFO) property: departing later can never make you arrive strictly earlier [IGP03; Fon24]. Recent surveys of this field are given by Gendreau et al. [G15] and Adamo et al. [Ada+24]. KAYROS targets the duration-minimization variants of this problem, with or without time windows (TDVRPTW, TDVRP). Under this objective the departure time of each route from the depot is itself a decision variable, and a routeâs cost is the total time its vehicle is away, including any time spent waiting for a time window to open [VS20; LMS20]. This is a natural objective (drivers are paid for their working time, not for the clock time at which they return), and a computationally demanding one: as Section 2.3 illustrates, even evaluating the cost of a single fixed route requires optimizing over its departure time. Exact algorithms for these variants exist in the academic literature, notably the branch-and- price line of Dabia et al. [Dab+13] and the branch-price-and-cut (BPC) solver of Lera-Romero et al. [LMS20], alongside exact approaches on related TD problems [Ari+19; Vu+20; FDS23]. What has been missing is availability: to the best of the authorâs knowledge, no previously released solver combines, in one open-source package that installs with one command, (i) exact solving of the duration-minimization TDVRP(TW) over rich piecewise-linear travel-time functions rather than a time discretization, (i) anytime behavior, meaning that the solver streams improving solutions from the first seconds and can be interrupted at any point with an honest answer, and (i) no proprietary dependency, in particular no commercial LP solver. That combination is the claim this report makes for KAYROS, and it is deliberately narrow: this report claims neither that KAYROS is faster than existing exact TD solvers (no head-to-head has been run, see Section 8), nor that other solvers could not be extended similarly. 2.2 Why this gap matters: a decade of unmet demand The gap just described is not a theoretical nicety. Time-dependent routing over realistic travel times is a need that practitioners have voiced, in the open and for well over a decade, without ever receiving an integrated answer. The rest of this subsection puts that demand on the record, alongside the landscape of partial answers, so the claim of Section 1.1 can be read in context. The issue trackers of mainstream routing engines have publicly documented and collected requests for time-of-day-dependent travel times for over a decade, and the recorded answers trace the gap precisely: OR-Tools has closed such requests since 2017 with verdicts ranging from âhighly experimental, and currently not working very wellâ to, in 2024, âShort answer: you cannotâ; jsprit has carried the request since 2013; VROOMâs maintainer explains that a static travel-time matrix is the price of constant-time move evaluation; and PyVRP tracks time-dependent VRP as an open feature request awaiting funding, in which the lead maintainer proposes representing time dependence by âmatrices of piecewise linear arrival time functionsâ, 6 which is exactly the representation KAYR O S is built on 2 . Vendors and maintainers have each attempted an answer, with varying degrees of realism and success, as examined below. Meanwhile, the open metaheuristic libraries are laying piecewise-linear groundwork, with the most prominent published time-dependent result of that lineage targeting arc routing rather than the VRP [Vid+21]. The âto the best of the authorâs knowledgeâ in the availability claim above is not a shrug: before announcing the solver, we swept the obtainable landscape (open-source solvers, commercial solvers with academic access, and public research artifacts) for anything that could serve as a same-problem baseline, and the closest systems each miss a different part of the combination. Google OR-Tools [Goo26] comes closest: its routing layer publicly exposes cumul-dependent (departure-time-dependent) transit callbacks with piecewise-linear machinery and streams incumbents through solution callbacks, but its piecewise-linear transit anchors are integers, so carrying our arrival-time functions (the ATFs of Section 2.3) into it means quantizing them. Our probe found this quantization to be faithful (on probed instances the encoding error shrinks like the inverse of the scale, with zero feasibility flips), but it also found that the cumul-dependent part of this API cannot currently be activated: the Python bindings reject the callback registration, and the shipped engine stores such callbacks without ever evaluating them during search or solution restoration. The OR-Tools team had independently reached the same verdict months before our probe, announcing the public APIâs removal rather than its completion 3 . So OR-Tools cannot presently be fielded as a native time-dependent contender. The faithful-quantization result keeps a future comparison open should the evaluation machinery ever land upstream. jsprit [Gra26] accepts user-coded departure-time-dependent transport costs, but its search evaluates routes forward only (a limitation its own issue tracker documents), which is the wrong bias when the departure time is a decision. Timefold [Tim26] offers a clean extension surface for building a time-dependent route evaluator inside an open-source engine (arrival times already chain through its routing model), but ships no time-dependent travel times in the open solver. Its traffic-aware routing belongs to a proprietary platform we cannot audit and benchmark. Hexaly [Hex26] publishes a runnable time-dependent template under academic licensing, but it models time dependence as five constant travel-time matrices across the day and optimizes lateness, then fleet size, then distance: a legitimate industrial model, and a different computational problem from duration minimization over rich arrival-time functions (Section 2.4). Against that landscape, KAYROS is, to the best of the authorâs knowledge, the first integrated, openly available answer to this documented demand, for the duration-minimization variants it targets: exact and anytime, over the rich continuous representation proposed in the PyVRP thread itself. A cross-solver comparison campaign, tiered by what is honestly comparable (same 2 Representative threads, all accessed 2026-07-19:https://github.com/google/or-tools/ issues/339 ,https://github.com/google/or-tools/discussions/4230,https://github. com/PyVRP/PyVRP/issues/867,https://github.com/VROOM-Project/vroom/issues/1280, https://github.com/graphhopper/jsprit/issues/22. 3 https://github.com/google/or-tools/issues/5070, closed 2026-02-28 by an OR-Tools maintainer: âThis code does not work. We will remove the c++ version and not expose it in other languages.â Our probe ran againstortools9.15.6755 and the upstream development branch as of 2026-07-15. An internal implementation appears to exist but was never exported to the open-source tree. 7 objective, routes re-scored by the public checker, or disclosed model conversion), is under way at the time of writing. Whatever it reports will be arbitrated by that checker, the benchmark platformâs reference implementation of route cost (Section 3): its arithmetic is published, anyone can re-run it, and KAYROSâ own bit-level alignment with it (Section 3.2) will be disclosed up front in any comparison. 2.3 Travel times as functions: a two-client tour Everything specific about time-dependent routing can be seen on a tour with two clients, and this section walks through one. A vehicle leaves the depotoat a departure timet 0 of our choosing, visits client 1, then client 2, and returns to the depot (writtendfor the return copy of o, a standard convention). Client 1 accepts service between times 4 and 9, client 2 between 6 and 9, and service itself takes zero time in this toy. Time units are abstract. Think of hours of a working day. The travel time of each of the three arcs is a functionĎ(t) of the departure time ton that arc: here the two arcs into and out of client 2 always take 2 hours, while the arc from the depot to client 1 takes 2 hours off-peak but climbs to 4 hours during a morning rush, as plotted in Figure 1. These are Travel Time Functions (TTFs): piecewise-linear, and FIFO in the sense above. 012345678 0 1 2 3 4 5 rush hour departure time t on the arc travel time Ď ( t ) Ď o1 : congestion peak Ď 12 = Ď 2d = 2 Figure 1: The three arc Travel Time Functions (TTFs) of the toy tourâ¨o,1,2,dâŠ. The arc from the depot to client 1 has a morning congestion peak. The two other arcs are constant. Every travel time in this example is a continuous piecewise-linear function of the departure time on the arc. Suppose the vehicle leaves att 0 = 0. It arrives at client 1 at time 2, but client 1 only opens at 4: the vehicle waits two hours. It then reaches client 2 at 6, right at opening, and returns to the depot at 8. The route takes 8 hours, 2 of them spent waiting. Now suppose it leaves att 0 = 2 instead: it arrives at client 1 exactly at 4, at client 2 exactly at 6, and is back at 8, for a duration of 6 hours. Leaving two hours later gets the driver home at the same instant. Any later, though, and the departure runs into the rush hour on the first arc: arrival times now grow three times faster than the departure delay (the arcâs travel time grows at slope 2, so arrival grows at slope 3), and pastt 0 = 3 the vehicle can no longer reach client 2 before its time window closes at 9: the route becomes infeasible. 8 Two functions summarize this behavior completely, and they are the objects a time-dependent solver actually computes with. Composing the arc Arrival Time Functions (ATFs)Îą(t) =t+Ď(t) with the time-window waiting at each client yields the routeâs ready-time functionδ r (t 0 ): the time the vehicle is back at the depot as a function of its departure time [VS20; LMS20]. For our tour, this entire analysis collapses to a three-breakpoint piecewise-linear function, plotted in Figure 2 (left). Subtracting the departure time gives the route duration function â r (t 0 ) =δ r (t 0 )â t 0 , written â after Lera-Romero et al. [LMS20] (right panel): it falls at slopeâ1 while later departure eats into waiting, reaches the optimum â â r = 6 att 0 = 2, then climbs at slope +2 into the congestion, until infeasibility att 0 = 3. This minimum duration, â â r = 6, is the routeâs Minimum Duration Time (MDT). It is attained at the optimal departure timet â 0 = 2, both marked on the right panel. Finding the best departure time of a route means minimizing this function. 01234 5 6 7 8 9 10 11 12 infeasible plateau: same arrival EAT = 8 depot departure time t 0 arrival back at depot δ r ( t 0 ) 0123 4 5 6 7 8 9 infeasible MDT = 6 t â 0 = 2 waiting-dominated congestion depot departure time t 0 route duration â r ( t 0 ) Figure 2: The toy route summarized by two piecewise-linear functions of the depot departure timet 0 . Left: the ready-time functionδ r (arrival time back at the depot), with breakpoints at (0,8), (2,8), (3,11). Right: the route duration function â r (t 0 ) =δ r (t 0 )â t 0 , minimized at departure time 2 with optimal duration â â r = 6. Pastt 0 = 3 the route is infeasible. Following the per-route displays of the MAMUT-routing store, the left panel marks the Earliest Arrival Time (EAT = 8, the plateau value ofδ r ) and the right panel the Minimum Duration Time (MDT = â â r = 6, attained at the optimal departure timet â 0 = 2). All plotted values were computed with the MAMUT-routing reference checker. The left panel also shows why the departure time is a genuine decision and not an afterthought. Every departure in [0,2] produces the same arrival at 8, which is also the routeâs Earliest Arrival Time (EAT) at the depot: an objective that only minimizes the arrival time (the makespan, natural when departures are fixed [FDS23]) cannot distinguish leaving at 0 from leaving at 2, while their durations differ by two full hours. Duration minimization sees the difference, which is precisely what makes it harder: for a route with many clients over travel-time functions with many pieces,δ r must be built by repeated function composition, and its number of breakpoints grows with both [VS20]. A time-dependent solver performs this kind of composition millions of times: inside every local-search move evaluation of a heuristic and inside every labeling step of an exact pricing algorithm. Making that operation fast, and above all exact, is where much of the engineering of Section 3 goes. 9 2.4 Representing time dependence How the travel-time functions themselves are represented splits the field, and locating KAYROS in that split is the last piece of context needed. The richest common representation, adopted by the exact literature KAYROS builds on, keeps arc travel times as explicit continuous piecewise- linear functions, either given directly or generated from compact speed profiles in the model of Ichoua et al. [IGP03], as in the canonical TD benchmark derived from Solomon instances by Dabia et al. [Dab+13]. KAYR O S consumes this representation natively: its engine composes Non-Decreasing Continuous PieceWise-Linear Functions (NDCPWLF, the ATFs of the previous section) exactly, with no approximation anywhere between the instance data and the reported cost. The main alternative is to discretize time. Commercial solvers that handle time dependence typically model the horizon as a small number of constant-speed periods 4 , and part of the exact literature works on time-expanded graphs whose discretization is refined on demand [Vu+20; He+22]. Discretized models are legitimate and useful, but they answer a different computational question: a piecewise-constant approximation of a continuous travel-time landscape changes optimal values and can change optimal routes, so results on the two representations are not comparable. The claim of this report lives strictly on the rich piecewise-linear side of this divide. One benchmark family deserves a special mention because it stress-tests that divide from within. The Lyon instances of Rifki et al. [RCS20], derived from a real urban traffic simulation complemented with real-world data, have stepwise travel times: at certain instants, the travel time of an arc genuinely jumps (Figure 3, left). Such value jumps are vertical steps in the function graph, and they break the comfortable assumptions of continuous piecewise-linear machinery. How KAYROS initially mishandled these jumps through a smoothing trick, how that error was caught by its own verification protocol, and how the engine now carries verticals as tagged first-class objects, is the story of Section 4. Section 3 first presents the solver in which that story takes place. 4 For instance, the Hexaly modeling template for time-dependent routing divides the day into five parts (early morning, morning peak, day, evening peak, night):https://w.hexaly.com/templates/time-dependent- routing-problem-with-time-windows-tdcvrptw. 10 345 2 3 tagged vertical departure time t travel time Ď ( t ) stepwise: a genuine vertical step 345 2 3 width 10 â3 , slope â 10 3 h departure time t travel time Ď ( t ) mollified: a steep bridge (retired) Figure 3: Stepwise travel times. Left: a genuine value jump, represented in the KAYROS engine as a tagged vertical step, both of whose endpoint values are preserved. Right: the retired âmollifierâ approach, which replaced the jump by a steep bridge of width 10 â3 . For a jump of heighththe bridge has slope of order 10 3 h , which is what eventually made epsilon-based comparisons unsound (Section 4.3). 3 The KAYROS solver KAYROS is two solving modes on one exact time-dependent engine, as sketched in Figure 4: an anytime heuristic stack that produces good solutions early and keeps improving them, and an exact branch-price-and-cut component that proves optimality. Both express every cost through the same NDCPWLF engine, and both answer to an authority deliberately placed outside the solver: the reference checker of the MAMUT-routing benchmark platform [RP26], whose arithmetic defines what a route officially costs. The name KAYROS is a nod to Kairos (κιΚĎĎĎ), the ancient Greek notion of the right, opportune moment, fitting for a time-dependent solver where when each route departs is itself a decision. It is also a recursive acronym, Kayros Anytime-Yielding Routing Optimization Solver. Python API: kayros.solve (anytime), kayros.lera (exact) pip install kayros Anytime stack (C++) greedy construction, TD-ILS granular local search, TD-ACO Exact component (C++) vendored BPC (Lera-Romero et al. 2020) HiGHS LP backend NDCPWLF engine (C++): checker-exact composition of travel-time functions, exact IEEE-754 arithmetic, tagged verticals, bit-reproducible MAMUT reference checker (referee) arbitration solver outside the solver Figure 4: The KAYR O S architecture. Two solving modes, anytime and exact, share one NDCPWLF engine that ports the reference checkerâs arithmetic bit-identically. The checker itself stays outside the solver as the referee: every value KAYROS reports is a checker value, never an internal approximation. 11 3.1 Design principles Seven commitments, stated up front because every later design choice follows from one of them. â˘The checker is the referee. Every solution and every certificate is priced by the reference checker ofmamut-routing-lib. The checkerâs value is the value. The solver never grades its own homework. â˘Exact arithmetic. The engine computes in plain IEEE-754 double precision with no epsilon comparisons and no fused-multiply-add contraction (-ffp-contract=off). Results are bit-reproducible across machines, which is what makes the cross-platform certification gate of Section 4.2 meaningful. â˘Anytime first. Time budgets are hard deadlines honored by every component, heuristic and exact alike, and improving solutions stream out as they are found. A solver that only answers at the end is not a solver you can interrupt. ⢠Honest verdicts. A run ends with an answer: optimum, time limit, or resource limit (the OPEN and RESOURCE_LIMIT verdicts of Section 4.1), with valid bounds where they exist. The solver is never killed mid-certificate by the operating system, and it never claims more than its arithmetic supports. ⢠One-command install, no proprietary dependency. The default build, including the exact component, is pure open source: the HiGHS linear-programming solver is built statically into the wheels. A faster CPLEX backend exists but is strictly a source-build opt-in and never ships in a wheel. â˘One run is one thread. There is no intra-run parallelism. Parallelism belongs to the experiment layer above, where it cannot perturb reproducibility. In practice that layer is an experiment runner built on GNUparallel, which schedules thousands of independent single-threaded solver runs across the hosts of a multi-host Gridâ5000 reservation. The solver itself never spawns a second thread. â˘POD core. The new C++ is plain structs, flat arrays and free functions, in optimization- kernel style with no framework. The vendored BPC keeps its upstream style, contained under its own directory. 3.2 The NDCPWLF engine The bottom layer answers one question: what does a route cost? As Section 2.3 showed, in duration-minimization TD routing that question is answered by composing piecewise-linear functions, so the engine is a library for representing and exactly composing NDCPWLFs. It is a C++ port of the reference checkerâs arithmetic, and the port is bit-identical: an equivalence suite over the full benchmark set gates any change against the Python checker, so a route evaluated inside the solverâs innermost loop costs exactly, to the last bit, what the public checker 12 says it costs. Composition follows the move-evaluation theorems of Visser et al. [VS20] and is implemented as a two-pointer event merge, linear in the total number of breakpoints of the two operands. Since version 1.1, vertical steps (the value jumps of Section 2.4) travel through this machinery as tagged first-class objects: a vertical knows whether it encodes a travel-time jump or a departure-time choice, and both endpoint values are preserved through composition, addition and minimum operations rather than collapsed to a representative point. 3.3 The anytime stack The heuristic mode, exposed askayros.solve, is a single-trajectory TD Iterated Local Search (ILS). A greedy constructor builds a first feasible solution. Local search then descends through tree-ranked relocate, swap and 2-opt* moves restricted to granular candidate lists, with every accepted move repriced by the checker-identical route evaluation before it counts. Perturbation applies ruin-and-recreate kicks, acceptance follows the late-acceptance hill-climbing rule [B17], and the trajectory restarts to the best-known solution when it stalls. Move evaluation in the time-dependent setting is itself nontrivial: KAYROS maintains the route functions in the balanced-tree scheme of Blauth et al. [Bla+24], selected over the alternative structure of Visser et al. [VS20] after microbenchmarks on our instance families. A MAX-MIN TD Ant Colony Optimization (ACO) strategy is available as an alternative. The choice of ILS as the default is an experimental result, reported in Section 6.5. Every improving solution is surfaced to the caller the moment it is found, which is what anytime means in practice: the solver is already useful after a few seconds and keeps improving until the deadline. 3.4 The exact component The exact mode, exposed askayros.lera, is built on the branch-price-and-cut solver that Lera-Romero et al. [LMS20] published as open source alongside their paper: a set-partitioning master problem, subset-row cuts, and bidirectional labeling with piecewise-linear domination. In column-generation terms: a master linear program selects routes from a pool, a pricing subproblem proposes new candidate routes (the columns), and labeling is the dynamic program that enumerates those candidates. KAYR O S vendors that solver whole, under its MIT license and original naming, and every local modification is enumerated in a NOTICE file that has grown into a detailed engineering ledger. The substantive extensions are: the open-source HiGHS LP backend as the default (making the exact component the part of KAYROS that would traditionally have required a commercial license); full deadline compliance, so that every phase of the search draws its residual budget from one absolute deadline and incumbents stream out through a callback (anytime behavior inside an exact method); warm starts injected as columns, which turns the certification of an already-known good solution into the fast path; repricing of every column entering the master problem in the checkerâs exact arithmetic; support for the TDVRP variant without time windows; a memory self-guard that polls a resident-set-size (RSS) watermark at the same interruption points as the deadline and unwinds cleanly with an honest resource-limit verdict instead of being OOM-killed; and the exact value-jump labeling 13 path for stepwise travel times, recounted in Section 4. The semantics of a resulting certificate are stated precisely and modestly: optimal under checker-exact route costs and standard LP and pricing tolerances, completeness modulo the search engineâs epsilon dominance. Turning the LP dual bounds themselves into rigorous certified bounds (safe bounding) is explicitly (phd-size) future work, not a claim. 3.5 Packaging and availability KAYROS installs withpip install kayros(PythonâĽ3.11, with Linux x86-64 wheels for CPython 3.11 to 3.14), which also pulls the benchmark loaders and the reference checker through its one runtime dependency,mamut-routing-lib. The source builds with a C++23 compiler, CMake and the Boost.Graph headers and library, fetching and statically linking HiGHS when absent. The code is MIT-licensed, developed on GitHub, and archived by Software Heritage [Ras26a]. For academic referencing, the archived release identifiers are preferable to the moving repository. The heuristic and exact APIs shown in this section are the entire public surface: an instance path in, checker-priced solutions and verdicts out. 4 Certificates, and the day we retracted 160 of them Exactness is a claim about software, and software is where such claims die. This section describes the protocol under which KAYROS calls a solution proven optimal, and then recounts, deliberately and in some detail, the episode in which that protocol caught the solver certifying wrong optima, leading to the public retraction of 160 certificates and, ultimately, to the exact stepwise machinery of version 1.1. We tell this story at length because it is the part of the work we would most want a skeptical reader to check. 4.1 What a certificate is An optimality certificate is a stamp of optimality on a stored solution: it asserts that the solutionâs value has been proven to be the best achievable on its instance, so the protected number is no longer a best-so-far but a final answer, within the semantics stated at the end of this subsection. Because such a stamp is only as strong as the process behind it, a KAYROS certificate is never the output of a single run. An instance is stamped proven optimal only when four independent exact solves agree: cold-started and warm-started, each under two distinct labeling configurations. Each of the four runs must have completed an audited exact-pricing phase (a run that only ever priced heuristically cannot certify, a condition that exists because of the bug recounted below), and every column that entered the master problem is repriced in the reference checkerâs arithmetic, with any checker-infeasible column disqualifying the run. The four checker-exact values must agree on the optimum. The resulting claim is stated with its exact scope: optimal under checker-exact route costs and standard LP and pricing tolerances, 14 completeness modulo the search engineâs epsilon dominance. Runs that do not reach a certificate end in one of two honest verdicts: OPEN when the time budget runs out, RESOURCE_LIMIT when the memory self-guard stops a pricing phase that would outgrow the machine. Certified instances currently range fromn= 10 ton= 100 clients, with per-run wall times on the published stamps from seconds to roughly 85 minutes. 4.2 The validation ladder Before any build of the exact component is allowed to stamp certificates, it must climb a ladder of validation gates on the Gridâ5000 testbed. A gate is a pass-or-fail test campaign whose criterion is fixed in advance: the build either clears it or is not promoted. The first gate checks arithmetic. Two independently compiled builds, on different Linux distributions with different compilers, must reproduce certified values bit for bit. The version 1.1 promotion passed this gate on 13 of 13 instances. The second gate is a differential fuzzer: a harness that generates randomized instances, solves each one in the solverâs different labeling modes, and fails on any disagreement between runs that should be equivalent. The third gate is a full-family sweep, 778 runs at the last promotion, which scans every stamped family for unsound or protocol-violating outcomes. It found none. The final gate re-runs the complete four-solve protocol of Section 4.1 with the promoted build. For version 1.1 this covered the 360 instances of the stepwise families plus one historically problematic non-stepwise instance, for 1444 runs in total. The outcome: 93 stored certificates re-confirmed at their exact stored values, with a worst four-run spread of 4Ă10 â12 ; 249 instances left honestly OPEN; 19 ended at the memory frontier with a RESOURCE_LIMIT verdict; zero checker-infeasible columns anywhere. No stored value changed. The campaignâs instances carried 108 previously stored certificates. The 15 that were not re-confirmed simply exceeded the campaignâs per-run budgets and ended OPEN, and every certifying run they did produce reproduced the stored value exactly. 4.3 The self-refutation and its repair The Lyon-derived Rifki2020 family [RCS20] has stepwise travel times: genuine value jumps of the kind shown in Figure 3. The original exact component inherited machinery for continuous functions only, so the first supported path mollified the steps, replacing each vertical jump by a steep bridge of width 10 â3 . We argued at the time that this smoothing could not certify a wrong optimum. That argument was wrong, and we refuted it ourselves: on 2026-07-08, independent heuristic campaigns produced checker-valid solutions strictly better than 43 of the 160 certified Rifki2020 optima, by up to 1.46%, and certification outcomes turned out to depend on the warm start. All 160 Rifki2020 certificates were retracted from the public store the same day. The forensic work that followed found not one cause but several, stacked. A bridge of width 10 â3 over a jump of heighthhas slope of order 10 3 h , so the solverâs inherited 10 â6 epsilon comparisons from the original code of Lera-Romero could misprice a function merge by an amount proportional to the jump itself. The function-inversion routine was rebuilt as an exact 15 coordinate swap. An uninitialized boolean in the labeling code silently read stack garbage and made certification outcomes differ between identically fed builds. It is now explicitly initialized. Most consequential of all, the pricing ladder that escalates from heuristic to exact pricing could, under a deduplication interaction, declare victory without ever running a single exact-pricing iteration, issuing a certificate whose exactness no component had actually checked. Escalation is now driven by column additions, and the audited exact-pricing phase became a hard precondition of the certificate itself (Section 4.1). The definitive repair shipped in version 1.1. Rather than smoothing the steps, the labeling now prices them exactly, carrying verticals through every function operation as tagged first-class objects. Activating this path exposed three further completeness defects, each found by tracing a witness column that the labeling should have produced and did not. The label-extension composite erased position-dependent mandatory waiting exactly where a departure-function plateau meets a same-abscissa jump (fixed by recasting the extension through an elapsed-time identity on step-carrying arcs); the solution pool deduplicated candidate routes by their customer set, so a cheaper ordering of the same customers could remain shadowed behind a costlier one (the exact path now keys the pool by the full path); and the piecewise-linear operators dropped stacked vertical tails at operand exhaustion (they now preserve tags and attained endpoints throughout). With the three fixes in place, the three pinned reproducer instances certify identical values cold and warm. The stepwise mollifier was thus deleted rather than merely disabled, and the full validation ladder of Section 4.2 came back clean, including the 1444-run re-certification. On instance families without value jumps, the version 1.1 build is bit-identical to its predecessor, such that the original certificates from Lera-Romero over the classic Dabia2013 benchmark family remain valid. What we take from the episode is not that the protocol failed, but that it worked: the wrong certificates were found by the projectâs own redundancy (independent heuristic campaigns feeding the same public checker), diagnosed by its own audit trail, and repaired under gates that make a regression of the same kind loud. Section 7 returns to this point, because it is also the honest answer to a question every reader should ask about software built at the speed this one was. 5 Poryos2026: an OpenStreetMap-based modern TD benchmark family Poryos2026 is a second concrete deliverable of this work: a family of 1,080 paired instances for CVRP, VRPTW, TDVRP and TDVRPTW, designed and generated by the author of this report from the road networks of five cities [Ras26b]. It is distributed through MAMUT-routing, the collaborative benchmark platform developed as part of the ANR-MAMUT project [RP26]. Authorship and infrastructure should not be conflated: the author is solely responsible for the design and generation of Poryos2026, while the collaborative MAMUT-routing project provides the shared schemas, checker, catalog and publication surface. 16 The name Poryos2026 is a coinage built on Poros (ĎĎĎÎżĎ), the allegorical figure in Platoâs Symposium who personifies the expedient, resourceful way through. The underlying Greek word pĂłros means a passage or route and, by extension, the means of reaching a goal 5 . The added y mirrors the respelling of Kairos as KAYROS: KAYROS supplies the timing, while Poryos2026 supplies the paths, which is the natural pairing of a time-dependent routing solver and its road-network benchmark. The suffix 2026 is the release year. The intended realism is specific. Road topology, directed connections, edge lengths, road classes and route geometry derive from OpenStreetMap data for Lyon, Paris, San Francisco, Hong Kong and Tokyo [Ope26]. Customer positions are attached to those road networks: the POI method uses OpenStreetMap points of interest, while the hybrid method supplements them with a controlled parametric spatial sample. Demands, vehicle capacities, service times, time windows and traffic are synthetic constructions. Poryos2026 is therefore an OSM-based, realism-oriented benchmark with actual urban road geometry, not a claim to measured demand or observed traffic. This distinction preserves both the benchmarkâs practical value and the reproducibility of the factors it varies. 5.1 A paired design across four routing problems The family begins with 60 bases: five cities, six customer countsnâ10,25,50,100,500,1000, and two sampling methods. The POI method samples OpenStreetMap points of interest. The hybrid method combines such points with a parametric spatial sample so that sparse POI coverage does not determine the entire topology. Each base fixes the customers, their coordinates, demands and vehicle capacity. The capacity policy targets several customers per route and rejects any base whose capacity lower boundâ P i q i /Qâis smaller than two, preventing nominally routing-shaped instances that collapse to a single tour (TSP degeneracy). Problem type Variants per basePer base Instances CVRPEuclidean, shortest-road and fastest-road costs3180 VRPTWShared, tight and spread time-window sets3180 TDVRPTwo traffic models at three intensities6360 TDVRPTW The same six overlays with shared audited windows6360 Total over 60 bases1080 Table 1: Composition of Poryos2026. The counts are generated directly from the canonical collection. Every base shares its customer set, demands and capacity across all variants. All 1,080 instances have a checker-validated best-known solution obtained by PyVRP (static) and KAYROS (TD) on Gridâ5000 campaigns. The three CVRP variants use Euclidean distance, shortest-road distance and free-flow fastest- road travel time. The three VRPTW variants use the fastest-road metric with shared, tight and 5 https://fr.wikipedia.org/wiki/Poros_(mythologie) 17 spread time-window sets. The TDVRP and TDVRPTW sides each cross two traffic models with light, moderate and heavy intensities. The bare-base VRPTW instance and its six TDVRPTW twins share the same windows. The tight and spread sets are deliberately static-only. This construction supports controlled comparisons in which the customer geography stays fixed: Euclidean versus road-network cost, static versus time-dependent travel, windows versus no windows, and light versus heavy congestion. Figure 5: Road graph and checker-validated best-known solution for the TDVRPTW instance poryos-lyon-n100-poi-bpr-heavy. The 100 customers lie on the extracted Lyon road graph and the eight colored routes follow its directed edges. Geographic and road data are from OpenStreetMap contributors under ODbL 1.0 [Ope26]. Arc costs are stored as three-decimal values rather than rounded to the CVRPLIB integer convention, giving the static and time-dependent variants a common cost space. This choice is not cosmetic: scaling and rounding can alter feasibility, distort objectives and change empirical 18 solver comparisons [Ras+26]. Solvers that require integers can multiply all three-decimal quantities by 1,000 without discarding decimal precision, but published solutions are always re-evaluated by the MAMUT-routing checker in the canonical instance space. The checker, rather than a solverâs internal arithmetic, determines feasibility and the stored BKS cost. 5.2 From a city extract to time-dependent instances The complete generation pipeline is implemented in Python by MAMUT-routing-tools 0.4.0, and the generated instances are loaded and checked by mamut-routing-lib 0.8.0. The public website is a static publisher of these canonical artifacts, not an opaque generation service. Figure 6 summarizes the stages. 1. City data OpenStreetMap city extract 2. Road foundation Drivable graph real geometry class-derived free-flow speeds 3. Cus- tomer base POI or hybrid sampling demands, capacity and ser- vice times 4. Derivations Three static metrics three win- dow sets six traffic overlays pinned paths and ATFs 5. Validation Capacity and horizon anchor au- dit under all six overlays SHA-256 pins reference checker 6. Pub- lished family CVRPĂ3 VRPTWĂ3 TDVRPĂ6 TDVRPTWĂ6 complete BKS Figure 6: Generation, feasibility and publication pipeline for Poryos2026. Blue boxes are OSM-derived foundations, orange boxes are controlled benchmark derivations, the green box gathers validation gates, and the purple box summarizes the published paired variants. First, the generator extracts a drivable directed graph from each OpenStreetMap city file, retaining coordinates, road geometry, edge lengths and class-derived free-flow speeds. It samples customers, trims the graph to the routes relevant to them, and computes Euclidean, shortest- distance and free-flow fastest matrices. Each customer pair also pins its free-flow fastest path through the trimmed graph. This last decision is important: traffic changes the time required to traverse that path, but does not dynamically reroute the vehicle to a different path. It makes the time-dependent construction deterministic and comparable while leaving dynamic path choice as a future benchmark dimension. Second, the generator assigns synthetic demands, capacity and service times, then creates three time-window sets. The shared windows are centered around deterministic capacity-and-horizon- feasible anchor routes under free-flow fastest travel. The tight set narrows those route-centered windows, whereas the spread set redistributes their centers over feasible intervals. The latter two are useful static controls, while only the shared set proceeds into TDVRPTW generation. Third, two traffic constructions produce 24 hourly edge-speed bins at three intensities. The BPR construction samples a synthetic commuter population, routes its trips on free-flow fastest paths, accumulates hourly edge flows, and applies the standard Bureau of Public Roads volume- delay relationshipt=t 0 [1+0.15(v/c) 4 ] with road-class capacities [Fed22]. The wave construction instead imposes reproducible morning and evening speed depressions whose amplitude depends on intensity, road class and distance to the city center, with seeded per-edge variation. Both 19 constructions are clamped at the free-flow speed: congestion can slow an edge but never make it faster than its static twin. Finally, the loader composes the edge speeds along each pinned path over the 24-hour horizon. It samples departures every 60 seconds, preserves the resulting FIFO arrival-time behavior, and deterministically simplifies the materialized piecewise-linear arrival-time functions with a one-second tolerance up ton= 100 and two seconds above it. The instance pins the road graph, traffic overlay and materialized functions by SHA-256. A clone of the published collection is consequently sufficient to load the same canonical bytes and verify their internal relationships without consulting a live routing service. 5.3 Feasibility by construction, then by audit Random time windows combined with congestion easily produce infeasible benchmark instances, particularly atn= 500 andn= 1000. Poryos2026 avoids solving this problem after publication by carrying a feasibility witness through generation. Each route-centered base stores deterministic anchor routes that cover every customer exactly once, respect capacity, fit the 24-hour horizon and are feasible under free-flow travel. Before the TD twins are emitted, the complete anchor solution is simulated under all six traffic overlays. If congestion makes a customer deadline too early, the generator applies the smallest shared integer deadline lift needed across the six overlays. Earliest bounds are never reduced, every window must retain strictly positive width, and every route must still return before the horizon. Failure of any check aborts generation. This is an existence guarantee, not a claim that the anchor is good. The anchor proves that every published TDVRPTW instance has at least one feasible solution under the same checker semantics used later for experiments. Independent validation then checks schemas and hashes, hydrates the sidecars, materializes the arrival-time functions, and evaluates solution files. Every one of the 1,080 published instances carries a complete checker-valid BKS. On the 720 time-dependent instances those BKS were produced by KAYROSâ anytime component. None is presented as proven optimal because these large OSM-based instances lie (far) beyond the exact reach described in Section 6.2. The design deliberately separates repeatability of the published collection from regeneration from a changing upstream map. Every artifact is canonical JSON seeded from its instance name and checksummed. These published bytes are the benchmark. Re-running the raw OSM extraction with a different toolchain or map snapshot may change source identifiers or roads, so such a run creates a new derivation rather than silently redefining an existing instance. The dataset inherits the Open Database License and credits OpenStreetMap contributors in its metadata and documentation. 20 6 Experimental evidence on MAMUT-routing 6.1 The benchmark collection KAYR O S is developed against, and evaluated on, the open MAMUT-routing benchmark platform [RP26]. Its canonical public deployment is the official MAMUT-routing website, while a separately hosted personal mirror maintained by the author provides the same publication surface. At the time of writing the catalog spans 4 problem classes, 17 instance families and 4,678 instances, every one of which carries a checker-validated best-known solution. Its time-dependent side curates the four legacy TD families of the literature into one explicit distribution format in which travel-time functions are shipped as checksummed artifacts rather than left to each groupâs reimplementation: the TD-Solomon instances of Dabia et al. [Dab+13] built on Solomon [Sol87] with the speed model of Ichoua et al. [IGP03], the families of Arigliano et al. [Ari+19] (distributed as Ari2018) and Vu et al. [Vu+20], and the Lyon traffic-simulation instances of Rifki et al. [RCS20]. Each family exists in TDVRPTW and TDVRP variants sharing the same travel-time data. Two new families extend the catalog beyond the literatureâsn= 100 ceiling: Lera2026 6 , which ports the classic large-scale instances of Gehring and Homberger [HG99] to time dependence atn= 200 to 1000, and Poryos2026, presented in Section 5. The best-known-solution store behind these families was produced on the Gridâ5000 testbed. Its largest single heuristic campaign comprised 20,808 runs over 30 hosts. 6.2 Optimality certificates in the public store Running the exact component under the four-solve protocol of Section 4.1 over the four legacy families has produced, as of 2026-07-18, 468 optimality certificates out of their 1,352 instances, published in the store as per-instance metadata that anyone can recompute against the reference checker. Table 2 gives the breakdown. Certified sizes range fromn= 10 ton= 100. The distribution is informative in itself: the Vu2020 TDVRPTW family is essentially closed (166 of 168), while the TDVRP variants are markedly harder, because removing time windows removes the pruning they provide and pushes exact pricing toward a memory frontier where the self-guard of Section 3.4 converts would-be crashes into honest resource-limit verdicts. The instances left OPEN or at the resource limit are not defects of the protocol but the current computational frontier of the exact component on an NP-hard problem, published as such. No certificates are claimed on Lera2026 or Poryos2026, which lie beyond current exact reach. Of the 468 certificates, 170 strictly improved the best-known solution previously recorded in the store. Since most of those prior records had been produced by KAYROSâ own heuristic, this figure measures the exact component against the heuristic, not against the literature, and the only literature-facing comparison we can honestly make is the one of Section 6.3. 6 The name is purely honorific and honors Gonzalo Lera-Romero, whose open-source exact TDVRPTW solver [LMS20] shaped this work. Lera-Romero is not an author of the benchmark family. The author of this report solely designed and generated the 480-instance TDVRPTW family and its paired TDVRP layer from the GehringâHomberger bases by applying the IGP travel-time model in the Dabia et al. five-period pattern, with deterministic congestion scenarios, feasibility repair and checksum-pinned reproducibility metadata. 21 Problem type FamilyInstances Proven optimal Share TDVRPTW Dabia2013168115 68% TDVRPTW Vu2020168166 99% TDVRPTW Rifki202018071 39% TDVRPTW Ari201816040 25% TDVRPDabia201316840 24% TDVRPVu202016800% TDVRPRifki202018036 20% TDVRPAri201816000% Total (four legacy families)1352468 35% Table 2: Proven-optimal instances per family in the public MAMUT-routing store (as of 2026- 07-18), out of the 1352 instances of the four legacy TD families (Ari2018 denotes the instances of Arigliano et al. [Ari+19]), under the four-solve certification protocol of Section 4.1. The table is generated from the campaignâs machine-readable verdict records, and the counts match the per-instance flags published on the platform. 6.3 Comparing against published results Comparing against the literature requires published reference values, and only one of the certified families has published proven optima in a machine-checkable form: the Dabia2013 TDVRPTW instances, through the solution distribution of Lera-Romero et al. [LMS20]. On that family, the 115 KAYR O S certificates decompose cleanly. Of these, 104 re-confirm a published proven optimum, at the exact published value. Another 11 are on instances the published tables left unproven, and 5 of those 11 strictly improve the published best value. Table 3 lists them. Nowhere in the store does a KAYROS certificate contradict a published proven optimum, which, given how different the two arithmetic pipelines are, we read as evidence for the solidity of both. For the Vu2020 TDVRPTW family, the published references are heuristic values, so we believe the 166 certificates there to be the first published proven optima for those instances. We state this as a belief rather than a verified claim, because it has not been machine-checked against the original tables of Vu et al. [Vu+20]. The 76 TDVRP certificates concern a variant for which we know of no prior exact results at all. Readers who know of published optima we should cross-check against, on any of these families, are warmly invited to point us to them. 22 InstancePublished best value KAYR O S certified optimum Improvement RC106_5011830.26411756.556 â0.62% RC106_10021382.24321233.331 â0.70% R104_10018344.46917949.848 â2.15% RC101_10024778.29424762.734 â0.06% R110_10018786.88218607.788 â0.95% Table 3: The five Dabia2013 TDVRPTW instances on which a KAYR O S certificate strictly improves the best published value from the distribution of Lera-Romero et al. [LMS20]. The improved values are read directly from the public store, where each carries its full certification metadata. 6.4 Complete heuristic coverage of Poryos2026 The link between the two deliverables is complete on the time-dependent side of Poryos2026. The public store contains checker-valid KAYROS BKS files for all 360 TDVRP and all 360 TDVRPTW instances, fromn= 10 throughn= 1000, under both traffic models and every intensity. Together with the 360 static BKS, this gives complete solution coverage of the 1,080- instance family. These are best-found solutions rather than exact certificates. Their purpose is to make the dataset usable immediately, supply reproducible baselines, and expose every stored route to the same public cost calculation used by the solver. This separation between a solverâs internal objective and the canonical re-evaluation space is particularly important when floating-point costs, scaling or rounding enter a benchmark [Ras+26]. 6.5 Choosing the default heuristic The one internal algorithmic comparison worth reporting is the choice of the default anytime strategy. The TD-ILS of Section 3.3 and the TD-ACO alternative were compared, alongside an ACO-then-ILS hybrid arm, in a 20,808-run head-to-head on Gridâ5000 across five TD families at sizesn= 10 to 1000, under matched time budgets and seeds. Of the 6936 paired comparison cells, ILS won 5714 and lost 305, with its margin growing with instance size. It has been the default ever since. We report this as an internal, same-engine comparison on our benchmark setup, not as a general statement about ILS versus ACO, though the author had previously observed the same pattern on the VRPTW literature families in another upcoming work. Figure 7 shows the anytime behavior behind that verdict, from a dedicated 4,160-run con- vergence campaign with five seeds and matched budgets, on two representative settings: the classic Dabia2013 family atn= 100 and Poryos2026 atn= 1000. ILS drives the mean gap to the post-campaign best-known solutions down to 0.56% and 0.06%, respectively, while ACO plateaus near 3.2% and 1.5% and never reaches a 1% mean gap on either row. Per run the picture is the same: at budget end, 84% of ILS runs sit within 1% of the best known atn= 100, and 100% at n = 1000, against 24% and 11% for ACO. 23 10 0 10 1 10 2 10 3 0 2 4 6 8 mean gap to BKS (%) Dabia2013, n = 100 TD-ILS TD-ACO 10 0 10 1 10 2 10 3 0 0.2 0.4 0.6 0.8 1 fraction of runs within 1% 10 0 10 1 10 2 10 3 0 0.2 0.4 0.6 0.8 1 within 0.5% 10 0 10 1 10 2 10 3 0 1 2 time (s) mean gap to BKS (%) Poryos2026, n = 1000 10 0 10 1 10 2 10 3 0 0.2 0.4 0.6 0.8 1 time (s) fraction of runs within 1% 10 0 10 1 10 2 10 3 0 0.2 0.4 0.6 0.8 1 time (s) within 0.5% Figure 7: Anytime convergence of the two KAYROS strategies, TD-ILS versus TD-ACO, on TDVRPTW Dabia2013 atn= 100 (top row, 1,200 s budget) and Poryos2026 atn= 1000 (bottom row, 7,200 s budget), from a 4,160-run campaign with five seeds and matched budgets on the same engine. Left: mean gap to the post-campaign best-known solutions, in percent, against wall-clock time on a logarithmic scale. Middle and right: fraction of runs within 1% and 0.5% of the best known by timet. The reference values are the public storeâs BKS, proven optimal for part of the Dabia2013 row and best-found on Poryos2026, so the plotted gaps in the latter case are upper bounds on the true optimality gap. 7 The humanâAI collaboration KAYROS had been on its authorâs roadmap for years before it existed. This section documents how it came to exist in about two weeks, because the author believes the working method is itself a result worth reporting, with the same care for what is and is not claimed as the rest of this document. 7.1 Setting and division of labor The human side of this project is one third-year PhD student. The AI side is Claude Fable 5 (Anthropic), a frontier model used in an agentic coding harness: the agent reads and edits files, runs builds and tests, launches and monitors experiments on the Gridâ5000 testbed, and works in long autonomous sessions (nights included) that are reviewed afterwards. Over roughly 14 days of wall-clock time, the author estimates the collaboration consumed over 100 hours of his 24 own working time 7 , on the order of 2.5Ă10 9 tokens across roughly ten thousand model calls, and over $4000 worth of API credits 8 . All of these figures are author-tracked estimates, reported for orders of magnitude rather than precision. The division of labor was stable throughout: the author owned the research direction, the design arbitrations (which algorithm, which invariant, which claim is publishable), the benchmark governance, and the final review of everything released, whereas the agent carried the bulk of the implementation, the iterative debugging, the experiment orchestration and the first drafts of technical documents, this report included. The agent is not an author of this report: authorship implies responsibility, and responsibility stays with the human. The corresponding disclosure appears in the acknowledgements. 7.2 Context-Oriented Programming The one practice the author would single out is what he informally calls Context-Oriented Programming (COP): treating the curation of the agentâs context, rather than the phrasing of requests, as the main lever on output quality. The project aggregates the ideas and negative results of more than twenty experimental repositories and over three thousand personal research notes accumulated during the authorâs PhD. The collaboration worked by distilling the relevant slice of that corpus, per work stream, into explicit written artifacts, namely design memos stating invariants and decision rationales, per-session logs recording what was tried and why it failed, and onboarding briefs that open each autonomous session with the mission, the files to read first, and the validation gates that define done. The agentâs sessions consume and extend these artifacts, so the projectâs memory lives in reviewable documents rather than in anyoneâs head, human or machine. The value-jump repair of Section 4.3, for instance, was launched from a written brief specifying the three failing reproducer instances, the tracing toolkit, and the full promotion ladder the fix would have to climb. The term is informal and the practice is not a validated methodology. It is simply the discipline that, in this projectâs experience, separated productive agent sessions from wasteful ones. AI-assisted programming and research are fast-moving fields, and it is not entirely clear what the best practices will be. The author hopes that this reportâs account of what worked and what did not will help other practitioners. 7.3 What became feasible Three concrete capabilities distinguish this project from what its author could have done alone, and none of them is âtyping fasterâ. The first is iterative design search inside inherited code. The exact component of KAYR O S extends a research solver whose internals (labeling, pricing ladder, piecewise-linear kernel) encode years of specialized decisions by its original authors. Diagnosing and repairing the defects 7 Real work time, i.e. not counting any form of pause. In practical terms, 2 weeks of intensive full-day working sessions. 8 The author made a great use of the promotional period offered by Anthropic following the public release of Claude Fable 5 25 recounted in Section 4.3 meant instrumenting that codebase, formulating competing hypotheses, building reproducers, and discarding several candidate designs, a cycle the collaboration could run many times per day. The engineering ledger kept in the vendored directoryâs NOTICE file records this process across its successive amendments, including the designs that were tried and abandoned. Working alone, the author estimates each such cycle in days rather than hours, with a corresponding pressure to stop at the first plausible fix rather than the correct one. The second is experimental thoroughness as a default. Calibrating the anytime stack (granular neighborhood sizes, acceptance parameters, kick strengths, the ILS-versus-ACO decision of Section 6.5) and validating every exact-path change through the full ladder of Section 4.2 required designing, launching, monitoring and analyzing campaigns of hundreds to tens of thousands of runs. With the agent handling orchestration and first-pass analysis, a 20,808-run comparison became a routine overnight experiment rather than a milestone. The third is the freedom to rewrite cleanly. The authorâs honest pre-agent practice, common in PhD work, was to build on top of existing research code and accept the accumulating debt. With the agent, the marginal cost of a disciplined rewrite dropped enough that KAYR O Sâ own layers (engine, local search, heuristics, bindings) were written fresh in a deliberately plain C++ style, with the inherited solver contained behind a documented boundary instead of being entangled with new code. The authorâs overall estimate, stated as such, is that the two weeks of collaboration compressed work he had previously scoped at two or more years of post-doctoral effort without use of AI. What this estimate cannot say is what a second attempt would cost, by him or by anyone else: this is a sample of one, a limitation Section 7.5 takes seriously. 7.4 Accountability: the checker is the referee The obvious objection to all of the above is trust: why should anyone believe results produced at this speed, partly by a system whose outputs are known to be fluent regardless of correctness? The projectâs answer predates the agent and is architectural rather than procedural: every value that matters is arbitrated by a reference checker that lives outside the solver, certificates require four independent agreeing solves with an audited exact-pricing phase, promotions climb a fixed ladder of gates, and every run ends in an explicit verdict and the state-of-the-art BKS solutions provided by Lera-Romero serve as a solid reference point (Section 4). Under this discipline, agent speed is safe in a specific sense: an error can still be produced quickly, but it has to survive redundant, externally checkable evidence to become a published claim, and the episode of Section 4.3, in which the protocol caught the solver certifying 43 wrong optima and forced a public retraction and repair, is the empirical demonstration rather than a counterexample. The same lesson reached beyond code: during the preparation of the launch materials, a fact-checking pass found that an AI-drafted reference in the solverâs own README misattributed the vendored solverâs paper to the wrong co-authors 9 . The correction shipped as a dedicated release within 9 This issue is not just about AI hallucination, I clearly read the reference and let the wrong author list slip through. This is because, as a human, I only remembered the citation from its first author, and the AIâs draft phrasing made me skim past the co-author list. The lesson is that a fluent draft can make a human reader skip verification steps, and that the checker must be external. 26 a day, and the project now derives every citation from its bibliography files rather than from any drafting process, human or machine. As a matter of fact, neither the human nor the agent are infallible. The authorâs position, argued by this reportâs existence, is that AI-augmented engineering does not lower the bar for verification. It raises it because verification becomes the binding constraint on what the collaboration may claim. 7.5 Limits of this account This is a single project, by a single practitioner, with effort figures that are self-reported and a counterfactual (âyears of solo workâ) that is an informed estimate, not an observation. The author was unusually well prepared for exactly this collaboration, with years of accumulated notes, benchmarks and failed prototypes for the agent to stand on, and the agent generation used here was released days before the work. Both facts limit generalization in opposite directions. Nothing here was a controlled comparison: no baseline team, no ablation of the working method, no blinded review of output quality. A proper study of AI-assisted solver engineering would need several teams, matched tasks, and independent verification budgets. Until such studies exist, accounts like this one should be read as documented experience reports, and this section has tried to be exactly that, failure included. 8 Limitations and outlook The limitations stated throughout this report deserve one consolidated list. No head-to- head comparison against another solver exists yet, and none is claimed. Section 2.2 reviews the obtainable near-misses and why none yields an honest same-problem table today, and benchmarking against the solver of Lera-Romero et al. [LMS20] would compare a fork against its own origin (and partly measure HiGHS against CPLEX). The tiered comparison campaign described in Section 2.2 is under way, and its results, if meaningful, are intended for a dedicated publication. We would sincerely welcome further solvers to measure KAYROS against, on equal representational terms. Certificates are exact under the stated semantics only: checker-exact route costs, standard LP and pricing tolerances, completeness modulo the vendored labelingâs epsilon dominance. Making the LP dual bounds themselves rigorous (safe bounding) is the one missing soundness layer and is future work. The exact reach currently stops atn= 100, and the TDVRP variants hit a genuine memory frontier that the self-guard converts into honest verdicts rather than results. No performance figures are published for the composition engine itself as it belongs to the planned dedicated publication featuring the NCPWLF machinery, so no speed claim is made anywhere. The distributed wheels cover Linux x86-64 only. The benchmark families are curated ports with explicit, versioned conventions, so results on them are not directly comparable to numbers reported on the historical distributions of the same names. Finally, KAYR O S is beta software with a compressed version history, and the storeâs own record shows that we have retracted certificates before. The protocol that caught that error remains in force, and we would retract again. 27 Poryos2026 adds a different set of limits. Its road geography and route geometry are real OSM-derived data, but hybrid customer placement and all demand, service, capacity, time-window and traffic data are synthetic. It should not be presented as an empirical city- logistics dataset. Its time-dependent costs follow fixed free-flow paths, so vehicles do not dynamically reroute around congestion, and its BPR and wave profiles provide controlled traffic scenarios rather than calibrated reconstructions of observed traffic. The complete BKS coverage establishes feasible baselines, not optimality. OSM itself evolves, which is why the canonical checksummed release, rather than a fresh extraction, defines each instance. These choices are conscious first-release boundaries. Measured traffic, alternative path behavior and cross-city calibration are natural extensions, but should be introduced as new benchmark versions rather than retroactive changes. 9 Conclusion Routing under time-dependent travel times is not a niche wish. For more than a decade, users of mainstream routing engines have requested it, time and again, and the public record of Section 2.2 shows several major solver teams, open-source engines and large commercial vendors alike, attempting an answer independently and each stopping short of the combination practitioners keep asking for. That documented, unmet demand is the gap KAYROS was built to close. It closes a precise part of it. KAYROS is, to the best of the authorâs knowledge, the first openly available solver that is both exact and anytime for duration-minimization time-dependent vehicle routing over rich piecewise-linear travel times: one command to install, no proprietary dependency, 468 published optimality certificates behind it, and a certification protocol that anyone can re-run against a public reference checker. The research program continues past it: safe dual bounds, larger exact reach and honest cross-solver comparisons are open, on a benchmark platform designed to make each of them checkable by construction. The second deliverable is Poryos2026, the authorâs 1,080-instance OSM-based family spanning CVRP, VRPTW, TDVRP and TDVRPTW. It supplies real road topology and geometry, controlled paired static and time-dependent variants, explicit feasibility witnesses, checksummed generation artifacts and a checker-valid BKS for every instance. Together, KAYROS and Poryos2026 provide a solver and a realism-oriented benchmark on which its anytime behavior can be reproduced from n = 10 to n = 1000. The reportâs third contribution is its account of how this work came to exist. Two weeks of intensive collaboration between one PhD student and an AI agent delivered work the author had scoped at years, and the verification discipline documented in Sections 4 and 7 is what made that speed scientifically sound. KAYROS thus stands as a documented use case of effective humanâAI research and engineering. Its outcomes are concrete: an open-source solver, a new benchmark family, and public reference infrastructure through which anyone can run and verify them today. 28 Acknowledgements I thank Romain Billot, Christine Solnon and Lina Fahed, who supervise the PhD this work is built for. I owe special thanks to Christine for her guidance and for more than a decade of involvement in time-dependent routing, reaching back to her supervision of PĂŠnĂŠlope Aguiar- Melgarejoâs doctoral thesis on the time-dependent traveling salesman problem [Agu16]. I thank Romain Fontaine for his help with Gridâ5000, where every KAYROS validation and certification campaign runs. This PhD is a multi-vehicle follow-up to his TDTSPTW thesis and the exact-and-anytime dynamic-programming solver presented in that thesis and its EJOR article [Fon24; FDS23]. I thank Gonzalo Lera-Romero for making his branch-price-and-cut solver open source [LMS20]: a major milestone on the road to this thesis and the direct inspiration for the exact component of KAYROS. I thank Leon Lan, Niels Wouda, Wouter Kool and the other contributors to PyVRP, whose open-source framework was a major inspiration for KAYROSâ anytime heuristic layer, both for the insight that a single-trajectory iterated local search is a strong, simple and scalable anytime metaheuristic for vehicle routing and for its C++/Python architecture. I thank Thibaut Vidal, who initiated the movement of open-source vehicle-routing solvers and whose HGS-CVRP is a reference anytime metaheuristic for vehicle routing. I thank Adrien Pichon 10 for the collaboration on MAMUT-routing [RP26], the platform on which the benchmark catalog and best-known-solution store of Section 6 are published. I also thank Marc Sevaux and Alexandru-Liviu Olteanu, fellow members of the ANR-MAMUT project behind that catalog. Poryos2026 itself was designed and generated by the author. I thank OpenStreetMap contributors for the geographic data on which its road networks are based [Ope26]. 11 Experiments presented in this report were carried out using the Gridâ5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several universities as well as other organizations 12 . This work is funded by the French National Research Agency (ANR) as part of the MAMUT project, ANR-22-CE22-0016, âMachine learning et matheuristiques pour le transport urbainâ. AI-use disclosure. The author is solely responsible for this report, KAYROS and Poryos2026. Substantial portions of the solver and benchmark-generation tooling, experimentation and debugging, and a substantial part of the drafting of this report, were carried out by the AI agents (Fable 5, Sol 5.6) under the authorâs direction and review, as documented in Section 7. References [Ada+24]Tommaso Adamo, Michel Gendreau, Gianpaolo Ghiani, and Emanuela Guerriero. âA review of recent advances in time-dependent vehicle routingâ. In: European Journal of Operational Research 319.1 (2024), p. 1â15. doi:10.1016/j.ejor.2024.06.016. 10 https://github.com/Anzury; ORCID: 0009-0005-8630-3962. 11 Extended acknowledgements are given in the AUTHORS file of the source repository:https://github. com/0nyr/kayros/blob/e30fa492466b67809cdfd1e4b945230ba0bdcb2e/AUTHORS.md 12 https://w.grid5000.fr 29 [Agu16]PĂŠnĂŠlope Aguiar-Melgarejo. âA Constraint Programming Approach for the Time Dependent Traveling Salesman Problemâ. PhD thesis. INSA Lyon, Dec. 16, 2016. url: https://hal.science/hal-01514369. [Ari+19]Anna Arigliano, Gianpaolo Ghiani, Antonio Grieco, Emanuela Guerriero, and Isaac Plana. âTime-Dependent Asymmetric Traveling Salesman Problem with Time Windows: Properties and an Exact Algorithmâ. In: Discrete Applied Mathematics 261 (2019), p. 28â39. doi: 10.1016/j.dam.2018.09.017. [Bla+24]Jannis Blauth, Stephan Held, Dirk MĂźller, Niklas Schlomberg, Vera Traub, et al. âVehicle routing with time-dependent travel times: Theory, practice, and bench- marksâ. In: Discrete Optimization 53 (Aug. 2024), p. 100848. issn: 15725286. doi: 10.1016/j.disopt.2024.100848. url:https://linkinghub.elsevier.com/ retrieve/pii/S1572528624000276 (visited on 03/10/2025). [B17] Edmund K. Burke and Yuri Bykov. âThe late acceptance hill-climbing heuristicâ. In: European Journal of Operational Research 258.1 (2017), p. 70â78. doi:10.1016/j. ejor.2016.07.012. [Dab+13]Said Dabia, Stefan Ropke, Tom Van Woensel, and Ton De Kok. âBranch and Price for the Time-Dependent Vehicle Routing Problem with Time Windowsâ. In: Transportation Science 47.3 (Aug. 2013), p. 380â396. issn: 0041-1655, 1526-5447. doi:10.1287/trsc.1120.0445. url:https://pubsonline.informs.org/doi/ 10.1287/trsc.1120.0445 (visited on 02/19/2024). [Fed22] Federal Highway Administration. Multiresolution Modeling for Traffic Analysis: Final Report. FHWA-HRT-22-055. U.S. Department of Transportation, Federal Highway Administration, May 2022. url:https://highways.dot.gov/sites/ fhwa.dot.gov/files/FHWA-HRT-22-055.pdf (visited on 07/22/2026). [Fon24]Romain Fontaine. âExact and anytime heuristic search for the Time-Dependent Traveling Salesman Problem with Time Windowsâ. PhD thesis. INSA Lyon, July 9, 2024. url: https://hal.science/tel-04697323. [FDS23]Romain Fontaine, Jilles Dibangoye, and Christine Solnon. âExact and anytime approach for solving the time dependent traveling salesman problem with time windowsâ. In: European Journal of Operational Research 311.3 (Dec. 2023), p. 833â 844. issn: 03772217. doi:10.1016/j.ejor.2023.06.001. url:https://linking hub.elsevier.com/retrieve/pii/S0377221723004289 (visited on 01/25/2024). [G15]Michel Gendreau, Gianpaolo Ghiani, and Emanuela Guerriero. âTime-dependent routing problems: A reviewâ. In: Computers & Operations Research 64 (Dec. 2015), p. 189â197. issn: 03050548. doi:10.1016/j.cor.2015.06.001. url:https: //linkinghub.elsevier.com/retrieve/pii/S030505481500146X (visited on 05/01/2024). [Goo26]Google. OR-Tools. Routing library, version 9.15, Apache-2.0 license. 2026. url: https://github.com/google/or-tools (visited on 07/19/2026). 30 [Gra26]GraphHopper GmbH. jsprit: a toolkit for rich vehicle routing problems. Apache- 2.0 license. 2026. url:https://github.com/graphhopper/jsprit(visited on 07/19/2026). [He+22]Edward Yuhang He, Natashia Boland, George Nemhauser, and Martin Savelsbergh. âDynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problemsâ. In: INFORMS Journal on Computing 34.2 (Mar. 2022), p. 1086â1114. issn: 1091-9856, 1526-5528. doi:10.1287/ijoc.2021.1084. url:https://pubso nline.informs.org/doi/10.1287/ijoc.2021.1084 (visited on 03/10/2025). [Hex26] Hexaly. Time-Dependent Capacitated Vehicle Routing Problem with Time Windows (TDCVRPTW) model template. Hexaly Optimizer 14.5, proprietary with academic licensing. 2026. url:https://w.hexaly.com/templates/time-dependent- routing-problem-with-time-windows-tdcvrptw (visited on 07/19/2026). [HG99] JĂśrg Homberger and Hermann Gehring. âTwo evolutionary metaheuristics for the vehicle routing problem with time windowsâ. In: INFOR: Information Systems and Operational Research 37.3 (1999), p. 297â318. doi:10.1080/03155986.1999. 11732386. [IGP03]Soumia Ichoua, Michel Gendreau, and Jean-Yves Potvin. âVehicle dispatching with time-dependent travel timesâ. In: European Journal of Operational Research 144.2 (Jan. 2003), p. 379â396. issn: 03772217. doi:10.1016/S0377-2217(02)00147-9. url:https://linkinghub.elsevier.com/retrieve/pii/S0377221702001479 (visited on 11/18/2024). [LMS20]Gonzalo Lera-Romero, Juan J. Miranda Bront, and Francisco J. Soulignac. âLinear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windowsâ. In: Networks 76.1 (July 2020), p. 24â53. issn: 0028- 3045, 1097-0037. doi:10.1002/net.21937. url:https://onlinelibrary.wiley. com/doi/10.1002/net.21937 (visited on 03/01/2025). [MD92]Chryssi Malandraki and Mark S. Daskin. âTime Dependent Vehicle Routing Prob- lems: Formulations, Properties and Heuristic Algorithmsâ. In: Transportation Science 26.3 (Aug. 1992), p. 185â200. issn: 0041-1655, 1526-5447. doi:10.1287/trsc.26. 3.185. url:https://pubsonline.informs.org/doi/10.1287/trsc.26.3.185 (visited on 05/30/2024). [Ope26] OpenStreetMap contributors. OpenStreetMap. Map data licensed under the Open Database License 1.0. 2026. url:https://w.openstreetmap.org/copyright (visited on 07/22/2026). [Ras26a]Florian Rascoussier. KAYROS. Version 1.1.3. July 20, 2026. url:https://archive. softwareheritage.org/swh:1:dir:ba5d8e22795d91155334793acfe25b1590dbc f71. [Ras26b] Florian Rascoussier. Poryos2026: An OpenStreetMap-Based Benchmark Family for Static and Time-Dependent Vehicle Routing. Benchmark data released under the Open Database License 1.0. July 22, 2026. url:https://github.com/ANR-MAMUT/ MAMUT-routing/tree/main/benchmarks/Poryos2026 (visited on 07/22/2026). 31 [Ras+26]Florian Rascoussier, Romain Billot, Lina Fahed, and Christine Solnon. âImpact of Scaling and Rounding on Metaheuristic Performance for the Vehicle Routing Problem with Time Windowsâ. In: 16th Metaheuristics International Conference. Ischia, Italy: Springer, 2026. url: https://hal.science/hal-05646952. [RP26]Florian Rascoussier and Adrien Pichon. MAMUT-routing. Version 0.1.0. HAL: hal- 05629810. May 21, 2026. url:https://archive.softwareheritage.org/swh:1: dir:ecf205f4e673542cafd8ae7a73756f1a3a1edaf7. [RCS20]Omar Rifki, Nicolas Chiabaut, and Christine Solnon. âOn the impact of spatio- temporal granularity of traffic conditions on the quality of pickup and delivery optimal toursâ. In: (2020). doi:10.1016/j.tre.2020.102085. url:https: //w-sciencedirect-com.docelec.insa-lyon.fr/science/article/pii/ S136655452030733X?via%3Dihub. [Sol87] Marius M. Solomon. âAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraintsâ. In: Operations Research 35.2 (Apr. 1987), p. 254â 265. issn: 0030-364X, 1526-5463. doi:10.1287/opre.35.2.254. url:https:// pubsonline.informs.org/doi/10.1287/opre.35.2.254 (visited on 02/27/2024). [Tim26]Timefold BV. Timefold Solver. Open-source planning solver, Apache-2.0 license, continuation of OptaPlanner. 2026. url:https://github.com/TimefoldAI/ timefold-solver (visited on 07/19/2026). [Vid+21]Thibaut Vidal, Rafael Martinelli, Tuan Anh Pham, and Minh HoĂ ng HĂ . âArc Routing with Time-Dependent Travel Times and Pathsâ. In: Transportation Science 55.3 (2021), p. 706â724. doi: 10.1287/trsc.2020.1035. [VS20] Thomas R. Visser and Remy Spliet. âEfficient Move Evaluations for Time-Dependent Vehicle Routing Problemsâ. In: Transportation Science 54.4 (July 2020), p. 1091â 1112. issn: 0041-1655, 1526-5447. doi:10.1287/trsc.2019.0938. url:https://p ubsonline.informs.org/doi/10.1287/trsc.2019.0938 (visited on 05/29/2025). [Vu+20]Duc Minh Vu, Mike Hewitt, Natashia Boland, and Martin Savelsbergh. âDynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Prob- lem with Time Windowsâ. In: Transportation Science 54.3 (2020), p. 703â720. doi: 10.1287/trsc.2019.0911. 32