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

A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem

Author

Listed:
  • Mads Jepsen

    (Department of Management Engineering, Technical University of Denmark, 2800 Kgs.Lynby, Denmark)

  • Simon Spoorendonk

    (Department of Management Engineering, Technical University of Denmark, 2800 Kgs.Lynby, Denmark)

  • Stefan Ropke

    (Department of Transport, Technical University of Denmark, 2800 Kgs.Lynby, Denmark)

Abstract

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms.

Suggested Citation

  • Mads Jepsen & Simon Spoorendonk & Stefan Ropke, 2013. "A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem," Transportation Science, INFORMS, vol. 47(1), pages 23-37, February.
    • Handle: RePEc:inm:ortrsc:v:47:y:2013:i:1:p:23-37
    DOI: 10.1287/trsc.1110.0399
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1110.0399
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1110.0399?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. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    2. 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.
    3. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    4. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    5. 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.
    6. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    7. 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.
    8. Roberto Baldacci & Aristide Mingozzi & Roberto Wolfler Calvo, 2011. "An Exact Method for the Capacitated Location-Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1284-1296, October.
    9. 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.
    10. Guido Perboli & Roberto Tadei & Daniele Vigo, 2011. "The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics," Transportation Science, INFORMS, vol. 45(3), pages 364-380, August.
    11. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    12. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    13. R. Baldacci & M. Dell'Amico & J. Salazar González, 2007. "The Capacitated m -Ring-Star Problem," Operations Research, INFORMS, vol. 55(6), pages 1147-1162, December.
    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. 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.
    2. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    3. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2016. "Branch-and-Price-and-Cut for the Truck-andTrailer Routing Problem with Time Windows," Working Papers 1617, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Ben Mohamed, Imen & Klibi, Walid & Sadykov, Ruslan & Şen, Halil & Vanderbeck, François, 2023. "The two-echelon stochastic multi-period capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 645-667.
    5. Yu Zhang & Zhenzhen Zhang & Andrew Lim & Melvyn Sim, 2021. "Robust Data-Driven Vehicle Routing with Time Windows," Operations Research, INFORMS, vol. 69(2), pages 469-485, March.
    6. 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.
    7. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    8. 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.
    9. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    10. 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.
    11. Nicola Bianchessi & Stefan Irnich & Christian Tilk, 2020. "A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand," Working Papers 2003, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    12. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.
    13. Shijin Wang & Xiaodong Wang & Xin Liu & Jianbo Yu, 2018. "A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction," Sustainability, MDPI, vol. 10(11), pages 1-21, November.
    14. Katrin Heßler & Stefan Irnich, 2021. "Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem," Working Papers 2115, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Cherkesly, Marilène & Desaulniers, Guy & Irnich, Stefan & Laporte, Gilbert, 2016. "Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks," European Journal of Operational Research, Elsevier, vol. 250(3), pages 782-793.
    16. Christian Tilk & Katharina Olkis & Stefan Irnich, 2021. "The last-mile vehicle routing problem with delivery options," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 877-904, December.
    17. 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.
    18. Miao Yu & Viswanath Nagarajan & Siqian Shen, 2022. "Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 953-973, March.
    19. Claudio Contardo & Jean-François Cordeau & Bernard Gendron, 2014. "An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 88-102, February.
    20. Ciancio, Claudio & Laganá, Demetrio & Vocaturo, Francesca, 2018. "Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 267(1), pages 187-199.

    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:47:y:2013:i:1:p:23-37. 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.