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.