Autodispatch: The Assignment Problem, Live

A Note on the Name

Autodispatch was not always called autodispatch. It was originally two services: a planner that decided what should happen, and a worker node that carried it out. The planner was called marx. The worker was called prole.

As a piece of naming this is internally consistent and even a little bit clever, right up until you notice what the workers being dispatched actually were. They were people. Nobody set out to call couriers proles — the name described a node in a service topology, and by the time anyone traced the line from the topology to the humans on the other end of it, the name was load-bearing across a dozen repos.

We kept it internal and hoped. When a new director arrived, the very first thing he ordered was that it be renamed, and to make sure it stuck he stood up a Slackbot that replied "autodispatch" to anyone who typed "prole" in any channel. He was completely right. We also added a banner.txt to the Spring service that rendered, on every single startup, a note to the effect of don't let that guy name things. Both the rename and the banner were correct responses to the same mistake.

The dispatch module in this codebase carries a one-line comment about where the name came from and nothing else. It seemed worth recording once, in the place where someone might actually wonder.

The Problem

At any moment there is a set of orders needing a courier and a set of couriers who could take one. Dispatch is the recurring decision of how to pair them. The naïve version — hand each order to its nearest available courier the instant it is confirmed — throws away the two facts that matter most: who else is about to need a courier, and who is about to become free. It gives the nearest courier to whichever order happened to be confirmed first, which is an ordering with no meaning.

So dispatch batches. Orders pool for a cycle, and then the whole board is solved at once as a bipartite graph: couriers on one side, orders on the other, an edge for every pairing worth considering. That is the picture the demo below draws, because it is the actual data structure — not an analogy for it.

Learning to see problems this way is the kind of thing that leaks into the rest of your life. The wedding seating optimizer on this site exists directly because of this work: sitting down to arrange a reception, I recognised the shape immediately — guests and tables instead of couriers and orders, a preference matrix instead of drive times, the same assignment skeleton underneath.

The Formulation

x_co assigns order o to courier c. u_o holds an order back for a later cycle at a price that escalates the longer it waits, so deferral is a decision the model makes deliberately rather than a failure it falls into.

The cost coefficient prices the projected consequence of the pairing rather than the distance. Dispatch projects each pair forward — the courier becomes free at some time and place, drives to the merchant, waits if the food isn't up, then drives to the diner — and charges for everything that goes wrong along the way: lateness against the promise, deadhead, a courier idling at a counter, cooked food sitting under a lamp.

Why It Solves Exactly

This is an integer program, and integer programs are NP-hard in general. This one isn't, and the reason is worth seeing. Look at any column of the constraint matrix: variable x_co appears in exactly two rows — the assignment row for order o, and the capacity row for courier c — each with a coefficient of +1.

That makes it a bipartite incidence matrix, which is the textbook example of a totally unimodular matrix. Every vertex of the LP relaxation's polytope is therefore integral, the integrality constraints are redundant, and the whole thing collapses to a min-cost flow — source to couriers with capacity, couriers to orders at cost, orders to sink, plus a parallel "defer" node that lets an order route around the couriers entirely at its escalating price. Successive shortest paths with Johnson potentials makes each augmentation a plain Dijkstra. It is exact, and it runs in well under a millisecond on a realistic board.

This property is also fragile, and knowing exactly how fragile is most of the value of understanding it. It survives any change that prices a pair: every new term below is a per-pair constant, so the columns keep their shape and the solver never changes. It does not survive anything that couples orders to each other. Stacking two pickups into one trip puts a +1 in two order rows at once, and the matrix stops being an interval matrix; so does route sequencing, and so do hard fairness quotas. Those need real branch-and-bound, and the honest way to describe that boundary is not "we didn't get to it" but "that is a different problem and it costs a different solver."

Estimating Acceptance — and Refusing to Use Tips

The base model prices an assignment as though it will happen. It won't always. An offer is a proposal, and a refused one is strictly worse than a slightly-worse offer that gets taken: the order loses a full cycle, the food sits, and the next round starts from a worse board. Pricing that risk means estimating p̂_co, the probability a given courier takes a given offer, and charging every pair for the chance it is refused.

