Lab Contact: Mark Batty
Supervisor: Jagdish Modi
Special Resources: None
Efficient parallel route planning on the national rail network, with use of the Fox-Otto algorithm.
This should appeal to students interested in the design of parallel
algorithms, but does not assume any previous parallel computing
Various investigations have been made into parallel algorithms for
fastest-route determination, in particular for journeys between London
Underground stations (for example ). These involve a sequence of
operations on route matrices.
Dijkstra’s algorithm (see ) is essentially serial and does not
parallelise well to lead to a performance improvement. An alternative
method involves using an analogue of matrix multiplication, in which
we find the minimum of a sum of weights (route-lengths), instead of
forming a sum of products. By repeatedly ‘multiplying’ the route matrix
with itself, we can find the lengths of the shortest paths between all
pairs of destinations. Since matrix multiplication is a highly parallel
operation, this method is well suited to parallel computation.
The aim of the project is to implement such an algorithm, applying it to
part of the National rail network. Furthermore, if possible to consider
such developments as improving the efficiency of computation by
avoiding large sparse areas in order to minimise data movements using the Fox-Otto algorithm [3,4].
Further developments might include:
The dataset can be downloaded from the Association of Train Operating Companies (ATOC) Rail Industry Data website.
An additional suggestion for the project is to limit
its scope and concentrate on specific rail network operators, to ensure
that the number of nodes to be dealt with is manageable.
- If there are two or more lines through any particular station S
then for journeys via S with a possible change of trains there,
S must be treated as S1, S2, …, one for each line , with
time from, for example, S1 to S2 referring to the expected wait,
calculated from the frequencies of services, when changing
- Identifying and temporarily removing nodes that are not
necessary for computing the shortest paths can reduce the
Parallel computers have as a core structure a set of interconnected
processors. The optimal choice of interconnection for a particular
problem may not always be available. In fact, in practice the
interconnection usually takes place within some sort of plane two-
dimensional lattice. In the consideration of the parallel algorithm, it
would be interesting to explore the features of the two-dimensional
graph arising from the connections between destinations (edges), and
to relate this to the lattice of processor connectivity. If the student is
mathematically inclined, it may be worthwhile to investigate certain
properties possessed by the processor graph, such as degree of
symmetry and homogeneity , as well as the extent to which it can be
embedded in a lattice.
 Batty M. Parallel Route Planning for the London
Underground, Diploma in Computer Science, Computer
 Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms,
second edition, 2003.
 Grama, Gupta, Karypis, Kumar. Introduction to Parallel
Computing, Pearson Education, second edition, 2005.
 Akpan, O. Efficient parallel implementation of the Fox
algorithm. Computer Science Department, Bowie State
 Modi J. Parallel Algorithms and Matrix Computation, OUP,