Adaptive Dynamic Programming for Multi-Driver Order Dispatching at Large-Scale

Order dispatching, which involves assigning orders to demand-matched vehicles, is an underlying issue for ride-sharing services. Previous works on order dispatching are often quasi-static and myopic 1, thus performing unsatisfactorily in the ride-sharing setting. To address these challenges, recent studies attempt to augment large-scale decision optimization from a data-driven perspective. Among them, Adaptive Dynamic Programming (ADP) has exhibited its particular potential for sequential decision-making with a long-term objective under uncertainty. In this paper, we investigate order dispatching with consideration of vehicle repositioning by exploiting ADP. We first formulate the optimization problem as a Markov Decision Process (MDP), where the dispatching decision is determined by a series of agents (the decision-making entity) under the time sequence model. Then, based on the generated available trips by a graph theory-based method, an ADP-based Multi-driver Order Dispatching method (AMOD) is proposed. In particular, AMOD reconstructs the Bellman update process around the post-decision states to avoid approximating the embedded expectations explicitly. As for non-linear function approximation, it converts the value function into a linear combination by a quadratic decomposition, and estimates the decomposed value function with neural network-based parameter approximation. In addition, vehicle repositioning is performed along with each batch dispatching to balance ride supply across geographic dimensions. Extensive simulations are conducted based on real-world data. Especially, AMOD can achieve 34.6% improvement at maximum and 15.9% on average compared with other baselines, when the capacity constraint is 10.