Here is the uncomfortable part. The single strongest predictor of whether a courier accepts is how much the offer pays, and the tip is most of that. Dispatch is not allowed to know it. In this codebase that is enforced by the type rather than by a comment: the acceptance feature struct has no pay field, no tip field, no order total. A model that cannot see the number cannot come to depend on it.

The reason is that the alternative is a tip-gated marketplace. Let dispatch optimise against predicted acceptance with tips in the feature set and it learns, correctly and immediately, that low-tip orders are bad bets — so it routes around them. Those orders age, get deferred, and are eventually delivered late by whoever is left. That sounds almost like fairness until you notice the mechanism punishes the diner whose app defaulted the tip to zero exactly as hard as the one who chose it, and that a pre-delivery tip is a bid on service, not payment for service rendered. A platform that sorts its service levels by pre-tip is running an auction it never disclosed.

So the features are all about the shape of the work: deadhead, predicted wait at the counter, trip length, how far the drop-off strands the courier from home, whether it runs past the end of their shift, whether it stacks on existing work, how many offers they have turned down recently. Several of these are things dispatch can fix rather than merely predict, which is the useful kind of feature — a long predicted counter wait lowers acceptance and is a real cost worth avoiding anyway.

ghost

Dispatch changes are close to impossible to judge from a single board. The boards are noisy, the effects are a few percent, and — as it turns out — the sign of an effect can flip with market conditions. Shipping to a live market and watching the dashboard answers the question in about a week, costs real deliveries to find out, and confounds the change with the weather.

So changes went through ghost first: an offline harness that replayed many boards through competing formulations, with identical seeds under every policy, and reported the difference with its spread rather than as a single number. It is a cousin of the actor simulation — same instinct, narrower scope. The actor sim exists to make a whole marketplace behave; ghost exists to answer one question about one objective function.

The demo below runs a version of it. What ghost was most useful for, though, was not confirming good ideas:

Two Plausible Improvements, Measured

I built two extensions to the objective and measured both over replicated simulated days in the actor simulation. Neither did what I designed it to do.

Acceptance-awareness helps only when supply is scarce. Over five replicate days at a balanced fleet it made things worse — on-time fell from 78.8% ± 0.9 to 76.2% ± 1.2. At a skeleton fleet it clearly helped: 50.3% ± 2.1 to 55.1% ± 2.5 with both new terms enabled. The mechanism is obvious in hindsight and invisible in advance. When couriers are plentiful a refusal is cheap — someone else is right there — so hedging against it only buys deadhead. When couriers are scarce a refusal drops the order onto an empty board, and hedging is worth real money.

The equity discount did nothing. The idea was to counteract the optimiser's tendency to feed the same well-placed couriers all night while others sit. It was supposed to spread the work. Measured across couriers, the Gini coefficient of deliveries went from 0.290 ± 0.017 to 0.306 ± 0.021 — unchanged inside noise, arguably slightly worse — while the number of couriers who never got a delivery went from 2.0 to 2.4 and on-time fell about a point and a half. A term that costs throughput and doesn't deliver the fairness it was designed for is not a trade-off; it is just a worse objective function.

Both therefore ship disabled by default. That is the finding, not a hedge: the constant in the code is zero because the measurement said so, and the comment next to it says which measurement. Enabling acceptance-awareness adaptively when a market goes supply-constrained is the obvious follow-up, and the obvious follow-up is exactly the sort of thing that should be tested in ghost before anyone believes it.

What the Demo Shows About Tips

The backtest in the demo includes one policy this codebase refuses to ship: a tip-aware objective. It cannot be expressed through the acceptance model at all — the feature type has no slot for money — so it has to reach for an explicit experimental hook, which is the guardrail doing its job.

In the scarce regime it posts the best acceptance rate of any policy, and leaves roughly 83% of the lowest-tip third of orders unassigned against about 70% for the money-blind policies. It is a straightforward improvement on the metric you would naturally put on a dashboard, and a marketplace quietly sorting diners by their pre-tip. Run it yourself below; the harm shows up only in the last column, and only when supply is tight — which is to say, it is invisible in exactly the conditions where you would be evaluating it, and severe in exactly the conditions where it matters.