Kolloquium Geoinformatik Adaptive Trip Planning

Route planning makes direct use of geographic data and provides beneficial recommendations to the public. In real-world the schedule of transit vehicles is dynamic and delays in the schedules occur. Incorporation of these dynamic schedule changes in multi-modal route computation is difficult and requires a lot of computational resources. We present an approach that extends the state-of-the-art for statictransit schedules, Transfer Patterns, for the dynamic case. Therefore, we amend the patterns by additional edges that cover the dynamics. Our approach is implemented in the open-source routing framework OpenTripPlanner and compared to existing methods in the city of Warsaw. Our results are an order of magnitude faster then existing methods. In Addition, urban areas are increasingly subject to congestions. Most navigation systems and algorithms that avoid these congestions consider drivers independently and can, thus, cause novel congestions at unexpected places. Pre-computation of optimal trips (Nash equilibrium) could be a solution to the problem but is due to its static nature of nopractical relevance. In contrast, we present an approach to avoid traffic jams with dynamic self-organizing trip planning. We apply reinforcement learning to learn dynamic weights for routing from the decisions and feedback logs of the vehicles. In order to compare our routing regime against others, we validate our approach in an open simulation environment (LuST) that allows reproduction of the traffic in Luxembourg for a particular day. Additionally, in two realistic scenarios: (1) usage of stationary sensors and (2) deployment in amobile navigation system, we perform experiments with varying penetration rates. All our experiments reveal that performance of the traffic network is increased and occurrence of traffic jams are reducedby application of our routing regime.