A dispatcher for delivery riders: one routing problem a minute

The platform I work on in Andorra delivers food, parcels and supermarket orders. Until this summer, orders reached riders one at a time, as each one came in, and often because an operator picked a rider for it in the dashboard. The new system does it differently: every minute, one round takes every open order and every rider on duty and solves them together as a single vehicle routing problem. Out of it comes who takes what, in what order and at what time, written as the legs each rider sees in the app.

I was part of the team that designed and built it, and a good part of the dispatcher’s shape comes from the classic “design Uber” system-design exercise and from what Uber has published about its matching. Uber’s own description of batched matching is the idea in one sentence: instead of giving each request the closest driver, wait a few seconds, let a batch build up, and pair the whole batch at once. Our batch window is a minute instead of seconds, and our fleet is a few riders in a small country instead of a city, but the move is the same.

This post is how it is built: the round step by step, choosing the solver, what happens when the promises cannot all be kept, why the solver’s answer is never written as it comes, and how the legs are written without losing what a rider has already done.

The problem in the solver’s terms#

Each order is a pickup-and-delivery pair. It is collected at a shop and handed over at a door, and each stop has a promise: the time the shop said the order would be ready, and the time the customer was told. A rider is a vehicle: where and when they next come free, when their shift ends, and what kinds of order they work. In the literature this is a dynamic pickup-and-delivery problem with time windows. Dynamic, because orders keep arriving while riders are already on the road.

A rider’s work is written as legs, four per order: EN_ROUTE_TO_PICKUP, AT_PICKUP, EN_ROUTE_TO_DROPOFF and AT_DROPOFF. The legs are what the rider app lists and what the forms, the handover PIN and the incidents hang from.

The routing package states all of that in its own small language, which knows nothing about riders or shops:

type Stop struct {
  ID        string    // the address: two orders at one shop share it
  Location  GeoPoint
  Deadline  time.Time // the promise for this stop
  NotBefore bool      // a collection: the food does not exist sooner
}

type Order struct {
  ID       string
  Stops    []Stop   // collection, then handover
  Needs    []string // order type, a vehicle the customer asked for
  Excluded []string // riders who let it expire
  LockedTo string   // the rider who already holds it, if any
  Done     int      // stops already visited
}

type Vehicle struct {
  ID           string
  Position     *GeoPoint
  StartAfter   time.Time // when this rider is next free
  EndBy        time.Time // end of shift
  Capabilities []string
  Carrying     int // bags on board that this round is not asked about
}

Two decisions in those types matter later. Work already given to a rider is not a different type: it is an order with LockedTo set and Done counting what is behind it. The solver may re-sequence it and slot new work around it, but it cannot hand it to anybody else. And all time lives on the stops. An earlier version had a ready time, a maximum transit time and a soft delivery time on the order. They were removed in favour of one deadline per stop, because three clocks on one order kept disagreeing with each other.

One round, step by step#

The dispatcher has no tables of its own. Each tick rebuilds the whole problem from the orders, the legs and the riders, solves it, applies it and forgets it. That makes a round easy to reason about: there is no in-memory plan that can drift from the database, and a round that fails changes nothing that the next one will not look at again.

0. Gate and lock. The round runs only when the dispatch strategy in the configuration table is VRP, which is how it was switched on and how it can be switched off without a deploy. A Redis lock with a two-minute TTL makes sure a slow round never overlaps the next tick: if the lock is taken, the tick is skipped.

1. Take back what nobody accepted. An order the round gave to a rider five minutes ago, whose rider has not started any of its legs, is taken back. The unassignment is written to the assignment log, and that log row is also what excludes that rider from that order in every later round. There is no table of exclusions: the log is the source of truth, and the order source reads it. This step lives outside the sources on purpose, because sources translate and never mutate.

2. Gather. The open pool is every order waiting for a rider and marked for automatic dispatch. Next to it goes every order a rider already holds, including the ones an operator assigned by hand. Leaving those out would let the solver stack new work on a rider it believes is idle. The fleet is the riders on duty, each anchored where and when they next come free: the end of the leg they are on, or their last GPS fix.

