Un algoritmo memético para el problema de localización-ruteo con ventanas de tiempo para la atención de desastres sísmicos: un caso de estudio de Bucaramanga, Colombia

Resumen

Introducción: En años recientes gran parte de la población ha sido afectada por desastres tanto naturales como antrópicos. Por esto, la planificación de la evacuación juega un papel importante en la reducción del número de víctimas ante un desastre natural. Objetivo: Con el propósito de contribuir a los estudios actuales desde la investigación de operaciones en gestión de desastres, esta investigación aborda la planificación de la evacuación de áreas urbanas usando buses para recoger afectados. Metodología: El problema se modela mediante un problema de localización-ruteo con ventanas de tiempo (LRPTW) para determinar el número y la ubicación de los albergues las y rutas de recolección para evacuación, cumpliendo restricciones en tiempo de atención. Para solucionar el LRPTW, se diseña un algoritmo memético (MA) que minimiza el tiempo total de respuesta en la evacuación. El algoritmo es validado en instancias de la literatura y mediante un caso de estudio de un evento sísmico en Bucaramanga (Colombia). Resultados y conclusiones: La contribución principal de este artículo es el desarrollo de un MA para solucionar el modelo propuesto, que permite resolver instancias de tamaño real. La inicialización híbrida del MA evita una convergencia temprana, combinando aleatoriedad con una técnica heurística. Los resultados computacionales indican que el MA es un enfoque viable para solucionar el LRPTW. Así mismo, se presenta un caso de estudio en Bucaramanga para validar el modelo propuesto. Se plantean dos escenarios de desastre, evidenciando que el tratamiento que se da a las ventanas de tiempo (homogénea o aleatoria) influye directamente en la solución y afecta la función objetivo. Desde un enfoque práctico, el problema debe considerar otros criterios que pueden influir en la planificación de la evacuación, como el costo de la evacuación, costo de la demora en la atención, costo de apertura y de ruteo.
Palabras clave: Logística humanitaria, evacuación, terremoto, problema de localización-ruteo, ventanas de tiempo, algoritmo memético

Referencias

[1] EM-DAT The International Disaster Database, "Centre for Research on the Epidemiology of Disasters-CRED." [Online]. Available: http://www.emdat.be/.

[2] J. Holguín-Veras, M. Jaller, L. N. Van Wassenhove, N. Pérez, and T. Wachtendorf, "On the unique features of post-disaster humanitarian logistics," J. Oper. Manag., vol. 30, no. 7–8, pp. 494–506, 2012. https://doi.org/10.1016/j.jom.2012.08.003

[3] FEMA, "Guide for All-Hazard Emergency Operations Planning," 1996.

[4] N. Altay and W. G. Green, "OR/MS research in disaster operations management," Eur. J. Oper. Res., vol. 175, no. 1, pp. 475–493, 2006.https://doi.org/10.1016/j.ejor.2005.05.016

[5] A. M. Anaya-Arenas, J. Renaud, and A. Ruiz, "Relief distribution networks: a systematic review," Ann. Oper. Res., no. April, pp. 53–79, 2014.https://doi.org/10.1007/s10479-014-1581-y

[6] G. Galindo and R. Batta, "Review of recent developments in OR/MS research in disaster operations management," Eur. J. Oper. Res., vol. 230, no. 2, pp. 201–211, 2013.https://doi.org/10.1016/j.ejor.2013.01.039

[7] G. Kovács and K. M. Spens, "Humanitarian logistics in disaster relief operations," Int. J. Phys. Distrib. Logist. Manag., vol. 37, no. 2, pp. 99–114, 2007.https://doi.org/10.1108/09600030710734820

[8] N. C. Simpson and P. G. Hancock, "Fifty Years of Operational Research and Emergency Response," J. Oper. Res. Soc., vol. 60, pp. s126–s139, 2009.https://doi.org/10.1057/jors.2009.3

[9] L. E. De la Torre, I. S. Dolinskaya, and K. R. Smilowitz, "Disaster relief routing: Integrating research and practice," Socioecon. Plann. Sci., vol. 46, no. 1, pp. 88–97, 2012.https://doi.org/10.1016/j.seps.2011.06.001

[10] A. M. Caunhye, X. Nie, and S. Pokharel, "Optimization models in emergency logistics: A literature review," Socioecon. Plann. Sci., vol. 46, no. 1, pp. 4–13, 2012.https://doi.org/10.1016/j.seps.2011.04.004

