Deep Ant Colony Optimization for Electric Pickup and Delivery Problem
摘要
Efficient routing is a fundamental challenge in Electric Vehicle Routing Problems (EVRPs), where service timeliness, cost minimization, and energy efficiency are critical performance factors. Ant Colony Optimization (ACO), a widely used metaheuristic for solving Combinatorial Optimization Problems (COPs), has shown strong performance but often relies on manually designed, problem-specific heuristics that require significant domain expertise. This paper focuses on the Electric Pickup and Delivery Problem (EPDP), a variant of the Pickup and Delivery Problem (PDP) that incorporates constraints such as limited battery capacity and charging station availability. We propose DeepACO, a neural-enhanced ACO framework that integrates deep reinforcement learning to automatically learn effective heuristic measures for EPDP. By combining the adaptive learning capabilities of neural networks with the solution construction mechanisms of ACO, DeepACO dynamically generates energy-efficient routes while accounting for operational constraints like battery levels and strategic recharging. Experimental results demonstrate that DeepACO consistently outperforms traditional ACO methods in terms of feasibility, energy efficiency, and overall solution quality. Our code is publicly available at https://github.com/nhantrnh/EPDP-DeepACO .