One routing problem, two engines
Vehicle routing is the decision behind every delivery fleet: serve every stop at least cost, within vehicle capacity and time windows. It is NP-hard, so there is a real choice — prove the optimum with an exact model, or scale past it with a tailored engine. BIS builds both. This series solves the same problem two ways and shows when each wins, on real last-mile problems, reproducing the published best-known solutions. BIS has no routing product to sell here — every routing result here is computed by the linked repository.
Least-cost routes, within the constraints
The capacitated vehicle routing problem (CVRP) asks: given a depot, a fleet of capacity-limited vehicles, and a set of stops with demands, what set of routes serves every stop at least total distance? Add delivery time windows and it becomes the VRPTW. It is the shape of decision behind last-mile delivery, field service, and distribution — and it is the same craft as the dispatch, scheduling, and allocation engines BIS delivers.
An exact model, and a tailored search
Exact — in AMPL. A mixed-integer program with a binary variable per arc; the MTZ load constraints enforce capacity and kill subtours at once. An open-source solver (HiGHS) proves the optimum — a certificate, and a model a customer’s team can read and change.
Tailored — Hybrid Genetic Search. Thibaut Vidal’s HGS is the state of the art for routing at scale. BIS built it from the papers as a compact, in-browser engine (the live demo); the reference open-source implementation, PyVRP, carries it to the largest instances. Same family, two deployments.
minimize distance:
sum {i in N, j in N: i <> j} d[i,j] * x[i,j];
subject to leave {i in C}: sum {j in N: j <> i} x[i,j] = 1; # each stop left once
subject to enter {i in C}: sum {j in N: j <> i} x[j,i] = 1; # ... and entered once
# MTZ load propagation — enforces capacity AND eliminates subtours in one stroke
subject to load_link {i in C, j in C: i <> j}:
u[j] >= u[i] + q[j] - Q * (1 - x[i,j]);Reproducing the published best-known solutions
Trust starts with reproducing a known answer. On the classic Solomon VRPTW benchmark, PyVRP reaches the published best-known solution exactly; the exact AMPL model proves the optimum on a 25-customer slice (617.1), and the metaheuristic matches it there.
| Solomon instance | PyVRP | Best-known | gap | vehicles | seconds |
|---|---|---|---|---|---|
| C101 | 827.3 | 827.3 | 0.00% | 10 | 8 |
| R101 | 1,637.7 | 1,637.7 | 0.00% | 20 | 8 |
| RC101 | 1,635.7 | 1,619.8 | 0.98% | 16 | 8 |
The two enterprise chapters put this to work: Amazon-scale last-mile on the CVRPLIB benchmark, and Loggi’s real Rio de Janeiro deliveries.
Benchmarks and best-known solutions: Uchoa et al. (2017, CVRPLIB); Kool et al. (2023, the EURO Meets NeurIPS VRP competition and PyVRP); Vidal’s HGS. The ORTEC/EURO-NeurIPS and Amazon datasets are non-commercial, so we cite them and run the reproducible solves on openly-licensed benchmarks (Solomon, CVRPLIB); Loggi’s data is MIT and is solved on directly.
When AMPL, and when a bespoke engine
- 01
Exact, when it fits
A small or mid-size instance where a certificate matters (audit, contracts, a proof of optimality): AMPL + an open-source MIP proves it — and hands over as readable model, not a black box.
- 02
Tailored, at scale
Thousands of stops, a tight response budget, or an engine embedded in a product: a Hybrid Genetic Search returns a near-best-known answer in seconds where exact cannot finish.
- 03
Both, honestly bounded
Run the exact model on a slice to anchor the optimum, then let the metaheuristic scale — and report the gap to the best-known instead of claiming optimality you did not prove.
BIS builds the routing models AMPL license customers need — exact where it pays, a tailored engine where it must scale, reviewed against the literature and handed over to run. If a customer needs model development, this is what they get. Referrals welcome.
Have a routing or scheduling problem worth solving?
We frame it, prove the value on your real data, and ship the engine — exact or tailored, whichever the problem needs.