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

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

0.00 Avg rating0 Votes
Article ID: iaor20042201
Country: Netherlands
Volume: 144
Issue: 3
Start Page Number: 565
End Page Number: 580
Publication Date: Feb 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: networks: path
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 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.

Reviews

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