Lightweight Computation of Overlaid Traffic Flows by Shortest Origin-Destination Trips

• GOTO Hiroyuki

  Hosei University

• KAKIMOTO Yohei

  Hosei University

• SHIMAKAWA Yoichi

  Hosei University

抄録

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.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A (1), 320-323, 2019-01-01

  一般社団法人 電子情報通信学会

キーワード

• road network
• traffic flow
• shortest path
• origin-destination trip
• GIS

詳細情報

• CRID: 1390001288104902272
• NII論文ID: 130007541812
• DOI: 10.1587/transfun.e102.a.320
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E102.A/1/E102.A_320/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可