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

Yen Liang Chen, Hsu Hao Yang

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)565-580
Number of pages16
JournalEuropean Journal of Operational Research
Volume144
Issue number3
DOIs
StatePublished - 1 Feb 2003

Keywords

  • Road network
  • Shortest path
  • Time window
  • Traffic light

Fingerprint

Dive into the research topics of 'Minimization of travel time and weighted number of stops in a traffic-light network'. Together they form a unique fingerprint.

Cite this