The construction of efficient vehicle routes is of crucial importance in modern society, for both economic and environmental reasons. This leads to a family of combinatorial optimisation problems, known collectively as Vehicle Routing Problems (VRPs). Due to their importance, VRPs have received a great deal of attention from the Operational Research and Combinatorial Optimisation communities.

This thesis, which essentially consists of four papers, makes additional contributions to this body of work. All of the papers apart from the first concentrate on Arc Routing Problems (ARPs). An ARP is a special type of VRP, in which the demands are located along edges or arcs, rather than at nodes.

The first paper is concerned with Euclidean approximation. Most VRP algorithms, whether exact or heuristic, assume that the instance is defined on a complete graph. In practice, of course, most VRPs are defined on road networks. We explore the potential of a heuristic approach for VRPs on road networks, based on the use of planar Euclidean distances to approximate real-life road distances.

The second paper addresses the use of matchings and T-joins to compute lower bounds for ARPs. For large-scale instances, the existing lower-bounding procedures consume a huge amount of both time and memory. We show how to exploit the structure of real-life road networks, to dramatically reduce the amount of computational effort without deteriorating the quality of the output.

The third paper deals with with the so-called General Routing Problem (GRP), defined by Orloff in 1974. We examine in detail a popular constructive heuristic for the GRP, due to Christofides. The heuristic can be very slow for large-scale instances. We show how to modify the heuristic so that it runs orders of magnitude more quickly, yet yields solutions that are at least as good as
before.

In the last paper, which is also the longest, we tackle the real-life ARP given by our industrial partner. This ARP is remarkably complex, with multiple vehicles, capacity constraints, a time deadline, intermediate facilities, multiple objectives, and a combination of one- and two-way streets. For this problem, we develop specialised solution algorithms, which are specially tailored to give good upper and lower bounds as quickly as possible for large-scale instances.