.png){kind=icon}
.png){kind=icon}
Return
Adaptive Dynamic Programming for Multi-Driver Order Dispatching at Large-Scale
.png){kind=icon}
PRE
AI
DOI：10.1109/TCCN.2023.3327578.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Dispatching
Vehicle dynamics
Decision making
Optimization
Adaptation models
Uncertainty
Real-time systems
Order dispatching
adaptive dynamic programming
graph theory
Markov decision process
Journal
I
IF:
7
Papers:
1.5K
Citations:
5.5K
View more organizations