Towards Mobile Time-Dependent Route Planning

Road networks with time-dependent edge weights can describe rush hours and similar regular changes in traffic over a day. Optimal routes can be calculated efficiently using time-dependent Contraction Hierarchies. On mobile devices it is usually not possible and also not reasonable to hold the entire data in the limited main memory. Therefore the main performance bottleneck is the data access on the flash memory, which can only be read blockwise. For fast route query calculations, the number of accessed blocks has to be low. To achieve this, we first reduce the amount of data using a lossy compression. This introduces inaccuracies in the calculations hence not always the optimal route is chosen. Nevertheless using this method the result is still nearly exact because the average introduced delay compared to the optimal route is less than 0.001%. In the worst case a delay of about 0.1% occurs which still is too small to be noticed. Second, the data is rearranged in a way that increases the locality. This leads to a lower number of required block loads. For a road network of Germany we can answer random route queries with an average of 102 block loads. ... mehrAssuming that a block access takes 1.3 ms, this can be done in 133 ms. Users perceive this as a nearly instant reaction. Everyday route calculations tend to be even smaller and can be calculated faster.