Transforming Energy-Efficient Routes: Deep Reinforcement Learning for Electric Vehicle Routing Optimization

By Dr Silpaja Chandrasekar, PhDReviewed by Susha Cheriyedath, M.Sc.Aug 13 2023

In an article published in the journal Applied Energy, researchers explored a novel approach using deep reinforcement learning (DRL) to find energy-optimal routes for electric logistic vehicles. Focusing on reducing operating expenses, the study tackled an Energy-Minimization Electric Vehicle Routing Problem (EM-EVRP). This approach incorporated aspects such as vehicle dynamics, road features, and charging losses. Utilizing a transformer-based DRL technique, the researchers adopted a policy network design akin to the structure of Transformers. This methodology surpassed existing methods in both EM-EVRP and the conventional Distance Minimization Electric Vehicle Routing Problem (DM-EVRP), resulting in substantial cost reduction within the formulated EM-EVRP context.

Background

Recently, electric vehicles (EVs) have gained momentum in urban transportation and logistics owing to their environmental benefits and reduced operational expenses. Governments globally endorsed the shift from conventional diesel-powered vehicles to electric ones for urban freight transport. Additionally, self-driving delivery vehicles surged in popularity, suggesting a future where autonomous green vehicles dominate urban delivery operations.

To optimize the cost-efficiency of electric fleets, meticulous planning of delivery routes became imperative, often known as the EVRP. It involves capacitated EV fleets departing from a designated depot, catering to customers with specific time restrictions, and accounting for battery recharging. The central aim was to determine the most economical routes while respecting all constraints.

Related work

The EVRP presents challenges stemming from constraints like limited driving range, a nonlinear energy consumption model, and complex time windows, further compounded by real-world road data integration. These complexities, coupled with combinatorial aspects, the trade-off between distance and energy, stochastic factors, and multi-objective optimization, highlight the intricacy of the problem. Prior research has explored heuristic algorithms and learning-based approaches, particularly reinforcement learning, applied to related problems. However, the unique EVRP constraints demand novel strategies that effectively balance energy efficiency and routing dynamics while accommodating these challenges.

Addressing the challenges posed by EVRP's constraints and nonlinearities is no small task, as it necessitates finding optimal solutions within reasonable time frames. Traditional exact algorithms like branch-and-bound prove effective for small-scale problems but falter in complexity for larger instances. To tackle these challenges, many methods have used heuristic algorithms, although their suboptimality and limited applicability persist.

The emergence of artificial intelligence and machine learning has brought learning-based approaches, with past studies focusing on simpler combinatorial optimization problems like the traveling salesman problem (TSP). However, some of these studies have turned to reinforcement learning (RL) to address more extensive problems in the Vehicle Routing Problem (VRP).

Proposed method

The present paper introduced the formulation of EM-EVRP, which encompassed the definition of the directed graph and routing-related constraints. Additionally, a comprehensive energy consumption model for EVs is presented, considering factors such as vehicle dynamics, potential energy variations, and battery efficiency. Finally, the optimization problems for both EM-EVRP and DM-EVRP are outlined.

The policy within the DRL framework is structured using a novel transformer-based deep neural network, featuring attention mechanisms for both encoding and decoding tasks. Notably, a feature embedding module is incorporated to capture the nuanced aspects of the EVRP, thereby enhancing contextual awareness. The training of the policy network within this framework utilizes the policy gradient method.

For a specific instance of the EM-EVRP, the encoder absorbs relevant information from the graph. Subsequently, the decoder constructs EV routes step by step, informed by the encoded information from the encoder and the insights extracted from the feature capture module. Critically, the parameters of the policy network are updated iteratively based on rewards derived from both the policy network and a baseline network. This collaborative evaluation mechanism ensures a responsive and adaptable learning process.

The DRL approach integrates a transformer-based neural network, the policy gradient method, and a feature embedding module. This fusion equips the approach to effectively address the complexities of the EM-EVRP, enabling the determination of energy-efficient routes for electric vehicle fleets while accommodating the diverse constraints and challenges of the problem.

Experimental results and analysis

The study comprehensively compares the proposed transformer-based DRL approach with state-of-the-art methods, encompassing exact algorithms, enhanced ant colony algorithms (ACO), Adaptive large neighborhood search algorithms (ALNS), and DRL with a general attention model (AM). The experimental setup involves generating EVRP cases using specific methods, varying problem scales, and employing different decoding strategies during testing. DRL (12800) emerges as superior in cost-effectiveness and computational efficiency. Additionally, assessments on adapted Capacitated Vehicle Routing Problem Library (CVRPLib) instances and the contrast between EM-EVRP and DM-EVRP highlight the robustness and energy efficiency of the proposed DRL method. The analysis of model generalization underscores its adaptability across varying problem scales.

Conclusion

Overall, this study presented a DRL approach that employed a transformer-based policy to optimize energy-efficient routes for EV fleets. Initially, an intricate EV energy consumption model was proposed, encompassing factors such as vehicle mass, speed, and road gradient. Subsequently, a DRL framework was established, featuring a refined transformer-based policy network composed of an encoder, a feature embedding module, and a decoder. The embedded feature module incorporated EV state and routing features for enhanced contextual awareness.

Extensive numerical experiments were conducted, demonstrating the superior effectiveness of the proposed DRL method over both existing learning-based and traditional approaches, showcasing its robust generalization capabilities. Furthermore, the formulated EM-EVRP exhibited significant energy consumption reduction compared to regular DM-EVRP scenarios.