Shortest paths in traÅc-light networks
Yen‐Liang Chen, Hsu‐Hao Yang · 2000
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 traAc-light constraint, to simulate the operations of traAc-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 · n 3 ) is developed, where n denotes the number of nodes in the network and r the number of diAerent windows in a node. In addition, we also prove that the time complexity of this algorithm is optimal. ” 2000 Elsevier Science Ltd. All rights reserved.