Inside Didi’s Dispatch Engine: From Simple Matching to AI‑Powered Ride‑Hailing

1. Problem Definition

Order assignment (dispatch) is the process of allocating a passenger’s request to an online driver. The naïve rule "assign to the nearest driver" accounts for 70‑80 % of assignments, but a purely greedy strategy ignores future orders, driver arrivals, and spatial constraints, leading to sub‑optimal system‑wide performance.

2. Core Challenges

Temporal dynamics – orders and drivers appear continuously, requiring the algorithm to reason about future supply and demand.

Spatial constraints – drivers may be unavailable due to network failures, service restrictions, or region‑specific rules.

Business rules – e.g., fast‑car drivers cannot take premium orders, drivers must avoid restricted zones, drivers with a preset destination are filtered from unrelated requests, each order is sent to a driver only once, etc.

Scalability – Didi processes >30 million ride requests per day, with peak loads >60 000 requests per minute; the system must match hundreds to thousands of drivers every two seconds.

3. Algorithmic Approaches

3.1 Batch Matching (Delayed Centralized Dispatch)

Orders and driver statuses are collected over a short time window (typically a few seconds). The problem is then formulated as a bipartite‑graph matching:

Given:
  O = {o1, o2, …, oN}   // pending orders
  D = {d1, d2, …, dM}   // available drivers
  c(oi, dj) = navigation distance (or travel time) from driver dj to order oi
Goal:
  Find a matching M ⊆ O × D that minimizes Σ_{(oi,dj)∈M} c(oi,dj)
  subject to business‑rule constraints.

The optimal matching can be obtained with Hungarian algorithm, min‑cost flow, or specialized linear‑programming solvers. By postponing the decision, the algorithm avoids the myopic “first‑come‑first‑served” pitfall and reduces total passenger waiting time.

3.2 Demand‑Prediction Based Matching

Spatio‑temporal models predict future order density and driver supply for each region (e.g., using deep‑learning time‑series or graph neural networks). The predicted demand D̂(t, r) and supply Ŝ(t, r) are used to bias the objective:

Adjusted cost c'(oi,dj) = c(oi,dj) – λ·(predicted supply – predicted demand)_{region(oi)}

λ controls the trade‑off between immediate distance and long‑term balance. Prediction uncertainty limits reliability, so the system still limits the batching window to a few seconds to meet user‑response‑time expectations.

3.3 Chain Dispatch (Sequential Dispatch)

When a driver is about to finish a trip, the algorithm checks whether the driver’s destination is close to a newly arrived order. If the distance between the driver’s expected drop‑off point and the order’s pickup location is below a threshold τ, the order is assigned immediately, compressing response time and reducing dead‑head mileage.

3.4 Learning‑Based Enhancements

Spatio‑temporal prediction: Deep neural networks (e.g., ConvLSTM, GraphSAGE) forecast order arrivals and driver availability at a granularity of minutes and city blocks.

Reinforcement learning (RL): The dispatch problem is cast as a Markov Decision Process where the state includes current driver locations, pending orders, and predicted future supply. Policies are trained with policy‑gradient or Q‑learning to maximize a long‑term reward that balances passenger waiting time, driver travel distance, and platform revenue.

Simulation platform: High‑fidelity simulators replay historical trajectories and inject synthetic demand to evaluate algorithmic changes before online rollout.

4. Practical Impact

By moving from a pure greedy “nearest‑driver” dispatch to the combination of batch matching, demand‑aware biasing, chain dispatch, and learning‑based refinements, Didi achieved:

Response‑rate increase of >20 percentage points, reaching >90 % during peak periods.

Reduction of total passenger pickup time compared with per‑order greedy assignment (empirically up to 15 % improvement in peak hours).

Additional capacity of >1 million rides per day relative to the earliest dispatch version.

The system continuously processes millions of orders, matches drivers in real time, and iterates on the algorithmic pipeline to improve fairness and efficiency.