3. Solve. The whole fleet is asked at once, with one exception: an order that no rider could ever take, because nobody has the skill or every capable rider is excluded, is set aside before the solver sees it. The solver gets its own sections below.

4. Validate and 5. apply, which are most of the code, get their own sections.

6. Log. Each round ends with one JSON line: which solvers were tried, how many assignments expired, the routes, the unassigned orders, every deviation from the solver’s answer, every stop planned late and the duration. When someone asks why an order went to a given rider at 13:42, that line is the answer.

Choosing the solver#

The routing package has a Solver port and two adapters behind it, Mapbox Optimization v2 and VROOM, the open-source engine behind OpenRouteService, which runs on our own cluster.

Mapbox came first and did the basic job, but when the policy was tested against the real API, it could not express it. With soft time windows it spread the lateness over every order in the round, five to sixteen minutes each, instead of giving up on one. With strict windows it did not drop the conflicting order either: it answered that no solution existed, and the whole round was lost without saying which order was the problem. There was no priority to say which order matters more; sending one returned HTTP 422.

VROOM was put through the same scenarios before anything was built on it. It returns the orders it could not place in an unassigned list, with a reason, and routes the rest. A priority per order changes which one is left out. Two orders from one shop are collected in one visit. A round took about 0.3 seconds, against 10 to 20 seconds of submit-and-poll with Mapbox.

The engine is not a deploy-time choice. The configuration holds a chain, vroom,mapbox, read on every round: the first engine that answers serves the round and the next one is its failover. VROOM being self-hosted is a risk as well as a saving, and the chain covers it.

The adapter has one trick worth showing. VROOM matches vehicles to jobs only through skills: a job lists the skills it needs and a vehicle must hold all of them. So every reason a rider may or may not take an order is written as a skill, including the ones that are not really skills:

switch {
case o.Locked():
  // Committed work: a skill only its rider holds.
  skills = []int{grant("locked/"+o.LockedTo, func(v Vehicle) bool { return v.ID == o.LockedTo })}
default:
  skills = table.skillSet(o.Needs)
  if len(o.Excluded) > 0 {
    // "Must NOT be rider X" cannot be said, so it is turned around:
    // a skill granted to every rider except the excluded ones.
    skills = append(skills, grant("order/"+o.ID, func(v Vehicle) bool { return !o.Excludes(v.ID) }))
  }
}

Late rather than unassigned#

The business rule was stated plainly: out of three orders, two delivered late are better than one left without a rider. An order with no rider is worse than an order that arrives late.

Our VROOM adapter writes its time windows as hard limits, which is what lets it say “this order does not fit” instead of quietly spreading lateness over everything. To turn that into “late rather than unassigned”, the round buys lateness, one rung at a time, and only for the orders that did not fit.

Every order is sent with priority 100. VROOM fills priority before it minimises cost, so it leaves an order out only when no vehicle can take it, never because it is late. If something is still unplaced after the third rung, there is one last pass. Every order already placed is pinned to its rider, and the leftovers are asked with no window and no bag limit. Without the pin, a pass with no constraints could re-cut the whole round around one leftover; with it, the pass can only add.

The model also leaves room for a ceiling per stop: a stop that says it must not be served more than N minutes late is never released past N, because serving it at an hour it refused is worse than the unassigned it asked for. No order type sets one today, so in practice every order is served late rather than dropped.

The lateness is not hidden either. After the solve, every stop planned past its promise plus five minutes of tolerance is reported in the round log, measured from the promise.

The solver’s answer is a proposal#

The adapter turns VROOM’s routes back into stops, but nothing is applied as it comes. NewSolution checks it first, and it is designed never to fail. What it cannot accept, it leaves out one order at a time and records as a deviation:

