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

Henry Lamos Díaz, Karin Aguilar Imitola, Melissa Andrea Barreto Robles, Paula Nathalia Niño Niño, Daniel Orlando Martínez Quezada

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

Texto completo:

PDF (English)

Referencias


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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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.

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.

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

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

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.

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.

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

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

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

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

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

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

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.

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.

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.


Enlaces refback

  • No hay ningún enlace refback.


Copyright (c) 2018 INGE CUC

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.


INGE CUC (e-ISSN: 2382-4700, ISSN: 0122-6517) , Universidad de la Costa CUC - 2018.

 

Contador de Visitas: contador de visitas
Flag Counter


Last Updated: 2018-05-30