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...

Full description

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
id UNIANDES2_82d235096991693016fb789d7cfe4daf
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/55172
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
spelling Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdfinfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Medaglia González, Andrés L.03b46028-bf28-41b2-afea-2c5026b6c2bf400Prakash, A. Arunf066d523-427a-4588-9bb3-bc89e88f5dbf500Yamín Silva, Daniel94ca28b0-3c75-4404-b70e-a824331fdab1500Valencia Arboleda, Carlos FelipeMendoza, Jorge E.2022-02-22T19:52:11Z2022-02-22T19:52:11Z2021http://hdl.handle.net/1992/5517225423.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/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.The problem of finding the most reliable routes on Stochastic and Time-Dependent (STD) networks refers to determining the time-adaptive strategy and a priori path that maximizes the probability of on-time arrival at the destination. To find the Maximum Probability of On-time arrival Strategy on STD networks (MPOS-STD), we present a label-correcting algorithm. We prove the correctness of the method and derive its polynomial time complexity expression. To find the Maximum Probability of On-time arrival Path on STD networks (MPOP-STD), we present an exact method based on an implicit enumeration of the solution space. Several acceleration strategies enhance the algorithm, including a bidirectional search, a network reduction rule, and a more effective dominance criterion. An extensive set of computational experiments over real-world transportation networks show that the algorithms perform well against state-of-the-art methods.Magíster en Ingeniería IndustrialMaestría20 páginasapplication/pdfengUniversidad de los AndesMaestría en Ingeniería IndustrialFacultad de IngenieríaDepartamento de Ingeniería IndustrialOn finding the most reliable routes on stochastic and time-dependent networksTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersionTexthttp://purl.org/redcol/resource_type/TMStochastic time-dependent networksOn-time arrival probabilityTravel time reliabilityMost reliable policyReliable path findingPulse algorithmIngeniería201534064PublicationTHUMBNAIL25423.pdf.jpg25423.pdf.jpgIM Thumbnailimage/jpeg12425https://repositorio.uniandes.edu.co/bitstreams/83c655a4-e02e-4723-966f-4558d7c2a750/downloadba105259b283367a239f54d88f07033aMD53ORIGINAL25423.pdfapplication/pdf514055https://repositorio.uniandes.edu.co/bitstreams/f111038d-1a18-46ef-ba41-8ab46d625df4/downloadf59399135bbbaa8f9f600fa8302f0aa5MD51TEXT25423.pdf.txt25423.pdf.txtExtracted texttext/plain57337https://repositorio.uniandes.edu.co/bitstreams/bcec2e7b-d59f-4664-9437-464b6bea1d8e/download316602e5279d8a59e12a95d4abf7ff85MD521992/55172oai:repositorio.uniandes.edu.co:1992/551722023-10-10 19:19:07.591https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdfopen.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co
dc.title.eng.fl_str_mv On finding the most reliable routes on stochastic and time-dependent networks
title On finding the most reliable routes on stochastic and time-dependent networks
spellingShingle On finding the most reliable routes on stochastic and time-dependent networks
Stochastic time-dependent networks
On-time arrival probability
Travel time reliability
Most reliable policy
Reliable path finding
Pulse algorithm
Ingeniería
title_short On finding the most reliable routes on stochastic and time-dependent networks
title_full On finding the most reliable routes on stochastic and time-dependent networks
title_fullStr On finding the most reliable routes on stochastic and time-dependent networks
title_full_unstemmed On finding the most reliable routes on stochastic and time-dependent networks
title_sort On finding the most reliable routes on stochastic and time-dependent networks
dc.creator.fl_str_mv Yamín Silva, Daniel
dc.contributor.advisor.spa.fl_str_mv Medaglia González, Andrés L.
Prakash, A. Arun
dc.contributor.author.spa.fl_str_mv Yamín Silva, Daniel
dc.contributor.jury.spa.fl_str_mv Valencia Arboleda, Carlos Felipe
Mendoza, Jorge E.
dc.subject.keyword.none.fl_str_mv Stochastic time-dependent networks
On-time arrival probability
Travel time reliability
Most reliable policy
Reliable path finding
Pulse algorithm
topic Stochastic time-dependent networks
On-time arrival probability
Travel time reliability
Most reliable policy
Reliable path finding
Pulse algorithm
Ingeniería
dc.subject.themes.none.fl_str_mv Ingeniería
description 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.
publishDate 2021
dc.date.issued.none.fl_str_mv 2021
dc.date.accessioned.none.fl_str_mv 2022-02-22T19:52:11Z
dc.date.available.none.fl_str_mv 2022-02-22T19:52:11Z
dc.type.spa.fl_str_mv Trabajo de grado - Maestría
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TM
status_str acceptedVersion
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/1992/55172
dc.identifier.pdf.spa.fl_str_mv 25423.pdf
dc.identifier.instname.spa.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.spa.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url http://hdl.handle.net/1992/55172
identifier_str_mv 25423.pdf
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.spa.fl_str_mv eng
language eng
dc.rights.uri.*.fl_str_mv https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.spa.fl_str_mv 20 páginas
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Universidad de los Andes
dc.publisher.program.spa.fl_str_mv Maestría en Ingeniería Industrial
dc.publisher.faculty.spa.fl_str_mv Facultad de Ingeniería
dc.publisher.department.spa.fl_str_mv Departamento de Ingeniería Industrial
institution Universidad de los Andes
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/83c655a4-e02e-4723-966f-4558d7c2a750/download
https://repositorio.uniandes.edu.co/bitstreams/f111038d-1a18-46ef-ba41-8ab46d625df4/download
https://repositorio.uniandes.edu.co/bitstreams/bcec2e7b-d59f-4664-9437-464b6bea1d8e/download
bitstream.checksum.fl_str_mv ba105259b283367a239f54d88f07033a
f59399135bbbaa8f9f600fa8302f0aa5
316602e5279d8a59e12a95d4abf7ff85
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1812134046370627584

Publicaciones similares