[11] T. YAMADA, "A network flow approach to a city emergency evacuation planning," Int. J. Syst. Sci., vol. 27, no. 10, pp. 931–936, Oct. 1996.https://doi.org/10.1080/00207729608929296

[12] Q. Lu, B. George, and S. Shekhar, "Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results," Springer, Berlin, Heidelberg, 2005, pp. 291–307.

[13] Y.-C. Chiu, H. Zheng, J. Villalobos, and B. Gautam, "Modeling no-notice mass evacuation using a dynamic traffic flow optimization model," IIE Trans., vol. 39, no. 1, pp. 83–94, Jan. 2007. https://doi.org/10.1080/07408170600946473

[14] F. Sayyady and S. D. Eksioglu, "Optimizing the use of public transit system during no-notice evacuation of urban areas," Comput. Ind. Eng., vol. 59, no. 4, pp. 488–495, Nov. 2010. https://doi.org/10.1016/j.cie.2010.06.001

[15] D. R. Bish, "Planning for a bus-based evacuation," OR Spectr., vol. 33, no. 3, pp. 629–654, 2011.https://doi.org/10.1007/s00291-011-0256-1

[16] M. Goerigk, B. Grün, and P. Heßler, "Branch and bound algorithms for the bus evacuation problem," Comput. Oper. Res., vol. 40, no. 12, pp. 3010–3020, 2013.https://doi.org/10.1016/j.cor.2013.07.006

[17] D. R. Bish, H. D. Sherali, and A. G. Hobeika, "Optimal evacuation planning using staging and routing," J. Oper. Res. Soc., vol. 65, no. 1, pp. 124–140, 2014. https://doi.org/10.1057/jors.2013.3

[18] M. Goerigk and B. Grün, "A robust bus evacuation model with delayed scenario information," OR Spectr., vol. 36, no. 4, pp. 923–948, Oct. 2014. https://doi.org/10.1007/s00291-014-0365-8

[19] M. Goerigk, B. Grün, and P. Heßler, "Combining bus evacuation with location decisions: A branch-and-price approach," Transp. Res. Procedia, vol. 2, pp. 783–791, 2014. https://doi.org/10.1016/j.trpro.2014.09.088

[20] S. Salhi and G. K. Rand, "The effect of ignoring routes when locating depots," Eur. J. Oper. Res., vol. 39, no. 2, pp. 150–156, Mar. 1989. https://doi.org/10.1016/0377-2217(89)90188-4

[21] M. Drexl and M. Schneider, "A Survey of the Standard Location-Routing Problem," 2014.

[22] H. Min, V. Jayaraman, and R. Srivastava, "Combined location- routing problems: A synthesis and future research directions," Eur. J. Oper. Res., vol. 108, no. 1, pp. 1–15, 1998. https://doi.org/10.1016/S0377-2217(97)00172-0

[23] G. Nagy and S. Salhi, "Location-routing: Issues, models and methods," Eur. J. Oper. Res., vol. 177, no. 2, pp. 649–672, Mar. 2007.https://doi.org/10.1016/j.ejor.2006.04.004

[24] C. Prodhon and C. Prins, "A survey of recent research on location-routing problems," Eur. J. Oper. Res., vol. 238, no. 1, pp. 1–17, Oct. 2014. https://doi.org/10.1016/j.ejor.2014.01.005

[25] K. Govindan, a. Jafarian, R. Khodaverdi, and K. Devika, "Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food," Int. J. Prod. Econ., vol. 152, pp. 9–28, Jun. 2014. https://doi.org/10.1016/j.ijpe.2013.12.028

[26] A. Ceselli, G. Righini, and E. Tresoldi, "Combined location and routing problems for drug distribution," Discret. Appl. Math., vol. 165, pp. 130–145, Mar. 2014. https://doi.org/10.1016/j.dam.2013.07.016

[27] R. Caballero, M. González, F. M. Guerrero, J. Molina, and C. Paralera, "Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia," Eur. J. Oper. Res., vol. 177, no. 3, pp. 1751–1763, Mar. 2007. https://doi.org/10.1016/j.ejor.2005.10.017

[28] S. Alumur and B. Y. Kara, "A new model for the hazardous waste location-routing problem," Comput. Oper. Res., vol. 34, no. 5, pp. 1406–1423, 2007. https://doi.org/10.1016/j.cor.2005.06.012

