Dynamic Electric Vehicle Routing Problem with Stochastic Requests

The dynamic electric vehicle routing problem (DEVRP) is a variant of the classical dynamic vehicle routing problem, where electric vehicles (EVs) are employed to provide on-demand logistics services. We investigate the DEVRP with stochastic requests and proactive charging decisions, where an EV must optimize its route and energy management to maximize the number of served requests while adhering to constraints on battery capacity and depot deadline. We formulate the DEVRP as a route-based Markov decision process (MDP) model and develop two complementary solution approaches: (1) a perfect-information rollout (PIR) policy based on stochastic lookahead and (2) a deep Q-learning (DQN) policy based on neural networks. Compared with conventional stochastic lookahead policies, such as rollout, the PIR policy improves the quality of reward-to-go estimation by better utilizing stochastic information, and we design two adjustable acceleration mechanisms to improve its balance between efficiency and accuracy. Although the PIR policy performs all computation online and adapts well to various scenarios, the DQN policy relies on offline training of neural networks to achieve faster online decision making. We also propose enhancement techniques to improve the performance of DQN. Through extensive numerical experiments, we demonstrate the advantages of the proposed policies in terms of solution quality and computational efficiency over multiple state-of-the-art approaches (such as value function approximation and rollout). Compared with the best-performing benchmark approaches, our proposed policies improve the decision quality by up to 5.3% while reducing the online computation time by more than half. Moreover, the merits of proactively and partially charging the EV in the DEVRP are investigated and validated. Robustness experiments further demonstrate the effectiveness of the proposed policies when demand prediction is inaccurate. Funding: This research is supported by the National Natural Science Foundation of China (NSFC) [Grant 72301109]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2025.0476 .