Optimal location of capacitated service units through a metaheuristic optimization approach

Roger Z. Ríos Mercado, Dagoberto R. Quevedo Orozco


Introduction The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the maximum distance between any customer and its assigned facility, subject to demand capacity constraints for each facility.

Method In this work, a metaheuristic for this location problem is presented. It integrates several components such as a greedy randomized construction with an adaptive probabilistic sampling scheme and an iterated greedy local search with variable neighborhood descent.

Results Empirical evidence over a widely used set of benchmark instances on location literature, reveals the positive impact of each of the developed components and the quality of the solutions delivered by the heuristic when compared with existing methods. For instance, the proposed heuristic was able to find feasible solutions to all but two instances, while the best of the existing methods failed in 18 of these instances.

Conclusion It is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.


operations research; combinatorial optimization; discrete location; capacitated p-center problem; metaheuristics


Albareda-Sambola, M., Díaz, J.A., y Fernández, E. (2010). Lagrangean duals and exact solution to the capacitated p-center problem. European Journal of Operational Research, 201(1):71–81.

Beasley, J.E. (1990). OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–72.

Ceselli, A., y Righini, G. (2005). A branch-and-price algorithm for the capacitated p-median problem. Networks, 45(3):125–42.

Elloumi, S., Labbé, M., y Pochet, Y. (2004). A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing, 16(1):84–94.

Farahani, R.Z. y Hekmatfar, M. (2009). Editores. Facility Location: Concepts, Models, Algorithms and Case Studies. Physica-Verlag, Heidelberg, Alemania.

Fanjul-Peyro, L. y Ruiz, R. (2010). Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207(1):55–69.

Feo, T.A., y Resende, M.G.C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109–133.

Hansen, P., y Mladenović, N. (1999). An introduction to variable neighborhood search. En: S. Voß, S. Martello, I.H. Osman y C. Roucairol (editores), Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 433–58, Kluwer, Boston, EUA.

Huerta-Muñoz, D.L., Ríos-Mercado, R.Z., y Ruiz, R. (2017). An iterated greedy heuristic for a market segmentation problem with multiple attributes. European Journal of Operational Research, 261(1):75-87.

Kariv, O., y Hakimi, S.L. (1979). An algorithmic approach to network location problems, I: The p-centers. SIAM Journal of Applied Mathematics, 37(3):513–38.

Loosemore, S., Stallman, R.M., McGrath, R., Oram, A., y Drepper, U. (2012). The GNU C Library Reference Manual: For version 2.17. Free Software Foundation.

Lorena, L.A.N., y Senne, E.L.F. (2004). A column generation approach to capacitated p-median problems. Computers & Operations Research, 31(6):863–76.

Lourenço, H.R., Martin, O., y Stützle, T. (2002). Iterated local search. En: F. Glover F y G.A. Kochenberger (editores), Handbook of Metaheuristics, pp. 321–353, Kluwer, Boston, EUA.

Martins, A.X., Duhamel, C., Souza, M.C., Saldanha, R.R., y Mahey, P. (2011). A VND-ILS heuristic to solve the RWA problem. En: J. Pahl, T. Reiners y S. Voß (editores), Network Optimization. Lecture

Notes in Computer Science, vol. 6701, pp. 577–582, Springer, Berlin, Alemania, 2011.

Özsoy, F.A., y Pınar, M.Ç. (2006). An exact algorithm for the capacitated vertex p-center problem. Computers & Operations Research, 33(5):1420–36.

Quevedo-Orozco, D.R., y Ríos-Mercado, R.Z. (2015). Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent. Computers & Operations Research, 62:133–144.

Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer, Heidelberg, Alemania.

Galvão, R. D. y ReVelle, C. (1996). A lagrangean heuristic for the maximal covering location problem. European Journal of Operational Research, 88(1):114–123.

Ríos-Mercado, R.Z., y Escalante, H.J. (2016). GRASP with path relinking for commercial districting. Expert Systems with Applications, 44:102-113.

Ríos-Mercado, R.Z. y Fernández, E. (2009). A reactive GRASP for a commercial territory design problem with multiple balancing requirements. Computers & Operations Research, 36(3):755–776.

Ruiz, R., y Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177 (3):2033–49.

Ruiz, R., y Stützle, T. (2008). An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187(3):1143–59.

Scaparra, M.P., Pallottino, S., y Scutellà, M.G. (2004). Large-scale local search heuristics for the capacitated vertex p-center problem. Networks, 43(4):241–55.

Subramanian, A., Drummond, L.M.A., Bentes, C., Ochi, L.S., y Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11):1899–911.

Urlings, T., Ruiz, R., y Stützle, T. (2010). Shifting representation search for hybrid flexible flowline problems. European Journal of Operational Research, 207(2):1086–95.

DOI: https://doi.org/10.21640/ns.v9i19.1105


  • There are currently no refbacks.

Copyright (c) 2017 Nova Scientia

Nova Scientia, year 9, issue 19, November 2017 – April 2018, is a biannual journal printed by the Universidad De La Salle Bajío, with its address: Av. Universidad 602, Col. Lomas del Campestre, C. P. 37150, León, Gto. México. Phone: (52) 477 7108500, e-mail: http://nova_scientia.delasalle.edu.mx. Chief editor: Ph.D. Rolando Pérez Álvarez and Ph.D. Ramiro Rico Martínez. ISSN 2007 - 0705. Copyright for exclusive use No. 04-2008-092518225500/102, Diffusion rights via computer net 04 - 2008 – 121011584800-203 both granted by the Instituto Nacional del Derecho de Autor.

Editor responsible for updating this issue: Direction of Research Department of the Universidad De La Salle Bajío, last updated on Nov 2th, 2017.