Vehicle routing
hgs_advance finds shorter delivery routes, faster than VROOM, PyVRP and NVIDIA cuOpt
Thibaut Vidal submitted hgs_advance to TIG. He developed Hybrid Genetic Search, the method that PyVRP and the winner of the 2021 DIMACS routing challenge are built on. TIG Foundation tested the new algorithm independently against three other routing engines.
- Speed
- ~90×
- faster than VROOM's fastest setting, with shorter routes
- 0.4 s against 37.5 s on 1,000-stop problems
- Route length against other engines
- 4–6%
- shorter routes than the next-best engine
- Same time limit for every engine, from 10 s to 2 min, on 1,000-stop problems
- Route length against TIG's earlier algorithm
- ~5%
- shorter routes than TIG's earlier algorithm
- Shorter in 40 of 40 public benchmark problems
Why route planning is hard
A delivery company sends out a fleet of vans from one depot. Each van can carry only so much, and each customer expects delivery within a time window. With hundreds or thousands of stops there are far too many possible plans to check one by one, so routing software searches for a good plan within a time limit.
Shorter routes mean less fuel and fewer hours on the road. For a fleet that drives 10 million km a year, routes 5% shorter would save 500,000 km.
Head-to-head
Against VROOM, PyVRP and NVIDIA cuOpt
TIG Foundation ran hgs_advance and three other routing engines on the same delivery problems: the open-source VROOM and PyVRP, and NVIDIA's GPU-based cuOpt. There were three problems each at 600, 1,000 and 2,000 stops.
Time needed to match each engine's routes
How long hgs_advance took to find routes at least as short as each engine's result.
~90×faster
than VROOM (fastest setting)
0.4 s against 37.5 s
42×faster
than VROOM (most thorough, 8 threads)
5.2 s against 3.6 min
25×faster
than PyVRP (best result)
12.0 s against 5.0 min
116×faster
than NVIDIA cuOpt (best GPU result)
5.2 s against 10 min
Every tested setting
Each point is one engine setting on TIG's generated problems, and lines join settings of the same engine. Lower and further left is better: shorter routes, found sooner. Each point averages three problems unless its tooltip says otherwise.
hgs_advanceVROOMPyVRPNVIDIA cuOpt
Distance above the best plan found (%) · Lower is better
Runtime · log scale
Route length with the same time limit
Pick a time limit. Each bar shows how much longer an engine's routes were than the best routes found in these tests, so shorter bars are better.
hgs_advance finds routes 4.2% shorter than the next-best engine, PyVRP.hgs_advance
30.6 s
VROOM
37.5 s
PyVRP
60.9 s
NVIDIA cuOpt
4.5 s
Progress inside TIG
Better than TIG's earlier routing algorithm
hgs_v1 is an earlier routing algorithm from TIG. Both algorithms had 30 seconds for each of 40 public benchmark problems with 600 to 1,000 stops. hgs_advance found shorter routes in every one and used fewer vehicles in 36.
Both algorithms ran the same problems with the same time limit. Shorter bars are better.
1,000 stops · tight windows R1
- hgs_v1 (earlier)
- hgs_advance
1,000 stops · random locations R2
- hgs_v1 (earlier)
- hgs_advance
1,000 stops · mixed locations RC2
- hgs_v1 (earlier)
- hgs_advance
600 stops · mixed locations RC2
- hgs_v1 (earlier)
- hgs_advance
Distance in benchmark units · 10 problems per group · Same scale for all bars
How it works
Vidal introduced Hybrid Genetic Search in 2012. hgs_advance keeps that method and adds three shortcuts that let it handle large problems quickly.
- 01
Merge stops that good plans agree on
When many good plans put the same stops next to each other, the search treats them as one stop and works on a smaller problem.
Consensus compression
- 02
Work on one area at a time
The best plan is split into groups of nearby routes. Each group is improved on its own, then the groups are joined back together.
Reverse-mode decomposition
- 03
Skip bad changes early
A quick estimate rules out most poor changes before the slower full check of every time window.
Bound-based local search