TY - JOUR
T1 - Lightweight computation of overlaid traffic flows by shortest origin-destination trips
AU - Shimakawa, Yoichi
AU - Kakimoto, Yohei
AU - Goto, Hiroyuki
N1 - Publisher Copyright:
Copyright © 2019 The Institute of Electronics, Information and Communication Engineers
PY - 2019/1
Y1 - 2019/1
N2 - 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 2 ) in worst-case time complexity, respectively, our technique is executed with O (m + n) and O(m + n 2 ), 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.
AB - 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 2 ) in worst-case time complexity, respectively, our technique is executed with O (m + n) and O(m + n 2 ), 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.
KW - GIS
KW - Origin-destination trip
KW - Road network
KW - Shortest path
KW - Traffic flow
UR - http://www.scopus.com/inward/record.url?scp=85059977790&partnerID=8YFLogxK
U2 - 10.1587/transfun.E102.A.320
DO - 10.1587/transfun.E102.A.320
M3 - Article
AN - SCOPUS:85059977790
SN - 0916-8508
SP - 320
EP - 323
JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
IS - 1
ER -