Skip to main content
SpringerLink
Log in

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

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahn J, De Weck O, Hoffman J (2008) An optimization framework for global planetary surface exploration campaigns. J Br Interplanet Soc 61(12):487–498

    Google Scholar 

  • Ahn J, De Weck O, Geng Y, Klabjan D (2012) Column generation based heuristics for a generalized location routing problem with profits arising in space exploration. Eur J Oper Res 223(1):47–59

    Article  Google Scholar 

  • Akca Z, Berger R, Ralphs T (2009) A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions. Operations research/computer science interfaces book series, vol 47. Springer, New York, pp 309–330

  • Albareda-Sambola M, Díaz J, Fernández E (2005) A compact model and tight bounds for a combined location-routing problem. Comput Oper Res 32(3):407–428

    Article  Google Scholar 

  • Araque JR, Hall LA, Magnanti TL (1990) Capacitated trees, capacitated routing and associated polyhedra. Catholic University of Louvain, Belgium, Discussion paper, Center of Operations Research and Econometrics

  • Archetti C, Speranza MG, Vigo D (2014) Vehicle routing problems with profits. In: Vigo D, Toth P (eds) Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, pp 273–298

  • Augerat P (1995) Approche polyédrale du probléme de tournées de véhicles. Polytechnique de Grenoble, Ph.D. Thesis

  • Baldacci R, Mingozzi A, Calvo RW (2011) An exact method for the capacitated location-routing problem. Oper Res 59(5):1284–1296

    Article  Google Scholar 

  • Barahona F, Grötschel M (1986) On the cycle polytope of a binary matroid. J Comb Theory Ser B 40(1):40–62

    Article  Google Scholar 

  • Barreto S, Ferreira C, Paixao J, Santos BS (2007) Using clustering analysis in a capacitated location-routing problem. Eur J Oper Res 179(3):968–977

    Article  Google Scholar 

  • Belenguer JM, Benavent E, Prins C, Prodhon C, Calvo RW (2011) A branch-and-cut method for the capacitated location-routing problem. Comput Oper Res 38(6):931–941

    Article  Google Scholar 

  • Clarke G, Wright JV (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581

    Article  Google Scholar 

  • Contardo C, Cordeau JF, Gendron B (2013) A computational comparison of flow formulations for the capacitated location-routing problem. Discrete Optim 10(4):263–295

    Article  Google Scholar 

  • Contardo C, Cordeau JF, Gendron B (2014) An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS J Comput 26(1):88–102

    Article  Google Scholar 

  • Contardo C, Cordeau JF, Gendron B (2014) A GRASP + ILP based metaheuristic for the capacitated location-routing problem. J Heuristics 20(1):1–38

    Article  Google Scholar 

  • CPLEX (2014) IBM ILOG CPLEX optimizer version 12.6.1. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

  • Dezsö B, Jüttner A, Kovács P (2011) LEMON - an open source C++ graph template library. Electron Notes Theor Comput Sci 264(5):23–45. http://lemon.cs.elte.hu/trac/lemon

  • Duhamel CPC, Lacomme P, Prodhon C (2010) A GRASP x ELS approach for the capacitated location-routing problem. Comput Oper Res 37(11):1912–1923

    Article  Google Scholar 

  • Escobar JW (2013) Heuristic algorithms for the capacitated location-routing problem and the multi-depot vehicle routing problem. Ph.D. Thesis, Università di Bologna

  • Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2):188–205

    Article  Google Scholar 

  • Gavish B (1984) The delivery problem: New cutting planes procedure, TIMS XXVI Conference, Copenhagen

  • Golden BL, Raghavan S, Wasil EA (2008) The vehicle routing problem: latest advances and new challenges. Springer, New York

    Book  Google Scholar 

  • Gouveia L (1995) A result on projection for the vehicle routing problem. Eur J Oper Res 85:610–624

    Article  Google Scholar 

  • Hansen PH, Hegedahl B, Hjortkjaer S, Obel B (1994) A heuristic solution to the warehouse location-routing problem. Eur J Oper Res 76(1):111–127

    Article  Google Scholar 

  • Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228

    Article  Google Scholar 

  • Jabal-Ameli M, Aryanezhad M, Ghaffari-Nasab N (2011) A variable neighborhood descent based heuristic to solve the capacitated location-routing problem. Int J Ind Eng Comput 2(1):141–154

    Google Scholar 

  • Jokar A, Sahraeian R (2012) A heuristic based approach to solve a capacitated location-routing problem. J Manag Sustain 2(2):219–226

    Google Scholar 

  • Laporte G, Mercure H, Nobert Y (1986) An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16(1):33–46

    Article  Google Scholar 

  • Letchford A, Reinelt G, Theis D (2008) Odd minimum cut-sets and b-matchings revisited. SIAM J Discrete Math 22(4):1480–1487

    Article  Google Scholar 

  • López-Ibáñez M, Dubois-Lacoste J, Stützle T, Birattari M (2011) The IRACE package, iterated race for automatic algorithm configuration. IRIDIA, Université Libre de Bruxelles, Belgium, Tech. Report TR/IRIDIA/2011-004

  • Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program l(100):423–445

  • Lysgaard J (2005) CVRPSEP: A package of separation routines for the Capacitated Vehicle Routing Problem. Department of Management Science and Logistics, Aarhus School of Bussiness, Denmark. http://www.hha.dk/~lys/CVRPSEP.htm

  • Maranzana FE (1964) On the location of supply points to minimise transport costs. Oper Res Q 15(3):261–270

    Article  Google Scholar 

  • Melechovský PC, Wolfler-Calvo R (2005) A metaheuristic to solve a location-routing problem with non-linear costs. J Heuristics 11:375–391

    Article  Google Scholar 

  • Min H, Jayaraman V, Srivastava R (1998) Combined location-routing problems: a synthesis and future research directions. Eur J Oper Res 108(1):1–15

    Article  Google Scholar 

  • Nagy G, Salhi S (2007) Location-routing: Issues, models and methods. Eur J Oper Res 177(2):649–672

    Article  Google Scholar 

  • Negrotto D (2015) Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios. Ph.D. Thesis, Universidad de Buenos Aires. https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n5818_Negrotto

  • Perl J, Daskin MS (1985) A warehouse location-routing problem. Transp Res Part B Methodol 19(5):381–396

    Article  Google Scholar 

  • Pirkwieser S, Raidl GR (2010) Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem. Lect Notes Comput Sci 6373:174–189

    Article  Google Scholar 

  • Polat E (2008) A location and routing-with-profit problem in glass recycling. Master thesis, Middle East Technical University

  • Prins C, Prodhon C, Calvo R (2006) Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR 4(3):221–238

  • Prins C, Prodhon C, Calvo RW (2006) A memetic algorithm with population management for the capacitated location-routing problem. Lect Notes Comput Sci 3906:183–194

    Article  Google Scholar 

  • Prins C, Prodhon C, Ruiz A, Soriano P, Calvo RW (2007) Solving the capacitated location-routing problem by a cooperative lagrangean relaxation-granular tabu search heuristic. Transp Sci 41(4):470–483

    Article  Google Scholar 

  • Prodhon C (2006) Le problème de localisation-routage, Ph.D. Thesis, Troyes University of Technology. http://prodhonc.free.fr/Instances/instances_us.htm

  • Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur J Oper Res 238(1):1–17

    Article  Google Scholar 

  • Salhi S, Rand GK (1989) The effect of ignoring routes when locating depots. Eur J Oper Res 39(2):150–156

    Article  Google Scholar 

  • Stenger A, Vigo D, Enz S, Schwind M (2013) A variable neighborhood search algorithm for a vehicle routing problem arizing in small package shipping. Transp Sci 47(1):64–80

    Article  Google Scholar 

  • Ting CJ, Chen CH (2013) A multiple ant colony optimization algorithm for the capacitated location routing problem. Int J Prod Econ 141(1):34–44

    Article  Google Scholar 

  • Toth P, Vigo D (2003) The Granular Tabu search and its application to the vehicle-routing problem. INFORMS J Comput 15(4):333–346

    Article  Google Scholar 

  • Toth P, Vigo D (2002) The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelphia

    Book  Google Scholar 

  • Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia

    Book  Google Scholar 

  • Tuzun D, Burke LI (1999) A two-phase Tabu Search approach to the location routing problem. Eur J Oper Res 116(1):87–99

    Article  Google Scholar 

  • Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1–10

    Article  Google Scholar 

  • Von Boventer E (1961) The relationship between transportation costs and location rent in transportation problems. J Reg Sci 3:27–40

    Article  Google Scholar 

  • Watson-Gandy C, Dohrn P (1973) Depot location with van salesmen–a practical approach. Omega 1(3):321–329

    Article  Google Scholar 

  • Webb M (1968) Cost functions in the location of depots for multi-delivery journeys. Oper Res Q 19:311–328

    Article  Google Scholar 

  • Yu VF, Lin SW, Lee W, Ting CJ (2010) A simulated annealing heuristic for the capacitated location routing problem. Comput Oper Res 58(2):288–299

    Google Scholar 

Download references

Acknowledgements

We are indebted (in memorial) to Prof. Julián Aráoz for the talks we had that help us to initially formulate the problem. We thank the referee for his/her comments and suggestions. This work was partially supported by Universidad de Buenos Aires through grant UBACyT 20020100100920.

Author information

Authors and Affiliations

  1. Departamento de Computación, ICC, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina

    Daniel Negrotto & Irene Loiseau

Authors
  1. Daniel Negrotto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Irene Loiseau
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Negrotto.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Negrotto, D., Loiseau, I. A Branch & Cut algorithm for the prize-collecting capacitated location routing problem. TOP 29, 34–57 (2021). https://doi.org/10.1007/s11750-020-00590-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-020-00590-x

Keywords

Search

Navigation