SIMULATING, RECONSTRUCTING, AND ROUTING METROPOLITAN-SCALE TRAFFIC

Few phenomena are more ubiquitous than traffic, and few are more significant economically, socially, or environmentally. The vast, world-spanning road network enables the daily commutes of billions of people and makes us mobile in a way our ancestors would have envied. And yet, few systems perform so poorly so often. Gridlock and traffic jams cost 2.9 billion gallons of wasted fuel and costs over 121 billion dollars every year in the U.S. alone. One promising approach to improving the reliability and efficiency of traffic systems is to fully incorporate computational techniques into the system, transforming the traffic systems of today into cyber-physical systems. However, creating a truly cyber-physical traffic system will require overcoming many substantial challenges. The state of traffic at any given time is unknown for the majority of the road network. The dynamics of traffic are complex, noisy, and dependent on drivers' decisions. The domain of the system, the real-world road network, has no suitable representation for high-detail simulation. And there is no known solution for improving the efficiency and reliability of the system. In this dissertation, I propose techniques that combine simulation and data to solve these challenges and enable large-scale traffic state estimation, simulation, and route planning. First, to create and represent road networks, I propose an efficient method for enhancing noisy GIS road maps to create geometrically and topologically consistent 3D models for high-detail, real-time traffic simulation, interactive visualization, traffic state estimation, and vehicle routing. The resulting representation provides important road features for traffic simulations, including ramps, highways, overpasses, merge zones, and intersections with arbitrary states. Second, to estimate and communicate traffic conditions, I propose a fast technique to reconstruct traffic flows from in-road sensor measurements or user-specified control points for interactive 3D visualization and communication. My algorithm estimates the full state of the traffic flow from sparse sensor measurements using a statistical inference method and a continuum traffic model. This estimated state then drives an agent-based traffic simulator to produce a 3D animation of traffic that statistically matches the sensed traffic conditions. Third, to improve real-world traffic system efficiency, I propose a novel approach that takes advantage of mobile devices, such as cellular phones or embedded systems in cars, to form an interactive, participatory network of vehicles that plan their travel routes based on the current, sensed traffic conditions and the future, projected traffic conditions, which are estimated from the routes planned by all the participants. The premise of this approach is that a route, or plan, for a vehicle is also a prediction of where the car will travel. If routes are planned for a sizable percentage of the vehicles using the road network, an estimate for the overall traffic pattern is attainable. If fewer cars are being coordinated, their impact on the traffic conditions can be combined with sensor-based estimations. Taking planned routes into account as predictions allows the entire traffic route planning system to better distribute vehicles and to minimize traffic congestion. For each of these challenges, my work is motivated by the idea of fully integrating traffic simulation, as a model for the complex dynamics of real world traffic, with emerging data sources, including real-time sensor and public survey data.Doctor of Philosoph