[29] J. Ahn, O. de Weck, Y. Geng, and D. Klabjan, "Column generation based heuristics for a generalized location routing problem with profits arising in space exploration," Eur. J. Oper. Res., vol. 223, no. 1, pp. 47–59, Nov. 2012. https://doi.org/10.1016/j.ejor.2012.06.018

[30] W. Yi and L. Özdamar, "A dynamic logistics coordination model for evacuation and support in disaster response activities," Eur. J. Oper. Res., vol. 179, no. 3, pp. 1177–1193, Jun. 2007. https://doi.org/10.1016/j.ejor.2005.03.077

[31] S. Li and H. Zhou, "Optimization model of fuzzy location routing problem of victim search in flood disaster," J. Chem. Pharm. Res., vol. 6, no. 6, pp. 2080–2085, 2014.

[32] A. Pramudita, E. Taniguchi, and A. Qureshi, "Location and Routing Problems of Debris Collection Operation after Disasters with Realistic Case Study," Procedia - Soc. Behav. Sci., vol. 125, pp. 1–15, 2014. https://doi.org/10.1016/j.sbspro.2014.01.1487

[33] S. V. Ukkusuri and W. F. Yushimito, "Location Routing Approach for the Humanitarian Prepositioning Problem," Transp. Res. Rec. J. Transp. Res. Board, vol. 2089, no. 1, pp. 18–25, 2009. https://doi.org/10.3141/2089-03

[34] R. Tavakkoli-Moghaddam, a. Makui, and Z. Mazloomi, "A new integrated mathematical model for a bi-objective multi-depot location-routing problem solved by a multiobjective scatter search algorithm," J. Manuf. Syst., vol. 29, no. 2–3, pp. 111–119, 2010. https://doi.org/10.1016/j.jmsy.2010.11.005

[35] Z. Mingang, C. Zengshou, and W. Xiaoyan, "Research on location-routing problem of relief system based on emergency logistics," in Industrial Engineering and Engineering Management, 2009. IE&EM'09. 16th International Conference on, 2009, pp. 228–232. https://doi.org/10.1109/ICIEEM.2009.5344599

[36] S. Li, Z. Ma, and B. Zheng, "Dynamic multi-objective location- routing problem in post-earthquake logistics system," J. Chem. Pharm. Res., vol. 6, no. 6, pp. 1515–1520, 2014.

[37] S. Hua-li, W. Xun-qing, and X. Yao-feng, "A Bi-level Programming Model for a Multi-facility Location-Routing Problem in Urban Emergency System," in Engineering Education and Management, Springer Berlin Heidelberg, 2012, pp. 75–80.

[38] L. Alçada-Almeida, L. Tralhão, L. Santos, and J. Coutinho- Rodrigues, "A multiobjective approach to locate emergency shelters and identify evacuation routes in urban areas," Geogr. Anal., vol. 41, no. 1, pp. 9–29, 2009. https://doi.org/10.1111/j.1538-4632.2009.00745.x

[39] J. Coutinho-Rodrigues, L. Tralhão, and L. Alçada-Almeida, "Solving a location-routing problem with a multiobjective approach: the design of urban evacuation plans," J. Transp. …, vol. 22, pp. 206–218, May 2012. https://doi.org/10.1016/j.jtrangeo.2012.01.006

[40] M. Goerigk, K. Deghdak, and P. Heßler, "A comprehensive evacuation planning model and genetic solution algorithm," Transp. Res. Part E Logist. Transp. Rev., vol. 71, pp. 82–97, 2014.

[41] E. Nikbakhsh and S. H. Zegordi, "A Heuristic Algorithm and a Lower Bound for the Two-Echelon Location-Routing Problem with Soft Time Window Constraints," vol. 17, no. 1, pp. 36–47, 2010.

[42] H. I. Gündüz, "The Single-Stage Location-Routing Problem with Time Windows," pp. 44–58, 2011. https://doi.org/10.1007/978-3-642-24264-9_4

[43] M. H. Fazel Zarandi, A. Hemmati, S. Davari, and I. Burhan Turksen, "Capacitated location-routing problem with time windows under uncertainty," Knowledge-Based Syst., vol. 37, pp. 480–489, Jan. 2013. https://doi.org/10.1016/j.knosys.2012.09.007

