A note on solving DiDi’s driver-order matching problem
A note on solving DiDi’s driver-order matching problem
复制标题
解决滴滴司机订单匹配问题的笔记
作者：
Yanchao Liu
本文研究了 DiDi 为解决驾驶员订单匹配问题而提出的组合非线性规划模型。该模型被重新表述为等效的连续非线性程序，适用于高效的商业求解器。还提出了计算下界的后向归纳过程。计算实验表明，重新表述产生的局部解越来越接近全局解，从而表明随着问题规模的增加，追求全局最优的边际效益递减。
This paper investigates the combinatorial nonlinear programming model that DiDi proposed for solving their driver-order matching problem. The model is reformulated to an equivalent continuous nonlinear program which is amenable to efficient commercial solvers. A backward induction procedure for computing the lower bound is also proposed. Computational experiments demonstrate that the local solution produced by the reformulation becomes increasingly close to the global solution, thereby suggesting a diminishing marginal benefit of pursing global optimality as the problem size increases.