Building a dial-a-ride routing engine in Rust: what we learned

Where this stands

We’re building a custom routing engine for a New York shared-ride operator. This piece is for ops and engineering teams weighing up whether to build their own. The engine isn’t in production yet, and we’ll publish a case study with real operating results once it has been running for a while. Every figure here comes from benchmarks or simulated days, and each one says so.

We test on synthetic days of 1,000 bookings and 200 vehicles, and we have also run simulated days at ten times that, on a simplified travel model (see “How far it scales” below).

The problem: promises, not just routes

In a shared-ride service, each booking comes with a promise, and the engine treats every part of it as a configurable service rule: a pickup window, a latest arrival time for trips that need one, a maximum ride time, and a detour limit that decides when a second rider can be picked up on the way.

That is a version of the dial-a-ride problem, one of the harder problems in operations research. Each new booking has to fit into routes that already carry other riders’ promises, and every insertion shifts the timing of everything after it on that route. Meanwhile traffic changes by the hour, riders cancel or don’t show, and drivers run late.

The brief was an engine that answers a booking immediately, never accepts a plan that breaks a promise, keeps improving the plan through the day, and plans on real New York roads rather than straight lines.

A deterministic planning core

The heart of the engine is a planning core with no network, disk, clock or threads in it. Time is passed in as an argument. Randomness comes only from an explicit seed. Optimisation budgets are iteration counts, never wall-clock time. Time is held as integers throughout, nothing iterates over unordered collections, and every tie is broken explicitly.

That’s deliberate. The same inputs always produce the same plan, byte for byte, a bug found in simulation can be replayed from its seed, and the core can be tested without mocking anything.

Around the core sits a thin shell, including a stateless HTTP service. The service takes the current plan and new events in, and returns the updated plan. It holds caches, never the plan itself, so it can be rebuilt from scratch at any time. Only one owner ever changes planning state, so there are no shared locks to reason about.

Exact insertion, made fast

When a booking arrives, the engine searches every vehicle and every feasible pickup and drop-off position for the cheapest insertion that keeps every promise. Done naively, that is cubic in route length per vehicle, across the whole fleet.

We didn’t want to approximate, so we put six provably sound filters in front of the full timing check. Each one rules out a vehicle or position only when it can prove the full check would refuse it: the vehicle can’t reach the pickup window, the new rider would overfill a stretch of the route, or a detour would push someone on board past their limit. The filters are designed to change speed, never decisions. We kept the slow exhaustive search as a reference, and tests check that the fast path returns exactly the same answer.

What the benchmarks show

• In a randomised property test over 256 synthetic days (3,891 bookings), only 4.1% of the 258,476 candidate positions reached the full timing check, and every decision matched the exhaustive search.
• In the same benchmark stage, on a synthetic day of 1,000 bookings and 200 vehicles with a simplified travel model, median booking time fell from 0.416 ms to 0.031 ms, about 13 times faster, with byte-identical simulator output.
• On the current build, with real New York road times that vary by time of day, booking benchmarks at 1,000 bookings and 200 vehicles give a median of 0.073–0.086 ms and a 95th percentile of 0.150–0.197 ms on a single core (ranges over 10 seeded synthetic days).

All of our timings come from release builds with overflow checks on, running single-threaded on an Apple M5 Pro.

Continuous optimisation with ALNS

Insertion alone gives good plans, not great ones, because early bookings are placed before later ones are known. So the engine also runs an adaptive large neighbourhood search (ALNS). It repeatedly removes a handful of rides, puts them back using the same exact insertion logic, and keeps the result if it’s better. We use random, worst, related and whole-route removal, plus greedy and regret-based repair.

Promises stay hard constraints throughout. Every route the optimiser proposes is fully re-timed and checked before it is accepted.

In a brute-force check on 128 tiny plans, small enough to solve exactly, the optimiser never beat the true optimum (which would have meant a scoring bug) and reached it in 117 of the 128.

Keeping the live plan stable

Changes are applied in small groups and re-checked at the moment they’re applied, so anything that has gone stale is dropped. Limits on how often a ride can move, plus a rule that a driver’s imminent stops never change order, keep the plan usable for the people driving it.

• In simulated operating days at the synthetic test size of 1,000 bookings and 200 vehicles, on a simplified travel model, the live optimiser cut driving by 5.8% (lower on all five seeds), almost all of it empty running, with no measurable cost to acceptance or punctuality in those simulated days.
• In simulated days on the New York road model, the live optimiser saved 5–6.4% of driving.
• In those benchmarks, one 1,000-iteration optimiser call on a synthetic 1,000-booking plan took 0.24–0.40 s.

Time-of-day travel times on top of OSRM

