IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i5p1284-1296.html
   My bibliography  Save this article

An Exact Method for the Capacitated Location-Routing Problem

Author

Listed:
  • Roberto Baldacci

    (Department of Electronics, Computer Science and Systems, University of Bologna, 47521 Cesena, Italy)

  • Aristide Mingozzi

    (Department of Mathematics, University of Bologna, 47521 Cesena, Italy)

  • Roberto Wolfler Calvo

    (Laboratoire d'Informatique de Paris-Nord (LIPN, UMR 7030), 93430 Villetaneuse, France)

Abstract

The capacitated location-routing problem (LRP) consists of opening one or more depots on a given set of a-priori defined depot locations, and designing, for each opened depot, a number of routes in order to supply the demands of a given set of customers. With each depot are associated a fixed cost for opening it and a capacity that limits the quantity that can be delivered to the customers. The objective is to minimize the sum of the fixed costs for opening the depots and the costs of the routes operated from the depots. This paper describes a new exact method for solving the LRP based on a set-partitioning-like formulation of the problem. The lower bounds produced by different bounding procedures, based on dynamic programming and dual ascent methods, are used by an algorithm that decomposes the LRP into a limited set of multicapacitated depot vehicle-routing problems (MCDVRPs). Computational results on benchmark instances from the literature show that the proposed method outperforms the current best-known exact methods, both for the quality of the lower bounds achieved and the number and the dimensions of the instances solved to optimality.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:5:p:1284-1296
    DOI: 10.1287/opre.1110.0989
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0989
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0989?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. Kulcar, Thierry, 1996. "Optimizing solid waste collection in Brussels," European Journal of Operational Research, Elsevier, vol. 90(1), pages 71-77, April.
    3. Wasner, Michael & Zapfel, Gunther, 2004. "An integrated multi-depot hub-location vehicle routing model for network planning of parcel service," International Journal of Production Economics, Elsevier, vol. 90(3), pages 403-419, August.
    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. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(4), pages 1007-1017, August.
    6. Srivastava, R, 1993. "Alternate solution procedures for the location-routing problem," Omega, Elsevier, vol. 21(4), pages 497-506, July.
    7. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(6), pages 1461-1465, December.
    8. Barreto, Sergio & Ferreira, Carlos & Paixao, Jose & Santos, Beatriz Sousa, 2007. "Using clustering analysis in a capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 968-977, June.
    9. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(1), pages 193-194, February.
    10. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(5), pages 1273-1289, October.
    11. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    12. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(3), pages 819-821, June.
    13. Laporte, Gilbert & Louveaux, Francois & Mercure, Helene, 1989. "Models and exact solutions for a class of stochastic location-routing problems," European Journal of Operational Research, Elsevier, vol. 39(1), pages 71-78, March.
    14. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(2), pages 541-545, April.
    15. Tuzun, Dilek & Burke, Laura I., 1999. "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 87-99, July.
    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. Ting, Ching-Jung & Chen, Chia-Ho, 2013. "A multiple ant colony optimization algorithm for the capacitated location routing problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 34-44.
    2. Rieck, Julia & Ehrenberg, Carsten & Zimmermann, Jürgen, 2014. "Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery," European Journal of Operational Research, Elsevier, vol. 236(3), pages 863-878.
    3. 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.
    4. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    5. Nasrin Asgari & Mohsen Rajabi & Masoumeh Jamshidi & Maryam Khatami & Reza Zanjirani Farahani, 2017. "A memetic algorithm for a multi-objective obnoxious waste location-routing problem: a case study," Annals of Operations Research, Springer, vol. 250(2), pages 279-308, March.
    6. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    7. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. 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.
    9. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    10. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2012. "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach," Omega, Elsevier, vol. 40(4), pages 465-477.
    11. 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.
    12. 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.
    13. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2011. "A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery," European Journal of Operational Research, Elsevier, vol. 211(2), pages 318-332, June.
    14. Pourya Pourhejazy & Oh Kyoung Kwon, 2016. "The New Generation of Operations Research Methods in Supply Chain Optimization: A Review," Sustainability, MDPI, vol. 8(10), pages 1-23, October.
    15. 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.
    16. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    17. Prodhon, Caroline, 2011. "A hybrid evolutionary algorithm for the periodic location-routing problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 204-212, April.
    18. Hunkar Toyoglu & Oya Karasan & Bahar Kara, 2012. "A New Formulation Approach for Location-Routing Problems," Networks and Spatial Economics, Springer, vol. 12(4), pages 635-659, December.
    19. Gao, Shangce & Wang, Yirui & Cheng, Jiujun & Inazumi, Yasuhiro & Tang, Zheng, 2016. "Ant colony optimization with clustering for solving the dynamic location routing problem," Applied Mathematics and Computation, Elsevier, vol. 285(C), pages 149-173.
    20. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2021. "An evaluation of three DoE-guided meta-heuristic-based solution methods for a three-echelon sustainable distribution network," Annals of Operations Research, Springer, vol. 296(1), pages 421-469, January.

    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:oropre:v:59:y:2011:i:5:p:1284-1296. 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.