A Deep Reinforcement Learning-Based Adaptive Large Neighborhood Search for Capacitated Electric Vehicle Routing Problems

作者：Chao Wang, Mengmeng Cao, Hao Jiang, Xiaoshu Xiang, Xingyi Zhang · 发表于：IEEE Transactions on Emerging Topics in Computational Intelligence · 年份：2025 · DOI：10.1109/tetci.2024.3444698 · 被引用次数：23 · 研究领域：Computer Science

The Capacitated Electric Vehicle Routing Problem (CEVRP) poses a novel challenge within the field of vehicle routing optimization, as it requires consideration of both customer service requirements and electric vehicle recharging schedules. In addressing the CEVRP, Adaptive Large Neighborhood Search (ALNS) has garnered widespread acclaim due to its remarkable adaptability and versatility. However, the original ALNS, using a weight-based scoring method, relies solely on the past performances of operators to determine their weights, thereby failing to capture crucial information about the ongoing search process. Moreover, it often employs a fixed single charging strategy for the CEVRP, neglecting the potential impact of alternative charging strategies on solution improvement. Therefore, this study treats the selection of operators as a Markov Decision Process and introduces a novel approach based on Deep Reinforcement Learning (DRL) for operator selection. This approach enables adaptive selection of both destroy and repair operators, alongside charging strategies, based on the current state of the search process. More specifically, a state extraction method is devised to extract features not only from the problem itself but also from the solutions generated during the iterative process. Additionally, a novel reward function is designed to guide the DRL network in selecting an appropriate operator portfolio for the CEVRP. Experimental results demonstrate that the proposed algori...