Vehicle Routing, the way the state of the art does it
A capacitated vehicle routing problem, solved live in your browser with a compact Hybrid Genetic Search: one giant tour, decoded into routes by Split, educated by SWAP* local search, then improved by a population that keeps its diversity on purpose — the ideas Thibaut Vidal's research made standard.
Understand exactly what you're looking at
The theory, how the data is acquired and cleaned, how to read the result — and what BIS would do for you next.
Give one truck every stop and it is a travelling-salesman tour; give a fleet a shared depot and a capacity limit and it becomes the capacitated vehicle routing problem — decide which stops each vehicle serves and in what order, minimising total distance. It is NP-hard, so at real scale you do not prove the optimum; you get very close, fast. The method that has defined “very close, fast” for over a decade is Hybrid Genetic Search (HGS), and this demo is a compact, honest reimplementation of it from the papers of Thibaut Vidal (CIRRELT / Polytechnique Montréal). Four ideas do the work:
- Giant tour + Split. A solution is stored as one depot-less permutation of every stop. Split decodes it into the optimal set of capacity-feasible routes as a shortest path on a graph — in linear time (Vidal, C&OR 2016, doi:10.1016/j.cor.2015.11.012). We reimplement it from the paper; Vidal’s own Split-Library is GPL-licensed, so none of that code is copied here.
- SWAP* and friends. Local search “educates” a solution with relocate, swap, 2-opt, 2-opt*, Or-opt and the distinctive SWAP* — which trades two customers between routes but reinserts each at its own best position, not in the other’s vacated slot (Vidal, C&OR 2022, doi:10.1016/j.cor.2021.105643).
- Biased-fitness diversity. The genetic loop ranks survivors by cost and by how different they are from the rest of the population, so diversity is an explicit objective and the search does not collapse onto one idea (Vidal, Crainic, Gendreau, Lahrichi, Rei, Operations Research 2012, doi:10.1287/opre.1120.1048).
- Constant-time moves. Storing preprocessed data per route segment lets each move’s cost be a constant-time concatenation — the trick that makes enormous neighbourhoods affordable (Vidal, Crainic, Gendreau, Prins, C&OR 2013, doi:10.1016/j.cor.2012.07.018).
Full citations, DOIs, and the licences of the reference implementations are listed under the demo.
The instance is a seeded synthetic delivery set across metro Atlanta: a depot in West Midtown and several dozen stops with real latitude/longitude and a demand each, scattered over neighbourhood clusters and the wider metro so a greedy first pass leaves real distance on the table. The coordinates are genuine points in Atlanta; the delivery locations themselves are made up — nothing here is a real customer.
It ships as static JSON the page fetches — the instance, a real OSRM driving-distance matrix, and the road geometry — all precomputed once offline, so the solver optimises on real road distances and the map draws real streets with no routing-API call at runtime. Change the vehicle capacity or try a new random start and a fresh solve runs on the spot.
What you are watching is HGS-lite, and it is worth being exact about what that means:
- Capacity only, no time windows. Real deliveries have opening hours and service times; this models load and distance alone.
- Real distances, precomputed. Legs use OpenStreetMap road distances and geometry (via OSRM), computed once offline rather than live — so they reflect the road network, but not time-of-day traffic.
- A browser-sized search. A small population and a short generation budget so it runs live in a tab — Vidal’s production HGS runs far longer, on far larger instances, in C++.
- Local optimum, honestly labelled. Local search reaches a local optimum; the genetic loop escapes many but proves nothing. The baseline it improves on is a genuine nearest-neighbour giant tour decoded by Split, not a strawman.
Play the four stages, or jump to any of them with the numbered rail:
- Giant tour — one dashed path visits every stop; no vehicles yet, just an ordering.
- Split — that path is cut into coloured, capacity-feasible routes at the optimal points.
- Local search + SWAP* — moves fire one after another and the distance ticks down toward a local optimum.
- Evolve — generations run live; the top chart shows the best feasible distance dropping, the lower one shows the population keeping its diversity. The map redraws whenever a new best is found.
The tiles read the current plan’s distance and vehicle count against the nearest-neighbour baseline; the “HGS saving” tile fills in once the Evolve stage has run.
Routing is where operations-research theory meets a fuel bill. The published research is deep and open; the value is in fitting it to your constraints — time windows, driver shifts, heterogeneous vehicles, real road-network distances — and putting the result where dispatch can trust it.
BIS builds the production version: the full HGS (or a solver like PyVRP, both open-source and MIT-licensed) against your depots, your demand, and your rules, behind an API your systems call. This preview runs on synthetic public data; yours would run on yours.
This preview runs on real public data. Yours would run on your data.
We start with a conversation, prove the value on a focused POC with your real data, then ship it — in our environment or deployed into yours.