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

Imagine you are the dispatcher for a fleet of delivery trucks in a bustling city. Your goal is simple: get packages to customers and get the drivers home as quickly as possible to save money on wages. But there's a catch: the city is alive. A road that takes ten minutes at 8:00 AM might take forty minutes at 9:00 AM because of rush hour traffic. This is the world of Time-Dependent Vehicle Routing. It's a classic puzzle in the field of Operations Research, which is basically the science of making the best possible decisions when you have limited resources and complex rules.

For decades, computers have been great at solving these puzzles, but usually with a big simplification: they pretend traffic is static, like a map where roads never change. Real life, however, is a flowing river, not a still pond. To solve the puzzle perfectly, you need to know exactly when a truck leaves the depot, because leaving five minutes later might mean hitting a traffic jam that adds an hour to the trip, or it might mean avoiding a red light that saves ten minutes. The challenge is that the math to figure out the "perfect" departure time for every single truck, while respecting customer time windows and traffic patterns, is incredibly difficult. It's like trying to solve a Rubik's Cube where the colors keep shifting as you twist the sides.

This is where a new tool called KAYROS comes in. Think of KAYROS as a super-smart, tireless traffic wizard that doesn't just guess; it calculates the absolute best possible schedule. But here's the magic trick: it doesn't just give you a "good enough" answer after waiting an hour. It starts giving you better and better answers the very first second it starts thinking, and if you stop it, it tells you the best solution it found so far. Even cooler, it can prove that a solution is mathematically perfect, not just a lucky guess. The paper also introduces a massive new set of practice puzzles called Poryos2026, built from real city maps, to test if these wizards are actually good at their jobs.

The Magic of KAYROS: A Solver That Never Sleeps

The paper introduces KAYROS, an open-source software tool designed to solve the "Time-Dependent Vehicle Routing Problem." Imagine you are trying to plan a road trip for a fleet of delivery drivers. You have a list of stops, and each stop has a specific time window when the customer is home (e.g., "You can only drop off the package between 2:00 PM and 4:00 PM"). The tricky part is that the time it takes to drive between stops changes depending on what time of day you leave.

KAYROS is special because it does two things at once, which is a rare combination in the world of computer solvers:

1. It's "Anytime": When you run KAYROS, it doesn't sit silent for hours. It immediately starts spitting out solutions. The first one might be okay, but the next one is better, and the next one is even better. It's like a chef tasting a soup and adding spices continuously; you can stop the cooking at any moment, and you'll have the best soup possible for that amount of time.
2. It's "Exact": If you let it run long enough, it doesn't just guess the best answer; it proves it is the best possible answer. It generates a "certificate," which is like a mathematical receipt that anyone can check to verify that no other route could possibly be faster.

The authors built this tool to be completely free and open. You can install it with a single command on your computer, and it doesn't require any expensive, secret software from big companies. It uses a clever engine that treats travel time not as a single number, but as a flowing function—a line that goes up and down depending on the time of day. This allows it to handle complex, real-world traffic patterns where a road might suddenly get clogged at a specific minute.

The "Self-Refutation" Story: How They Caught Their Own Mistake

One of the most fascinating parts of the paper is a story about honesty. The authors wanted to make sure their "perfect" certificates were actually perfect. They set up a strict rule: to claim a solution is the best, four different computer runs must all agree on the exact same answer.

During a test, they found a problem. KAYROS had issued 160 "certificates" claiming certain routes were the best possible. But then, their own "anytime" solver (the one that keeps improving) found routes that were actually faster than those "perfect" certificates! This was a shock. It turned out that KAYROS had been using a "smoothing" trick to handle sudden jumps in traffic data (like a road that instantly becomes a parking lot). This trick was slightly wrong, causing the computer to miscalculate the time.

The authors didn't hide this. They publicly retracted all 160 certificates, fixed the code to handle these "jumps" exactly, and ran the tests again. This story is included to show that their system is robust: even when the AI makes a mistake, the verification rules catch it, and the truth wins.

The New Playground: Poryos2026

To test if KAYROS really works, the authors needed a playground that looked like the real world. They created Poryos2026, a family of 1,080 new test puzzles. Instead of using fake, made-up maps, they pulled real road networks from five major cities: Lyon, Paris, San Francisco, Hong Kong, and Tokyo, using data from OpenStreetMap (a free, community-built map).

They then added synthetic (fake but realistic) traffic, customer demands, and time windows to these real maps. This created a massive set of challenges that mix real geography with controlled traffic scenarios. For every single one of these 1,080 puzzles, they generated a "best-known solution" using their own solver. This gives other researchers a fair and realistic way to test their own tools against a standard that reflects actual city driving, not just abstract math problems.

The Human and the AI Team-Up

Perhaps the most unique part of this paper is how it was written. The author, a PhD student, worked in an intense collaboration with an AI agent (a large language model) for about two weeks. The human set the goals, made the big decisions, and checked the work, while the AI did the heavy lifting: writing code, running thousands of computer experiments, and debugging errors.

The author estimates that this two-week collaboration did the work that would have taken them two or more years to do alone. However, the paper is very careful to note that this wasn't just "typing faster." The human had to spend a lot of time preparing the AI with the right context, checking its work, and ensuring that the results were scientifically sound. The paper argues that this kind of partnership is the future of research, but only if there are strict rules (like the "certificate" system) to verify that the AI didn't make up facts or hallucinate results.

What This Means for the Future

The paper doesn't claim that KAYROS is the fastest solver in the world (they haven't compared it head-to-head with every other tool yet), nor does it claim to have solved every possible routing problem. Instead, it offers a solid, verified, and free tool that finally brings "exact" and "anytime" solving to complex, time-dependent traffic problems.

By combining a powerful new solver, a massive new set of real-world test cases, and a transparent story about how humans and AI can work together responsibly, the authors have provided a new foundation for logistics. Whether it's delivering pizza, managing garbage trucks, or planning emergency response routes, the ability to calculate the perfect time to leave, while knowing you can stop and get a good answer at any moment, is a significant step forward for the science of moving things around our busy world.