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

The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics

Author

Listed:
  • Guido Perboli

    (DAUIN, Politecnico di Torino, 10129 Torino, Italy and CIRRELT, Montréal, Québec H3T 1J4, Canada)

  • Roberto Tadei

    (DAUIN, Politecnico di Torino, 10129 Torino, Italy)

  • Daniele Vigo

    (Department of Electronics, Information, and Systems, University of Bologna, 40136 Bologna, Italy)

Abstract

Multiechelon distribution systems are quite common in supply-chain and logistics. They are used by public administrations in their transportation and traffic planning strategies, as well as by companies, to model own distribution systems. In the literature, most of the studies address issues relating to the movement of flows throughout the system from their origins to their final destinations. Another recent trend is to focus on the management of the vehicle fleets required to provide transportation among different echelons. The aim of this paper is twofold. First, it introduces the family of two-echelon vehicle routing problems (VRPs), a term that broadly covers such settings, where the delivery from one or more depots to customers is managed by routing and consolidating freight through intermediate depots. Second, it considers in detail the basic version of two-echelon VRPs, the two-echelon capacitated VRP, which is an extension of the classical VRP in which the delivery is compulsorily delivered through intermediate depots, named satellites. A mathematical model for two-echelon capacitated VRP, some valid inequalities, and two math-heuristics based on the model are presented. Computational results of up to 50 customers and four satellites show the effectiveness of the methods developed.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:3:p:364-380
    DOI: 10.1287/trsc.1110.0368
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1110.0368
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1110.0368?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. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    2. Min, Hokey & Melachrinoudis, Emanuel, 1999. "The relocation of a hybrid manufacturing/distribution facility from supply chain perspectives: a case study," Omega, Elsevier, vol. 27(1), pages 75-85, February.
    3. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    4. Christian Prins & Caroline Prodhon & Angel Ruiz & Patrick Soriano & Roberto Wolfler Calvo, 2007. "Solving the Capacitated Location-Routing Problem by a Cooperative Lagrangean Relaxation-Granular Tabu Search Heuristic," Transportation Science, INFORMS, vol. 41(4), pages 470-483, November.
    5. Tony J. Van Roy & Donald Erlenkotter, 1982. "A Dual-Based Procedure for Dynamic Facility Location," Management Science, INFORMS, vol. 28(10), pages 1091-1105, October.
    6. Zuo-Jun Max Shen & Collette Coullard & Mark S. Daskin, 2003. "A Joint Location-Inventory Model," Transportation Science, INFORMS, vol. 37(1), pages 40-55, February.
    7. Verrijdt, J. H. C. M. & de Kok, A. G., 1995. "Distribution planning for a divergent N-echelon network without intermediate stocks under service restrictions," International Journal of Production Economics, Elsevier, vol. 38(2-3), pages 225-243, March.
    8. Mark Daskin & Collette Coullard & Zuo-Jun Shen, 2002. "An Inventory-Location Model: Formulation, Solution Algorithm and Computational Results," Annals of Operations Research, Springer, vol. 110(1), pages 83-106, February.
    9. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    10. Melachrinoudis, Emanuel & Min, Hokey, 2000. "The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: A multiple objective approach," European Journal of Operational Research, Elsevier, vol. 123(1), pages 1-15, May.
    11. Jacobsen, S. K. & Madsen, O. B. G., 1980. "A comparative study of heuristics for a two-level routing-location problem," European Journal of Operational Research, Elsevier, vol. 5(6), pages 378-387, December.
    12. VAN ROY, Tony J. & ERLENKOTTER, Donald, 1982. "A dual-based procedure for dynamic facility location," LIDAM Reprints CORE 490, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    14. John J. Bartholdi & Kevin R. Gue, 2004. "The Best Shape for a Crossdock," Transportation Science, INFORMS, vol. 38(2), pages 235-244, May.
    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. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2009. "Facility location and supply chain management - A review," European Journal of Operational Research, Elsevier, vol. 196(2), pages 401-412, July.
    2. 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.
    3. Güden, Hüseyin & Süral, Haldun, 2014. "Locating mobile facilities in railway construction management," Omega, Elsevier, vol. 45(C), pages 71-79.
    4. Simona Mancini, 2013. "Multi-echelon distribution systems in city logistics," European Transport \ Trasporti Europei, ISTIEE, Institute for the Study of Transport within the European Economic Integration, issue 54, pages 1-2.
    5. Jesus Gonzalez-Feliu & Guido Perboli & Roberto Tadei & Daniele Vigo, 2008. "The two-echelon capacitated vehicle routing problem," Working Papers halshs-00879447, HAL.
    6. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    7. H K Smith & G Laporte & P R Harper, 2009. "Locational analysis: highlights of growth to maturity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 140-148, May.
    8. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    9. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    10. Zhalechian, M. & Tavakkoli-Moghaddam, R. & Zahiri, B. & Mohammadi, M., 2016. "Sustainable design of a closed-loop location-routing-inventory supply chain network under mixed uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 182-214.
    11. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    12. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Schuster Puga, Matías & Minner, Stefan & Tancrez, Jean-Sébastien, 2019. "Two-stage supply chain design with safety stock placement decisions," International Journal of Production Economics, Elsevier, vol. 209(C), pages 183-193.
    14. Mahdi Bashiri & Zeinab Rasoulinejad & Ehsan Fallahzade, 2016. "A new approach on auxiliary vehicle assignment in capacitated location routing problem," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(4), pages 886-902, March.
    15. 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.
    16. Stenger, Andreas & Schneider, Michael & Schwind, Michael & Vigo, Daniele, 2012. "Location routing for small package shippers with subcontracting options," International Journal of Production Economics, Elsevier, vol. 140(2), pages 702-712.
    17. Snoeck, André & Winkenbach, Matthias & Fransoo, Jan C., 2023. "On-demand last-mile distribution network design with omnichannel inventory," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    18. Onur Kaya & Dogus Ozkok, 2020. "A Blood Bank Network Design Problem with Integrated Facility Location, Inventory and Routing Decisions," Networks and Spatial Economics, Springer, vol. 20(3), pages 757-783, September.
    19. Snoeck, André & Winkenbach, Matthias & Fransoo, Jan C., 2023. "On-demand last-mile distribution network design with omnichannel inventory," Other publications TiSEM 83b06c9f-2a65-4aaf-880b-2, Tilburg University, School of Economics and Management.
    20. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.

    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:45:y:2011:i:3:p:364-380. 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.