Time-dependent stochastic shortest path(s) algorithms for a scheduled transportation network

Wu, Q, Hartley, JK ORCID: https://orcid.org/0000-0003-0727-9588 and Al-Dabass, D, 2005. Time-dependent stochastic shortest path(s) algorithms for a scheduled transportation network. International Journal of Simulation Systems, Science & Technology, 6 (78), pp. 53-60. ISSN 1473-8031

Preview

Text 188153_5777 Hartley Publisher.pdf Download (195kB) | Preview

Abstract

Following on from our work concerning travellers’ preferences in public transportation networks (Wu and Hartley, 2004), we introduce the concept of stochasticity to our algorithms. Stochasticity greatly increases the complexity of the route finding problem, so greater algorithmic efficiency becomes imperative. Public transportation networks (buses, trains) have two important features: edges can only be traversed at certain points in time and the weights of these edges change in a day and have an uncertainty associated with them. These features determine that a public transportation network is a stochastic and time-dependent network. Finding multiple shortest paths in a both stochastic and time-dependent network is currently regarded as the most difficult task in the route finding problems (Loui, 1983). This paper discusses the use of k-shortest-paths (KSP) algorithms to find optimal route(s) through a network in which the edge weights are defined by probability distributions. A comprehensive review of shortest path(s) algorithms with probabilistic graphs was conducted.

Item Type:	Journal article
Publication Title:	International Journal of Simulation Systems, Science & Technology
Creators:	Wu, Q., Hartley, J.K. and Al-Dabass, D.
Publisher:	United Kingdom Simulation Society
Date:	2005
Volume:	6
Number:	78
ISSN:	1473-8031
Divisions:	Schools > School of Science and Technology
Record created by:	EPrints Services
Date Added:	09 Oct 2015 10:28
Last Modified:	09 Jun 2017 13:30
URI:	https://irep.ntu.ac.uk/id/eprint/13333

Actions (login required)

Edit View

Statistics

Views

Downloads