On finding the most reliable routes on stochastic and time-dependent networks
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...
- Autores:
-
Yamín Silva, Daniel
- Tipo de recurso:
- Fecha de publicación:
- 2021
- Institución:
- Universidad de los Andes
- Repositorio:
- Séneca: repositorio Uniandes
- Idioma:
- eng
- OAI Identifier:
- oai:repositorio.uniandes.edu.co:1992/55172
- Acceso en línea:
- http://hdl.handle.net/1992/55172
- Palabra clave:
- Stochastic time-dependent networks
On-time arrival probability
Travel time reliability
Most reliable policy
Reliable path finding
Pulse algorithm
Ingeniería
- Rights
- openAccess
- License
- https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
| Summary: | 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. |
|---|