Abstract

We investigate the problem of optimal route planning for massive-scale trips: Given a traffic-aware road network and a set of trip queries Q, we aim to find a route for each trip such that the global travel time cost for all queries in Q is minimized. Our problem is designed for a range of applications such as traffic-flow management, route planning and congestion prevention in rush hours. The exact algorithm bears exponential time complexity and is computationally prohibitive for application scenarios in dynamic traffic networks. To address the challenge, we propose a greedy algorithm and an epsilon-refining algorithm. Extensive experiments offer insight into the accuracy and efficiency of our proposed algorithms.


Original document

The different versions of the original document can be found in:

https://academic.microsoft.com/#/detail/3034378860
Back to Top

Document information

Published on 01/01/2020

Volume 2020, 2020
DOI: 10.24963/ijcai.2020/470
Licence: CC BY-NC-SA license

Document Score

0

Views 4
Recommendations 0

Share this document

Keywords

claim authorship

Are you one of the authors of this document?