Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips

Ke Li; Lisi Chen; Shuo Shang

IJCAI 2020poster0 citations

Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips

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.

Multidisciplinary Topics and Applications: DatabasesMultidisciplinary Topics and Applications: TransportationPlanning and Scheduling: Real-time PlanningPlanning and Scheduling: Planning Algorithms

BibTeX

@inproceedings{ijcai2020p470,
  title     = {Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips},
  author    = {Li, Ke and Chen, Lisi and Shang, Shuo},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {3400--3406},
  year      = {2020},
  month     = {7},
  note      = {Main track},
  doi       = {10.24963/ijcai.2020/470},
  url       = {https://doi.org/10.24963/ijcai.2020/470},
}