Shortest paths in traffic-light networks

Shortest paths in traffic-light networks

0.00 Avg rating0 Votes
Article ID: iaor2001977
Country: United Kingdom
Volume: 34B
Issue: 4
Start Page Number: 241
End Page Number: 253
Publication Date: May 2000
Journal: Transportation Research. Part B: Methodological
Authors: ,
Keywords: transportation: road
Abstract:

The time-constrained shortest path problem is an important generalization of the shortest path problem 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.

Reviews

Required fields are marked *. Your email address will not be published.