Transit tomography using probabilistic time geography: planning routes without a road map

Abstract

Vehicle routing usually depends on a road map, and road maps are expensive to create and maintain. While crowdsourcing road maps from logged GPS data has proven effective, the limited availability of GPS data limits their coverage area. To overcome this limitation, we show how to use location data from geotagged tweets, which cover much of the world, to compute routes directly without making a road map. We compensate for the wide spacing of tweets' latitude/longitude points by using probabilistic time geography, which explicitly models the uncertain location of someone traveling between measured locations. In our formulation, each pair of temporally adjacent tweets contributes an estimate of the driving time along hypothesised roads in a regular grid. We show how to compute these estimates as expected values based on probabilistic Brownian bridges. We can compute routes on this regular grid using traditional A^* search. Our experiments demonstrate that our computed routes match well with routes computed on the actual road network using a commercial router. Furthermore, we show that our computed routes vary sensibly with changes in traffic between rush hour and weekends. We also apply the same technique to compute reasonable airplane routes.

Keywords::

• road maps
• vehicle routing
• probabilistic time geography
• Brownian bridge
• geotagged Twitter