Advance Submission: Vehicle Routing

[Aoibheann]

Advance Rewards Submission

We are thrilled to announce that our second Advance submission for the Vehicle Routing Challenge has been made public today (round 121)!

The algorithm, HGS_advance, is now open for the community to review.

Please see here: Advance Evidence Form. The code submission that embodies the method described above: Code Submission.

You are invited to explore the evidence and code and prepare to cast your vote in the token-weighted vote on the submission’s eligibility for Advance rewards. Voting will open at the beginning of the next round (round 122) and remain open until the end of that round.

Vehicle Routing

The Vehicle Routing Problem (VRP) is one of the most studied problems in combinatorial optimization. Given a fleet of vehicles and a set of customers, each with demands, and delivery time windows, the goal is to find the set of routes that serves every customer at minimum total cost while respecting vehicle capacities and timing constraints.

The challenge is that the number of possible route combinations explodes as instances grow, making exact methods impractical at real-world scale. Modern solvers rely on powerful metaheuristics such as Hybrid Genetic Search (HGS), which combine population-based exploration with aggressive local search to navigate this enormous solution space.

HGS_advance extends the current state-of-the-art with three coordinated mechanisms: evolutionary consensus compression, a “reverse mode” decomposition strategy, and a high-performance local-search engine, that together make HGS dramatically more scalable.

The results speak for themselves. Across the full Homberger-Gehring benchmark, the average gap to the best known solutions (BKS) from the literature drops from 0.151% for the DIMACS-challenge-winning HGS to 0.086% for HGS_advance, while average runtime falls from 24.0 to 8.3 minutes. The gains are most pronounced on the hardest 1000-customer instances, where the average gap shrinks from 0.349% to 0.142% and runtime from 40.0 to 16.1 minutes, an error-gap reduction of roughly 59% alongside a runtime reduction of roughly 60%.

While benchmark gains don’t convert directly into dollar savings, the scale is striking: even a 0.1% routing-driven efficiency improvement would be worth roughly $95.8 million per year for a company like Amazon.

Why It Matters

Vehicle routing sits at the heart of global logistics. Better routing algorithms are crucial for:

• Last-Mile Delivery and Supply Chains: Parcel carriers, e-commerce fleets, and distributors solve VRPs with thousands of stops every day. Routing quality directly determines cost, fuel consumption, emissions, and on-time service across global logistics networks.
• Field Services and Municipal Operations: Technician dispatch, home healthcare visits, waste collection, and school bus planning are all vehicle routing problems with capacities and time windows.
• Cleaning Up Space: Routing algorithms now extend beyond Earth. Planning active debris removal missions: sequencing a servicer spacecraft’s rendezvous with multiple debris objects to minimize fuel and mission time, is a vehicle routing problem in orbit. Routing-based methods are being applied to help keep low Earth orbit safe and usable.

Transportation operates at enormous cost levels. Even marginal improvements in routing efficiency compound into massive savings in cost, fuel, and emissions across the industry.

This submission represents a potential significant step forward in one of the most fundamental problems in operations research. Your participation in reviewing, discussing, and voting will help determine whether it qualifies for Advance Rewards. For more information on the Challenge, check out our technical paper.

[vidalt]

Hello everyone, and thank you for the great introduction to this advance submission.

I’m very glad to see it submitted and now under consideration. Before entering the TIG ecosystem, I did not expect to dive back so deeply into vehicle routing research (which has been my main area for over 15 years). I also certainly did not expect that improvements of this scale on top of my HGS framework would still be within reach. I will be actively following the forum discussions as a contributor, so please feel free to share comments, questions, or criticism. I’ll be happy to discuss the method, the ideas behind it, and the evidence.

Thanks again!
–Thibaut

[AxelParmentier]

Hello everyone.

Please find below a report on the novelty and significance of the HGS_advance contribution.

All the best,

Axel Parmentier

---

Vehicle routing is a major research field, which has successively served as a testbed for classical heuristics, metaheuristics, machine learning methods, and, more recently, LLM-designed algorithms. Although substantial progress has been achieved, major commercial solvers still struggle to produce high-quality solutions on instances with around 1,000 customers. For example, recent benchmarks report error gaps of around 4.5% to 14.4% in distance for mainstream general-purpose combinatorial optimization solvers such as Hexaly and OR-Tools on large CVRPTW instances (Hexaly, Gurobi, OR-Tools on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)), while specialized routing solvers such as PyVRP reach gaps around 0.45%. In this context, a contribution capable of reaching solution quality close to 0.14% on such instances within a few minutes is of clear practical and commercial significance, especially given the scale and cost of real-world delivery operations.

