Driver‑Passenger Matching in Didi’s Ride‑Hailing Market: Algorithms and Techniques

This article provides a comprehensive overview of the matching problems that arise in Didi’s ride‑hailing transaction market and the technical solutions developed to address them.

Core matching problem : When a passenger places an order, the platform must decide which online driver(s) should receive the request. The simplest case is a one‑to‑one (single passenger–single driver) match, but real‑world scenarios involve many‑to‑many, one‑to‑many, and dynamic matching problems.

Matching techniques covered :

Greedy nearest‑driver assignment (simple, fast, but may lead to poor outcomes under heavy load).

Maximum‑weight bipartite matching using the Kuhn‑Munkres (KM) algorithm (O(n³) time).

Stable matching (Gale‑Shapley) to avoid "regret" pairs; also known as the stable marriage problem.

Extension to one‑to‑many matching (Hospitals/Residents problem) for semi‑assignment and car‑pooling.

Dynamic bipartite matching that accounts for time‑varying orders and driver availability.

Optimal stopping (Secretary problem) for simultaneous driver‑passenger decisions.

Reinforcement‑learning‑based dynamic matching, treating the environment as a Markov decision process.

Vehicle routing (PDP/VRP) and time‑window constraints for route planning.

Queueing theory (M/M/1) to model passenger‑queue experience during supply shortages.

Simulation and digital‑twin platforms for offline strategy evaluation and competitive‑ratio analysis.

Statistical validation of queueing assumptions :

【北京某日排队入队间隔的假设检验结果】
原假设：队列入队间隔分布与负指数分布一致
检验结果：
Kolmogorov‑Smirnov检验：pvalue=0.45 >= 0.05
Wilcoxon检验：pvalue=0.41 >= 0.05
Kruskal‑Wallis检验：pvalue=0.09 >= 0.05
结论：原假设成立，即【队列入队间隔分布服从负指数分布】

The article also discusses how Didi integrates machine‑learning predictions, driver‑passenger preference modeling (including incomplete and fuzzy preferences), and multi‑objective optimization (fairness, efficiency, robustness) into its matching engine.

Finally, the paper outlines future directions such as extending stable matching to multi‑objective settings, improving competitive ratios via online algorithms, and leveraging high‑fidelity digital twins for large‑scale policy testing.

References include seminal works on market design (Roth & Shapley), online matching, reinforcement learning for logistics, and recent surveys on dynamic vehicle routing.