On finding the most reliable routes on stochastic and time-dependent networks (2021)
El problema de encontrar las rutas más confiables en redes estocásticas y dinámicas (STD) se refiere a determinar la estrategia adaptativa y la ruta a priori que maximizan la probabilidad de llegar a tiempo al destino. Para encontrar la estrategia de probabilidad máxima de llegada a tiempo en redes STD (MPOS-STD), presentamos un algoritmo de basado en etiquetas. Demostramos la corrección del método y derivamos su expresión de complejidad de tiempo polinomial. Para encontrar la ruta de probabilidad máxima de llegada a tiempo en redes STD (MPOP-STD), presentamos un método exacto basado en una enumeración implícita del espacio de solución. Varias estrategias de aceleración mejoran el algoritmo, incluida una búsqueda bidireccional, una regla para reducir el tamaño de la red y un criterio de dominio más eficaz. Unos experimentos computacionales sobre redes de transporte del mundo real muestran que los algoritmos funcionan bien frente a métodos de vanguardia.