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

Kurzfassung

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 multiple 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. This study presents a NCO solution method for a time-constrained capacitated vehicle routing problem with finite vehicle fleet. Our method incorporates customer constraints dynamically, making it flexible and applicable across various transport logistics scenarios. The Pointer Amplifier (PAMP), 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 (POMO) protocol and trained via Proximal Policy Optimization (PPO) algorithm. The proposed framework was successfully trained and validated on medium and large instances, providing competitive, cost-efficient solutions while exhibiting robustness and generalization when compared to the 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.