IDEAS home Printed from https://ideas.repec.org/a/spr/eurjco/v6y2018i1d10.1007_s13675-017-0089-z.html
   My bibliography  Save this article

New exact solution approaches for the split delivery vehicle routing problem

Author

Listed:
  • Gizem Ozbaygin

    (Bilkent University)

  • Oya Karasan

    (Bilkent University)

  • Hande Yaman

    (Bilkent University)

Abstract

In this study, we propose exact solution methods for the split delivery vehicle routing problem (SDVRP). We first give a new vehicle-indexed flow formulation for the problem and then a relaxation obtained by aggregating the vehicle-indexed variables over all vehicles. This relaxation may have optimal solutions where several vehicles exchange loads at some customers. We cut off such solutions, in a nontraditional way, either by extending the formulation locally with vehicle-indexed variables or by node splitting. We compare these approaches using instances from the literature and new randomly generated instances. Additionally, we introduce two new extensions of the SDVRP by restricting the number of splits and by relaxing the depot return requirement and modify our algorithms to handle these extensions.

Suggested Citation

  • Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    • Handle: RePEc:spr:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0089-z
    DOI: 10.1007/s13675-017-0089-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13675-017-0089-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13675-017-0089-z?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    2. J. M. Belenguer & M. C. Martinez & E. Mota, 2000. "A Lower Bound for the Split Delivery Vehicle Routing Problem," Operations Research, INFORMS, vol. 48(5), pages 801-810, October.
    3. 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.
    4. Archetti, Claudia & Bianchessi, Nicola & Speranza, M. Grazia, 2014. "Branch-and-cut algorithms for the split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 685-698.
    5. Gulczynski, Damon & Golden, Bruce & Wasil, Edward, 2010. "The split delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 612-626, September.
    6. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    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. D Sariklis & S Powell, 2000. "A heuristic method for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(5), pages 564-573, May.
    9. Lee, Chi-Guhn & Epelman, Marina A. & White III, Chelsea C. & Bozer, Yavuz A., 2006. "A shortest path approach to the multiple-vehicle routing problem with split pick-ups," Transportation Research Part B: Methodological, Elsevier, vol. 40(4), pages 265-284, May.
    10. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    11. 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.
    12. 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.
    13. Jin, Mingzhou & Liu, Kai & Bowden, Royce O., 2007. "A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 105(1), pages 228-242, January.
    14. 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.
    15. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    16. Yi, Wei & Kumar, Arun, 2007. "Ant colony optimization for disaster relief operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(6), pages 660-672, November.
    17. Özdamar, Linet & Demir, Onur, 2012. "A hierarchical clustering and routing procedure for large scale disaster relief logistics planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 591-602.
    18. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    19. Wang, Haijun & Du, Lijing & Ma, Shihua, 2014. "Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 160-179.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    2. Annelieke C. Baller & Said Dabia & Wout E. H. Dullaert & Daniele Vigo, 2020. "The Vehicle Routing Problem with Partial Outsourcing," Transportation Science, INFORMS, vol. 54(4), pages 1034-1052, July.
    3. 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.
    4. Efraín Ruiz y Ruiz & Irma García-Calvillo & Samuel Nucamendi-Guillén, 2022. "Open vehicle routing problem with split deliveries: mathematical formulations and a cutting-plane method," Operational Research, Springer, vol. 22(2), pages 1017-1037, April.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Yangkun Xia & Zhuo Fu & Lijun Pan & Fenghua Duan, 2018. "Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-19, May.
    10. 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.
    11. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    12. Yangkun Xia & Zhuo Fu & Sang-Bing Tsai & Jiangtao Wang, 2018. "A New TS Algorithm for Solving Low-Carbon Logistics Vehicle Routing Problem with Split Deliveries by Backpack—From a Green Operation Perspective," IJERPH, MDPI, vol. 15(5), pages 1-12, May.
    13. Jin, Mingzhou & Liu, Kai & Bowden, Royce O., 2007. "A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 105(1), pages 228-242, January.
    14. 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.
    15. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.
    16. Salazar-González, Juan-José & Santos-Hernández, Beatriz, 2015. "The split-demand one-commodity pickup-and-delivery travelling salesman problem," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 58-73.
    17. Frank Hennig & Bjørn Nygreen & Marco E. Lübbecke, 2012. "Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 298-310, April.
    18. 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.
    19. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    20. Saman Eskandarzadeh & Reza Tavakkoli-Moghaddam & Amir Azaron, 2009. "An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 214-234, February.

    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:spr:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0089-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.