[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Optimal Solutions for the Vehicle Routing Problem with Split Demands

  • Conference paper
  • First Online:
Computational Logistics (ICCL 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11756))

Included in the following conference series:

Abstract

This paper describes a branch-and-cut algorithm for a generalization of the Capacitated Vehicle Routing Problem where a customer can be visited several times. The algorithm is based on solving a Mixed Integer Programming model for a relaxed problem, and a cutting-plane procedure to eliminate invalid integer solutions. Computational results on benchmark instances show the performance of the algorithm compared with other approaches found in the literature. In particular, the new algorithm is able to solve a testbed SDVRP instance that was unsolved in the literature.

This work has been partially supported by the research project MTM2015-63680-R (MINECO/FEDER) and ProID2017010132 (Gobierno de Canarias/FEDER).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Archetti, C., Bianchessi, N., Speranza, M.: A column generation approach for the split delivery vehicle routing problem. Networks 58(4), 241–254 (2011)

    Article  MathSciNet  Google Scholar 

  2. Archetti, C., Bianchessi, N., Speranza, M.: Branch-and-cut algorithms for the split delivery vehicle routing problem. Eur. J. Oper. Res. 238(3), 685–698 (2014)

    Article  MathSciNet  Google Scholar 

  3. Archetti, C., Speranza, M.G.: Vehicle routing problems with split deliveries. Int. Trans. Oper. Res. 19, 3–22 (2012)

    Article  MathSciNet  Google Scholar 

  4. Belenguer, J.M., Martinez, M.C., Mota, E.: A lower bound for the split delivery vehicle routing problem. Oper. Res. 48, 801–810 (2000)

    Article  MathSciNet  Google Scholar 

  5. Chen, P., Golden, B., Wang, X., Wasil, E.: A novel approach to solve the split delivery vehicle routing problem. Int. Trans. Oper. Res. 24, 27–41 (2017)

    Article  MathSciNet  Google Scholar 

  6. Dror, M., Trudeau, P.: Saving by split delivery routing. Transp. Sci. 23, 141–145 (1989)

    Article  Google Scholar 

  7. Dror, M., Laporte, G., Trudeau, P.: Vehicle routing with split deliveries. Discrete Appl. Math. 50, 239–254 (1994)

    Article  MathSciNet  Google Scholar 

  8. Erdogan, G., Battarra, M., Wolfler Calvo, R.: An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. Eur. J. Oper. Res. 245, 667–679 (2015)

    Article  MathSciNet  Google Scholar 

  9. Hernández-Pérez, H., Salazar-González, J.J., Santos-Hernández, B.: Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem. Comput. Oper. Res. 97, 1–17 (2018)

    Article  MathSciNet  Google Scholar 

  10. Hernández-Pérez, H., Salazar-González, J.-J.: The one-commodity pickup-and-delivery travelling salesman problem. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization — Eureka, You Shrink!. LNCS, vol. 2570, pp. 89–104. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36478-1_10

    Chapter  Google Scholar 

  11. Jin, M., Liu, K., Bowden, R.O.: A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. Int. J. Prod. Econ. 105(1), 228–242 (2007)

    Article  Google Scholar 

  12. Jin, M., Liu, K., Eksioglu, B.: A column generation approach for the split delivery vehicle routing problem. Oper. Res. Lett. 36(2), 265–270 (2008)

    Article  MathSciNet  Google Scholar 

  13. Lee, C.G., Epelman, M.A., White, C.C., Bozer, Y.A.: A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transp. Res. Part B Methodol. 40(4), 265–284 (2006)

    Article  Google Scholar 

  14. Moreno, L., Poggi, M., Uchoa, E.: Improved lower bounds for the split delivery vehicle routing problem. Oper. Res. Lett. 38, 302–306 (2010)

    Article  MathSciNet  Google Scholar 

  15. Ozbaygin, G., Karasan, O., Yaman, H.: New exact solution approaches for the split delivery vehicle routing problem. EURO J. Comput. Optim. 6, 85–115 (2018)

    Article  MathSciNet  Google Scholar 

  16. Salazar-González, J.J., Santos-Hernández, B.: The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transp. Res. Part B Methodol. 75, 58–73 (2015)

    Article  Google Scholar 

  17. Sierksma, G., Tijssen, G.A.: Routing helicopters for crew exchanges on off-shore locations. Ann. Oper. Res. 76, 261–286 (1998)

    Article  Google Scholar 

  18. Silva, M., Subramanian, A., Ochi, L.: An iterated local search heuristic for the split delivery vehicle routing problem. Comput. Oper. Res. 53, 234–249 (2015)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DMEIO, Facultad de Ciencias, Universidad de La Laguna, 38200, La Laguna, Tenerife, Spain

    Hipólito Hernández-Pérez & Juan-José Salazar-González

Authors
  1. Hipólito Hernández-Pérez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan-José Salazar-González
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juan-José Salazar-González .

Editor information

Editors and Affiliations

  1. Universidad del Norte, Barranquilla, Colombia

    Carlos Paternina-Arboleda

  2. Universität Hamburg, Hamburg, Germany

    Stefan Voß

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hernández-Pérez, H., Salazar-González, JJ. (2019). Optimal Solutions for the Vehicle Routing Problem with Split Demands. In: Paternina-Arboleda, C., Voß, S. (eds) Computational Logistics. ICCL 2019. Lecture Notes in Computer Science(), vol 11756. Springer, Cham. https://doi.org/10.1007/978-3-030-31140-7_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-31140-7_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-31139-1

  • Online ISBN: 978-3-030-31140-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation