A note on solving DiDi's driver-order matching problem

作     者：Liu, Yanchao 

作者机构：Wayne State Univ Dept Ind & Syst Engn 4815 4th StRm 2169 Detroit MI 48202 USA 

出 版 物：《OPTIMIZATION LETTERS》 (最优化通信)

年 卷 期：2021年第15卷第1期

页      面：109-125页

核心收录：

学科分类：02[经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0201[经济学-理论经济学] 020101[经济学-政治经济学] 0701[理学-数学] 

基　　金：Carnegie Mellon University  CMU 

主　　题：Combinatorial optimization Submodular welfare problem Mixed integer nonlinear programming Transportation applications 

摘      要：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.