A Novel GPU-Based Approach to Exploit Time-Respectingness in Public Transport Networks for Efficient Computation of Earliest Arrival Time

Abstract

In static temporal networks, the Earliest Arrival Time (EAT) problem is to calculate the earliest possible time of arrival at a set of vertices from a given source vertex. Applications of the EAT problem include designing efficient evacuation planning in dynamic scenarios, optimal journey planning in transport networks, and optimal flow management in supply chains. There exist several solutions for the EAT problem in the literature, however, there is limited work on GPU (Graphics Processing Unit) based solutions to leverage the capabilities of the high throughput accelerator for better performance. Further, there is also a need for more efficient methods to process the inherent earliest arrival dependencies in a transport network. In this paper, we propose a suite of five incremental (GPU) algorithms for the one-to-all Earliest Arrival Time problem in public transport networks. The Selective-check-version is the most optimized approach and hence, the key algorithm. It uses an edge coloring based approach to trace the time-respectingness of paths and processing the in-edges in a sorted order based on their arrival times. Its key characteristic is that it is very fast for the best-case networks where all temporal paths are time-respecting. For the Selective-check version, we observed an average speedup of 6.45 against the Serial Connection-scan algorithm and 2.77 w.r.t. the Edge-version algorithm.

Keywords

• Earliest arrival time
• GPU
• shared memory
• temporal graph
• transport network