Source-linked AI summary
A Deep Value-network Based Approach for Multi-Driver Order Dispatching
Xiaocheng Tang, Zhiwei Qin, Fan Zhang, Zhaodong Wang, Zhe Xu, Yintai Ma, Hongtu Zhu, Jieping Ye
TL;DR
Ride-dispatching requires policies that account for spatial and temporal effects while improving transportation efficiency. The paper proposes an SMDP-based deep reinforcement-learning system with CVNet and Lipschitz regularization, and evaluates it in simulations and DiDi’s online platform. CVNet improves driver-income and user-experience metrics, with further gains from transfer learning across cities.
Problem
Ride-dispatching policies must capture spatial and temporal dynamics and address instability when neural networks replace tabular value approximators.
Method
The paper combines an SMDP formulation, Cerebellar Value Networks with distributed state representations, Lipschitz-regularized policy evaluation, and transfer learning for multi-city dispatching.
Results
CVNet consistently outperforms other dispatching methods in real-data simulations and improves total driver income, order answer rate, and order finish rate by 0.5%–2% over the production baseline in online tests.
Takeaways & Limitations
Transfer learning, especially CFPT, shifts the trade-off between total driver income and pickup distance upward across cities.
Takeaways & Limitations
The current approach separates learning and planning rather than combining them end to end.
Abstract
from arXiv · showhide
Recent works on ride-sharing order dispatching have highlighted the importance of taking into account both the spatial and temporal dynamics in the dispatching process for improving the transportation system efficiency. At the same time, deep reinforcement learning has advanced to the point where it achieves superhuman performance in a number of fields. In this work, we propose a deep reinforcement learning based solution for order dispatching and we conduct large scale online A/B tests on DiDi's ride-dispatching platform to show that the proposed method achieves significant improvement on both total driver income and user experience related metrics. In particular, we model the ride dispatching problem as a Semi Markov Decision Process to account for the temporal aspect of the dispatching actions. To improve the stability of the value iteration with nonlinear function approximators like neural networks, we propose Cerebellar Value Networks (CVNet) with a novel distributed state representation layer. We further derive a regularized policy evaluation scheme for CVNet that penalizes large Lipschitz constant of the value network for additional robustness against adversarial perturbation and noises. Finally, we adapt various transfer learning methods to CVNet for increased learning adaptability and efficiency across multiple cities. We conduct extensive offline simulations based on real dispatching data as well as online AB tests through the DiDi's platform. Results show that CVNet consistently outperforms other recently proposed dispatching methods. We finally show that the performance can be further improved through the efficient use of transfer learning.
1 INTRODUCTION
The paper frames ride-dispatching as a long-term, multi-driver decision problem whose policy must capture spatial and temporal effects. It proposes a deep reinforcement-learning approach using an SMDP formulation, CVNet, robustness regularization, and practical training and deployment techniques.
- Ride-dispatching must assign available drivers to nearby passengers while accounting for spatial extent and temporal dynamics that affect future driver distribution.
- Earlier approaches either ignored global spatiotemporal optimality or used tabular values that could not generalize beyond historical data or respond in real time to changing conditions.
- The proposed framework models dispatching as an SMDP because assignments trigger temporally extended driver transitions across different trip durations.
- CVNet extends CMAC with concatenated tile-embedding vectors, providing adjustable representation capacity and built-in robustness to small perturbations within tile interiors.
- The system addresses production issues through context randomization, a distilled spatiotemporal CVNet for real-time temporal-difference computation, and evaluation in simulation and DiDi’s production system.
2 A SEMI-MDP FORMULATION
The dispatching environment is modeled as an SMDP in which drivers choose options that produce transitions, rewards, and state changes over variable durations. This formulation supports value evaluation with duration-aware discounted rewards and distinguishes dispatching from standard one-step MDP updates.
- An SMDP augments a Markov decision process with temporally extended actions, called options, whose durations can span multiple time steps.
- A dispatching state contains the driver’s geographic status, raw real-world timestamp, and contextual features describing dynamic supply-demand conditions and static information.
- An option moves a driver to a future spatiotemporal status through a trip assignment or idle movement, with duration k_t that may exceed one.
- Trip options produce total fees, whereas idle movements produce zero reward; discounted rewards distribute the option’s reward sequence across its duration.
- The value function estimates expected cumulative reward under a policy from historical driver trajectories, and its Bellman updates account for variable option horizons.
3 DISPATCHING POLICY EVALUATION WITH NEURAL NETWORKS
This section develops a neural value-function approach for policy evaluation, combining cerebellar state embeddings with Lipschitz regularization and context-randomized training. The resulting network is trained from historical trajectories using a stabilized value-update procedure.
- Cerebellar Embedding: Cerebellar embedding combines multiple state-space quantizations with a sparse activation vector and dense embedding memory to produce a distributed representation.Each quantization activates a mapped memory entry, and the resulting vector contains at most n non-zero entries when n ≪ A.
- Cerebellar Embedding: The cerebellar embedding extends CMAC by associating overlapping tiles with embedding vectors, providing built-in generalization for value approximation.The method uses a wide CMAC-based architecture with embedding vectors linked to quantized regions of the state space.
- Robustness in Value Network: The value network is regularized through its global Lipschitz constant to bound sensitivity to input changes and improve robustness against perturbations.The network’s Lipschitz bound is controlled by regularizing the constants of the cerebellar embedding and multilayer perceptron layers.
- Policy Evaluation: Historical driver trajectories are converted into state, reward, and next-state transitions for neural approximation of the unknown dispatching policy’s value function.Training uses a main value network and a periodically synchronized target network in a Double-DQN structure.
- Policy Evaluation: Context randomization augments historical trajectories with contextual features retrieved over hierarchical time ranges rather than matched only at exact spatiotemporal states.The procedure addresses high contextual variance and scheduling bias in production logs while building temporal invariance into training.
4 PLANNING WITH MULTI-DRIVER DISPATCHING
This section extends value-based evaluation to real-time multi-driver planning by solving a constrained matching problem with value-derived utilities. It also addresses unavailable destination-time features through a distilled value network.
- Multi-Driver Matching: Real-time dispatching assigns orders to drivers by maximizing pairwise utility scores subject to feasibility constraints that prevent conflicting assignments.The matching objective can be solved using standard algorithms such as the Hungarian Method.
- Multi-Driver Matching: The utility score for a driver-order pair is computed from the Temporal Difference error between the driver’s current state and the order’s destination state.This connects the learned state-value function to online combinatorial assignment.
- Policy Evaluation: Training uses historical trajectories, hierarchical contextual queries, mini-batches, and gradient descent on a value loss augmented with a Lipschitz regularization penalty.The procedure initializes main and target networks, samples transitions and contextual features, then updates the network parameters iteratively.
- Dispatch Objective: The dispatch objective combines long-term driver income with an additional user-experience term weighted by Ω ≥ 0.The user-experience component characterizes experience for both drivers and passengers.
- Real-Time Planning: Because destination dynamic features are unavailable before trip completion, a separate value function marginalizes those features and is trained by knowledge distillation from the original network.The distilled network shares state-representation layers with the teacher while using separate multilayer perceptron and output layers.
5 MULTI-CITY TRANSFER
The paper treats dispatching across cities as a multi-task learning problem and uses correlated-feature progressive transfer to scale CVNet across regional tasks.
- Multi-City Transfer: CFPT transfers adaptive contextual and temporal features across cities while allowing target-city training to focus on nonadaptive absolute GPS locations.This parallel progressive structure seeks to maximize transferable knowledge without forcing city-specific spatial features to transfer.
- Multi-City Transfer: The paper avoids both a single all-city agent that may create deployment and serving concerns and independent task training that is suboptimal.Each city is treated as a regional task within the multi-task learning formulation.
6 EXPERIMENTS
Experiments evaluate CVNet’s temporal behavior, robustness, value generalization, dispatching performance, online impact, and transfer across cities using real-data simulations and DiDi A/B tests.
- Characteristics of CVNet: CVNet values decrease toward zero near day’s end, while larger γ produces higher average values and γ=0.8 temporarily raises values during morning rush hour.Small γ favors short-horizon earnings; large γ encourages longer-term behavior.
- Characteristics of CVNet: Lipschitz regularization controls the global Lipschitz bound, which explodes during training when λ=0; weight corruption tests robustness to parameter noise.The experiments train CVNet on City A without contextual features and examine robustness under different regularization settings.
- Characteristics of CVNet: CVNet produces compact value distributions with fewer outliers than DQN, including on unseen locations requiring generalization.DQN shows large variance and incorrect negative values, whereas cerebellar embeddings collaboratively learn tile representations.
- Results on Simulations With Real Data: CVNet improves simulated Total Driver Income over the baseline by 1% to 15%, with average improvements across days ranging from 3% to 8%.The comparison averages three days spanning weekdays and weekends across cities; CVNet is consistently advantageous over the other methods.
- Results on the Real World: Online A/B tests show consistent 0.5%−2% improvements over the production baseline in total driver income, order answer rate, and order finish rate across three cities.The reported answer- and finish-rate changes indicate improved driver distribution and fewer cancellations after answered orders.
- Results on Transfer Across Cities: Transfer learning, especially CFPT, shifts the TDI–pickup-distance trade-off upward, enabling higher TDI improvement while maintaining short pickup distance.Simulations transfer CVNet from City A to Cities B, C, and D under five pickup-distance penalty levels.
7 CONCLUSIONS AND FUTURE WORK
CVNet provides a deep reinforcement learning solution for order dispatching that improves driver income and user-experience metrics in DiDi evaluations. Transfer learning further improves results and supports scaling across cities, while end-to-end learning and other transportation applications remain future work.
- CVNet improves total driver income and user-experience-related metrics in large-scale online A/B tests on DiDi’s ride-dispatching platform.
- The method combines an SMDP formulation, Cerebellar Value Networks, and Lipschitz regularization to address temporal actions, stability, and robustness.
- Extensive simulations and online A/B tests show that CVNet outperforms the other dispatching policies evaluated.
- Transfer learning further improves prior results and facilitates scaling CVNet across cities.
- Future work includes combining the separate learning and planning steps into end-to-end learning and extending CVNet to fleet management.
A TRAINING CONFIGURATION
Training uses a cerebellar embedding followed by fully connected layers, target-network synchronization, and Adam optimization with Lipschitz regularization. Discount-factor experiments show a trade-off between value scale, convergence speed, and future-reward lookahead.
- The training configuration uses three cerebellar quantization functions, memory size 20000, embedding dimension 50, and fully connected hidden units [32, 128, 32].
- The target network is updated every 100K steps, with batch size 32 and 20 training epochs over the dataset.
- Adam optimization uses a constant step size 3e−4, while Lipschitz regularization uses λ=1e−4.
- Smaller discount factors produce smaller converged average values and faster convergence during training.
- A smaller γ discounts future rewards more aggressively, shortening the lookahead horizon and making training easier.
- The experiments use γ=0.92, selected through randomized search on out-of-sample simulations.
B TRANSFER NETWORK CONFIGURATION
The transfer configurations adapt CVNet across cities using finetuning, progressive networks, and correlated feature progressive transfer. These methods differ in whether they reuse weights directly, through lateral connections, or through feature-specific data tunnels.
- The implemented cross-city transfer methods are finetuning, progressive networks, and correlated feature progressive transfer.
- Finetuning: Finetuning initializes the target city’s green blocks with trained source-city weights and continues training on the new dataset.
- Progressive Network: Progressive networks use lateral connections to leverage trained source-city weights while retaining the source parallel network’s trained green blocks.
- Progressive Network: In the progressive-network connection, h_i^(t) and h_i^(s) are linked through a lateral connection weight matrix, with f(·) as the activation function.
- CFPT: CFPT separates data tunnels during source-city training, with green blocks processing correlated cross-city features suitable for transfer.
- CFPT: After source-city training, CFPT copies the green blocks to a same-structure target network while retaining the lateral connection.
C ORDER DISPATCHING SIMULATOR
The study evaluates dispatching policies with a realistic simulator initialized from historical driver and order states. The simulator then determines driver states through assigned-order fulfillment or modeled random walking and operation.
- The order dispatching simulator is designed to provide an intuitive assessment of different dispatching policies.
- The simulator’s composition and workflow are presented in Figure 11.
- The simulator is initialized using drivers’ status and order information from particular historical dates.
- After initialization, the simulator determines driver states through policy-assigned orders or modeled random walking followed by offline or online operation.