• an order routed to a rider other than the one who holds it, or routed to two riders;
• a rider who lacks a skill the order needs, or one the order excludes;
• an order planned only halfway: a collection with no handover is a state no round should ever write;
• a visit that ends past the end of the rider’s shift;
• a time the solver gave that is earlier than the rider can physically be there, which is moved onto the route’s own clock and reported as repaired.

The same idea applies before the solve, for a different reason: a few bad inputs make the solver reject the whole document, not just one order. An address that was never geocoded reads back from MySQL as a valid POINT(0 0), which passes every nil check and then gets the entire request refused as out of bounds. So stops off the map are filtered out before the request. A request also has a budget of 200 job locations, the routing backend’s matrix limit. What does not fit waits for the next round instead of breaking this one.

The rule behind all of it: one bad order costs that order, never the round.

Who gets the work#

The first versions concentrated work on whoever was closest. That is not a bug in the solver. A solver minimises what the whole fleet costs, and one rider doing five orders almost always beats two riders doing them, because the second one has to be driven there first.

The first attempt to fix it was the obvious one: give the riders a cost per hour. Measured against the real service, it did not work. With two orders from one counter, the cheaper rider took both. The cost moved the whole round to another rider instead of splitting it, because VROOM’s per_hour prices the rider, never the order. With two shops six kilometres apart, the round split by itself, cost or no cost: a second shop that far away is a journey, not a detour.

What spreads the work is stated in the request: capacity and geography. Each rider’s bag holds two orders at once, collected and not yet delivered. A third would go cold while the rider is busy elsewhere. Orders the rider already carries outside the round, such as bags on hold, come off that capacity. A rider who holds two orders is therefore not offered a third while someone else is free, and two orders from the same shop can still ride together, because one stop with two bags fits in the bag.

There are trade-offs, and it is better to name them. Two orders from one restaurant split between two riders means two trips to that counter where one would have done. That buys two customers served in parallel instead of one after the other. The bag limit is also a preference rather than a refusal: on the last pass it yields before an order is left without a rider.

Deciding is not writing#

The part of the dispatcher with the most code is not the solve. It is applying the result without breaking what is already on the road.

When the round applies its result to a rider, it does not create the legs from the round’s stops. It only records the decision, these orders are this rider’s, in one transaction per batch of orders collected together, after checking that each order is still waiting for a rider. Between the solve and the apply, an operator may have assigned one by hand. In that case the batch is skipped, and the next tick will look at it again.

Then a separate component, the reconciler, re-plans that one rider’s whole round, everything they hold now, and makes their legs say what the new plan says. It does not delete and re-create the legs. It computes a diff:

• Missing: work the plan contains that no leg describes yet is created.
• Claim: an order riding a journey another order’s leg already describes is linked to that leg. One road is one leg, however many bags come off the bike at its end.
• Cancel: a leg the plan no longer contains is cancelled.
• Retime: surviving legs get the new plan’s windows and positions.

The diff is what keeps the rider’s history intact. A leg in progress keeps its status, its forms and its incidents, because it is the same row.

Three concurrency rules hold all of this together:

1. The solve never runs inside a transaction. It is a network call that can take seconds, and holding row locks while waiting for it is how a database falls over. Decisions commit, then the round is solved, then the diff is written in one short transaction.
2. Each rider has a Redis lock with a 30-second TTL. It is held from the first decision to the last write, and every writer takes it: the dispatch round, the dashboard, the rider app. Each transaction is atomic on its own; only the lock serialises the whole pass against a manual reassignment of the same rider.
3. Nobody hears about an assignment before its legs exist. The order status change, the push to the customer and the rider’s notification happen after the reconcile. Each rider gets one aggregated push per round, not one per order.

The same reconciler is used when a person changes a rider’s work by hand from the dashboard. That way manual and automatic assignment share one model of time, instead of the dashboard keeping its own arithmetic.

Time is append-only#

Each leg’s times live in task_times, and that table is append-only. A row is never updated. A new row with a higher sequence is inserted, with a reason: INITIAL, DISPATCH, MANUAL, RIDER_LATE, INCIDENT or REORDER.

