Heurísticas de Construccción Voraces para el Problema de Máxima Cobertura Dinámico.

• Autores: Yadira Rosabal Alfonso, Cynthia Porras Nodarse, Jenny Fajardo Calderín
• Localización: Revista Cubana de Ciencias Informáticas, ISSN-e 2227-1899, Vol. 13, Nº. 4, 2019
• Idioma: español
• Títulos paralelos:
  • Heuristic Constructive Greedy for Dynamic Maximal Covering Location Problem.
• Enlaces
  • Texto completo
• Resumen
  • español

    Los problemas de localización de instalaciones se aplican a una gama amplia de situaciones reales ganando un gran interés en el ámbito de la investigación. El problema de localización de máxima cobertura (MCLP) es uno de los modelos clásicos de la literatura y su objetivo es maximizar la cobertura sobre la demanda de una población con recursos limitados. De este problema se conoce la variante dinámica (DMCLP) que a diferencia del clásico maximiza la cobertura en múltiples períodos. Los métodos aproximados han sido muy utilizados en la resolución del MCLP y sus variantes. Las heurísticas constructivas, clasificadas dentro del grupo de las heurísticas, son muy conocidas por la rapidez en encontrar soluciones de buena calidad de los problemas de localización, utilizadas en ocasiones como solución inicial en los algoritmos metaheurísticos y obteniendo buenos resultados. Para dar solución al DMCLP se proponen en este trabajo cuatro heurísticas constructivas voraces. Se realiza un primer experimento para conocer la heurística más adecuada para el DMCLP. Finalmente, se comparan las mejores heurísticas con el algoritmo metaheurístico Escalador de Colinas empleado en la literatura para resolver el DMCLP.

  • English

    The problems of localization of facilities are applied to a wide range of real situations winning a great interest in the environment of the investigation. The maximal covering location problem (MCLP) it is one of the classic models of the literature and their objective is to maximize the population's covering with limited resources. Of this problem the dynamic variant is known (DMCLP) that maximizes the covering in multiple periods contrary to the classic. The approximate methods have been very used in the resolution of the localization problems and their variants. The heuristic constructive classified inside the group of the heuristic ones they are very well-known for the speed and quality in finding solutions to the localization problems, used in occasions as initial solution in the algorithms metaheuristics, obtaining good results this combination. To give solution to the dynamic pattern they intend in this work four heuristic constructive greedy. they are carried out a first experiment to know which of the heuristic ones outlined it is the most appropriate in the proposed pattern. Finally, it is compared the best heuristic with the algorithm metaheuristics Hill Climbing used in the literature to solve the DMCLP.

• Referencias bibliográficas
  • Zarandi, M. H. F. (2013). The large-scale dynamic maximal covering location problem. Mathematical Computer Modelling. 57. 710
  • Church, R,ReVelle, C. (1974). The maximal covering location problem. Papers of the Regional Science Association. 32. 101
  • Murray, A. T. (2016). Maximal Coverage Location Problem: Impacts, Significance, and Evolution. Internacional Regional Science Review. 39....
  • Curtin, K. (2010). Determining Optimal Police Patrol Areas with Maximal Covering and Backup Covering Location Models. Netw Spat Econ. 10....
  • Guarín, A. (2015). Fast reaction police units in Medellín: A budget-constrained maximal homicide covering location approach. Banco de la República....
  • Chawathe, S. S. (2007). Organizing Hot-Spot Police Patrol Routes. Intelligence and Security Informatics.
  • Tutschku, K. (1998). Demand-based Radio Network Planing of Cellular Mobile Communication System. 1054
  • Erdemir, E. T. (2008). Location coverage models with demand originating from nodes and paths: application to cellular network design. European...
  • Farahani, R. Z. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering.
  • Wei, R,Murray, A. T. (2015). Continuous space maximal coverage: insights, advances and challenges. Computers & Operations Research.
  • Rezazadeh, H. (2018). Robust cooperative maximal covering location problem: a case study of the locating Tele-Taxi stations in Tabriz, Iran....
  • Martí, R. (2006). Procedimientos Metaheurísticos en Optimización Combinatoria. Matemátiques.
  • Murray, A. T,Church, R. L. (1996). Applying Simulated Annealing to Location-planning Models. Journal of Heuristics.
  • Adenso-Díaz, B,Rodríguez, F. (1995). A Simple Search Heuristic for the MCLP: Application to the Location of Ambulance Bases in a Rural Region....
  • Fajardo, J. (2015). Soft Computing en Problemas de Optimización Dinámicos. Universidad de Granada. España.
  • Stutzle, T,Ruiz, R. (2018). Iterated Greedy. IRIDIA-Technical Report Series. Belgium.
  • Talbi, E. G. (2009). Metahueristics: from design to implementation. John Wiley and Sons, Inc.
  • Kuehn, A. A,Hamburger, M. J. (1963). A heuristic program for locating warehouses. Management Science. 9. 643
  • Feldman, E. (1966). Warehouse location under continuous economics of scale. Management Sciences. 12. 670
  • Downs, B. T,Camm, J. D. (1996). An exact algorithm for the maximal covering problem.. Naval Research Logistics Quarterly. 43. 435
  • Xia, L. (2019). An empirical comparison of five efficient heuristics for maximal covering location problems. IEEE/INFORMS International Conference...
  • Dzatora, M,Dzatorb, J. (2015). An Efficient Modified Greedy Algorithm for the P-Median Problem.. 1855
  • Haghani, A. (1996). Capacitated maximum covering location models: Formulations and solution procedures. Journal of Advanced Transportation....
  • Hochbaum, D. S,Pathria, A. (1998). Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics Quarterly....
  • Saldanha, F,Captivo, M. E. (1998). Heuristic approach for the discrete dynamic location problem. Location Science. 6. 1211
  • Indriasari, V. (2008). Integration of Travel Time Zone for Optimal Siting of Emergency Facilities. University Putra. Malaysia.
  • Rodsi, M,Indriasari, V. (2009). Facility Location Models Development to Maximize Total Service Area. Theoretical and Empirical Researches...
  • Pratap, D. (2015). Big Step Greedy Heuristic for Maximum Coverage Problem. International Journal of Computer Applications (0975 - 8887). 125....
  • Bulut, E,Szymanski, B. (2016). Rethinking Offloading WiFi Access Point Deployment from User Perspective. Workshop on Smart Environments &...
  • Schilling, D. (1980). Dynamic Location Modeling for Public-Sector Facilities: A Multicriteria Approach. D. S. 11. 714
  • Gunawardane, G. (1982). Dynamic versions of set covering type public facility location problems. European Journal of Operational Research....
  • Marti, R,Reinel, G. (2011). The Linear Ordering Problem Exact and Heuristics Method in Combinatorial Optimization. Springer.
  • Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research.
  • Friedman, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical...
  • Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics.
  • Finner, H. (1993). On a monotonicity problem in step-down multiple test procedures. Journal of the American Statistical Association.
  • Li, J. (2008). A two-step rejection procedure for testing multiple hypotheses. Journal of Statistical Planning and Inference.
  • García, S. (2009). A study on the use of nonparametric tests for analyzing the evolutionary algorithms behaviour: a case study on the cec2005...
  • Reinelt, G. (1991). TSPLIB.A traveling salesman problem library. ORSA Journal on Computing. 3. 376
  • Bagherinejad, J. (2017). Developing dynamic maximal covering location problem considering capacitated facilities and solving it using hill...