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

Yoichi Shimakawa, Yohei Kakimoto, Hiroyuki Goto

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)320-323
Number of pages4
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
DOIs
Publication statusPublished - Jan 2019
Externally publishedYes

Keywords

  • GIS
  • Origin-destination trip
  • Road network
  • Shortest path
  • Traffic flow

Fingerprint

Dive into the research topics of 'Lightweight computation of overlaid traffic flows by shortest origin-destination trips'. Together they form a unique fingerprint.

Cite this