IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v42y2008i1p32-43.html
   My bibliography  Save this article

Pickup and Delivery with Split Loads

Author

Listed:
  • Maciek Nowak

    (Department of Management, Marketing, and Logistics, Georgia Southern University, Statesboro, Georgia 30460)

  • Özlem Ergun

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Chelsea C. White

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip results in opportunities for a reduction in cost and the number of vehicles used. Several studies have shown the benefit of split deliveries for the vehicle routing problem, in which a vehicle operating out of a depot makes a series of deliveries on each route. In this paper, we quantify the benefit of using split loads for the pickup and delivery problem. A heuristic to solve the pickup and delivery problem with split loads is developed and applied to a set of random large-scale problem instances, revealing the potential benefit of split loads. This benefit is reduced when the heuristic is applied to a real-world trucking industry problem because of several problem instance characteristics. The benefit of split loads is found to be most closely tied to three characteristics: load size, cost associated with a pickup or delivery, and the frequency with which loads have origins or destinations in common. Prior to a discussion of these results, we define the pickup and delivery problem with split loads and prove that for a set of given origins and destinations the most benefit can occur with load sizes just above one half of vehicle capacity.

Suggested Citation

  • Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
  • Handle: RePEc:inm:ortrsc:v:42:y:2008:i:1:p:32-43
    DOI: 10.1287/trsc.1070.0207
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1070.0207
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.1070.0207?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    2. Claudia Archetti & Martin W. P. Savelsbergh & M. Grazia Speranza, 2006. "Worst-Case Analysis for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 40(2), pages 226-234, May.
    3. Nanry, William P. & Wesley Barnes, J., 2000. "Solving the pickup and delivery problem with time windows using reactive tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 107-121, February.
    4. C. Archetti & M. G. Speranza & A. Hertz, 2006. "A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 40(1), pages 64-73, February.
    5. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    6. Paolo Toth & Daniele Vigo, 1997. "Heuristic Algorithms for the Handicapped Persons Transportation Problem," Transportation Science, INFORMS, vol. 31(1), pages 60-71, February.
    7. Gerard Sierksma & Gert Tijssen, 1998. "Routing helicopters for crew exchanges on off-shore locations," Annals of Operations Research, Springer, vol. 76(0), pages 261-286, January.
    8. Archetti, Claudia & Savelsbergh, Martin W.P. & Grazia Speranza, M., 2008. "To split or not to split: That is the question," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 114-123, January.
    9. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    10. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    2. Guy Desaulniers, 2010. "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 58(1), pages 179-192, February.
    3. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    4. Cortes, Juan David & Suzuki, Yoshinori, 2020. "Vehicle Routing with Shipment Consolidation," International Journal of Production Economics, Elsevier, vol. 227(C).
    5. C. Archetti & M. Bouchard & G. Desaulniers, 2011. "Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows," Transportation Science, INFORMS, vol. 45(3), pages 285-298, August.
    6. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    7. Lin, Yen-Hung & Batta, Rajan & Rogerson, Peter A. & Blatt, Alan & Flanigan, Marie, 2011. "A logistics model for emergency supply of critical items in the aftermath of a disaster," Socio-Economic Planning Sciences, Elsevier, vol. 45(4), pages 132-145, December.
    8. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    10. Pedro Munari & Martin Savelsbergh, 2020. "A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows," SN Operations Research Forum, Springer, vol. 1(4), pages 1-24, December.
    11. Berbotto, Leonardo & García, Sergio & Nogales, Francisco J., 2011. "A vehicle routing model with split delivery and stop nodes," DES - Working Papers. Statistics and Econometrics. WS ws110906, Universidad Carlos III de Madrid. Departamento de Estadística.
    12. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    13. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    14. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    15. Nowak, Maciek & Ergun, Ozlem & White III, Chelsea C., 2009. "An empirical study on the benefit of split loads with the pickup and delivery problem," European Journal of Operational Research, Elsevier, vol. 198(3), pages 734-740, November.
    16. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    17. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    18. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    19. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.
    20. Hertz, Alain & Uldry, Marc & Widmer, Marino, 2012. "Integer linear programming models for a cement delivery problem," European Journal of Operational Research, Elsevier, vol. 222(3), pages 623-631.

    More about this item

    Keywords

    vehicle routing; split pickup and delivery;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:42:y:2008:i:1:p:32-43. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.