Journal homepage http://revistas.unitru.edu.pe/index.php/SSMM SELECCIONES MATEMÁTICAS Universidad Nacional de Trujillo ISSN: 2411-1783 (Online) 2020; Vol. 7(2): 340-353. REVIEW Estado del arte del ruteo de vehı́culos aplicado a desastres naturales en Sudamérica Vehicle routing applied to natural disasters in South América: state of art Flavio Gutiérrez-Guzman∗ , Vladimir Navarro C.† , Jose Rodriguez-Melquiades‡ , Edwar Lujan S.§ and Flabio Gutiérrez S.¶ Received, Jul. 30, 2020 Accepted, Nov. 30, 2020 How to cite this article: Gutierrez-Guzman F., et al. Estado del arte del ruteo de vehı́culos aplicado a desastres naturales en Sudamérica. Se- lecciones Matemáticas. 2020;7(2):340–353. http://dx.doi.org/10.17268/sel.mat.2020.02.15 Resumen En este artı́culo se presenta una revisión de la literatura del Problema de Ruteo de Vehı́culos (VRP) aplicado a desastres naturales en Sudamérica. La revisión se enfoca en los últimos diez años (2009 - 2019), en bases de datos de libre acceso y de pago. el 83 % están en idioma español y el 17 % en ingles. La mayorı́a de trabajos tratan el envı́o y entrega de productos, en menor proporción existen trabajos sobre el problema de programación y ruteo de personal, como por ejemplo, voluntarios, especialistas en logı́stica humanitaria, personal medico, militares. En la revisión se han tomado en cuenta diversas caracterı́sticas del problema, tales como, el tipo de desastre, el modelo VRP utilizado, el método de solución empleado, la utilización o no de parámetros con incertidumbre. El 65 % de investigaciones se encontró en bases de datos de acceso libre, el 83 % son modelos deterministas, el modelo mas utilizado es el VRP clásico, los métodos de solución exactos son los mas utilizados, le siguen las metaheurı́sticas (principalmente los algoritmos genéticos). Se espera que este trabajo sirva para dar una perspectiva general sobre la aplicación del VRP a problemas de desastres, ası́ mismo de servir de antecedentes para trabajos en esta temática. Palabras clave. Problema de ruteo de vehı́culos, VRP, desastres naturales, logı́stica humanitaria. Abstract This paper presents a literature review of the Vehicle Routing Problem (VRP) applied to natural disasters in South America. The review focuses on the last ten years (2009 - 2019), in free access and paid databases. 83% are in Spanish and 17% in English. Most of the investigations deal with shipping and delivery of prod- ucts, but there are also papers on programming and routing of personnel, such as volunteers, humanitarian logistics specialists, medical personnel, and military personnel. In the review, several characteristics of the problem have been taken into account, such as, the type of disaster, the VRP model used, the solution method employed, the use or not of parameters with uncertainty. The 65 % of investigations were found in databases of free access, 83 % are deterministic models, the most used model is the classic VRP, the exact solution methods are the most used, followed by the metaheuristics (mainly the genetic algorithms). It is hoped that this work will serve to give a general perspective on the application of VRP to disaster problems, as well as to serve as a background for work in this area. Keywords . Vehicle routing problem, VRP, natural disasters, humanitarian logistics. ∗Facultad de Ingenieria, Universidad de Piura, Piura, Perú (flavio.j.g.g.p@gmail.com). †Departamento de Matematica, Universidad Nacional de Piura, Piura,Perú (gnavarrov@alumnos.unp.edu.pe). ‡Departamento de Informática, Universidad Nacional de Trujillo, Trujillo, Perú (jrodriguez@unitru.edu.pe). §Escuela de Posgrado, Universidad Nacional de Trujillo, Trujillo, Perú (elujans@unitru.edu.pe). ¶Departamento de Matematica, Universidad Nacional de Piura, Piura, Perú (flabio@unp.edu.pe). 340 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 341 1. Introducción. Los desastres naturales siempre han existido a lo largo de la historia de la humanidad algunas veces distanciados y otras en intervalos de tiempo relativamente cortos. Lamentablemente en la actualidad la posibilidad de ocurrencia de este tipo de desastres se ha incrementado debido a diversos factores que suceden tales como, calentamiento global, crecimiento demográfico, contaminación ambiental, concentración de la población en zonas de riesgo, etc. Sudamérica, ha sufrido desastres naturales, entres estos, el fenómeno del niño costero en el norte del Perú (2017); la avalancha en Mocoa, ubicada al sur de Colombia (2017); el terremoto con tsunami en Chile (2010) y el terremoto en la ciudad de Pisco, en el sur del Peru (2007). Cuando ocurren desastres naturales de gran magnitud, las zonas afectadas requieren ayuda de organi- zaciones públicas y privadas de los paı́ses afectados, además de paı́ses extranjeros y organismos internacio- nales quienes, por solidaridad humanitaria, se esfuerzan por remitir ayuda económica ası́ como productos no perecibles, medicina, ropa, entre otros. La logı́stica humanitaria, es un tipo de logı́stica que se encarga de planificar, ejecutar y controlar el almacenamiento y distribución de productos en la zona afectada. La rapidez y eficiencia del proceso de ayuda a través de la cadena de suministro involucrada, es importante para poder hacer llegar la ayuda a las zonas afectadas en el momento oportuno pues de este modo se evita o disminuye el incremento de muertes por hambruna o por enfermedades [1]. Propuestas de acciones a considerar en casos de emergencias lo encontramos en [2], quienes dividen el proceso en cuatro etapas (Ver Figura 1.1): En la etapa denominada Mitigación se aplican medidas que evitarán la aparición de un desastre o reducirán los impactos en caso de que ocurra; en la segunda etapa, Preparación se planifican las actividades a seguir en caso de un desastre; la siguiente etapa, Respuesta se da cuando ya ocurrió el desastre siendo necesario emplear recursos y planes de emergencia para preservar la vida, la propiedad, el medio ambiente y la estructura social, económica y polı́tica de la comunidad; por último, en la Recuperación se deben de tomar acciones para recuperar la estabilidad y normalidad en la zona del desastre. Figura 1.1: Etapas en la gestión de desastres Adaptado de [3] Los trabajos de investigación publicados, se enfocan en la etapa de Preparación para luego ser aplica- dos en la etapa de Respuesta con el fin de distribuir eficientemente la ayuda hacia las zonas afectadas. Si bien la mayorı́a de trabajos sobre la cadena de suministro en logı́stica humanitaria se enfocan princi- palmente en el envı́o y entrega de bienes [4]; también existen trabajos sobre el problema de programación y ruteo de personal, como por ejemplo, voluntarios, especialistas en logı́stica humanitaria, personal medico, militares [5, 6]. En los últimos años la literatura especializada reporta investigaciones con nuevas propuestas basadas en el diseño de modelos de optimización, en particular problemas de ruteo de vehı́culos (VRP), con el fin de obtener rutas que deben utilizar los vehı́culos de transporte para lograr la óptima distribución de perso- nas, bienes y servicios, que puedan ayudar a los damnificados de los desastres naturales [7]. Revisiones sobre modelos de optimización aplicados a problemas de desastres, se pueden encontrar en [4, 8], en estas revisiones no se han encontrado aplicaciones del VRP a problemas de desastres naturales en Sudamérica. En el artı́culo propuesto se revisa diversos modelos de VRP aplicados a desastres naturales en Su- damérica, siendo los criterios a tener en cuenta: el tipo de desastre, el modelo VRP utilizado, función 342 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 objetivo a optimizar, si los modelos investigados consideran o no parámetros con incertidumbre y los méto- dos de solución. La Sección 2, discute el alcance de la revisión; la Sección 3, presenta la terminologı́a y notaciones usadas; la Seccción 4, muestra los resultados que se obtienen en la investigación y comentarios de cada uno de los documentos encontrados; finalmente las conclusiones en la Sección 5. 2. Alcance de la revisión. En la revisión de las investigaciones se consideró aportes entre los años 2009 y 2019, en los idiomas ingles y español, restringiéndose a artı́culos publicados en revistas cientı́ficas, artı́culos de actas de congresos, capı́tulos de libros y tesis. La búsqueda se realizó en las bases de datos EBSCO, Science Direct, IEEE y Schoolar Google, utilizandose como palabra clave problema de ruteo de vehı́culos combinado con las palabras: desastres naturales, aluvión, terremoto, huracán, tornado, inunda- ción, tsunami, sequı́a, incendio y sus equivalentes en idioma ingles. Los métodos para resolver los modelos de VRP y sus variantes, fueron clasificados en exactos, heurı́sti- cos y metaheurı́sticos. Los métodos exactos obtienen una solución óptima, sin embargo son ineficientes en problemas para grandes escenarios, ya que el tiempo empleado para hallar las soluciones se incrementa considerablemente. Ejemplos de métodos utilizados son la programación lineal entera, programación dinámica, ramificación y acotamiento (Branch and Bound), etc. Las heurı́sticas y metaheurı́sticas aunque no encuentran la solución óptima son ampliamente acepta- dos, ya que permiten encontrar buenas soluciones en tiempos razonables. Las heurı́sticas son métodos de búsqueda local, y entre las dificultades de estos métodos es que pueden quedar atrapados en óptimos locales en el espacio de búsqueda. Las heurı́sticas se clasifican en constructivos, de dos fases y métodos de mejora. Finalmente las metaheuristicas son métodos generales que se adaptan para solucionar problemas par- ticulares, incluyen mecanismos que evitan quedar atrapados en óptimos locales en el espacio de búsqueda. Las mas populares son Algoritmos Genéticos (GA), Algoritmo de Optimización por Enjambre de Partı́culas (PSO), Algoritmo Colonia Artificial de Abejas (Artificial Bee Colony-ABC), Algoritmos Meméticos (MA), Recocido Simulado (SA), Greedy Randomized Adaptive Search Procedures (GRASP) [9, 10]. 3. Terminologı́a y notaciones. 3.1. Desastre.. La Organización Mundial de la Salud (OMS) define un “desastre” como cualquier evento que causa daño, destrucción, alteración ecológica, pérdida de vidas humanas, sufrimiento humano, deterioro de los servicios sanitarios y de salud en una escala suficiente para justificar una respuesta extraor- dinaria desde fuera de la comunidad o área afectada [11]. De acuerdo con el fenómeno que lo origina, los desastres se clasifican en aquellos que son provocados por fenómenos naturales (desastres naturales) y los que se derivan de actividades humanas. Los principales efectos primarios de los desastres son pérdida de vidas y lesiones en la población, la pérdida de bienes, el daño e interrupción de los servicios básicos, los daños en la infraestructura, la desorganización social y fı́sica de la comunidad, y las alteraciones orgánicas y conductuales de las personas [12]. Los desastres naturales son el resultado de variables meteorológicas, geológicas o biológicas que ocu- rren de forma independiente al accionar humano (aunque algunas condiciones pueden verse exacerbadas por el impacto de la civilización en el ecosistema). Algunos desastres naturales son cı́clicos, siguiendo un patrón estacional o geológico que ha sido documentado a través de la historia. Otros eventos, aunque son el resultado de las fuerzas naturales, son tan infrecuentes que su ocurrencia es interpretada como “rareza” de la naturaleza [11]. Estos eventos destructores de la naturaleza crean una demanda masiva de ayuda de socorro que incluyen alimentos, medicinas, refugio, agua y otros recursos los cuales para llegar al lugar del desastre requieren uso de una logı́stica eficiente. Un desastre de gran magnitud genera dificultades para contribuir con la ayuda en las fases de planifi- cación y mitigación. En la fase respuesta, los daños en las vias de comunicación tal como carreteras y las condiciones ambientales complican aún más las operaciones humanitarias. Los desastres ponen a prueba la capacidad de las diferentes operaciones de emergencia en trabajar juntos para ofrecer la mejor ayuda posible. El modelado, simulación y optimización son las principales herramientas para abordar y superar estos desafı́os [11]. La reducción del riesgo de desastres no es una actividad única si no un proceso continuo, que requiere de una planificación previa, es decir, que mediante las instituciones del estado es necesario estar preparados para hacer frente a posibles embates de la naturaleza. Es necesario tener registros históricos de eventos pa- sados para estar preparados ante tipos de desastres comunes en Sudamérica como terremotos, inundaciones pluviales, tsunamis, sismos, etc. Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 343 3.2. Problema de ruteo de vehiculos (VRP). Es un paradigma en la literatura especializada [13] que hace referencia a la asignación óptima de rutas de distribución o abastecimiento, a través de una flota de vehı́culos destinada a transportar la mercancı́a de un punto denominado depósito a otros puntos denomina- dos clientes (Ver Figura 3.1). Es un problema de optimización combinatoria, donde el tiempo de solución del algoritmo no se encuentra ligado a un tiempo polinomial, por el contrario tiene un comportamiento de tipo exponencial haciéndolo desde el punto de vista computacional un problema que pertenece a la clase de problemas NP difı́ciles. El VRP ha tenido un desarrollo importante a partir de su formulación en la segunda Figura 3.1: VRP con 30 clientes, la lı́nea de color azul representa la solución mitad de los años cincuenta; tanto, que hoy existe una gran variedad de clases del mismo, de acuerdo con las variaciones de un problema estándar (clientes, depósitos y flota de vehı́culos). Contextualizando las va- riantes a la logı́stica humanitaria, los usuarios finales o clientes se definen como las poblaciones afectadas por el desastre natural [1]. Los objetivos que persigue el ruteo de vehı́culos son obtener el menor costo total asociado a transporte, menor distancia recorrida, menor tiempo de distribución, entre otras variables, sujetas a los requerimientos de las organizaciones o casos de estudio. La flota de vehı́culos puede ser de tipo homogénea o heterogénea, de acuerdo a la capacidad establecida en relación a las unidades que puede transportar, siendo estas iguales o diferentes respectivamente. Las diferentes variaciones y restricciones del problema generan una “familia” de VRP [14]. Un modelo general de este problema de ruteo es presentado en [15], donde se optimiza las distancias para atender a los clientes, según sea la aplicación, tal como lo muestra la ecuación (3.1). El objetivo se alcanza bajo las condiciones de ruteo (3.2) y (3.3); la ecuación (3.4) evita la formación de subrecorridos. Finalmente en (3.5) se muestra que la variable de recorrido es de tipo binario, es decir, si esta variable obtiene un valor 1 para cada arco en red, significará que se obtiene un recorrido; caso contrario obtendrá un valor 0 lo cual indica que aquellos arcos con este valor no serán parte de la solución. ∑n (3.1) min Z = dijxij (i,j)∈E,i6=j s.a. ∑n (3.2) xij = 1,∀i ∈ V j∈V ∑n (3.3) xij = 1,∀j ∈ V i∈V ∑n (3.4) xij ≥ |S| − V (S), S : S ⊂ N − {1}, |S| ≥ 2 i∈V 344 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 (3.5) xij ∈ {0, 1},∀(i, j) ∈ E, i 6= j Una revisión reciente sobre el estado del arte del VRP, sus variantes, clasificación, métodos de solución y tendencias se puede hallar en [16]. De [13, 14, 17] se han tomado las definiciones de las variantes del VRP encontradas en la revisión. 3.2.1. Problema de ruteo de vehı́culos capacitado (CVRP). El VRP clásico, también conocido como VRP capacitado (CVRP), diseña rutas de entrega óptimas donde cada vehı́culo genera una ruta para atender a los clientes o usuarios, según sea la aplicación a determinar. Para este tipo de ruteo se considera que cada vehı́culo tiene las mismas caracterı́sticas y hay solo un depósito central. El objetivo del CVRP es encontrar un conjunto de rutas de menor costo para que cada cliente sea visitado exactamente una vez por un vehı́culo. La condición para lograr con éxito el objetivo es que cada vehı́culo debe iniciar y terminar su recorrido en el depósito, y no exceder la capacidad de los vehı́culos. 3.2.2. Problema de ruteo de vehı́culos con muchos depósitos (MDVRP). En este tipo de ruteo de vehı́culos, existen varios depósitos (cada uno con una flota de vehı́culos independiente) los cuales deben servir a todos los clientes. Se establece la premisa de que los clientes y los depósitos se encuentran mezcla- dos, de lo contrario podrı́a ser solucionado como problemas VRP independientes. 3.2.3. Problema de ruteo de vehı́culos de dos niveles (2E-VRP). Trata del diseño de rutas en una cadena de suministro de dos niveles, el primero de ellos conecta la carga desde un depósito central hasta su consolidación en depósitos intermedios denominados satélites, y el segundo nivel enlaza la carga de los satélites con el cliente final. 3.2.4. Problema de ruteo de vehı́culos con ventanas de tiempo (VRPTW). Incluye la restricción que cada cliente debe ser visitado durante un intervalo de tiempo denominado ventana, es decir, cada cliente solo esta dispuesto a recibir el bien o servicio durante un periodo de tiempo predeterminado. En este caso existen dos nuevas variantes, siendo el primero denominado ventana de tiempo duro, es decir, se cumple exactamente el intervalo de tiempo programado. Otro caso se le llama ventana de tiempo semisuave, es decir, que el cliente o usuario dá una holgura al proveedor del servicio con el pago de alguna penalidad y otras veces sin pago de penalidad. 4. Resultados. En esta sección, se muestran los resultados de la revisión de 23 trabajos. Si bien la búsqueda se hizo desde el año 2009, solo se encontraron investigaciones desde el año 2014. el 83 % de los documentos estan en idioma español y el 17 % en idioma ingles. En la Figura 4.1, muestra la cantidad de investigaciones realizadas por año, observándose una tendencia de crecimiento positivo, salvo el 2019, posi- blemente por que las bases de datos demoran en actualizar las publicaciones. El 17 % de las investigaciones se encontraron en EBSCO, el 9 % en Science Direct, el 9 % en IEEE y el 65 % restante en Google Schoolar. El 4 % son capı́tulos de libro, el 39 % artı́culos y el 43 % son tesis. Además el 83 % de las investigaciones encontradas utilizan modelos determinı́sticos y el 17 % modelos estocásticos. Figura 4.1: Investigaciones realizadas en los años 2009 - 2019 El VRP clásico se ha ampliado al introducir aspectos o caracterı́sticas de cada desastre, en las Figuras 4.2 y 4.3 se pueden apreciar los porcentajes y la cantidad de investigaciones realizadas según el tipo de VRP a resolver. Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 345 Figura 4.2: Porcentaje de investigaciones según el tipo de VRP Figura 4.3: Número de investigaciones según el tipo de VRP Figura 4.4: Número de investigaciones según la función objetivo. Figura 4.5: Porcentaje de investigaciones según el método de solución. 346 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 Por otro lado, en lo relacionado a la función objetivo de los modelos, el 39 % minimizan costos de operación y el 35 % buscan minimizar el tiempo de operación (Ver Figura 4.4). Respecto a los métodos de solución, según la Figura 4.5, el 48 % han optado por aplicar métodos exactos, el 39 % metaheuristicas y el 13 % las heurı́sticas. La Tabla 4.1, resume el tipo de desastre, variante del VRP, tipo de modelo, el método de solución y los autores que desarrollaron cada investigación. TABLA 4.1: Resumen de las investigaciones VRP en desastres naturales DESASTRE PROBLEMA MODELO MÉTODO DE SOLU- AUTOR CIÓN Terremoto VRP Determinı́stico Método exacto Alva, R. A [18], (2014) General VRP Determinı́stico Método exacto Reyes, L. S. et al. [5], (2014) General 2E-VRP Determinı́stico Método exacto González, E. L. [19], (2014) Inundación VRP Determinı́stico Método exacto Reyes, L. S [20], (2015) Terremoto VRPTW Determinı́stico Metaheurı́stica:MA Melissa Barreto R., & Paula Niño N. [11], (2016) General CVRP Estocástico Método exacto Toro, E. M. et al. [21], (2016) Terremoto VRPTW Determinı́stico Método exacto Pareja, C. A., & Rodriguez, X. M. [22], (2016) Terremoto CVRP Determinı́stico Metaheurı́stica: ABC Barrera, A. R., & Hernandez, A. P. [23], (2016) Terremoto/ VRP Estocástico Metaheurı́stica:SA Cantera, I. E. et al. Inundaciones [24],(2017) General MDVRP Determinı́stico Heurı́stica Gatica, G. et al. [25], (2017) Terremoto VRPTW Determinı́stico Heurı́stica Benavente, R. A., & Cornejo, C. S. [26], (2017) Terremoto VRP Determinı́stico Metaheurı́stica:MA Aguilar, K. J. [27],(2017) Terremoto CVRP Determinı́stico Metaheurı́stica: GA Martinez, D. O. [28],(2017) Incendio VRP Determinı́stico Metaheuristica:GRASP Vitali, J. L. et. al. [29],(2017) Terremoto MDVRP Determinı́stico Método exacto Benavente, R. A. [30], (2018) Inundaciones VRP Estocástico Metaheurı́stica: GA Constantino, D. C. et al. [31],(2018) Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 347 Terremoto CVRP Estocástico Metaheurı́stica: PSO Vesga, D. M., & Villar, S. A. [32],(2018) Terremoto 2E-VRP Determinı́stico Metaheurı́stica: GA Angarita, A. G. [33],(2018) Tsunami VRP Determinı́stico Método exacto Sepúlveda, J. M. et. al [34],(2018) Terremoto VRP Determinı́stico Método exacto Benavente, R. et. al [35],(2018) Sismos/ CVRP Determinı́stico Método exacto Barragán-Acevedo, Terremotos E. et al. [36], (2019) Tsunami VRP Estocástico Método exacto Garcı́a, A. J. [37], (2019) Sequı́a CVRP Determinı́stico Heurı́stica Vieira, Y. E. et al. [38], (2019) La Tabla 4.2, presenta una breve descripción del contenido de cada documento . TABLA 4.2: Comentarios de los documentos incluidos en la revisión TÍTULO COMENTARIO AUTOR Plan de despacho pa- Presenta un trabajo sobre VRP relacionado a la pro- Alva, R. A [18], ra la distribución de blemática surgida en la logı́stica humanitaria, supone (2014) ayuda humanitaria en un terremoto que afecta a las ciudades de Lima y Ca- caso de un terremo- llao. Para la solución del modelo aplica diversos méto- to de gran magnitud dos heurı́sticos y luego Programación Lineal en Lima Metropolita- na y Callao. Modelo matemático Se enfoca en la caracterización y formulación de un Reyes, L. S. et al. para la programa- modelo matemático para el problema de programación [5], (2014) ción de personal y ruteo de personal, relacionado con las operaciones especializado en de atención médica y psicológica, prestación de prime- logı́stica humanitaria ros auxilios y la construcción de albergues en situación post-desastre. post-desastre. El modelo se formuló empleando progra- mación lineal entera mixta; dicho modelo considera la dinámica de la situación, es decir, se considera que la demanda cambia en el tiempo. Un modelo de opti- Busca la configuración óptima y la forma de distribu- González, E. L. mización bi-nivel pa- ción de los productos que son enviados hacia las zo- [19], (2014) ra enviar, recibir y nas afectadas por algún medio de transporte. Además de distribuir ayuda en mostrar la importancia de utilizar un modelo Bi-nivel en especie después de lugar de un modelo de un solo nivel. haber ocurrido un de- sastre natural 348 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 Localización de ins- Se enfoca en determinar soluciones para el problema de Reyes, L. S talaciones y ruteo de localización de un punto de distribución y múltiples al- [20],(2015) personal especializa- bergues considerando el riesgo de inundación, además do en logı́stica huma- del problema de ruteo del personal especializado que nitaria post-desastre- permita aliviar las calamidades médicas y psicológicas caso inundaciones. entre otras, presentes en la población afectada en una situación post-desastre. Toma como caso de estudio la inundación que sufrió el municipio de Santa Lucı́a en el departamento del Atlántico, Colombia en 2010. Un Algoritmo Aborda un problema de localización-ruteo con ventanas Melissa Barreto memético para de tiempo (VRPTW) para llevar a cabo la evacuación R., & Paula Niño el problema de de afectados en caso de un desastre sı́smico en la ciudad N. [11],(2016) localizacion-ruteo de Bucaramanga. Diseñó un algoritmo memético (MA) con ventanas de que hace uso de operadores de búsqueda local, con el tiempo para la aten- objetivo de minimizar el tiempo total de respuesta. ción de desastres sı́smicos en la ciudad de Bucaramanga. Modelo matemático Presenta un nuevo modelo matemático para el proble- Toro, E. M. et al. para resolver el ma de localización y ruteo con flota propia y subcontra- [21], (2016) problema de lo- tada, en el que las restricciones clásicas para evitar los calización y ruteo sub-tours se reemplazan por un conjunto de restriccio- con restricciones de nes que establecen conexiones radiales entre los clientes capacidad conside- y los depósitos, permitiendo resolver de forma exacta rando flota propia y instancias de la literatura especializada usando solvers subcontratada. comerciales; validan los modelos con instancias de la literatura. Determinantes del Diseña un modelo multivariado para identificar los fac- Pareja, C. A., & número de damni- tores determinantes que explican el número de damnifi- Rodriguez, X. ficados por causa cados por causa de un terremoto en la región de Lima y M. [22], (2016) de un terremoto en Callao; asimismo, formula y resuelve un modelo de pro- Lima Metropolitana gramación lineal entera para la distribución de bienes de y Callao y contraste ayuda humanitaria. de medidas de res- puestas a través de modelos de progra- mación lineal entera para la distribución de bienes para ayuda humanitaria. Un algoritmo evolu- Aborda el problema de ruteo de vehı́culos capacita- Barrera, A. R., & tivo para el problema dos(CVRP) para llevar acabo la distribución de recursos Hernandez, A. P. de distribución de re- en caso de un desastre sı́smico en la ciudad de Bucara- [23], (2016) cursos postdesastres manga. Propone un algoritmo de colonia de abejas para sı́smicos en la ciudad minimizar la distancia recorrida. De Bucaramanga. Diseño de planes de Presenta un modelo de ruteo para la gestión del abaste- Cantera, I. E. et contingencia ante de- cimiento y la distribución de la ayuda humanitaria. El al. [24], (2017) sastres naturales: El modelo es resuelto mediante un algoritmo hı́brido en- caso de la distribu- tre un algoritmo metaheurı́stico y un método exacto. Su ción de ayuda hu- trabajo está orientado hacia el diseño de planes de con- manitaria balanceada tingencia ante desastres naturales. y su solución con técnicas de vanguar- dia. Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 349 Una aplicación web, Presenta una aplicación web que asigna los super- Gatica, G. et al. para asignación y ru- depósitos, y luego establece el ruteo que han de seguir [25], (2017) teo de vehı́culos en los vehı́culos para cubrir los centros de distribución. caso de desastres. Además, cumple con un conjunto de buenas prácticas de calidad de software. Plan de ruteo para la Presenta un escenario crı́tico frente a un terremoto de Benavente, R. distribución de ayuda magnitud 8,0 Mw con epicentro frente a Lima, ante el A., & Cor- humanitaria no ali- cual busca realizar la distribución de ayuda humanitaria nejo, C. S. mentaria ante un te- no alimentaria a 1 795 735 damnificados en Lima Me- [26],(2017) rremoto de gran mag- tropolitana y Callao.Evalúa tres heurı́sticas clásicas: el nitud en Lima Metro- algoritmo de ahorros, el método en dos fases y el algo- politana y Callao. ritmo del vecino más cercano. Un modelo mul- Se enfoca en un problema de Localización-ruteo multi- Aguilar, K. J. tiobjetivo De objetivo capacitado y desarrolla un algoritmo memético [27],(2017) localizacion-ruteo para encontrar soluciones al problema, este modelo es para La planeación evaluado con datos de un supuesto sismo en la ciudad logı́stica en la fase de de Bucaramanga. preparación a sismos en Bucaramanga. Diseño de un sistema Presenta el diseño y la implantación del SPT (Sistema Martinez, D. O. De apoyo a la toma de Producción y Transporte), un sistema de apoyo a las [28], (2017) de decisiones-Dss decisiones (DSS) basado en el modelo de transporte. El para la gestion de las SPT se implementa con un software para modelos ge- etapas pre-desastre nerales de red. de sismos en Buca- ramanga, basado en técnicas de apren- dizaje automático (Machine Learning). Bus Routing for Desarrollaron un modelo VRP para el problema de eva- Vitali, J. L. et. al. Emergency Evacua- cuación de personas en autobuses hacia lugares seguros, [29], (2017) tions: The Case of en caso de incendio en la ciudad de Valparaı́so, Chile the Great Fire of Valparaiso Minimización del Presenta una propuesta de la cantidad y ubicación de al- Benavente, R. A. impacto social en la macenes de ayuda humanitaria en Lima Metropolitana y [30], (2018) ayuda humanitaria Callao, ası́ como un plan de distribución de estos bienes ante un sismo en a la población damnificada ante un terremoto con epi- lima metropolitana centro frente a Lima. Simuló un escenario para ejecutar y callao, optimi- la metodologı́a propuesta y se calcularon 9 clústeres en zando la velocidad Lima Metropolitana y Callao con un almacén fijo en ca- de respuesta ante da uno de ellos, y un total de 161 almacenes temporales los sectores damni- dispersos por el territorio mencionado. ficados, mediante el uso de modelos matemáticos en la redistribución de almacenes y un plan de ruteo eficiente. 350 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 Diseño de una Proponen una solución preventiva al problema de Ubi- Constantino, técnica de solución cación-Inventario-Enrutamiento en caso de inundación D. C. et al. para el problema en Colombia, con incertidumbre de tipo estocástica en [31],(2018) de localización- la demanda y el estado de las vı́as de comunicación. inventario-ruteo en Diseñaron y ejecutaron un modelo simheurı́stico (ex- logı́stica humanita- tension de una metaheurı́stica para resolver problemas ria. bajo incertidumbre) basado en Algoritmos Genéticos. Presentan como caso de estudio una inundación en el municipio de Mocoa. Un modelo de pro- Presenta un problema de optimización multi-objetivo Vesga, D. M., gramación estocásti- resuelto por algoritmo de enjambre de partı́culas con & Villar, S. A. co multi-objetivo pa- componente evolutivo para el problema de asignación [32], (2018) ra la entrega de re- de recursos a los albergues temporales en la fase post- cursos a los alber- desastre por sismo en la ciudad de Bucaramanga. gues ante un sismo en la ciudad de Buca- ramanga. Un modelo para la Aborda el problema de localización y ruteo de dos esca- Angarita, A. G. localización de depo- lones (2E-VRP) en la gestión de la cadena de suministro [33],(2018) sitos centrales y ru- humanitaria, formula su problema como un modelo de teo de vehı́culos de programación lineal entera mixta con el objetivo de mi- dos escalones aplica- nimizar el costo total, aplica algoritmos genéticos para do a la distribución obtener la solución en un tiempo razonable. de recursos humani- tarios durante las fa- ses de pre y pos- desastre (2e-Lrp). A decision support Lo autores presentan un sistema de apoyo a las decisio- Sepúlveda, J. system for distribu- nes para desastres naturales, uno de los componentes del M. et. al. [34], tion of supplies in sistema es un modelo VRP para el suministro de ayuda (2018) natural disaster situa- en el transporte de alimentos y/o medicina. El sistema tions. se aplica al caso de estudio hipotético de un Tsunami en la costa de la región del BIO-BIO en Chile. Temporary warehou- Se muestra una propuesta para distribuir ayuda en un es- Benavente, R., ses for an earthquake cenario critico de un terremoto de magnitud 8.0 Mw con & Rojas, J. in San Borja and San epicentro en Lima. Se supone que la población afecta- [35],(2018) Luis, Lima, Peru da deberá acercarse al parque seleccionado para recibir los bienes de ayuda. Primero, se hace una localización de los almacenes temporales luego se aplica un modelo VRP para determinar la ruta óptima de distribución Desarrollo de un mo- Desarrolla un modelo matemático de logı́stica humani- Barragán- delo matemático de taria con resiliencia para la gestión del riesgo en sismos Acevedo, E. et logı́stica humanitaria y terremotos en Caqueza, Cundinamarca en Colombia; al. [36], (2019) con resiliencia para para esto emplea herramientas informáticas para validar la gestión del riesgo el modelo como Open Solver Promodel. en sismos y terremo- tos en Cáqueza, Cun- dinamarca. Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 351 Diseño de un plan Desarrolla el diseño y la simulación de un modelo de un Garcı́a, A. J. de evacuación en ca- plan de evacuación en caso de emergencia por tsunami [37], (2019) so de emergencia por en el distrito La Punta. Trabaja bajo el supuesto de un tsunami en el distri- terremoto de magnitud 8.5 Mw con epicentro en el mar, to La Punta usando frente al Callao. Busca una mejor preparación ante un métodos de optimi- desastre por tsunami para reducir el número de pérdidas zación. a través de optimizar las rutas de escape a utilizar por los vehı́culos de la zona. A procedure to sup- Pocos estudios se ocupan de los desastres lentos, como Vieira, Y. E et al. port the distribution la sequı́a. En este trabajo, se muestra un modelo CVRP [38],(2019) of drinking water for para la distribución de agua a los afectados por la sequı́a, victims of drought: el modelo se aplicó como caso de estudio a una región the case of the Brazi- semi árida de Brasil. lian semi-arid region 5. Conclusiones. • En Sudamérica, el interés de la aplicación del ruteo de vehı́culos aplicado a desastres naturales, ha ocurrido en los últimos seis años (2014 en adelante) y esta incrementándose cada año. • La mayor parte de artı́culos se han encontrado en bases de datos públicas como Google Schoolar, y en menor porcentaje en bases de datos de pago como EBSCO, Science Direct y IEEE. • Si bien la mayorı́a de trabajos se enfocan en el envı́o y entrega de productos, también existen trabajos sobre el problema de programación y ruteo de personal, como por ejemplo, voluntarios, especialistas en logı́stica humanitaria, personal medico, militares. • La mayor de parte de los modelos son determinı́sticos, son pocos los trabajos que consideran parámetros con incertidumbre, posiblemente por ser más complejos para resolverlos. • El VRP clásico es el más utilizado, ya que la mayorı́a de los escenarios post desastre se pueden adaptar con mas facilidad a este modelo. • En la mayoria de los modelos se busca minimizar el tiempo de operación ası́ como los costos de operación, en los desastres naturales, el factor dinero y el tiempo son factores determinantes en la distribución de productos en las zonas afectadas post desastres. • Los métodos de solución mas aplicados son los métodos exactos, para escenarios pequeños y medianos; para escenarios que contempla grandes escenarios, se utilizan las mataheuristicas, de estas, los Algoritmos Genéticos son los mas utilizados. 6. Agradecimientos. Este trabajo ha sido financiado por el Fondo Nacional de Desarrollo Cientı́fico, Tecnológico y de Innovación Tecnológica del Perú (FONDECYT), Proyecto 125-2018-FONDECYT-BM- IADT-AV. ORCID and License Flavio Gutiérrez-Guzman https://orcid.org/0000-0002-1032-9892 Vladimir Navarro C. https://orcid.org/0000-0002-9602-1679 Jose Rodriguez-Melquiades https://orcid.org/0000-0002-4763-4663 Edwar Lujan S. https://orcid.org/0000-0003-0663-4189 Flabio Gutiérrez S. https://orcid.org/0000-0003-0372-3864 This work is licensed under the Creative Commons Attribution-NoComercial-ShareAlike 4.0. Referencias [1] Camacho JF, González EL. Un modelo para enviar, recibir y distribuir ayuda en especie, después de haber ocurrido un desastre natural. Celerinet, 2013;1:27-59. Recuperado de http://eprints.uanl.mx/3279/. [2] Altay N, Green WG. OR/MS research in disaster operations management. Eur. j. of operational research. 2006; 175(1):475-493. doi:10.1016/j.ejor.2005.05.016. [3] Viera O, Moscatelli S, Mercader LT. Logı́stica humanitaria y su aplicación en Uruguay. Gerencia Tec. Informática. 2012; 11(30):47-56. Recuperado de https://biblat.unam.mx/hevila/Gerenciatecnologicainformatica/2012/vol11/no30/4.pdf. [4] Caunhye AM, Nie X, Pokharel S. Optimization models in emergency logistics: A literature review. Socio-Ec. Plan. Sciences. 2012; 46(1):4–13. doi:10.1016/j.seps.2011.04.004. 352 Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 [5] Reyes LS, Quintero-Araújo CL, Torres-Ramos AF. Modelo matemático para la programación de personal especializa- do en logı́stica humanitaria post-desastre. LACCEI. 2014; 1-7. Recuperado de http://www.laccei.org/LACCEI2014- Guayaquil/RefereedPapers/RP108.pdf. [6] Dessouky M, Ordonez F, Jia H, Shen Z. Rapid distribution of medical supplies. In Patient Flow: Reducing Delay in Healthcare Delivery. Springer. 2006. p.309-338. doi:10.1007/978-0-387-33636-7. [7] La Rotta ECG, Yazo OG, Fernández MB. Estado del arte del problema de ruteo de vehı́culos con componentes estocásticos. Rev. Inventum. 2018; 13(24):2. doi:10.26620/uniminuto.inventum.13.24.2018.2-14. [8] Hu H, He J, He X, Yang W, Nie J, Ran B. Emergency material scheduling optimization model and algorithms: A review. J. of traffic and transp. eng. 2019; 6(5):441-454. doi:10.1016/j.jtte.2019.07.001. [9] Laporte G. Fifty years of vehicle routing. Transportation science. 2009; 43(4):408-416. doi:10.1287/trsc.1090.0301. [10] Medina LBR, La Rota ECG, Castro JAO. Una revisión al estado del arte del problema de ruteo de vehı́culos: Evolución histórica y métodos de solución. Ingenierı́a. 2011; 16(2):35-55. Recuperado de https://www.redalyc.org/pdf/4988/498850173004.pdf [11] Barreto MA, Niño PN. Un Algoritmo memético para el problema de localizacion-ruteo con ventanas de tiem- po para la atención de desastres sı́smicos en la ciudad de Bucaramanga [Tesis Doctoral en internet]: Uni- versidad Industrial de Santander, Escuela de estudios industriales y empresariales; 2016). Disponible en http://tangara.uis.edu.co/biblioweb/tesis/2016/165444.pdf [12] Meli R, Bitrán D, Santa CruzS. El impacto de los desastres naturales en el desarrollo: documento metodológi- co básico para estudios nacionales de caso: Comisión económica para América Latina y Caribe; 2005. Recupe- rado de https://www.cepal.org/es/publicaciones/25766-impacto-desastres-naturales-desarrollo-documento-metodologico- basico-estudios. [13] Vagas GG, Aristizábal FG. Metaheurı́sticas aplicadas al ruteo de vehı́culos. Un caso de estudio. Parte 1: formulación del problema. Ing. e Investigación. 2006; 26(3):149-156. Recuperado de https://www.redalyc.org/pdf/643/64326319.pdf. [14] Velásquez YL. Análisis de las caracterı́sticas y aplicaciones de los sistemas de ruteo de vehı́culos[Internet]. 2015; Recuperado de https://repository.unimilitar.edu.co/bitstream/handle/10654/13308/. [15] Liong Y, Wan I, Khairuddin, Zirour M. Vehicle routing problem: Models and solutions. J. of quality measurement and analysis. 2008; 4(1):205–218. Recuperado de http://www.ukm.edu.my/jqma/v4 1/jqma-4-1-paper19.pdf. [16] Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review. Comp. and Indust.l Engineering. 2016; 99:300-313. doi:10.1016/j.cie.2015.12.007. [17] Eitzen H, López-Pires F, Barán B, Sandoya F, Chicaiza JL, Núñez CS. Ruteo de vehı́culos multi-objetivo en dos niveles para logı́stica urbana inteligente. Rev. de la Soc. Cientı́fica del Paraguay. 2018; 23(1):123-138. doi:10.32480/rscp.2018-23- 1.123-138. [18] Alva RA. Plan de despacho para la distribución de ayuda humanitaria en caso de un terremoto de gran magnitud en Lima Metropolitana y Callao[Tesis de Grado]: Pontificia Universidad Católica del Peru; 2014. Recuperado de http://tesis.pucp.edu.pe/repositorio/handle/20.500.12404/6186 [19] González EL. Un modelo de optimización bi-nivel para enviar, recibir y distribuir ayuda en especie después de ha- ber ocurrido un desastre natural[Tesis Doctoral]: Universidad Autónoma de Nuevo León; 2014. Recuperado de http://eprints.uanl.mx/4842/1/1080230785.pdf [20] Reyes LS. Localización de instalaciones y ruteo de personal especializado en logı́stica humanitaria post-desastre-caso inundaciones[Tesis de master]: Universidad de La Sabana; 2015. Recuperado de https://intellectum.unisabana.edu.co/handle/10818/15448 [21] Toro EM, Franco JF, Gallego RA. Modelo matemático para resolver el problema de localización y ruteo con res- tricciones de capacidad considerando flota propia y subcontratada. Ing. invest. y tecnologı́a. 2016; 17(3):357-369. doi:10.1016/j.riit.2016.07.006. [22] Pareja CA, Rodriguez XM. Determinantes del número de damnificados por causa de un terremoto en Lima Metropolita- na y Callao y contraste de medidas de respuestas a través de modelos de programación lineal entera para la distribu- ción de bienes para ayuda humanitaria [Tesis de grado]: Pontificia Universidad Católica del Perú; 2016. Recuperado de http://tesis.pucp.edu.pe/repositorio/handle/20.500.12404/7099. [23] Barrera AR, Hernandez AP. Un algoritmo evolutivo para el problema de distribución de recursos postdesastres sı́smicos en la ciudad De Bucaramanga[Tesis Doctoral]: Universidad Industrial de Santander, Escuela De Estudios Industriales Y Empresariales; 2016. Recuperado de http://tangara.uis.edu.co/biblioweb/tesis/2016/160917.pdf. [24] Cantera IE, Bartolomé AR, Vargas JM. Diseño de planes de contingencia ante desastres naturales: El ca- so de la distribución de ayuda humanitaria balanceada y su solución con técnicas de vanguardia[Internet]. Mexico: Logı́stica y cadena de suministros: Tendencia y desafı́os en México; 2017. Recuperado de http://editorial.upgto.edu.mx/index.php/20 logistica 16/article/view/99. [25] Gatica G, Bolton CC. Venegas N, Opazo O, Linfati R, Escobar J. Una aplicación web, para asignación y ruteo de vehı́culos en caso de desastres. ITECKNE: Innov. e Invest. en Ingenierı́a. 2017; 14(1):62-69. Recuperado de https://dialnet.unirioja.es/servlet/articulo?codigo=5894770 [26] Benavente RA, Cornejo CS. Plan de ruteo para la distribución de ayuda humanitaria no alimentaria an- te un terremoto de gran magnitud en Lima Metropolitana y Callao. LACCEI. 2017; 446. Recuperado de https://dialnet.unirioja.es/servlet/articulo?codigo=7352913. [27] Aguilar KJ. Un modelo multiobjetivo De localizacion-ruteo para La planeación logı́stica en la fase de preparación a sismos en Bucaramanga [Tesis Doctoral]: Universidad Industrial de Santander, Escuela De Estudios Industriales Y Empresariales; 2017. Recuperado de http://tangara.uis.edu.co/biblioweb/tesis/2017/165948.pdf [28] Martinez DO. Diseño de un sistema De apoyo a la toma de decisiones-Dss para la gestion de las etapas pre-desastre de sismos en Bucaramanga, basado en técnicas de aprendizaje automático (Machine Learning)[Tesis Doctoral]: Universidad Industrial de Santander, Escuela De Estudios Industriales Y Empresariales; 2017. [29] Vitali JL, Riff MC. Montero E. Bus Routing for emergency evacuations: The case of the Great Fire of Valparaiso. In 2017 IEEE Congress on Evolutionary Computation (CEC). 2017. p 2346-2353. doi:10.1109/CEC.2017.7969589. [30] Benavente RA. Minimización del impacto social en la ayuda humanitaria ante un sismo en lima metropolitana y callao, op- timizando la velocidad de respuesta ante los sectores damnificados, mediante el uso de modelos matemáticos en la re- distribución de almacenes y un plan de ruteo eficiente [Tesis de Master]: Pontificia Universidad Católica del Perú; 2018. Recuperado de http://tesis.pucp.edu.pe/repositorio/handle/20.500.12404/12427. [31] Constantino DC, Coronado DA, Herrera Ortı́z DC, Wilches AY. Diseño de una técnica de solución para el problema de localización-inventario-ruteo en logı́stica humanitaria[Tesis de grado]. Colombia: Pontificia Universidad Javeria- na; 2018. Recuperado de https://repository.javeriana.edu.co/ bitstream/handle/ 10554/44721/ ConstantinoDeLaEsprie- Gutierrez-Guzman F., et al.- Selecciones Matemáticas. 2020; Vol. 7(2): 340-353 353 lla2019.pdf?sequence=4&isAllowed=y [32] Vesga DM, Villar SA. Un modelo de programación estocástico - objetivo para la entrega de recursos a los albergues ante un sismo en la ciudad de Bucaramanga[Tesis Doctoral]: Universidad Industrial de Santander, Escuela De Estudios Industriales Y Empresariales; 2018. Recuperado de http://tangara.uis.edu.co/biblioweb/tesis/2018/172917.pdf [33] Angarita AG. Un modelo para la localización de depositos centrales y ruteo de vehı́culos de dos escalones apli- cado a la distribución de recursos humanitarios durante las fases de pre y pos-desastre (2e-Lrp) [Tesis Docto- ral]: Universidad Industrial de Santander, Escuela De Estudios Industriales Y Empresariales; 2018. Recuperado de http://tangara.uis.edu.co/biblioweb/tesis/2018/173637.pdf [34] Sepúlveda JM, Arriagada IA, Derpich I. A decision support system for distribution of supplies in natural disaster situa- tions. In 2018 7th International Conference on Computers Communications and Control (ICCCC); 2018. p 295-30. doi:10.1109/ICCCC.2018.8390474. [35] Benavente R, Rojas J. Temporary warehouses for an earthquake in San Borja and San Luis, Lima[Internet]. LACCEI. 2018. Recuperado de http://www.laccei.org/LACCEI2018-Lima/full papers/FP172.pdf [36] Barragán-Acevedo E, Castañeda LB, Fuentes EA. Desarrollo de un modelo matemático de logı́stica humanitaria con resiliencia para la gestión del riesgo en sismos y terremotos en Cáqueza, Cundinamarca. Ing. Solidaria. 2019; 15(27):1–33. doi: 10.16925/2357-6014.2019.01.02. [37] Garcı́a AJ. Diseño de un plan de evacuación en caso de emergencia por tsunami en el distrito La Punta usan- do métodos de optimización [Tesis de grado]: Pontificia Universidad Católica del Perú; 2019. Recuperado de http://tesis.pucp.edu.pe/repositorio/handle/20.500.12404/14019 [38] Vieira YE, Bandeira RA, Lopes LA, Júnior OSS, Júnior MMB. A procedure to support the distribution of drinking wa- ter for victims of drought: the case of the Brazilian semi-arid region. Transp. Research Procedia. 2019; 47:331-339. doi:10.1016/j.trpro.2020.03.106