Deep reinforcement learning with evolutionary algorithm-guided imitation for capacitated vehicle routing problems

The capacitated vehicle routing problem (CVRP) is a complex combinatorial optimization challenge that seeks to determine cost-effective routes for customer deliveries while adhering to specific capacity constraints. Although deep reinforcement learning (DRL) has shown promise in addressing CVRP, it often encounters issues such as slow convergence and suboptimal accuracy. This study introduces an innovative approach that enhances both convergence efficiency and solution quality by integrating DRL with imitation learning (IL), utilizing an evolutionary algorithm (EA) as an expert. The proposed methodology incorporates an attention mechanism-based neural network to effectively capture the intricate features of CVRP. It leverages IL to use EA-generated solutions as expert demonstrations, thereby guiding the DRL model toward a more efficient exploration of the solution space. The REINFORCE algorithm with baseline is employed to ensure stable and rapid training of the DRL model. Experimental results indicate that this hybrid approach significantly outperforms widely adopted baseline methods and approaches the performance levels of advanced algorithms like LKH3. Furthermore, the method demonstrates robust generalization capabilities across various CVRP instances, underscoring its potential for practical applications in diverse routing scenarios. This research contributes to the field by demonstrating how integrating EA as experts within an IL framework can effectively enhance DRL for solving CVRP.