Ubicación óptima de unidades de servicio bajo condiciones de capacidad limitada mediante un método metaheurístico

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

Resumen


Introducción. El problema de localización de p-centro capacitado consiste en ubicar p instalaciones y asignar usuarios a cada una de ellas, de tal manera que se minimice la distancia máxima entre cualquier usuario y su instalación asignada, sujeto a la capacidad en la demanda restringida por cada instalación. Este trabajo propone una metodología heurística para la solución del problema; los resultados de la experimentación demuestran la calidad de la heurística propuesta en relación con los métodos existentes en la literatura.         

Método. Se propone una metodología heurística para la solución de este problema, la cual integra varios componentes, tales como un método voraz-adaptativo con una selección probabilística, búsqueda local voraz iterada y una búsqueda descendente por entornos variables.                       

Resultados. La evidencia empírica sobre un conjunto de instancias de localización usualmente utilizadas en la literatura, revela el impacto positivo de cada uno de los componentes desarrollados y de la calidad de la heurística propuesta en relación con los métodos existentes. Por ejemplo, la heurística propuesta pudo encontrar soluciones factibles a todas las instancias probadas, excepto a dos; mientras que el mejor de los otros tres métodos probados falló en 18 de las instancias.                    

Conclusión. Se encontró empíricamente que la heurística propuesta supera a la mejor heurística existente para este problema en términos de calidad de la solución, tiempo de ejecución y confiabilidad en la búsqueda de soluciones factibles en instancias difíciles.

Palabras clave


Investigación de operaciones; Optimización combinatoria; Localización discreta; Problema de p-centro capacitado; Metaheurísticas

Texto completo:

PDF

Referencias


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

Enlaces refback

  • No hay ningún enlace refback.


Copyright (c) 2017 Nova Scientia

Scope

Nova Scientia es una revista multidisciplinaria de acceso abierto, peer reviewed y con una periodicidad semestral editada por la Universidad De La Salle Bajío y tiene como fin difundir los trabajos inéditos y originales de las distintas disciplinas científicas realizados por investigadores nacionales e internacionales con preferencia a aquellas contribuciones que tengan carácter multidisciplinario, interdisciplinario o transdisciplinario; no publica reseñas, revisiones bibliográficas, aplicaciones profesionales, ni artículos de divulgación.


Información Legal

Nova Scientia, año 9, número 18, Mayo – Octubre de 2017, es una publicación semestral editada por la Universidad De La Salle Bajío A. C. Av. Universidad 602, Col. Lomas del Campestre, C. P. 37150, León, Gto. México. Tel. 52 477 7108500, http://novascientia.delasalle.edu.mx/. Editores responsables: Dr. Ramiro Rico Martínez y Dr. Rolando Pérez Álvarez. ISSN 2007 - 0705. Reservas de Derechos al uso Exclusivo No. 04-2008-092518225500/102, Reserva de difusión vía red de cómputo 04 - 2008 – 121011584800-203 ambas otorgadas por el Instituto Nacional del Derecho de Autor.

Responsable de la última actualización de este número: J. Alvarez, Dirección de Investigación de la Universidad De La Salle Bajío, fecha de última actualización: 19 de mayo de 2017.