Optimal location of capacitated service units through a metaheuristic optimization approach

Authors

  • Roger Z. Ríos Mercado Universidad Autónoma de Nuevo León
  • Dagoberto R. Quevedo Orozco SINTEC

DOI:

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

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Roger Z. Ríos Mercado, Universidad Autónoma de Nuevo León

Labora actualmente como Profesor Titular A en la División de Posgrado en Ingeniería de Sistemas de la FIME de la UANL.  Recibió sus títulos de Doctor y Maestro en Ciencias en Investigación de Operaciones e Ingeniería Industrial de la Universidad de Texas en Austin, y su título de Lic. en Matemáticas de la UANL.  Sus áreas de interés se enfocan en el campo de la Investigación de Operaciones como soporte científico a los problemas de toma de decisiones.  Su énfasis es en la investigación y desarrollo de modelos y algoritmos eficientes para la solución de problemas de Optimización Combinatoria, en particular en problemas de localización, diseño territorial, ruteo y transporte, secuenciación de operaciones, con aplicaciones recientes en la gestión óptima de sistemas forestales y de salud pública, en sistemas de manufactura y sistemas de redes de transporte de gas natural.  Es miembro del Sistema Nacional de Investigadores (Nivel II), de la Academia Mexicana de Ciencias, de la Academia Mexicana de Computación y líder del Cuerpo Académico de "Optimización Metaheurística" de la UANL.  Más sobre su obra científica puede encontrarse en:  < http://yalma.fime.uanl.mx/~roger/ >.

Dagoberto R. Quevedo Orozco, SINTEC

Es actualmente analista de la empresa SINTEC, desarrollando modelos y software para problemas de optimización logística a nivel nacional y latinoamérica. Recibió su títulos de Maestro en Ciencias en Ingeniería de Sistemas de la UANL y su título de Ingenierio en Sistemas Computacionales del Instituto Tecnológico de Tepic.  Durante sus estudios de posgrado, llevo a cabo estancias de investigación en Lehigh University y University of Texas at Austin, en EUA.

References

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.

Published

2017-08-22

How to Cite

Ríos Mercado, R. Z., & Quevedo Orozco, D. R. (2017). Optimal location of capacitated service units through a metaheuristic optimization approach. Nova Scientia, 9(19), 329–347. https://doi.org/10.21640/ns.v9i19.1105

Issue

Section

Natural Sciences and Engineering

Metrics

Most read articles by the same author(s)

Similar Articles

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > >> 

You may also start an advanced similarity search for this article.