Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

Imagine a fleet of vehicles racing against the clock to visit a scattered collection of locations, each offering a different reward. The goal is simple: collect as much value as possible before time runs out. But the world is not a spreadsheet. The time it takes to complete a task at any given spot is uncertain; a sudden gust of wind might delay a drone, or rough seas might slow a boat. Furthermore, each location is only available for a specific window of time. If a vehicle arrives too early, it must wait; if it arrives too late, the opportunity vanishes forever. This is the essence of a complex logistical challenge known as the team orienteering problem with time windows. In the real world, this scenario plays out when firefighters try to contain a wildfire, oil spill crews race to contain a slick before it hits the shore, or medical teams must visit patients within critical timeframes. The difficulty lies in making the next move instantly, without knowing exactly how long the current task will take, and without the luxury of a supercomputer to re-calculate the entire plan every second.

For years, researchers have tried to solve this by teaching computers to evolve simple decision rules. These rules act like a traffic controller, looking at the current situation and immediately deciding which customer to visit next. The most successful method so far, known as NS-GP, relies on a fixed set of eleven basic features—such as how far away a customer is or how much time is left—to make these choices. While effective, this approach has a ceiling. It uses a limited vocabulary to describe the world, much like trying to write a novel using only a hundred words. The researchers behind this new study, led by Augusto Mendonça and his team at universities in Brazil, asked a bold question: what if the computer could learn a richer vocabulary by watching how an expert planner solves the problem offline? They wanted to see if they could extract the hidden logic of high-quality solutions and turn those insights into simple, readable rules that work in real-time.

The team developed a new method called SI-GP, which stands for Solver-Informed Genetic Programming. The process begins not with the computer guessing, but with the computer watching. First, the researchers used powerful, high-speed solvers to find the best possible routes for a set of forty different test problems, assuming everything would go perfectly. They then took these perfect routes and replayed them in a simulated world where delays happened randomly, just as they do in reality. By comparing the perfect plans against what actually happened, the team identified specific operations that the perfect plans performed but the standard rules missed. For instance, they noticed that the best plans often looked several steps ahead to see what rewards would remain reachable, or they calculated the risk of losing a future opportunity if they committed to a current one.

From these observations, the researchers built a new library of eighteen decision features. Sixteen of these were based on established concepts in scheduling, while two were entirely new combinations designed to weigh the cost of a decision against the potential gain. This new vocabulary gave the computer a much more nuanced way to understand the problem. However, having more options does not automatically mean better results; sometimes, too many choices confuse the system. To solve this, the team used a second layer of intelligence to select the best subset of these features for each specific problem. They treated the selection process like a tournament, evolving different combinations of features and testing them rigorously. This was made possible by a custom-built engine that runs on graphics cards, allowing them to test thousands of combinations in the time it used to take to test just one.

The results were striking. On the forty benchmark problems, the new method never performed worse than the old standard. In thirty-eight of the cases, the system evolved a new rule that outperformed the previous best. On average, the new rules improved the total collected reward by 1.0 percent across all tests, and by 1.3 percent on the problems where there was still room for improvement. In ten specific cases, the improvement was statistically significant and large enough to be considered a major breakthrough for that specific scenario. Perhaps most importantly, the new rules remained simple and readable. They were not black-box algorithms that no one could understand; they were compact mathematical expressions that a human could read and verify. In many cases, the new rules were also more stable, producing consistent results even when the random delays varied, whereas the old rules sometimes swung wildly between good and bad outcomes.

The study also revealed why the improvements happened. The new rules were particularly effective in situations where the baseline system struggled to visit every possible customer. In these "unsaturated" scenarios, the new vocabulary allowed the system to navigate complex trade-offs, such as visiting a distant, high-value customer even if it meant skipping a nearby, low-value one. The researchers found that the new features helped the system regularize its search, meaning it was less likely to get stuck in a local trap and more likely to find a robust path forward. The method worked by learning from the structure of high-quality solutions without simply copying them. It did not try to mimic the exact route of the expert planner; instead, it learned the principles that made those routes successful and applied them to a new, uncertain environment.

This work demonstrates that it is possible to bridge the gap between complex, offline optimization and fast, online decision-making. By using the insights from high-quality solvers to build a better vocabulary, and then carefully selecting the right tools for each specific job, the researchers created a system that is both powerful and transparent. The final product is a set of decision rules that can be embedded directly into vehicles or drones, allowing them to make intelligent choices in microseconds without needing to connect to a central computer or run complex simulations. The approach suggests a new path for artificial intelligence in logistics: one that values interpretability and adaptability, ensuring that the machines making critical decisions can be understood by the humans who rely on them. The researchers have made their code, data, and the specific rules they discovered available to the public, inviting others to build upon this foundation for future challenges in uncertain environments.