The first row is never touched, not when a round re-times the leg and not when the rider runs late, so the app can always show what was promised next to what is happening. Every later row says who moved the leg and why.

The order of a rider’s list is recorded the same way, as the position the plan gave each leg, not worked out from the times. An earlier version sorted by time and broke ties between two arrivals at the same instant by adding one second to one of them. That second ended up in the ETA the customer saw. A migration added the position column specifically to remove it.

Why MySQL#

All of this lives in MySQL, the platform’s database. That is a choice I am happy to defend, and the argument I would make is the one in Uber’s 2016 post, Why Uber Engineering Switched from Postgres to MySQL, which is one of the posts that shaped how I think about storage engines.

The core of it is write amplification. In the Postgres version the post analyses (9.2), an update writes a new version of the row, and because every index points at the row’s physical location, every index on the table can need a new entry, even for a column none of them covers. Postgres replicates its physical write-ahead log, so the amplification is shipped to every replica as well. In InnoDB, secondary indexes point to the primary key instead, so an update only touches the indexes whose columns actually changed. Replication is logical, which also means replicas can run a different version during an upgrade. The post covers more: process-per-connection against thread-per-connection, and MVCC on replicas. It is from 2016 and Postgres has moved on since, so I read it as a model of the trade-offs rather than a verdict.

For this workload the model fits. The dispatcher’s writes are many small inserts into tables that are read by indexes: time rows, assignment log rows, links between orders and legs. The dispatcher did not need a single new table. Exclusions are rows in the assignment log, shared rides are rows in the link table, and times are rows in task_times.

Testing a solver you do not control#

The riders’ side of the codebase has more test code than production code, around 29,000 lines of tests against 22,000, and two layers of tests that do different jobs.

The unit layer pins the arithmetic to the minute. Twenty-five dispatch scenarios are written down as tables of expected legs, such as “two orders from one counter, two minutes apart”, “the near rider is busy, the free one is farther”, or “the rider’s shift ends before the work does”. Each has a test that declares the route by hand and checks every window.

The live layer sends the same scenarios to a real VROOM and a real MySQL and checks the shape of the round, not the instants: which arrivals are shared, that one road leads to each place, that the chain of legs runs forward. It cannot demand that a delivery lands at 18:44 exactly, because an update to the map can find a better road, and a test that fails for a better road is testing the wrong thing.

Two habits made that layer trustworthy:

• A skipped live test fails when it is supposed to run. A live test skips itself when the solver is not reachable, so a clean go test ./... can be green without having asked anything. With DISPATCH_LIVE=1, which the script always sets, a skip becomes a failure.
• Tests were checked with fault injection. Turning off the code that merges shared rides reproduced the reported bug, two EN_ROUTE_TO_PICKUP rows, one of 15 minutes and one of 0 seconds, and the test caught it. Collapsing every journey to one minute produced exactly the message the test should give: is 1m0s on the rows but the solver said 30m0s.

Some live tests are red on purpose. Asked on its own, VROOM does not count waiting for a shift to start as a cost, so it still picks a rider who has not started yet. The round avoids that by not offering riders off shift. The live test that asks the solver directly stays red, as a reminder that the solver will not do it by itself.

Where it stands, and what Uber does differently#

The round runs every minute. Manual assignment from the dashboard is still there as the fallback, and it now goes through the same reconciler.

What is deliberately not built yet, with the reason for each:

• Two speeds. A dispatcher at a larger scale usually runs two loops: a fast insertion of each new order into the live plan, and a slower re-optimisation in the background. Ours is periodic only, so an order can wait up to a minute before it is considered. At this volume a minute is fine, and an event that brings the next tick forward is the obvious next step if it stops being fine.
• Partitioning. There is one global round, with no zones. A country this size fits in one request, inside the 200-location budget, and the day it does not, the round splits by zone and keeps the same model.
• A stable plan. Every round may reshuffle work that has not started yet. The windows rewrite themselves, and the first row keeps the promise, but there is no threshold yet that says “do not tell the rider about a change smaller than N minutes”.