Determining rail network accessibility
Ben J. Waterson · ePrints Soton (University of Southampton) · 2010
The usual representation of optimal path finding problems within transport networks is focused on well established algorithms for identifying the optimal path (or set of paths) between two specific network nodes. When the required solution is the identification of the optimal route between every possible pair of nodes in the network however, these algorithms are inefficient. The Floyd-Warshall algorithm provides an efficient way to compare all possible paths through each pair of nodes more efficiently, requiring only N3 comparisons for a network of N nodes. To illustrate the potential of this approach to network analysis within transport research, this paper considers the issue of determining accessibility between railway stations (on the route between Weymouth and London Waterloo) served by a mixture of high-speed and stopping services. A rail network is physically defined by the locations of tracks, but travel times are also dependent on whether stations are visited by high-speed services as well as stopping services. A single rail route therefore has to be represented not as a (topologically) straight line, but as a more traditional graph with high connectivity between nodes. Reformulating this into a matrix-based definition allows the Floyd-Warshall algorithm to efficiently determine the optimal routing (and hence travel times) between