Reliable Shortest Path Problems in Networks under Uncertainty: Models, Algorithms and Applications

Link travel times in congested urban road networks are highly stochastic. Many empirical studies have found that travellers on such networks prefer to choose reliable shortest paths (RSP) for their travel so that they can arrive at destinations with a higher on-time arrival probability. Therefore, it is necessary to investigate the problems of finding these RSP in realistic road networks with travel time uncertainties.;In the literature, few effective and efficient algorithms have been recorded. This is mainly due to the non-additive objective function of the RSP problems. Classical shortest path algorithms, built on the additive property, cannot be used to solve the RSP problems.;In this thesis, a multi-criteria shortest path-finding model is proposed to tackle the non-additive difficulty involved in RSP problems. Several dominance conditions of the RSP problems are established to enable the use of efficient multi-criteria A* algorithms for solving the RSP problems in stochastic stationary networks with and without travel time spatial correlations. The proposed RSP model and solution algorithm are then extended to stochastic time-dependent (STD) networks where link travel time distributions vary with time-of-day. The stochastic first-in-first-out property of travel times in STD networks is investigated and discussed. The applicability of the proposed RSP model and solution algorithms are illustrated in three transportation applications, including route guidance system, reliability-based traffic assignment and network vulnerability analysis.