Cf. Daganzo et Rw. Hall, A ROUTING MODEL FOR PICKUPS AND DELIVERIES - NO CAPACITY RESTRICTIONSON THE SECONDARY ITEMS, Transportation science, 27(4), 1993, pp. 315-329
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.