The Library
Collective shortest paths for minimizing congestion on temporal load-aware road networks
Tools
Tools
Tools
Conlan, Chris, Cunningham, Teddy, Demirci, Gunduz and Ferhatosmanoglu, Hakan (2021) Collective shortest paths for minimizing congestion on temporal load-aware road networks. In: SIGSPATIAL 2021 : 14th International Workshop on Computational Transportation Science (IWCTS '21), Beijing, China, 2-5 Nov 2021. Published in: IWCTS '21: Proceedings of the 14th ACM SIGSPATIAL International Workshop on Computational Transportation Science pp. 1-10. ISBN 9781450391177. doi:10.1145/3486629.3490691
|
PDF
WRAP-Collective-shortest-paths-minimizing-congestion-temporal-load-aware-road-networks-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1350Kb) | Preview |
Official URL: https://doi.org/10.1145/3486629.3490691
Abstract
Shortest path queries over graphs are usually considered as isolated tasks, where the goal is to return the shortest path for each individual query. In practice, however, such queries are typically part of a system (e.g., a road network) and their execution dynamically affects other queries and network parameters, such as the loads on edges, which in turn affects the shortest paths. We study the problem of collectively processing shortest path queries, where the objective is to optimize a collective objective, such as minimizing the overall cost. We define a temporal load-aware network that dynamically tracks expected loads while satisfying the desirable 'first in, first out' property. We develop temporal load-aware extensions of widely used shortest path algorithms, and a scalable collective routing solution that seeks to reduce system-wide congestion through dynamic path reassignment. Experiments illustrate that our collective approach to this NP-hard problem achieves improvements in a variety of performance measures, such as, i) reducing average travel times by up to 63%, ii) producing fairer suggestions across queries, and iii) distributing load across up to 97% of a city's road network capacity. The proposed approach is generalizable, which allows it to be adapted for other concurrent query processing tasks over networks.
| Item Type: | Conference Item (Paper) | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Spatial systems , Spatial data mining , Paths and cycles (Graph theory) , Traffic flow -- Mathematical models , Spatial analysis (Statistics) | ||||||||
| Journal or Publication Title: | IWCTS '21: Proceedings of the 14th ACM SIGSPATIAL International Workshop on Computational Transportation Science | ||||||||
| Publisher: | ACM | ||||||||
| ISBN: | 9781450391177 | ||||||||
| Official Date: | 18 November 2021 | ||||||||
| Dates: |
|
||||||||
| Page Range: | pp. 1-10 | ||||||||
| Article Number: | 1 | ||||||||
| DOI: | 10.1145/3486629.3490691 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | "© ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 14th ACM SIGSPATIAL Inter-national Workshop on Computational Transportation Science (IWCTS’21),November 1, 2021, Beijing, China. ACM, New York, NY, USA http://doi.acm.org/10.1145/3486629.3490691 Please cite as : "Chris Conlan, Teddy Cunningham, Gunduz Vehbi Demirci, and Hakan Fer-hatosmanoglu. 2021. Collective Shortest Paths for Minimizing Congestion on Temporal Load-Aware Road Networks. In 14th ACM SIGSPATIAL Inter-national Workshop on Computational Transportation Science (IWCTS’21),November 1, 2021, Beijing, China. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3486629.3490691 | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Copyright Holders: | © 2021 Association for Computing Machinery | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Conference Paper Type: | Paper | ||||||||
| Title of Event: | SIGSPATIAL 2021 : 14th International Workshop on Computational Transportation Science (IWCTS '21) | ||||||||
| Type of Event: | Workshop | ||||||||
| Location of Event: | Beijing, China | ||||||||
| Date(s) of Event: | 2-5 Nov 2021 | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
