The Distance Traveled to Visit N Points with a Maximum of C Stops per Vehicle: An Analytic Model and an Application

The purpose of this paper is to develop a simple formula to predict the distance traveled by fleets of vehicles in physical distribution problems involving a depot and its area of influence. Since the transportation cost of operating a break-bulk terminal (or a warehouse) is intimately related to the distance traveled, the availability of such a simple formula should facilitate the study of more complex logistics problems. A simple manual dispatching strategy intended to mimic what dispatchers do, but simple enough to admit analytical modeling is presented. Since the formulas agree rather well with the length of (nearly optimal) computer built tours, the predictions should approximate distances achievable in practice; the formulas seem realistic. The technique is a variant of the classical “cluster-first, route-second” approach to vehicle routing problems. In these approaches, the depot influence area is first partitioned into districts containing clusters of stops; one vehicle route is then constructed to serve each cluster. Our procedure is characterized by the way district shapes are chosen; ignoring shape during the clustering step can increase significantly travel distances. The technique is simple. To exercise it, one needs only a pencil, eraser, and a scale map showing the destinations. Once mastered, the technique takes only a few minutes. This time should increase only linearly with the number of destinations. For repetitive problems, the technique can be enhanced with the help of interactive computer graphics. A newspaper delivery problem for the city of San Francisco is used as an illustration.