An End-to-End Deep Reinforcement Learning Framework for Electric Vehicle Routing Problem

Abstract

Electric vehicles (EVs) have been increasingly used in the logistics and transportation industry due to their cost-effectiveness and sustainability. However, one of the major challenges in optimizing routes for EVs is the EV routing problem (EVRP), which arises from their limited battery capacity. This article proposes a reinforcement learning (RL)-based end-to-end framework to address EVRP with different sizes. The framework includes a graph attention network (GAT)-based encoder and an attention-based decoder. In particular, an improved GAT-based encoder is employed to encrypt node and edge information from the graph-structured EVRP instances, resulting in high-dimensional node embeddings and graph embedding for downstream tasks. The decoder comprises a dual-layer attention module, which generates solutions (a sequence of input nodes) based on the global state and the embeddings from the encoder. This encoder-decoder architecture constitutes the policy network, which takes instances as input and produces solutions in an auto-regressive manner. The policy network is trained using REINFORCE with a baseline. The experiments indicate that the proposed deep RL (DRL) method demonstrates more solvability efficiency than conventional methods (exact algorithms and heuristic algorithms) and shows superior performance than other DRL-based methods.

Topics & Concepts