Applications and improvements of the adaptive large neighbourhood search

Abstract

The Adaptive Large Neighbourhood Search (ALNS) is a popular metaheuristic widely recognised for efficiently solving complex combinatorial optimisation problems within reasonable computing time. The general principle behind the metaheuristic is ”destroy-and-repair”, which involves a perturbation process that iteratively deconstructs and reconstructs an initial solution to form new incumbents to explore unvisited regions of the solution space in the search for better local optima. This thesis concentrates on the implementation and enhancement of this metaheuristic, intending to further optimise its effectiveness and robustness under diverse settings and real-life scenarios.

Since its initial introduction almost two decades ago, the ALNS metaheuristic has been renowned for its effectiveness in generating good-quality solutions, particularly when addressing routing-related problems. The first direction of this thesis aims to validate this promising efficacy reported in the literature and demonstrate the advantages of the ALNS metaheuristic in tackling challenging real-life problems involving complex and dynamic decision-making processes. We begin with an in-depth analysis of the overall methodological process of the method, scrutinising the impact of the embedded heuristic components and hyper-parameter values on the general performance of the ALNS metaheuristic. Afterwards, we utilise the ALNS metaheuristic to tackle two real-life applications, where the first is a two-echelon location-routing problem that pertains to the food supply chain industry, specifically focusing on the design of a distribution network that incorporates heterogeneous vehicle types, facility and driver-based districts, and multiple commodities. A mixed-integer linear programming (MILP) formulation is proposed and solved with a two-stage decision-making heuristic involving ALNS as an improvement method. The second application arises in the home healthcare industry with integrated service team fleet size, assignment, routing and scheduling decisions under travel time, service time and customer cancellation uncertainties, referred to as the “H-SARA” problem. We model the H-SARA problem using a stochastic MILP formulation and employ Benders decomposition to tackle small to medium-sized instances. Based on the natural partition of our two-stage stochastic model, we can decompose the original problem into a routing master problem and scenario-based scheduling subproblems. In addition, we introduced an ALNS-based warm-start, several valid inequalities, and a closed-form primal formulation to accelerate the computational progress of the Benders algorithm. For larger instances, we develop a tailored two-stage decision support system built upon ALNS, which leverages the increased level of available information at each stage to construct time-sensitive decisions. The results from the computational experiments indicate that our proposed two-stage heuristic is competitive with CPLEX’s exact solution methods in terms of providing time and cost-effective decisions.

In the second part of the thesis, we focus on the mechanisms of the ALNS heuristic itself. The ALNS perturbation process is based on sequentially executing a selected pair of destroy and repair operators, each transforming one solution to another in its neighbourhood. This perturbation is governed by a Roulette Wheel mechanism that probabilistically selects operators to determine which neighbourhood of the current solution should be visited. The operator selection mechanism incorporates an adaptive layer, which tracks the historical performance of each operator and periodically adjusts its selection probability to favour the most efficient operator. However, recent studies have indicated that such an adaptive layer within the ALNS framework has limited capability to dynamically choose the best operators, despite being intentionally engineered for this purpose. We follow this up with a study of using Reinforcement Learning (RL) to improve the performance of the ALNS adaptive layer. We formulate the choice of operators as a Markov Decision Process and propose a hybrid operator selection mechanism based on Deep RL and Graph Neural Networks to enhance the performance of the classical ALNS framework. A key insight and contribution is the proposal of an RL-based operator selection process that is conditioned on the individual solution, which compared to the classical operator selector that is updated periodically by the Roulette Wheel algorithm, enables us to gain insight into the dynamic contribution of each operator in navigating the search towards promising neighbourhoods. We also discuss important considerations such as the size of the operator portfolio and the impact of the choice of operator scales. Lastly, we show that our learning-based ALNS is capable across a variety of routing-related variants with considerable instance scales. Notably, our approach can save significant time and labour costs for handcrafting problem-specific operator configurations.