Pointer Amplifier for Vehicle Routing Problem: Solving Time-Constrained Vehicle Routing Problems with Finite Fleet Using End-to-End Neural Combinatorial Optimization

Abstract

Finding prompt and optimal solutions to the vehicle routing problem (VRP) is a prerequisite for efficient freight transport, seamless logistics, and sustainable mobility. This requires algorithms that can quickly produce accurate solutions in minimal computational time. Traditional optimization methods struggle with the real-world complexity of VRPs that involve various constraints and different objectives. Recently, advances in neural combinatorial optimization (NCO), which employs generative artificial intelligence to solve combinatorial problems, have demonstrated mature results with promising perspectives. We present an NCO solution method for a time-constrained capacitated VRP with finite vehicle fleet. Our method incorporates customer constraints dynamically, making it flexible and applicable across various transport logistics scenarios. The pointer amplifier, a mechanism introduced here, prioritizes urgent services during tour generation by directly rescaling attention scores in the pointer network. For capacity constraints, we apply reward function penalties with masking to exclude infeasible actions. The architecture uses an encoder-decoder following the Policy Optimization with Multiple Optima protocol and trained via the Proximal Policy Optimization algorithm. The proposed framework was successfully trained and validated for medium and large instances, providing competitive cost-efficient solutions while exhibiting robustness and generalization, compared with state-of-the-art heuristics. Finally, we provide a critical analysis of the solutions generated by NCO and discuss the challenges and opportunities of this new branch of deep learning algorithms.