IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v29y2021i1d10.1007_s11750-020-00590-x.html
   My bibliography  Save this article

A Branch & Cut algorithm for the prize-collecting capacitated location routing problem

Author

Listed:
  • Daniel Negrotto

    (Universidad de Buenos Aires)

  • Irene Loiseau

    (Universidad de Buenos Aires)

Abstract

The Capacitated location routing problem (CLRP) is the combination of two well-studied problems in Operations Research: the capacitated facility location problem (CFLP) and the multiple depots vehicle routing problem (MDVRP). Given a set of available locations and a fleet of vehicles, the aim is to determine a set of depots to open and routes of the vehicles to satisfy the customers demands. The objective of the CLRP is to minimize the total cost, that is the cost of the opened depots, the fixed cost of the vehicles and the cost of the routes while satisfying vehicle and depot capacity constraints. In this work the prize-collecting capacitated location routing problem (PC-CLRP), a new variant of the CLRP is presented. In this case it is possible to leave some customers unvisited and if a customer is visited it gives a gain. The objective is to maximize the overall benefit. A two-index formulation for the PC-CLRP and a Branch & Cut algorithm based on this model are proposed. Valid inequalities for the CLRP are adapted for the PC-CLRP. Also new valid inequalities and optimality cuts are proposed together with their corresponding separation algorithms. A hierarchical branching strategy is also included. The initial solution was provided by an Ant Colony Algorithm. The algorithm is tested on a set of instances specially designed for the new problem. Computational results showed very promising. We also compare the performance of the algorithm with recent work for CLRP on instances from the literature.

Suggested Citation

  • Daniel Negrotto & Irene Loiseau, 2021. "A Branch & Cut algorithm for the prize-collecting capacitated location routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 34-57, April.
    • Handle: RePEc:spr:topjnl:v:29:y:2021:i:1:d:10.1007_s11750-020-00590-x
    DOI: 10.1007/s11750-020-00590-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-020-00590-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11750-020-00590-x?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    3. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    4. Perl, Jossef & Daskin, Mark S., 1985. "A warehouse location-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 19(5), pages 381-396, October.
    5. Andreas Stenger & Daniele Vigo & Steffen Enz & Michael Schwind, 2013. "An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping," Transportation Science, INFORMS, vol. 47(1), pages 64-80, February.
    6. 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.
    7. Araque, J. & Hall, L. & Magnanti, T., 1990. "Capacitated trees, capacitated routing, and associated polyhedra," LIDAM Discussion Papers CORE 1990061, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Salhi, Said & Rand, Graham K., 1989. "The effect of ignoring routes when locating depots," European Journal of Operational Research, Elsevier, vol. 39(2), pages 150-156, March.
    9. 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.
    10. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    11. 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.
    12. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    13. 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.
    14. Watson-Gandy, CDT & Dohrn, PJ, 1973. "Depot location with van salesmen -- A practical approach," Omega, Elsevier, vol. 1(3), pages 321-329, June.
    15. Paolo Toth & Daniele Vigo, 2003. "The Granular Tabu Search and Its Application to the Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 333-346, November.
    16. 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.
    17. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    18. Hansen, P. H. & Hegedahl, B. & Hjortkjaer, S. & Obel, B., 1994. "A heuristic solution to the warehouse location-routing problem," European Journal of Operational Research, Elsevier, vol. 76(1), pages 111-127, July.
    19. Ahn, Jaemyung & de Weck, Olivier & Geng, Yue & Klabjan, Diego, 2012. "Column generation based heuristics for a generalized location routing problem with profits arising in space exploration," European Journal of Operational Research, Elsevier, vol. 223(1), pages 47-59.
    20. 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.
    21. 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. 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).
    2. 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.
    3. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    4. 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.
    5. Escobar, John Willmer & Linfati, Rodrigo & Baldoquin, Maria G. & Toth, Paolo, 2014. "A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 344-356.
    6. Michael Schneider & Maximilian Löffler, 2019. "Large Composite Neighborhoods for the Capacitated Location-Routing Problem," Service Science, INFORMS, vol. 53(1), pages 301-318, February.
    7. 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.
    8. Bagheri Hosseini, Mozhde & Dehghanian, Farzad & Salari, Majid, 2019. "Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network," European Journal of Operational Research, Elsevier, vol. 272(2), pages 655-673.
    9. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    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. 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.
    12. 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.
    13. Jenn-Rong Lin & Hsien-Chung Lei, 2009. "Distribution systems design with two-level routing considerations," Annals of Operations Research, Springer, vol. 172(1), pages 329-347, November.
    14. Oktay Yılmaz & Ertan Yakıcı & Mumtaz Karatas, 2019. "A UAV location and routing problem with spatio-temporal synchronization constraints solved by ant colony optimization," Journal of Heuristics, Springer, vol. 25(4), pages 673-701, October.
    15. Yanwei Zhao & Longlong Leng & Chunmiao Zhang, 2021. "A novel framework of hyper-heuristic approach and its application in location-routing problem with simultaneous pickup and delivery," Operational Research, Springer, vol. 21(2), pages 1299-1332, June.
    16. 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.
    17. 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.
    18. 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.
    19. Paolo Gianessi & Laurent Alfandari & Lucas Létocart & Roberto Wolfler Calvo, 2016. "The Multicommodity-Ring Location Routing Problem," Transportation Science, INFORMS, vol. 50(2), pages 541-558, May.
    20. 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.

    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:spr:topjnl:v:29:y:2021:i:1:d:10.1007_s11750-020-00590-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.