Efficient parallel route-planning methods and rerouting to circumvent restrictions

Lab Contact: Dr Timothy G. Griffin
Supervisors: Dr Jagdish J. Modi
Special Resources: None

This should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise.

In the past students have considered rail networks, both underground and overground, minimizing a single parameter such as distance or time, and found an algorithm analogous to matrix multiplication to be suitable for parallel computation [1].

A number of different approaches can be utilised for parallel computation. For example, a modified form of matrix multiplication can be used, 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 to a dataset of your choice, for example, the California road network [2].  The implementation should also include improvements to the efficiency of computation by avoiding large sparse areas in order to minimise data movements. The Cannon or Fox-Otto algorithms [3,4] may be considered for the implementation.

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. 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.

An interesting consideration would be to recompute routes, with certain nodes and edges removed. This may arise, for example, on the California road network, when access to certain segments of the network has been restricted due to a fire hazard or road traffic accident. The problem then becomes one of utilizing the existing predetermined routes and modifying them, rather than recalculating them all again using the initial dataset.

A relatively recent result on the dynamic complexity of graph connectivity may prove to be useful in helping us achieve this goal [6].

References:

[1] Batty M. Parallel Route Planning for the London Underground, Diploma in Computer Science, Computer Laboratory, 2007.

[2] https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm

[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.

[6] Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. 2018. Reachability Is in DynFO. J. ACM 65, 5, Article 33 (August 2018), 24 pages.