A Sequential Route-building Algorithm Employing a Generalised Savings Criterion

Abstract

Sequential and concurrent route building methods for planning multiple drop delivery journeys are contrasted, and it is concluded that the former would offer important practical advantages if the quality of the routes could be improved. A new method for vehicle scheduling, based upon sequential generation of vehicle routes, is described in this paper. The possibility of several journeys being made by each vehicle is actively considered, and vehicle utilisation is high in consequence. The Clarke and Wright savings criterion is generalised, and each journey is automatically free from intersections. The method is also computationally efficient as evidenced by a study of the sensitivity with respect to fleet size, of changes in vehicle capacity and a driven distance constraint for a single depot problem with 225 customers.