Hyper-Heuristics for Automatic Configuration of Local Search-based Heuristics for the Large-Scale Vehicle Routing Problem

In this thesis we tackle one of the issues of a well-known hard-to-solve problem. The problem is the Vehicle Routing Problem (VRP), specifically in its large-scale version, also known as the Large Scale VRP (LSVRP). The LSVRP has a number of customers much larger than what traditional approaches can solve with ease, bringing extra challenges due to the amount of resources required to compute the solutions. Even when considering non-exact approaches, the scale of the problem demands reductions to the size of the solution search space. A challenge arises when doing this reduction while trying to maintain most or all of the very good solutions.

The issue we tackle is the number of manual decisions that exist in current method design. Most of the existing literature for the VRP utilises decisions that are seemingly arbitrary or based on expertise design, sometimes with little experimentation. This leads to methods that fail to generalise well for some instances or, especially, for large-scale problems. Considering the goal of minimisation problems, such as the VRP, to be reducing costs as much as possible, in several scenarios these manually designed fixed decisions often lead to a higher cost. We argue that it is possible to improve the effectiveness of the methods without manually setting up parameter values for each instance.

We approach this issue by considering the local search framework, which is arguably the most used engine in most methods for the VRP. We then consider its main design components: initialisation, improvement and acceptance. We apply several machine learning and evolutionary computation approaches as hyper-heuristics to reduce the amount of manual decisions in these three design components.

Hence, the overall goal of this thesis is to build hyper-heuristics as techniques for automatically improving and configuring local search-based methods in the context of the LSVRP.

For the initialisation step, first we consider its impact to the search process by analysing several baseline methods’ performances. We then introduce ways to utilise known and new features to predict best performing existing heuristic or build new solutions that can be easily improved. For predicting, we utilise several machine learning techniques to validate the results independently. The results show that cost is not the main feature in an initial solution. We show that some other characteristics, such as the compactness or width of a solution, have a stronger correlation than cost, leading to faster or better improvement phases.

This thesis also develops three evolutionary hyper-heuristic methods to automate the improvement phase. We consider new chromosomes incorporating pruning strategies that evolve to automatically design a heuristic configuration. These strategies minimise the amount of manual decisions leading to more generalisable methods. The results show that the improvement phase can be positively affected when automatically optimised, often outranking the manually designed methodologies.

We also consider an adaptive heuristic strategy which improves the efficiency of the local search. We apply this stochastic online approach to a robust framework, increasing its effectiveness due to the extra efficiency. Among the results, we observe a significant increase in the number of iterations given the same time-frame. We also observe a significant cost reduction for most instances considered, especially very-large cases. The proposed strategy also works independently of the instance, increasing the framework’s generality.

The fourth and final contribution regards how to predict which acceptance criteria can be used to escape local optima more effectively. We utilise machine learning and evolutionary computation to make such predictions by considering the same robust local search-based framework. The problem was modelled as both classification and regression tasks. The latter was added in an attempt to avoid bias on the labelled data. However, the results show that this task is difficult to correlate and predict. We are still able to find success for several cases, improving the quality in a number of scenarios.

In summary, this thesis develops strategies and methods that can be used in combination with existing and new local search-based methods to solve the LSVRP. The developed techniques have shown ability to reduce the search space effectively and improve the efficiency of the considered approaches for several cases, whilst minimising manual decisions in method design.