Long-Distance Charge-Route Planning for Electric Vehicles: A Multi-Solution Approach

The limited range of electric vehicles (EVs) necessitates frequent charging during long-distance travel, posing significant challenges in routing. Unlike traditional vehicles, EVs face additional constraints such as extended charging times and potential queues at charging stations, which can substantially increase travel time. Addressing these complexities is critical for enhancing travel efficiency and user experience. This paper presents MultiCRPlanner, a novel system that provides multiple optimized solutions tailored to real-world scenarios. Specifically, we introduce a comprehensive long-distance EV charge-route planning (LD-CRP) model, which is built upon a bi-layer network to balance practical details with routing efficiency. To enable users to flexibly adjust and select the most suitable plan based on their specific requirements, we develop a clustering-based multi-solution genetic algorithm. This clustering scheme enables the algorithm to identify a set of solutions with both high quality and diversity. Additionally, our algorithm is equipped with a few tailored crossover and mutation operators to enhance problem-solving efficiency. We validate the effectiveness of MultiCRPlanner through experiments on two real-world datasets, demonstrating its superiority over existing algorithms.