Algorithms

What actually happens between pressing Plan routes and seeing lines on a map — and why some of the decisions are about how a plan looks rather than how short it is.

The problem

This is a vehicle routing problem: given a depot, a set of stops and a number of vehicles, decide which vehicle visits which stops, and in what order, to minimise something you care about. It is NP-hard, so for anything past a handful of stops nobody computes the true optimum. Twenty stops on three vans is already more arrangements than there are atoms in the observable universe.

What good solvers do instead is find a very good answer quickly, and be honest that it is not provably the best one.

Step one: the distance matrix

Before any routing, the app needs the distance and time between every pair of points. That is the real cost and the real bottleneck — not the solver. Forty stops means 41 × 41, or 1,681 pairs.

These come from OSRM, using actual road networks. If OSRM is unreachable the app falls back to straight-line distance with a 1.3× correction for the fact that roads are not straight, and says so in the interface. A plan with approximate distances beats no plan, as long as nobody is misled about which they are looking at.

Step two: cluster first, then sequence

Here is the decision that shapes everything else. The obvious approach is one nearest-neighbour sweep across all the stops, opening a new vehicle each time the current one fills. It produces short routes and it looks broken.

Both panels are the same forty stops on three vans, generated from real data. On the left the vans interleave and cover each other's ground; on the right each keeps to its own area. Users read overlapping routes as a malfunction, and they are not entirely wrong — two drivers on the same street is waste.

So the solver does it the other way round:

1. Partition the stops into geographic clusters, one per vehicle.
2. Sequence each cluster independently into a good route.

Clustering uses k-means, on coordinates projected into local metres rather than raw latitude and longitude. That projection matters: a degree of longitude is 111 km at the equator and 71 km in Paris, so clustering raw coordinates produces clusters stretched east-west for no geographic reason.

Under even workload the clusters are size-constrained. Points are assigned in order of regret — the gap between their nearest and second-nearest cluster — so a stop that strongly prefers one van gets first refusal, and stops that barely care absorb the imbalance.

Step three: sequencing each route

Three passes, each cheap, each fixing what the last one leaves:

1. Nearest neighbour builds a first route by always driving to the closest unvisited stop. Fast, and usually 20–25% worse than optimal — it paints itself into corners.
2. 2-opt repeatedly takes two edges, reverses the segment between them, and keeps the change if the route got shorter. This is what removes a route crossing itself.
3. Or-opt lifts runs of one to three consecutive stops and reinserts them elsewhere. It catches improvements 2-opt cannot, and unlike 2-opt it stays valid when the matrix is asymmetric — which road networks are, wherever there are one-way systems.

The other three engines

The built-in engine is a heuristic that returns in milliseconds. The other three take a different approach: build a first solution, then spend a time budget improving it — OR-Tools with guided local search, PyVRP with a genetic algorithm, VROOM with its own local search.

All three run in a separate process, because all three are C++ libraries with Python bindings and no usable JavaScript build. They share one service, so choosing between them is a dropdown rather than a deployment.

Measured on forty stops and three vans, with real road distances. Visiting those forty stops in the order they were pasted is 344 km, which is the number every row below is an improvement on.

Three things in that table are worth reading slowly.

The single-van rows are not a bug. Asked for the shortest total, three of the four engines put every stop on one van and leave two idle. That genuinely is the shortest total — a second van means a second trip out to the round and back — and it is the correct answer to the question asked. Whether it is the answer you wanted is why the objective is a control and not a default.

VRoom and Best quality returned identical plans, and VRoom did it between five and thirty-eight times faster. Two engines agreeing to the metre is not suspicious here — on a problem this size they are both reaching the same answer, and the gap is in how long they take to be sure of it.

Balanced is beaten on its own objective. OR-Tools is the only one of the three with a real min-max objective, and it still finishes third on even workload: 33.6 km against 32.0 km. Optimising the right objective directly does not guarantee a better answer than approximating it with a stronger underlying search. The next section is about why.

The engines

Four engines, all built. One runs inside the app; the other three run in a solver service beside it, because OR-Tools, PyVRP and VROOM are C++ libraries with no usable JavaScript build. They share one service and one protocol, so which of them you pick is a dropdown rather than a deployment. Whether that service is configured here decides which are actually offered — ask GET /api/v1/solve and it will tell you.

How “even workload” is enforced

The two objectives are not equally easy to ask for. “Shortest total” is what every one of these engines optimises natively. “Even workload” — minimising the longest route rather than the sum — is a different objective, and only OR-Tools supports it directly, through a span cost on its distance dimension.

Left alone on a round trip, PyVRP and VROOM do the arithmetically correct and operationally useless thing: they put every stop on one vehicle, because a second van means a second trip out to the round and back. On a 40-stop test that is one driver covering 239 km while three vans sit idle.

Both accept a per-vehicle distance cap, so minimising the longest route becomes a search for the smallest cap that still admits a plan — a binary search bounded below by a perfectly even split and above by the uncapped answer. Four probes gets within a few percent, at the price of four solves instead of one.

That price is why VROOM takes 1.7 s on even workload and 239 ms on shortest total in the table above. It is not a slower engine on the harder objective; it is the same engine run several times.

The surprise is that the approximation wins. OR-Tools optimises the real min-max objective and lands on 33.6 km; the two engines bolting a cap search onto a min-sum solver land on 32.0 km. A span cost is the more principled formulation, but it is solved by a weaker search than PyVRP’s genetic algorithm, and on this instance the search matters more than the formulation. That is worth knowing rather than smoothing over: it is a result about these engines on this problem size, not a general claim about either technique.

What is deliberately not modelled

• Time windows. The data format carries the field; the solvers ignore it.
• Vehicle capacity. Same.
• Traffic. Distances are free-flow. A round planned for rush hour will run long.
• Service time is uniform unless you set it per stop — five minutes by default, which is the single number that most affects whether a plan survives contact with the day.

Try it Or call the API