Aarhus University Seal / Aarhus Universitets segl

Solving the covering tour problem using route length approximations

Mikkel Nørgaard
Final Examination for the Master's degree
Wednesday, 26 June, 2019, at 10:00-11:00, in Aud. D2 (1531-119)
In this Master’s Thesis heuristic solution procedures for the Covering Tour Problem are studied. The heuristics use route length approximations to determine the nodes that should be in the solution and then a Travelling Salesman Problem is solved to obtain the best route among those nodes. I present a method called "CA-method" that uses a cost allocation scheme to determine the cost to take each node on the tour. I present a regression method that generates problems similar to the problem that is currently solved in order to determine regression parameters for characteristic tour components, which are then used to estimate the costs to take each node on the tour. I also present a method called "RLA-method" that uses route length approximations to the Travelling Salesman Problem to determine the nodes that should be on the tour. I also propose a method called ImproveCTP which is designed to improve a feasible solution. Computations are made to find the best of the proposed methods and to compare them against a method known from the literature. In my computational study, I find that the two methods "CA-method" and "RLA-method" I propose can compete with the Minimal-Distance Maximal-Covering method previously proposed to solve the Covering Tour Problem. I also find that the ImproveCTP performs well and improves solutions obtained by the other methods proposed when the problems is of a certain size.
Contact person: Andreas Klose