Lightweight computation of overlaid traffic flows by shortest origin-destination trips

Given a network G (V, E), a lightweight method to calculate overlaid origin-destination (O-D) traffic flows on all edges is developed. Each O-D trip shall select the shortest path. While simple implementations for single-source/all-destination and all-pair trips need O (L · n) and O(L · n ² ) in worst-case time complexity, respectively, our technique is executed with O (m + n) and O(m + n ² ), where n = |V|, m = |E|, and L represents the maximum arc length. This improvement is achieved by reusing outcomes of priority queue-based algorithms. Using a GIS dataset of a road network in Tokyo, Japan, the effectiveness of our technique is confirmed.