Lab Contact: Mark Batty
Supervisor: Jagdish Modi
Special Resources: None

Efficient parallel calculation of fastest routes on the National rail network.

This should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise. Various investigations have been made into parallel algorithms for fastest-route determination, in particular for journeys between London Underground stations (for example [1]). These involve a sequence of operations on route matrices.

Dijkstra’s algorithm (see [2]) 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, for example by adapting the Cannon or Fox-Otto algorithm [3,4].

Further developments might include:

If there are two or more lines through any particular station S then 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 trains.
Identifying and temporarily removing nodes that are not necessary for computing the shortest paths can reduce the processor connectivity.

The dataset can be built up using this website which provides a station-to-station journey planner. Simply provide the From and To locations and it will calculate an approximate duration. It is therefore possible to calculate the journey time between any two stations in the UK and this can be used to build the required data set for the proposed project. 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.

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 [5], as well as the extent to which it can be embedded in a lattice.

References

[1] Batty M. Parallel Route Planning for the London Underground, Diploma in Computer Science, Computer Laboratory, 2007.
[2] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, second edition, 2003.
[3] Grama, Gupta, Karypis, Kumar. Introduction to Parallel Computing, Pearson Education, second edition, 2005.
[4] Akpan, O. Efficient parallel implementation of the Fox algorithm. Computer Science Department, Bowie State University, 2003.
[5] Modi J. Parallel Algorithms and Matrix Computation, OUP, 1988.