Minimization of travel time and weighted number of stops in a traffic-light network

Yen Liang Chen, Hsu Hao Yang

研究成果: 雜誌貢獻期刊論文同行評審

18 引文 斯高帕斯(Scopus)


The time-constrained shortest path problem is an important generalization of the shortest path problem. Recently, a model called traffic-light control model was introduced by Chen and Yang [Transport. Res. B 34 (2000) 241] to simulate the operations of traffic-light control in a city. The constraints of the model consist of a repeated sequence of time windows, and each window allows only certain routes to pass through a node. In this paper, we introduce a new kind of network called on-off time-switch network in which an arc is associated with a sequence of windows with status "on" or "off" analogous to "go" or "wait". We show that both networks have the same mathematical structure in the sense that a path in one network corresponds to a path in the other one. Since Chen and Yang have developed algorithms to find the minimum total time path in the previous paper, we include one more criterion in this paper: weighted number of stops. To solve this bi-criteria path problem, we transform the traffic-light network into the on-off time-switch network, which allows us to take advantages of the special structure to design more efficient algorithms. By this transformation, finding the bi-criteria shortest path in the traffic-light network can be done in time O(#Wn3), where n is the number of nodes and #W is a given maximum number of weighted stops.

頁(從 - 到)565-580
期刊European Journal of Operational Research
出版狀態已出版 - 1 2月 2003


深入研究「Minimization of travel time and weighted number of stops in a traffic-light network」主題。共同形成了獨特的指紋。