Obtaining dense road speed estimates from sparse GPS measurements

A major challenge for traffic management systems is the inference of traffic flow in regions of the network for which there is little data. In this thesis, GPS-based vehicle locator data from a fleet of 40-60 roving ambulances are used to estimate traffic congestion along a network of 20,000 streets in the city of Ottawa, Canada. Essentially, the road network is represented as a directed graph and a belief propagation algorithm is used to interpolate measurements from the fleet. The system incorporates a number of novel features. It makes no distinctions between freeways and surface streets, incorporates both historical and live sensor data, handles user inputs such as road closures and manual speed overrides, and is computationally efficient - providing updates every 5 to 6 minutes on commodity hardware. Experimental results are presented which address the key issue of validating the performance and reliability of the system.Un défi important en lien avec les systèmes de gestion de la circulation routière est de définir la situation actuelle du réseau routier dans les régions où peu de données sont disponibles. Les données provenant d'une flotte de 40-60 ambulances munies d'un GPS ont été utilisées afin d'estimer la congestion routière sur un réseau de plus de 20 000 rues dans la ville d'Ottawa, au Canada. Essentiellement, le réseau routier est représenté par un graphe orienté et un algorithme de propagation de confiance est utilisé pour interpoler les données provenant de la flotte d'ambulances. Ce système comprend des caractéristiques innovatives. Le système ne fait aucune distinction entre les autoroutes et les rues, il intègre les données archivées et actuelles, il gère les informations entrées par l'utilisateur au central concernant les fermeture des routes et les changements de vitesse sur le réseau routier et il est efficace dans ses calculs puisqu'il fournit des mises à jour de l'état du réseau routier toutes les 5-6 minutes sur un ordinateur standard. Les résultats de l'expérience, la validation de la performance ainsi que la fiabilité du système sont présentés