Using Neural Combinatorial Optimisation for Solving TimeConstrained Vehicle Routing Problems

Abstract

Developing fast optimisation algorithms and decision support frameworks that can produce accurate solutions in short computation time is crucial for integrated and real-time optimisation in the 21st century. Recently, a new trend in optimisation science has emerged: Neural Combinatorial Optimisation (NCO), where researchers apply generative Artificial Intelligence (AI) models to combinatorial problems. This paper presents an end-to-end NCO model designed to address the Vehicle Routing Problem (VRP) with time constraints and a finite vehicle fleet. The NCO model developed in this study incorporates and extends various state-of-the-art frameworks and algorithms, utilising Reinforcement Learning (RL) approach to train the attention-based encoder-decoder model. We validate our approach by comparing its constructed solutions with state-of-the-art VRP heuristics, demonstrating its performance and scalability to larger problem instances. This study highlights the ability of the NCO model to generalise, even to instances with unknown customer distributions and varying problem sizes. Our findings indicate that NCO offers promising prospects for solving complex, multiobjective optimisation problems in transport logistics, offering an effective solution strategy for solving highly complex sequential decision problems.