Network wireLoading updates…

Advances

New algorithms submitted to TIG, and how they compare with existing algorithms.

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.

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.

Number of 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.

Extra distance against runtime for every tested setting
  • hgs_advance
  • VROOM
  • PyVRP
  • NVIDIA 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.

With a 1 min limit, 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

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.

Average distance per problem

Both algorithms ran the same problems with the same time limit. Shorter bars are better.

  1. 1,000 stops · tight windows R1

    hgs_v1 (earlier)
    hgs_advance
  2. 1,000 stops · random locations R2

    hgs_v1 (earlier)
    hgs_advance
  3. 1,000 stops · mixed locations RC2

    hgs_v1 (earlier)
    hgs_advance
  4. 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.

  1. 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

  2. 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

  3. 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

Built by Thibaut Vidal

Thibaut Vidal (Polytechnique Montréal) designed and built hgs_advance and submitted it to TIG. TIG Foundation tested it independently on the published code and handles commercial licensing.

Full results and method

Research benchmarks, comparison with published records, test setup and current limits.

Published research benchmarks

On these long-studied public sets, Vidal reports smaller gaps to the best-known solutions than the methods it was compared with, in less time. On the 1,000-customer Gehring–Homberger instances the gap fell from 0.35% for HGS-DIMACS, the 2021 DIMACS winner, to 0.14%, a 59% reduction, in 16 minutes instead of 40.

Reported gaps and runtimes on public routing research benchmarks.
BenchmarkPrevious methodIts gap / timehgs_advance gap / time
Gehring–Homberger · 1,000 customersCapacity and time windowsHGS-DIMACS2021 challenge winner0.35%40 min0.14%16 min
Gehring–Homberger · all sizesCapacity and time windowsHGS-DIMACS0.15%24 min0.09%8 min
Uchoa XCapacity only · no time windowsAILS-II0.08%21 min0.07%9 min

These figures come from Vidal's submission and are means over 10 runs per instance. They were not re-run for TIGStats. The 59% reduction is Vidal's figure; the table rounds gaps and times, so recomputing from the table gives a slightly different number.

hgs_v1 and hgs_advance against published best-known solutions

Each of the 40 problems in the hgs_v1 comparison has a published best-known solution (BKS). Those records minimise the number of vehicles first and distance second. TIG minimises distance under a fleet cap, so compare vehicle counts as well as distance.

Distance gap to the BKS by group
hgs_v1hgs_advance
  1. 1,000 stops · R1+6.3% to +1.1%
  2. 1,000 stops · R2+5.6% to -0.4%
  3. 1,000 stops · RC2+5.7% to -0.6%
  4. 600 stops · RC2-1.4% to -5.0%
← Shorter distanceLonger distance →

0% is the published best-known distance. Each dot is the mean gap over 10 problems. A negative gap is not a new record (see the note below).

Average vehicles per problem

Average vehicle counts in each benchmark group
GroupBKShgs_v1hgs_advance
1,000 · R191.994.492.4
1,000 · R219.027.924.6
1,000 · RC218.225.723.0
600 · RC211.417.815.9

Both TIG algorithms use more vehicles than the published records on average. The counts are closest in the R1 group, which has tight time windows.

Why some gaps are negative

The published records minimise the number of vehicles first and distance second, so a solution that uses more vehicles can be shorter than the record. 16 of the 17 negative hgs_advance gaps here use more vehicles than their record.

The other, r1_10_1, uses fewer vehicles and depends on rounding. TIG stores travel distances and times as whole numbers rounded from the exact Euclidean values, so a route that is on time in whole numbers can arrive slightly late when re-timed with exact distances. 30/40 hgs_advance solutions here have at least one such arrival, by at most 1.954 benchmark time units. This comes from the distance convention, not from the solver.

In a separate re-run with distances and times multiplied by 1,000 and rounded up before solving, 0 of 39 valid hgs_advance solutions arrived late, all 13 negative gaps came with more vehicles than the record, and the mean gap changed by −0.04 percentage points. Against records that minimise distance only, none of those 39 gaps are negative.

Test setup

Head-to-head with VROOM, PyVRP and NVIDIA cuOpt

Problems and scoring
Three TIG-generated problems each at 600, 1,000 and 2,000 stops. Every scored plan passed the same feasibility checks. The gap is measured against the best plan any tested engine found for each problem.
Hardware
Every engine ran on one CPU thread, except NVIDIA cuOpt, which ran on an RTX 3060 GPU, and VROOM's most thorough setting, which used 8 threads.
Time limits
A time limit counts any run that finished within 25% over it, for every engine. The 4–6% figure covers 1,000-stop problems at limits from 10 s to 2 min; at 5 min PyVRP comes within 0.6%.
Rounding and partial results
Route savings are computed from mean gaps. Speed ratios based on sub-second timings are rounded. A few cuOpt and PyVRP settings have results for only one or two of the three problems, because the run was skipped or the plan was invalid; their tooltips say which.

Comparison with hgs_v1

Algorithms and time limit
hgs_v1 (c002_a089) ran at exploration level 5, labelled hgs_explore5 in the evaluation files. hgs_advance (c002_a110) used its shipped level-4 preset. Each run had one worker and a 30-second wall-clock limit, and a run that hit the limit kept its last saved solution. One seed and one run per algorithm per problem.
Distance and gap
Distances are recomputed from the coordinates as real-valued Euclidean distances. The ~5% figure is the mean, across problems, of the percentage distance saved relative to hgs_v1. The BKS gap is (TIG distance − BKS distance) ÷ BKS distance × 100. Timing checks include the return to the depot.
Problem selection
The 40 problems are a subset of the Gehring–Homberger sets. They include wide-window groups that the experiment identifies as hard for these algorithms. All runs used seed default_seed. The result files do not record the hardware or comparable BKS runtimes.
BKS source
BKS values come from SINTEF's 1,000-customer and 600-customer tables. SINTEF verifies the published solutions. The timing checks on the TIG solutions are this evaluation's own.

Runtime and current limits

At its default search depth, hgs_advance averaged 22.1 s on 600 stops, 30.6 s on 1,000 and 60.4 s on 2,000, so in this sample runtime grew roughly in line with problem size. The code is single-threaded Rust with a C interface and no external dependencies. Route decomposition could spread the work across several cores, but every reported run used one.

It handles one depot, identical vehicles, one time window per stop, and travel distances that are the same in both directions. It does not model multiple depots, mixed fleets, pickup and delivery, driver skills, breaks or soft lateness. The research describes an extension for asymmetric travel, which this code does not include.

    Advances | tigstats