An Exact Method for Reliable Shortest Path Problems with Correlation
Séminaires scientifiques
Andrés L. Medaglia, Professeur titulaire, Universidad de los Andes, Colombie
Séminaire organisé par le Département de gestion des opérations et de la logistiques
Ouvert à tous.
Salle : Port-au-Prince, 1er étage, section verte, édifice Côte-Sainte-Catherine
Pour informations ou questions : Jorge Mendoza jorge.mendoza@hec.ca
Information sur le conférencier :
With over 20 years of experience, Professor Medaglia develops and applies optimization methodologies in transportation and logistics, healthy and sustainable cities, engineering design, and agricultural systems. His work has resulted in more than 70 peer-reviewed publications in the field of Operations Research (OR). He currently serves on the editorial boards of Computers and Operations Research and Transactions in Operations Research (TOP), among other journals.
Information sur le séminaire :
Shortest path problems often arise in contexts where travel times are uncertain. In these settings, reliable paths are often valued more than paths with lower expected travel times. This has led to several variants of reliable shortest path problems (RSPP) that handle travel time reliability differently. We propose an algorithmic framework for solving RSPPs with nonnegatively correlated travel times and resource constraints. By building upon the flexibility of the pulse algorithm, our unified and exact algorithmic framework solves multiple variants of the RSPP: the -reliable shortest path (-RSP), the maximum probability of on-time arrival (MPOAP) problem, and the shortest -reliable path (S-RP). We derive a bound on the reliability of path travel times and incorporate three pruning strategies: bounds, infeasibility, and dominance, leveraging properties of the normal distribution and nonnegative correlation structures. Computational experiments on large-scale transportation networks (with up to 33,113 nodes and 75,379 arcs) demonstrate the framework's competitive performance, enabling potential real-world applications and extensions to other problems.