Learning to optimise routing problems using deep neural networks
Creators: name: Sultana, Nasrin
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 460210
subject: Satisfiability and optimisation
classificationCode: 461103
subject: Deep learning

description: Route optimisation problems are classic combinatorial optimisation problems. In practice, most modern industries, such as scheduling, supply chain management and transportation, require route optimisation. The route optimisation problem is to find the best solution to visit a set of locations while complying with constraints. The travelling salesman problem and vehicle routing problem are the two most prevalent examples of route optimisation problems. The travelling salesman problem is to find a tour of all cities/locations where each city is visited only once and has a minimum total distance travelled. The vehicle routing problem is to find the optimal set of routes for a fleet of vehicles. It has many variants; one example is the capacitated vehicle routing problem, which aims to find a set of routes with the minimum cost to fulfil customers' demands without violating the vehicle capacity constraints. 

Researchers have tried many ways to optimise route problems in the last few decades. Traditional approaches to tackling such complex problems include exact algorithms and heuristics. Exact algorithms are guaranteed to find optimal solutions for route problems, however, this guarantee comes at the expense of time. Meanwhile, heuristics employ problem-specific knowledge and carefully engineered approaches and parameters to find near-optimal solutions. Heuristics are effective algorithms that are often fast, but they may apply to only a specific problem. Therefore, applying current search heuristics to new problems or extending them to new instances of a similar problem is challenging. This challenge has motivated the development of learning-to-optimise-based algorithms to optimise route problems. Deep learning has been successfully extended to meta-learning, where previous solving efforts assist in learning how to optimise future optimisation instances. In recent years, learning to optimise approaches have succeeded in optimising route problems. An aim of learning to optimise is to train once and solve across a broad spectrum of route problems. Hence, this thesis focuses on developing a deep-learning-based method to effectively solve the most common route optimisation problems.

Recent developments in the learning-to-optimise field have solved route optimisation tasks. These models are often trained with supervised learning and reinforcement learning techniques. Recent supervised-learning-based approaches can solve easy route problems, e.g., the travelling salesman problem. However, various difficult travelling salesman problems need to be solved. As supervised learning techniques use previous experience to solve many real-world problems, we propose a supervised-learning-based technique to solve general travelling salesman problems.

Many works have proposed reinforcement-learning-based models with learning objectives, but such approaches do not necessarily generate better solution quality. One issue is that recent reinforcement-learning-based approaches use standard policy gradient methods to solve route problems. Standard policy gradient methods have exploration and sample complexity issues. Therefore, we propose sample-efficient exploration-based methods to optimise route problems to tackle the issue. Currently devised methods solve route problems faster, but the algorithms perform poorly in terms of solution quality. To overcome the issue of solution quality for route problems, we propose a hybrid approach. Hybrid approach inspired by operations research algorithms, which can produce better-quality solutions, combined with reinforcement-learning-based approaches, which can produce solutions faster. Our proposed approach can learn to solve route problems with less computation time (i.e. faster). To achieve both objectives, i.e. better solutions with less computation time, we have designed a method that uses a reinforcement-learning-based manager to improve the solution iteratively using local search heuristics. 

Overall, this thesis proposes deep-neural-network-based approaches to efficiently solve route optimisation problems; these approaches can be generalised over multiple applications.