A ROUTING MODEL FOR PICKUPS AND DELIVERIES - NO CAPACITY RESTRICTIONSON THE SECONDARY ITEMS

This paper examines a routing problem in which vehicles from a single depot cover a large area, where randomly Located customers request pic kup and delivery service. The paper assumes that each vehicle must ser ve its deliveries before it collects arty pickups, that vehicles do no t need to return to the depot between delivery and collection, and tha t each vehicle can serve at most C deliveries, but an unlimited number of pickups. This paper does not propose a detailed algorithm; rather, it discusses the pros and cons of various broad routing schemes, and quantifies their performance with simple distance formulas. The broad schemes describe implementable solutions, which can in turn be used to initialize fine-tuning algorithms. The choice of a routing scheme onl y depends on two dimensionless parameters: the size of the service are a, relative to the area covered by one delivery route; and the ratio o f the number of pickup customers to the number of deliveries. The clus ters of deliveries and pickups served by a vehicle should often be rad ically different; unlike deliveries, pickups should be clustered in zo nes that have been elongated as much as possible, reaching all the way to the depot if it is internally located. It also appears that in a m ajority of cases not much is lost by routing for deliveries first (ign oring pickups) and for pickups second. Instances where they should be considered jointly are identified.