A Novel Routing Solution for EV Fleets: A Real-World Case Study Leveraging Double DQNs and Graph-Structured Data to Solve the EVRPTW Problem

Abstract

The transition from Internal Combustion Engine vehicles to Electric Vehicles presents challenges for fleet managers in terms of adapting operational processes and systems. One prominent challenge is the Electric Vehicle Routing Problem, which requires careful consideration of battery monitoring, efficient route planning, charging infrastructure availability, and vehicle performance management. The goal is to alleviate range anxiety and ensure effective fleet management. In this context, we propose a Reinforcement Learning approach in conjunction with graph-based modeling to solve Electric Vehicle Routing Problem with Time Window. This paper provides a novel approach addressing the need for efficient and sustainable electric vehicle fleet management. Our aim is to minimize the distance traveled while serving customers within their time windows using the combination of Structure2vect and Double Deep Q-Network. Real-world data from a public utility fleet company in Tunisia is utilized to evaluate the proposed model, and comparisons are made with conventional benchmarking strategies and other Reinforcement Learning approaches. The results highlight the effectiveness of the proposed model achieving a reduction up to 50% in traveled distance while demonstrating enhanced computational efficiency through reduced complexity and optimized runtime. Moreover, the obtained model can be directly applied to treat the large-scale adoption of electric vehicles in fleets.

Keywords

• Deep reinforcement learning
• DDQN
• electric vehicles
• EVRPTW
• fleet
• graph structure