Go back to Carlos Daganzo's Publications PageThis paper examines a routing problem in which vehicles from a single depot cover a large area, where randomly located customers request pickup and delivery service. The paper assumes that each vehicle must serve its deliveries before it collects any pickups, that vehicles do not need to return to the depot between delivery and collection, and that 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 only depends on two
dimensionless parameters: the size of the service area, relative to
the area covered by one delivery route; and the ratio of the number
of pickup customers to the number of deliveries. The clusters of
deliveries and pickups served by a vehicle should often be
radically different; unlike deliveries, pickups should be clustered
in zones 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 majority of cases not much is lost by routing for
deliveries first (ignoring pickups) and for pickups second.
Instances where they should be considered jointly are identified.
Go back to Carlos Daganzo's Publications Page