Assigning Orders to Riders: Why Nearest-First Is the Wrong Algorithm

Dispatch looks like a one-line problem. An order comes in, you find the nearest free rider, you send it to them. That code is easy to write, it demos beautifully, and it survives until the moment two orders are in flight at once.

The reason it breaks is structural rather than a bug you can patch. Assigning riders is a matching problem, not a search problem. Searching answers "who is closest to this order", one order at a time. Matching answers "what is the best set of pairings across every order and rider I currently have", and those two questions have different answers more often than you would guess.

Why nearest-first goes wrong

Put two riders and two orders on a straight road. The orders arrive a few seconds apart, so a search-based dispatcher handles them in arrival order and commits to each decision before it sees the next:

position    0     1     2     3     4     5     6
            R1                      A     R2    B

nearest-first   A → R2 (1)    B → R1 (6)    total 7
matched         A → R1 (4)    B → R2 (1)    total 5

A is genuinely closer to R2, so the greedy answer is not a mistake in any local sense. It is only wrong once B exists, and when A was assigned B had not arrived yet. The dispatcher gave away the one rider B could reasonably use, and no later decision can recover it.

Forty per cent extra distance in a toy example does not sound alarming. In a real market the effect compounds, because the rider it strands is usually the one in the quiet part of town — the same rider who will now spend twenty minutes driving to a pickup while a customer watches the promised time slip.

Collect for three seconds, then match

The fix costs you a few seconds of latency and nothing else. Instead of dispatching each order the instant it is paid for, hold new orders in a short window, then assign the whole batch together. Three seconds is usually enough to change the answer and short enough that nobody notices.

With a batch in hand you can score every rider against every order and take the best pairs globally, rather than in the order the orders happened to arrive:

export function assignBatch(orders: Order[], riders: Rider[]) {
  // Every pair, cheapest first — not arrival order.
  const pairs = orders.flatMap((order) =>
    riders.map((rider) => ({ order, rider, cost: cost(order, rider) })),
  );
  pairs.sort((a, b) => a.cost - b.cost);

  const usedOrders = new Set<string>();
  const usedRiders = new Set<string>();
  const assignments: Assignment[] = [];

  for (const { order, rider, cost } of pairs) {
    if (usedOrders.has(order.id) || usedRiders.has(rider.id)) continue;
    // An absurd pairing is worse than no pairing. Leave it for
    // the next window rather than sending someone across the city.
    if (cost > MAX_COST_MS) break;

    usedOrders.add(order.id);
    usedRiders.add(rider.id);
    assignments.push({ orderId: order.id, riderId: rider.id });
  }

  return assignments;
}

This is still a greedy algorithm, but it is greedy over the whole batch instead of over the arrival sequence, and that single change recovers most of the gap. True optimal matching is the Hungarian algorithm or a min-cost flow solver, and it is worth reaching for a library once batches get large — but it is not where you should start, because the sort above is ten lines and gets you most of the way.

Score in seconds, not metres

Distance is the wrong unit. A rider 400 metres away on the far side of a river is further, in every sense the customer cares about, than one two kilometres away on the same road. Convert everything to time and the comparisons become honest — and, usefully, so does the arithmetic, because waiting and travelling are then in the same units and can simply be added.

function cost(order: Order, rider: Rider): number {
  // Not "is this rider free" but "when and where will they be".
  // A rider two minutes from dropping off next to the restaurant
  // beats an idle rider across town.
  const { freeAt, position } = projectedAvailability(rider);

  const waitMs = Math.max(0, freeAt - now());
  const toPickupMs = travelTimeMs(position, order.pickup);
  const prepMs = Math.max(0, order.readyAt - now());

  // If the food is not ready, arriving early buys nothing —
  // so the real cost is whichever of the two finishes last.
  const arrivalMs = Math.max(waitMs + toPickupMs, prepMs);

  return arrivalMs - idleBonusMs(rider);
}

The prepMs term is the one people leave out, and it changes assignments constantly. If a kitchen needs twelve more minutes, then every rider who can arrive within twelve minutes is equally good, and the dispatcher should be free to give the closest one to a different order instead. Scoring on distance alone throws that flexibility away.

idleBonusMs subtracts a small amount for riders who have been waiting a long time. Pure efficiency starves whoever happens to be in a quiet area, they log off, and your coverage in that area gets worse — which is a slow, self-inflicted problem that never shows up in the dispatch metrics you were watching.

Shortlist with geometry, rank with roads

Real travel time comes from the Routes API, and this is where dispatch quietly becomes expensive. Compute Route Matrix bills per element, and the element count is origins multiplied by destinations — so fifty riders against five orders is not one call, it is 250 billable elements.

Run that on every batch and the arithmetic gets bad quickly. Shortlist with cheap local geometry first, and only ask Google about the handful of riders that could plausibly win:

const SHORTLIST = 5;

export async function candidatesFor(orders: Order[], riders: Rider[]) {
  // Haversine is free, runs in memory, and is wrong in exactly
  // the way we can tolerate here: it never rules out a rider who
  // is genuinely near, only ranks the near ones imperfectly.
  const shortlisted = new Map(
    orders.map((order) => [
      order.id,
      riders
        .map((rider) => ({ rider, km: haversineKm(rider.position, order.pickup) }))
        .sort((a, b) => a.km - b.km)
        .slice(0, SHORTLIST)
        .map((c) => c.rider),
    ]),
  );

  // 5 orders x 5 riders = 25 elements, not 250.
  return routeMatrix({
    origins: unique(([...shortlisted.values()]).flat()),
    destinations: orders.map((o) => o.pickup),
  });
}

Straight-line distance is a bad final answer but a perfectly good filter. The rider who wins on road time is almost always inside the five nearest by geometry, and the two orders of magnitude you save on elements is the difference between dispatch costing nothing and dispatch costing more than your hosting.

An offer nobody accepts must expire

If riders can decline — and if they carry phones, they can always decline by ignoring you — then an assignment is only an offer. The failure mode is not rejection, which is fine and immediate. It is the rider who puts the phone in their pocket, so the order sits in offered with nobody looking at it and no event ever arriving to tell you.

await db.insert(offers).values({
  orderId: order.id,
  riderId: rider.id,
  // The offer, not the order, carries the deadline.
  expiresAt: new Date(Date.now() + 20_000),
});

// A sweep every few seconds returns expired offers to the pool.
// Without this the order is stuck until a human notices.
export async function reclaimExpired() {
  const stale = await db
    .update(offers)
    .set({ status: "expired" })
    .where(and(eq(offers.status, "offered"), lt(offers.expiresAt, new Date())))
    .returning();

  // Do not re-offer to someone who just let it lapse.
  for (const offer of stale) {
    await requeue(offer.orderId, { exclude: [offer.riderId] });
  }
}

Twenty seconds is a reasonable default and worth tuning against your own acceptance data. Track how many offers each order needed before somebody took it: a median above two means your scoring is proposing pairings riders do not want, and no amount of matching cleverness fixes a rider population that considers the job not worth taking.

Decide what you are optimising before you tune it

Every knob here trades one party against another. Shorter batch windows favour the customer who ordered first. Longer ones produce better pairings on average and make the first customer wait. Idle bonuses cost efficiency and buy rider retention. Stacking two orders on one rider raises earnings per hour and risks the second customer's food arriving cold.

There is no setting that wins on all of them, so pick the one number you are actually managing — most young marketplaces should pick the percentage of orders delivered within their promised window — and change one knob at a time against it. A dispatcher tuned against a metric nobody chose will drift towards whichever outcome is easiest to measure, and that is almost never the one that keeps customers.