Shortest paths in traffic-light networks

Yen-Liang Chen and Hsu-Hao Yang

Transportation Research Part B: Methodological, 2000, vol. 34, issue 4, 241-253

Abstract: The time-constrained shortest path problem (TCSPP) is an important generalization of the shortest path problem (SPP) and has attracted widespread research interest in recent years. This paper presents a novel time constraint, called traffic-light constraint, to simulate the operations of traffic-light control encountered in intersections of roads. Basically, the constraint consists of a repeated sequence of time windows. In each window, only the cars in specified routes are allowed to pass through the intersection. In a practical sense, this means that a car needs to wait if the light for its direction is red and can go if it is green. For this kind of network, a shortest path algorithm of time complexity O(r - n3) is developed, where n denotes the number of nodes in the network and r the number of different windows in a node. In addition, we also prove that the time complexity of this algorithm is optimal.

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(99)00023-5
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:34:y:2000:i:4:p:241-253

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().