In June 2021, Chang Gao's graduation project "Research on dynamic scheduling and dispatching algorithm of online car-hailing based on model predictive control" was awarded as the Excellent thesis of Beijing and the Excellent thesis of Tsinghua University.

Abstract: 

In recent years, the emergence and development of online car hailing platform has greatly changed people's travel mode. The matching of supply and demand directly affects the travel experience of users and the income of online car hailing platform. The purpose of this study is to propose a scheduling and dispatching algorithm to ensure the user travel experience and improve the total order matching amount. The amount of order matching depends on the number of supply and demand in each region. In this study, the future spatial distribution of supply is affected by order screening according to the destination and empty routing, to improve the amount of order matching.

Based on the framework of model predictive control (MPC) method, this paper designs a two-layer "Allocation layer-Execution layer" framework. The allocation layer combines online prediction and online optimization. According to the prediction of supply and demand in the future, the order matching and empty routing strategy are formulated, which are transmitted to the execution layer as control signals, affecting each supply and demand matching process. We design the experimental scenarios and two groups of supply and demand data for simulation experiments We compare the results with the existing algorithms’ results. It shows that when supply and demand have spatiotemporal imbalance, the order matching amount will be significantly improved by the scheduling and dispatching algorithm we proposed. The effectiveness of the algorithm is further verified by the true supply and demand data. Compared with the existing work, the innovation of this paper is to propose an online order dispatch and empty routing algorithm with strong interpretability, while considering the distribution of future supply and demand. We also analyze the real supply and demand data to verify the effectiveness of the algorithm in the actual scene.