[44] R. SONG, S. HE, and L. ZHANG, "Optimum Transit Operations during the Emergency Evacuations," J. Transp. Syst. Eng. Inf. Technol., vol. 9, no. 6, pp. 154–160, Dec. 2009. https://doi.org/10.1016/S1570-6672(08)60096-3

[45] L. Zhu, D. Hu, X. Wei, and X. Chen, "Solving the LRPTW Based on Tabu Search Algorithm," in ICLEM 2014, 2014, pp. 904–909.

[46] I. Karaoglan and F. Altiparmak, "A memetic algorithm for the capacitated location-routing problem with mixed backhauls," Comput. Oper. Res., vol. 55, pp. 200–216, 2014. https://doi.org/10.1016/j.cor.2014.06.009

[47] C. Prodhon, "Le Problème de Localisation-Routage,"2006.

[48] C. E. Coral-Gomez, "La convergencia de placas en el noroccidente Suramenricao y el origen del nido de bucaramanga," Rev. Acad. Colomb. Ciencias Exactas, Flsicas y Nat., vol. 17, no. 66, pp. 521–529, 1990.

[49] A. Barrera Navarro and A. Gomez Hernandez, "Un algoritmo evolutivo para el problema de distribución de recursos post-desastres sísmicos en la ciudad de Bucaramanga.," Universidad Industrial de Santander, 2016.

[50] E. Maldonado and G. Chio, "Identificación de las zonas sísmicas más vulnerables en la ciudad de Bucaramanga," UIS Ing., vol. 4, no. 2, pp. 99–116, 2005.

Acerca de los Autores

Henry Lamos Díaz, Universidad Industrial de Santander. Bucaramanga (Colombia).
Henry Lamos Díaz graduated in PhD. in Mathematical Physics in 1997 from Moscow State University (LOMONOSOV), Russia; MSc in Informatics in 1990 from the Industrial University of Santander, Colombia; MSc. in Mathematics in 1982 from the University of Friendship, Moscow, Russia, and Mathematics in 1981 from the University of Friendship, Moscow, Russia. He is a research professor at OPALO Research Group. He is a member of the Colombian Association of Operations Research ASOCIO and an associate professor at the Industrial University of Santander in which he is also adjunct professor in the School of Industrial and Business Studies. https://orcid.org/0000-0003-1778-9768 
Karin Aguilar Imitola, Universidad Industrial de Santander. Bucaramanga (Colombia).
Karin Aguilar Imitola received the title of MSc in Industrial Engineering and of Industrial Engineer from the Industrial University of Santander. Member of the OPALO Research group and adjunct professor to the School of Industrial and Business Studies. Her research interests include research applications of operations in humanitarian logistics, optimization and vehicle routing. http://orcid.org/0000-0001-9776-4258 
Melissa Andrea Barreto Robles, Universidad Industrial de Santander. Bucaramanga (Colombia).
Melissa Barreto received the title of Industrial Engineer from the Industrial University of Santander (Bucaramanga, Colombia) in 2016. Her research interests include operations research, optimization, metaheuristics, production planning and programming. Currently, she is a project analyst at Penagos Hermanos y Cía S.A.S. http://orcid.org/0000-0002-5365-6113
Paula Nathalia Niño Niño, Universidad Industrial de Santander. Bucaramanga (Colombia).
Paula N. Niño received the title of Industrial Engineer from the Industrial University of Santander (Bucaramanga, Colombia). Her research interests include operations research, optimization, metaheuristics, production planning and programming. http://orcid.org/0000-0002-5638-0853
Daniel Orlando Martínez Quezada, Universidad Industrial de Santander. Bucaramanga (Colombia).
Daniel Orlando Martínez-Quezada received his Master’s degree in Industrial Engineering in 2017 and his Industrial Engineering degree in 2014, both from the Industrial University of Santander, Colombia. Currently, he is a professor affiliated to the OPALO research group, and an adjunct professor in the School of Industrial and Business Studies of the Industrial University of Santander. http://orcid.org/0000-0002-9910-1770
Publicado
2018-01-01
Cómo citar
Lamos Díaz, H., Aguilar Imitola, K., Barreto Robles, M., Niño Niño, P., & Martínez Quezada, D. (2018). Un algoritmo memético para el problema de localización-ruteo con ventanas de tiempo para la atención de desastres sísmicos: un caso de estudio de Bucaramanga, Colombia. INGE CUC, 14(1), 75-86. https://doi.org/10.17981/ingecuc.14.1.2018.7
Sección
ARTÍCULOS