The Vehicle Routing Problem

In 2010 / 2011 I completed my D. Phil in Computer Science with this thesis. The abstract is below; do email me if you have an interest in any of this work.

Abstract

Logistical challenges abound in many fields; good solutions are not so abundant, and so are of both commercial and theoretical interest. The subset of routing problems has received particular attention, be- ginning with the infamous Travelling Salesman Problem and growing to encompass a range of different vehicle routing problems. Currently those solutions which are empirically superior have less sound theoret- ical underpinnings, and this work reflects that division. In chapter 2 I address fundamental questions about how empirical data can be used to assess algorithms’ quality, with respect to the celebrated No Free Lunch theorems. I give some new proofs of the existing theorems and unify their assumptions, and then extend current understanding to describe situations where they do not apply. In conclusion I argue that empiri- cism cannot be sufficient to settle the debate, and so a more principled approach is required. In chapter 4 I extend the scope of one such principled study of Local Search techniques, showing how some common search neighbourhoods for vehicle routing have desirable properties, and, for the first time, conducting an assay of how well these properties predict the quality of the optimisation. The results confirm my theoret- ical claims, but show problems with the use of the correlation coefficient as a performance indicator. In chapter 6 I present an amended version of Clarke and Wright’s savings heuristic which equals or exceeds several other techniques in performance and demonstrates the value of randomisation in search explained in chapter 2. Finally in chapter 7 I give some new deductive results about a distance constrained routing problem, including lower and upper bounds on the approximation ratio for metric and tree-like instances, and consider its relation to the k-tours problem.