IDEAS home Printed from https://ideas.repec.org/p/hhb/aarbls/2006-006.html
   My bibliography  Save this paper

A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem

Author

Listed:
  • Letchford, Adam N.

    (Department of Management Science)

  • Lysgaard, Jens

    (Department of Business Studies)

  • Eglese, Richard W.

    (Department of Management Science)

Abstract

In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch-and-cut. We show that, even though the open CVRP initially looks like a minor variation of the standard CVRP, the integer programming formulation and cutting planes need to be modified in subtle ways. Computational results are given for several standard test instances, which enables us for the first time to assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.

Suggested Citation

  • Letchford, Adam N. & Lysgaard, Jens & Eglese, Richard W., 2006. "A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem," CORAL Working Papers L-2006-06, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    • Handle: RePEc:hhb:aarbls:2006-006
    as

    Download full text from publisher

    File URL: http://www.hha.dk/bs/wp/log/L_2006_06.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Brandao, Jose, 2004. "A tabu search algorithm for the open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 552-564, September.
    2. Matteo Fischetti & Paolo Toth & Daniele Vigo, 1994. "A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs," Operations Research, INFORMS, vol. 42(5), pages 846-859, October.
    3. 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.
    4. 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.
    5. C D Tarantilis & G Ioannou & C T Kiranoudis & G P Prastacos, 2005. "Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 588-596, May.
    6. Gilbert Laporte & Yves Nobert & Martin Desrochers, 1985. "Optimal Routing under Capacity and Distance Restrictions," Operations Research, INFORMS, vol. 33(5), pages 1050-1073, October.
    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. Liu, Ran & Jiang, Zhibin, 2012. "The close–open mixed vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 349-360.
    2. T Bektaş & Seda Elmastaş, 2007. "Solving school bus routing problems through integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1599-1604, December.
    3. U Derigs & K Reuter, 2009. "A simple and efficient tabu search heuristic for solving the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1658-1669, December.
    4. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    5. D Aksen & Z Özyurt & N Aras, 2007. "Open vehicle routing problem with driver nodes and time deadlines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1223-1234, September.
    6. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    7. Zhen, Lu & Tan, Zheyi & Wang, Shuaian & Yi, Wen & Lyu, Junyan, 2021. "Shared mobility oriented open vehicle routing with order radius decision," Transportation Research Part A: Policy and Practice, Elsevier, vol. 144(C), pages 19-33.
    8. Abdelkader Sbihi & Richard W. Eglese, 2007. "The Relationship between Vehicle Routing & Scheduling and Green Logistics - A Literature Survey," Working Papers hal-00644133, HAL.

    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. 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.
    2. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    3. T Bektaş & Seda Elmastaş, 2007. "Solving school bus routing problems through integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1599-1604, December.
    4. Atefi, Reza & Salari, Majid & C. Coelho, Leandro & Renaud, Jacques, 2018. "The open vehicle routing problem with decoupling points," European Journal of Operational Research, Elsevier, vol. 265(1), pages 316-327.
    5. X-Y Li & P Tian & S C H Leung, 2009. "An ant colony optimization metaheuristic hybridized with tabu search for open vehicle routing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 1012-1025, July.
    6. P P Repoussis & C D Tarantilis & G Ioannou, 2007. "The open vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 355-367, March.
    7. N. Norouzi & R. Tavakkoli-Moghaddam & M. Ghazanfari & M. Alinaghian & A. Salamatbakhsh, 2012. "A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 12(4), pages 609-633, December.
    8. Russell, Robert, 2013. "A constraint programming approach to designing a newspaper distribution system," International Journal of Production Economics, Elsevier, vol. 145(1), pages 132-138.
    9. U Derigs & K Reuter, 2009. "A simple and efficient tabu search heuristic for solving the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1658-1669, December.
    10. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    11. Abdelkader Sbihi & Richard W. Eglese, 2007. "The Relationship between Vehicle Routing & Scheduling and Green Logistics - A Literature Survey," Working Papers hal-00644133, HAL.
    12. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    13. Roberto Baldacci & Paolo Toth & Daniele Vigo, 2010. "Exact algorithms for routing problems under vehicle capacity constraints," Annals of Operations Research, Springer, vol. 175(1), pages 213-245, March.
    14. Dasdemir, Erdi & Testik, Murat Caner & Öztürk, Diclehan Tezcaner & Şakar, Ceren Tuncer & Güleryüz, Güldal & Testik, Özlem Müge, 2022. "A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem," Omega, Elsevier, vol. 108(C).
    15. Yunyun Niu & Zehua Yang & Rong Wen & Jianhua Xiao & Shuai Zhang, 2022. "Solving the Green Open Vehicle Routing Problem Using a Membrane-Inspired Hybrid Algorithm," Sustainability, MDPI, vol. 14(14), pages 1-22, July.
    16. D Aksen & Z Özyurt & N Aras, 2007. "Open vehicle routing problem with driver nodes and time deadlines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1223-1234, September.
    17. Jesús Sánchez-Oro & Ana D. López-Sánchez & J. Manuel Colmenar, 2020. "A general variable neighborhood search for solving the multi-objective open vehicle routing problem," Journal of Heuristics, Springer, vol. 26(3), pages 423-452, June.
    18. Fleszar, Krzysztof & Osman, Ibrahim H. & Hindi, Khalil S., 2009. "A variable neighbourhood search algorithm for the open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 803-809, June.
    19. 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.
    20. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.

    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:hhb:aarbls:2006-006. 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: Helle Vinbaek Stenholt (email available below). General contact details of provider: https://edirc.repec.org/data/ifhhadk.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.