Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
18 November 2021Published
1 November 2021Available
8 October 2021Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
EP/L016400/1Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
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:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us