Vehicle routing problems in signalized traffic networks

by Jie Sun

Institution: University of Minnesota
Year: 2014
Keywords: Eco-routing; Environment; Shortest path; Traffic signal; Vehicle emissions; Vehicle routing; Civil Engineering
Record ID: 2042899
Full text PDF: http://hdl.handle.net/11299/167641


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.