Hyper-heuristics for two complex vehicle routing problems: the urban transit routing problem, and a delivery and installation problem

Hyper-heuristics have emerged as general purpose search techniques that explore the space of low-level heuristics to improve a given solution under an iterative framework. They were introduced to raise the level of generality of search techniques representing self-configuring and automated reusable heuristic approaches for solving combinatorial problems. There are two classes of hyper-heuristics identified in the literatire: generation and selection hyper-heuristics. In this thesis, we focus on the class of selection hyperheuristics and their efficient design and application on complex routing problems. We specifically focus on two routing problems: the Urban Transit Network design Problem (UTRP), and a rich vehicle routing problem for the delivery and installation of equipment which was the subject of the VeRoLog solver challenge 2019. The urban transit routing problem (UTRP) aims to find efficient travelling routes for vehicles in public transportation systems. It is one of the most significant problems faced by transit planners and city authorities throughout the world. This problem belongs to the class of combinatorial problems whose optimal solution is hard to find with the complexity that arises from the large search space, and the multiple constraints imposed in constructing the solution. Furthermore, realistic benchmark data sets are lacking, making it difficult for researchers to compare their problem solving techniques with those of other researchers. We evaluate and compare the performance of a set of selection hyperheuristics on the UTRP, with the goal of minimising the passengers’ travel time and the operators’ costs. Each selection hyper-heuristic is empirically tested on a set of known benchmark instances and statistically compared against all the other hyper-heuristics to determine the best approach. A sequence-based selection method utilising a hidden markov model achieved the best performance between the tested selection methods, and better solutions than the current known best solutions are achieved on benchmark instances. Then, we propose a hyper-heuristic algorithm specifically designed to solve the UTRP with defined terminal nodes that determine the start and end points of bus journeys. The algorithm is applied to a novel set of benchmark instances with real world size and characteristics representing the extended urban area of Nottingham city. We compare the hyper-heuristic performance on the data set with the NSGAII algorithm and real world bus routes, and prove that better solutions are found by hyper-heuristics. Due to the clear gap in research between the application of optimisation algorithms in public routes network optimisation and the real world planning processes, we implemented a hyper-heuristic algorithm that interactively work with interface procedures to optimise the public transport lines in Visum transportation modelling software. We adopt Selection Hyper-heuristics for two optimisation problems and the optimisation objectives include the passengers’ average travel time and operators’ costs. The results demonstrate the successful implementation of the applied optimisation methods for multi-modal public transport networks. Finally we introduce a population based hyperheuristic algorithm and apply it on a complex vehicle routing problem consisting of two stages: a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) for the delivery of equipment, and the Service Technician Routing and Scheduling Problem (STRSP) for the installation of the delivered equipment. This problem was the subject of the VeRoLog solver challenge 2019. We apply the hyper-heuristic population-based algorithm on a small and large size data sets, and show that our approach performed better in terms of results and run time on small instances compared to the results of mathematical model implemented for this problem. We perform analysis of the new proposed algorithm and show that it finds better quality solutions compared to its constituent selection hyper-heuristics when applied individually. Finally we conclude the thesis with a summary of the work and future plans