Due to the limited driving range, insufficient charging facilities, and time-consuming recharging, optimizing charging routes for electric vehicles (EVs) presents unique challenges compared to conventional vehicles. The time and location of EV charging during a trip not only affect an individual EV’s travel time but also influence others, as queues may form at charging station(s). This issue is at large seen as a significant constraint for uplifting EV sales in many countries. In this study, we introduce a novel EV Route Planning problem, which involves two parts: (i) finding the fastest route with recharging for an EV routing request. We model the problem as a new graph problem and prove its NP-hardness. We propose an innovative two-phase algorithm that efficiently traverses the graph to identify the optimal charging route for each EV. (ii) We find routes with minimized travel time for an EV while strategically avoid charging stations and time to recharge at those stations which can lead to minimized travel time for upcoming EVs. For this purpose, we introduce the concept of an “influence factor” to guide heuristic decisions. Our results demonstrate that this method reduces total travel time by 50% compared to the state-of-the-art on real-world datasets, with benefits becoming more significant as the number of EVs on the road increases.

The rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential. To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP (MDVRP) where the routing decisions of vehicles from multiple depots are highly interdependent. The complexities render traditional VRP methods suboptimal and non-scalable for the MDVRP. In this paper, we propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results. The key idea is, the MDVRP can be broken down into two core spatial tasks: assigning customers to depots and optimizing the sequence of customer visits. We adopt task-decoupling approach and propose a two-stage framework that is scalable: (i) an interdependent partitioning module that embeds spatial and tour context directly into the representation space to globally match customers to depots and assign them to tours; and (ii) an independent routing module that determines the optimal visit sequence within each tour. Extensive experiments on both synthetic and real-world datasets demonstrate that our method outperforms all baselines across varying problem sizes, including the adaptations of learning-based solutions for single-depot VRP. Its adaptability and performance make it a practical and readily deployable solution for real-world logistics challenges.

Due to limited driving ranges, inadequate charging facilities, and time-consuming recharging, finding an optimal charging route for electric vehicles (EVs) differs from that of other vehicle types. The time and location of charging not only impact an individual EV's travel time but also the travel time of other EVs, due to potential queuing at charging station(s). We present a novel Electric Vehicle Route Planning problem for finding the fastest route with recharging. We model this as a graph problem and propose a novel two-phase algorithm to traverse the graph to find the best charging route for each EV. We also introduce the notion of 'influence factor' to propose heuristics to find the route with the minimum travel time for an EV that avoids recharging at the charging stations that can be better utilized by other EVs. Our approach reduces 50% of total travel time over the state-of-the-art.

While the electric vehicle (EV) industry is facing some challenges concerning its refueling, its rapid growth in popularity is increasing these difficulties. In this paper, we demonstrate the gravity of the problems that EVs may experience for charging,both now and in the near future, and show how establishing new charging stations can be challenging. We also present the challenges in optimizing the use of charging stations by EV users. Then, we envisage opportunities for the rise of alternative charging options, such as distributed generation, crowdsourced, wireless and mobile charging stations. Additionally, we explain directions on how route and charging stations' location planning can cater to optimizing the charging infrastructure.