Vehicle routing problems in signalized traffic networks

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Vehicle routing problems in signalized traffic networks


Published Date




Thesis or Dissertation


This dissertation studied various path search problems when traffic signal information and traffic state is explicitly considered. The research is motivated by the increasing availability of high-resolution traffic data including signal information, which is seldom available in the past. In order to properly account for the randomness resulting from vehicle-actuated traffic signals and the correlation from signal coordination, the theory of Markov decision process (MDP) is used. By taking advantage of the cyclic property of traffic signals, the problem is formulated as an infinite horizon and finite state space MDP with absorbing state set. The objective is to find the optimal policy that gives the minimum expected total cost to the destination.The state space of the problem is generated based on underlying traffic network geometry and signal control information. Delay distributions at intersections together with signal control parameters, such as cycle length and offset, are used to construct the transition probabilities between states. It will be shown that the required delay distributions can be estimated from readily available field traffic data. The problem where the cost is travel time is first studied. When the cost of concern is the travel time, it includes intersection delays and link travel times. Value iteration method is used to solve the MDP problem when there is only one cost of concern.In addition, the problem whose cost of concern is environmentally related is also studied. Vehicle trajectories are estimated based on traffic signal information and queuing dynamics at intersections, and put into microscopic vehicle emission models, the results from which are used to calculate the environmental costs for the path search problem. When multiple costs of concern present, the problem is formulated as a constrained MDP problem. Linear programming formulation of MDP is introduced to solve constrained MDP problem. The proposed methods are tested in a hypothetical traffic network, as well as a real world traffic network in the City of Pasadena, CA.


University of Minnesota Ph.D. dissertation. August 2014. Major: Civil Engineering. Advisor: Henry X. Liu. 1 computer file (PDF); x, 104 pages, appendices p. 102-104.

Related to




Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Sun, Jie. (2014). Vehicle routing problems in signalized traffic networks. Retrieved from the University Digital Conservancy,

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.