The contribution builds upon the Hybrid Genetic Search algorithm introduced 12 years ago by the author “Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.”, and its more recent update “Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643.”. However, while these algorithms have been for a long time state-of-the art for instances with up to 500 customers, they were not suited for very large instances with 1000+ customers. This new algorithm introduces both many simple improvements that make the algorithms, as well as several major new ideas to make the algorithm state-of-the-art beating on XL instances.

From a methodological perspective, the innovation appears to rely on the combination of three main elements: an evolutionary consensus mechanism exploiting population information to infer stable edges; a simple but effective decomposition strategy; and high-performance local search acceleration techniques. While each of these components can be related, individually, to known ideas in the combinatorial optimization literature, their combination in the present innovation statement is clever and, to my knowledge, has not been previously seen in this form.

Notably, consensus strategies are reminiscent of the “backbone method” coined in the paper of “Jäger, G., Dong, C., Goldengorin, B., Molitor, P., & Richter, D. (2014). A backbone based TSP heuristic for large instances. Journal of Heuristics, 20(1), 107–124. A backbone based TSP heuristic for large instances | Journal of Heuristics | Springer Nature Link” for the traveling salesperson problem (TSP), in which the edges realizing the consensus of several starts of a construction method were fixed to then focus the search on non-consensual edges. However, the innovation also differs significantly in the way the consensus is built (extracted from evolution dynamics of a solution population in a genetic algorithm).

The second contribution concerns the decomposition mechanism, referred to as “reverse mode.” It relates to known decomposition strategies for vehicle routing, especially route-based decompositions using spatial or barycenter clustering. The method maintains a single master solution, decomposes it into route-cluster subproblems, solves these subproblems with HGS, and merges the improvements back into the master solution. This approach is conceptually very simple, yet surprisingly effective. Another aspect that I find interesting is the delayed insertion of the master-derived solution into the subproblem population. Inserting this seed too early would overly bias the search toward known solutions, while inserting it too late would waste effort rediscovering structures already known. The proposed compromise, where the seed is introduced around the middle of the iteration budget, appears to provide a simple but effective balance between exploration and exploitation. Moreover, the master solution participates in the analysis of consensus edges even before its insertion into the population, which creates an original interaction between decomposition, population search, and consensus-based compression.

In the high-performance local search component, the deterioration-budget mechanism appears to be an original contribution. To my knowledge, this precise form of controlled deterioration has not been commonly used previously. The closest conceptual relatives are “deterministic annealing” methods, especially threshold acceptingby Dueck and Scheuer. However, threshold accepting was proposed as a general-purpose metaheuristic, where a global threshold guides the full search trajectory. Here, the mechanism is more localized. It introduces a small budget during the first pass of local search: improvements generate limited credit, and worsening moves may be accepted only within this accumulated budget. This allows the search to cross small local barriers while remaining close to the improving trajectory. Thus, the method is not simply an application of threshold accepting to vehicle routing, but a focused adaptation of bounded deterioration as an exploration mechanism inside a high-performance VRP local search.

Overall, even though each of the main contributions, separately, can be tied to some form of related research; these advances introduce genuine innovations and collectively interact unexpectedly well. The results of the VRPTW benchmark instances are also striking and significantly superior to the current state-of-the-art, marking an important milestone in the progress of this research area. Finally, the three main contributions are quite generic in their nature, and may have impact on many important combinatorial optimization problems encountered in Operations Research beyond the CVRP.

[Aoibheann]

Advance Rewards Vote Result

The vote is in, and the result could not be clearer. The token-weighted vote on HGS_advance has now closed at the end of round 122, and the community has approved the submission for Advance Rewards in a landslide, with 1,121,451 tokens voting in favour of passing.

Thank you to everyone who took the time to read the evidence, study the code, and weigh in. A particular thank you to Axel Parmentier (@AxelParmentier), for his detailed report on the novelty and significance of the three core mechanisms, which gave the community a clear and authoritative basis on which to evaluate the work.

With this vote, HGS_advance is confirmed as eligible for Advance Rewards. It marks a meaningful step forward on one of the most fundamental and economically significant problems in operations research.

As confirmed by the token-holder vote, this is a significant advance in the field of vehicle routing, in particular, the VRPTW instances that TIG features. For context, as we approach the optimal solution, reducing the error gap becomes exponentially more difficult. This logarithmic plot demonstrates the scale of the improvement found on the hardest VRPTW instances, with that difficulty taken into account.

This new state-of-the-art algorithm would not exist without the incentives provided by the innovation game and offers a glimpse into the scale of innovation and impact TIG can drive in the future.