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

Daganzo, Carlos F.; Hall, Randolph W.
November 1993
Transportation Science;Nov93, Vol. 27 Issue 4, p315
Academic Journal
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.


Related Articles

  • Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows. Van Der Bruggen, L. J. J.; Lenstra, J. K.; Schuur, P. C. // Transportation Science;Aug93, Vol. 27 Issue 3, p298 

    We consider a single depot and a set of customers with known demands, each of which must be picked up and delivered at specified locations and within given time windows. We seek a route and a schedule for a single vehicle with known capacity, which minimizes the route duration, i.e., the...

  • Hybrid Genetic Algorithm for Vehicle Routing and Scheduling Problem. Ghoseiri, K.; Ghannadpour, S. F. // Journal of Applied Sciences;2009, Vol. 9 Issue 1, p79 

    This study aims to solve Vehicle Routing Problem with Time Windows (VRPTW), which has received considerable attention in recent years, using hybrid genetic algorithm. Vehicle Routing Problem with Time Windows is an extension of the well-known Vehicle Routing Problem (VRP) and involves a fleet of...

  • Multi-depot Vehicle Routing Problem with Pickup and Delivery Requests. Sombuntham, Pandhapon; Kachitvichyanukul, Voratas // AIP Conference Proceedings;10/15/2010, Vol. 1285 Issue 1, p71 

    This paper considers a multi-depot vehicle routing problem with pickup and delivery requests. In the problem of interest, each location may have goods for both pickup and delivery with multiple delivery locations that may not be the depots. These characteristics are quite common in industrial...

  • Scheduling movements in the network of an express service provider. Louwerse, Ilse; Mijnarends, Jos; Meuffels, Ineke; Huisman, Dennis; Fleuren, Hein // Flexible Services & Manufacturing Journal;Dec2014, Vol. 26 Issue 4, p565 

    Express service providers manage shipments from senders to receivers under strict service level agreements. Such shipments are usually not sufficient to justify a single transportation, so it is preferred to maximize consolidation of these shipments to reduce cost. The consolidation is organized...

  • A few slips lead to public inquiry. Jewell, Mike // Motor Transport;7/24/2003, p8 

    Reports on the appearance of hauler Partearly at a public inquiry in Great Britain in July 2003. Reason for its appearance at a public inquiry; Number of prohibitions collected by the firm since January 2002; Reason that its truck drivers did not fill defect notices abroad; Results of a depot...

  • Minimum Vehicle Fleet Size Under Time-Window Constraints at a Container Terminal. Vis, Iris F. A.; De Koster, RenĂ© (M.) B. M.; Savelsbergh, Martin W. P. // Transportation Science;May2005, Vol. 39 Issue 2, p249 

    Products can be transported in containers from one port to another. At a container terminal these containers are transshipped from one mode of transportation to another. Cranes remove containers from a ship and put them at a certain time (i.e., release time) into a buffer area with limited...

  • Intermodal's New Waterfront Outlook. Boyd, John D. // Traffic World;7/16/2007, Vol. 271 Issue 28, p18 

    The article reports that North American Pacific coast will open two new container terminals that could have big implications on intermodal growth for Canadian National and on Kansas City Southern's Mexican operations. The new facilities will be located at the Port of Prince Rupert in Canada and...

  • FOOD FOR THOUGHT.  // Motor Transport;2/17/2005, p16 

    Focuses on the assistance being provided by Nisa-Today organisation for small food retailers in Great Britain. Background on the organisation; Information on the Premier Service delivery of the organisation for retailers in England and Wales; Expansion of its depot network for its retailer...

  • Midnight Express. Rosenbloom, Joseph // Inc.;Jul2001, Vol. 23 Issue 10, p76 

    Provides information on the operation of Federal Express Corp. terminal in Memphis, Tennessee. Shipments of the packages; Companies that opened up distribution centers in Memphis; Benefits of the tracking system of Federal Express on customers; Quality of service of the company.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics