A Routing Model for Pickups and Deliveries: No Capacity Restrictions on the Secondary Items

Carlos F. Daganzo and Randolph W. Hall
Additional contact information
Carlos F. Daganzo: University of California, Berkeley, California 94720
Randolph W. Hall: University of California, Berkeley, California 94720

Transportation Science, 1993, vol. 27, issue 4, 315-329

Abstract: This 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.

Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.27.4.315 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:27:y:1993:i:4:p:315-329

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().