Algoritmos de flujo dinámico eficientes para problemas de planificación de evacuación con inversión parcial de carriles
Autores: Pyakurel, Urmila; Nath, Hari Nandan; Dempe, Stephan; Dhamala, Tanka Nath
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Algoritmos de flujo dinámico eficientes para problemas de planificación de evacuación con inversión parcial de carriles
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Técnica
Planificación de evacuación
Contracorriente
Algoritmos
Flujo dinámico
Contracorriente parcial
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
La técnica de contraflujo ha ganado un enfoque considerable en la investigación de planificación de evacuaciones en los últimos años. En este trabajo, diseñamos algoritmos eficientes para resolver los problemas de flujo máximo, lex-máximo, llegada más temprana y flujo dinámico más rápido con atributos constantes y sus generalizaciones con reconfiguración parcial de contraflujo en el contexto de la planificación de evacuaciones. También se estudian los problemas parciales estáticos de contraflujo, que son fundamentales para los flujos dinámicos. Además, se introduce el modelo de contraflujo con tiempo de tránsito dependiente del flujo en los arcos. Se presenta un algoritmo de tiempo polinómico fuertemente para calcular una solución aproximada del problema de contraflujo parcial más rápido en redes de dos terminales, que se sustenta en cálculos numéricos considerando la red vial de Katmandú como red de evacuación. Nuestros resultados muestran que el tiempo más rápido para evacuar un flujo de valor de 100,000 unidades se reduce en más del 42% utilizando la técnica de contraflujo parcial, y la diferencia es mayor con el aumento en el valor del flujo. Además, la técnica mantiene un registro de las porciones de la red vial no utilizadas por los evacuados.
Descripción
La técnica de contraflujo ha ganado un enfoque considerable en la investigación de planificación de evacuaciones en los últimos años. En este trabajo, diseñamos algoritmos eficientes para resolver los problemas de flujo máximo, lex-máximo, llegada más temprana y flujo dinámico más rápido con atributos constantes y sus generalizaciones con reconfiguración parcial de contraflujo en el contexto de la planificación de evacuaciones. También se estudian los problemas parciales estáticos de contraflujo, que son fundamentales para los flujos dinámicos. Además, se introduce el modelo de contraflujo con tiempo de tránsito dependiente del flujo en los arcos. Se presenta un algoritmo de tiempo polinómico fuertemente para calcular una solución aproximada del problema de contraflujo parcial más rápido en redes de dos terminales, que se sustenta en cálculos numéricos considerando la red vial de Katmandú como red de evacuación. Nuestros resultados muestran que el tiempo más rápido para evacuar un flujo de valor de 100,000 unidades se reduce en más del 42% utilizando la técnica de contraflujo parcial, y la diferencia es mayor con el aumento en el valor del flujo. Además, la técnica mantiene un registro de las porciones de la red vial no utilizadas por los evacuados.