Resumen

Motivados por aplicaciones en la planificación de evacuaciones, consideramos un problema de optimización de flujo con inversiones de arcos en el que el tiempo de tránsito depende de la orientación del arco. En los problemas considerados, el tiempo de tránsito en un arco puede cambiar cuando se invierte, a diferencia de los problemas considerados en la literatura existente. Ampliando la idea existente de construcción de redes auxiliares para permitir tiempos de tránsito asimétricos en los arcos, presentamos algoritmos de tiempo polinómico fuertemente para resolver el problema de máximo contraflujo dinámico de origen único-destino único y el problema de contraflujo más rápido. Los resultados están respaldados por un experimento computacional en una red vial de Katmandú. También se presenta un algoritmo para resolver el correspondiente problema de contraflujo de llegada más temprana con una complejidad pseudo-polinómica. También se ha discutido el enfoque de contraflujo parcial para los problemas correspondientes.

• Materias:Anillos Modelos dinámicos Teoría de grupos Variedades de curvas Ecuación diferencial
• Subjects:Rings Dynamic models Group theory Varieties of curves Differential Equation
• Palabras claves:Aplicaciones; Planificación de evacuaciones; Optimización del flujo; Inversiones de arco; Tiempo de tránsito; Tiempo de tránsito asimétrico
• Keywords:Applications; Evacuation planning; Optimizing flow; Arc reversals; Transit time; Asymmetric transit time