On the Complexity of Congestion Free Routing in Transportation Networks

Traffic congestion has been proven a difficult problem to tackle, particularly in big cities where the number of cars are steadily increasing while the infrastructure remains stagnant. Several approaches have been proposed to alleviate the effects of traffic congestion, however, so far congestion is still a big problem in most cities. In this work the authors investigate a new route reservation approach to address the problem which is motivated by air traffic control. This paper formulates the route reservation problem under different assumptions and examines the complexity of the resulting formulations. Two waiting strategies are investigated, (i) vehicles are allowed to wait at the source before they start their journey, and (ii) they are allowed to wait at every road junction. Strategy (i) though more practical to implement, results to an NP-complete problem while strategy (ii) results to a problem that can be solved in polynomial time but it is not easily implemented since the infrastructure does not have adequate space for vehicles to wait until congestion downstream is cleared. Finally, a heuristic algorithm (based on time-expanded networks) is derived as a solution to both proposed waiting strategies.

• Record URL:
  https://doi.org/10.1109/ITSC.2015.453
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/isbn/9781467365956
• Supplemental Notes:
  • Abstract reprinted with permission of IEEE.
• Corporate Authors:

  Institute of Electrical and Electronics Engineers (IEEE)

  3 Park Avenue, 17th Floor
  New York, NY  United States  10016-5997
• Authors:
  • Menelaou, Charalambos
  • Kolios, Panayiotis
  • Timotheou, Stelios
  • Panayiotou, Christos
• Conference:
  • 18th International IEEE Conference on Intelligent Transportation Systems (ITSC)
  • Location: Canary Islands , Spain
  • Date: 2015-9-15 to 2015-9-18
• Publication Date: 2015

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 2819-2824
• Monograph Title: 18th International IEEE Conference on Intelligent Transportation Systems (ITSC 2015)

Subject/Index Terms

• TRT Terms: Algorithms; Heuristic methods; Traffic congestion; Traffic mitigation
• Uncontrolled Terms: Route reservation
• Subject Areas: Highways; Operations and Traffic Management;

Filing Info

• Accession Number: 01599810
• Record Type: Publication
• ISBN: 9781467365956
• Files: TRIS
• Created Date: May 22 2016 6:35PM