Straight-line distance is a poor guide in a city of rivers, bridges and one-way streets. The engine plans on road travel times from OSRM, an open-source routing engine, with separate vehicle profiles because some vehicles can use parkways and others can’t.

OSRM has no notion of time of day. The usual advice is to run several instances or switch engines. We took a different route. OSRM provides the base road times, which we precompute into in-memory integer matrices, because a network call inside the planner’s inner loop would be far too slow. A time-of-day model then scales those times by weekday or weekend and time band, smoothed across each day. The model is built to keep two properties the algorithms depend on: leaving later never gets you there earlier, and going via a third place is never faster than going direct. We also apply borough-level speed corrections inside the road graph itself, so every matrix entry is still a real shortest path.

This is how the model held up against public data:

• We calibrated it on about 19.9 million public NYC taxi trip records from one month, then tested it against the following month, which the fit never saw. In that benchmark, 9 of 96 time-band and borough medians fell outside ±10%. A single all-day factor got 62 wrong.
• After the borough corrections, the same held-out check came out at 100 of 120 groups within ±10% (now including Staten Island). The remaining misses are all in quiet night and dawn hours.
• In lookup benchmarks, a time-of-day travel-time lookup costs 11.6–13.2 nanoseconds, against about 1.2–1.5 ns for a plain matrix read.

Benchmarking against Cordeau, honestly

To check the search itself, we ran it against the standard dial-a-ride benchmark instances from Cordeau (2006), Operations Research, and checked every result with an independent checker that applies Cordeau’s original rules. Gaps are measured against the best-known solutions tabulated by Gschwind and Drexl, cross-checked against Parragh and Schmid (2013).

These are our benchmark results on the “a” instances, best of five seeds, at 25,000 optimiser iterations:

• Insertion alone: a 13.15% average gap to the best-known solutions.
• With ALNS: 4.20%, with every optional service rule enabled.
• Like-for-like rules: 0.48% with one optional service rule switched off. It’s a configurable option that Cordeau’s problem doesn’t include, so we switched it off for the comparison. On those settings, the optimiser reached the best-known value on six instances.
• Published method: Gschwind and Drexl report 0.14% for their ALNS (Transportation Science, 2019), also as the best of five runs, so their method stays ahead of ours, by about 0.3 percentage points. Averaged over the five seeds, it’s 0.74% for us and 0.32% for them. Our average covers the 19 “a” instances that are fully served and have a published best-known value, so this is a close comparison but not an exact like-for-like one.
• Feasibility: across all 3,840 benchmark runs, every fully served plan passed the independent check.

The most useful finding was that one optional service rule, a configurable option we switched off for the comparison, accounted for most of the remaining gap. The search itself wasn’t the weak part. Most of the gain also comes early: in the benchmark, 1,000 iterations recovered 8.3 of the 8.95 points that 25,000 did, and 1,000 is roughly the budget the live plan gets.

Testing an optimiser you can’t eyeball

You can’t check a plan for a whole fleet by looking at it. So the planner and the validator are written independently, applying the same rules in different code, and each catches the other’s mistakes. Where a fact is stored twice, any disagreement is reported, never silently resolved.

Determinism pays off here: the simulator replays a whole day exactly from its seed, so intermittent bugs become reproducible ones. In debug builds the planner also re-runs the slow reference search on a sample of bookings and asserts that it gets the same result, so every test day doubles as an equality test. Every external input is size-checked before any work proportional to it, and every queue and collection has an explicit limit.

How far it scales

Our standard synthetic test size is 1,000 bookings and 200 vehicles. Here is what we have tested beyond that, and what we haven’t:

• Tested: in benchmarks on synthetic days of 10,000 bookings and 2,000 vehicles with a simplified travel model, median booking time was 0.39 ms (95th percentile 0.77 ms) on one core. The whole day’s bookings took 4.23 s.
• Tested: in the same simulated setting, a 1,000-iteration optimiser call took 1.3–2.3 s.
• Not yet tested: we haven’t yet benchmarked the time-of-day road model at that scale, and we haven’t load-tested the HTTP service. Both are on the list before we’d quote figures for a larger fleet.

What we learned

• Keep the slow version. Every fast path has a slow, obviously correct twin, and tests compare them. That’s what let us make booking about 13 times faster in benchmarks without changing a single decision.
• Measure optional rules separately. The Cordeau gap only became useful once we split it into “the rules” and “the search”.
• Calibrate against data the fit never saw. The held-out month showed us which errors were noise and which were structural, and that led to the borough corrections.

What’s next

The engine isn’t in production yet. Once it’s running for the client, we’ll write the case study, with operating results from real days rather than simulated ones.