Algorithms and data structures for the real-time processing of traffic data

This thesis is focused on gathering traffic information in a distributed fashion through an application running in each vehicle rather than through expensive hardware that must be embedded in roads at discrete locations. This allows for a new approach to gathering traffic data over a continuous-flow rather than at discrete locations, as is the case with existing technologies. Using mobile technology, the vehicles can transmit their speed and location to a central system, allowing the fastest path of each vehicle from its current location to its destination to be maintained in real-time. Gathering the speed and location of each vehicle in real-time over a continuous flow will allow more novel applications, such as incident identification and traffic prediction, to be developed.; I present an analysis of the bandwidth that would be required compared to the bandwidth that is currently available over cellular networks, from which I conclude that the bandwidth currently available is sufficient to run this application. To gather the speed and location of each vehicle and then generate fastest paths for each in an efficient manner, I build on the work of static shortest path algorithms and dynamic shortest path algorithms to produce a new class of algorithms called the Dynamic All-Pairs All-Paths (APAP) algorithms. I analyze the algorithmic running time of these algorithms, and show that the Dynamic APAP class of algorithms runs faster theoretically and the Dynamic APAP - Constant Update algorithm runs faster practically than existing algorithms.; I have created FreeSim (http://www.freewaysimulator.com), which is a freeway traffic simulator for Intelligent Transportation Systems (ITS), that allows individual vehicles to communicate autonomously with the roadway (V2R) or other vehicles (V2V). FreeSim's architecture is unique in that it supports constant communication between all vehicles and a central server that is monitoring traffic and sending advice about preferred paths to vehicle's destinations. FreeSim provides a testing environment that supports both user-generated and live traffic as input. It also supports plug-and-play algorithms for computing fastest/shortest paths or other graph or traffic algorithms. It also supports plug-and-play algorithms for computing fastest/shortest paths or other graph or traffic algorithms.