This thesis is concerned with the problem of finding routes for a fleet of vehicles which must make deliveries to a number of customers at various locations. If temporal aspects are also involved, such as customers specifying the range of times when they will accept delivery, or the goods being produced before delivery can begin, there is also a scheduling component to the problem.
At present, exact algorithms cannot be used on a day-to-day basis for large problems of this type, as they require too much processing time. In this thesis we investigate methods which, although heuristic, are based on exact methods. Such methods offer hope of finding good, quick solutions to these problems.
Research is centred on two types of problem. The first area of study concerns problems where the vehicles are only subject to capacity constraints. A new algorithm called PETAL, based on exactly solving a modified Assignment Problem, is suggested for this problem. This algorithm is described and compared with other algorithms from the literature. The PETAL algorithm performs well when compared with these algorithms.
The second area of study is in the situation where customers specify acceptable times for delivery, and where the product is being produced immediately before delivery. Such problems arise, for example in the delivery of newspapers. This is a relatively new area of research, and a full introduction is given. The only existing algorithm for this problem, developed by a number of researchers including the author, is described. A new algorithm based on Set Partitioning is introduced, and extended to incorporate column generation. The two algorithms are compared, with results that encourage further work on the Set Partitioning algorithm.