Adaptive Trip Planning

The task of planning a route from one start location to a target location is called trip planning. When multiple means of transportation (also called "travel modes") are involved this becomes multi-modal trip planning. The integration of transportation systems with personal constraints, residential and city services systems can offer real promise for implementing an intelligent transportation infrastructure that can efficiently address issues beyond congestion, resiliency and safety. Trip planning operates on a graph representation of the road and transit network, the so-called traffic network G consisting of vertices V (e.g. junctions) and connecting edges E (e.g. streets). A cost function maps each edge to a positive number that denotes how much it would ‘cost’ to travel along the corresponding segment. The cost function needs to be consistent throughout the traffic network, but can be defined in several ways, such that it holds the most important aspects: for example, length of the segment, travel time, or comfortableness. For a given start and end location in the traffic network, trip planning seeks the path that connects the start origin and destination and minimizes the cost.

With the emergence of smart cities, trip computation received increased attention. While conventional trip computation algorithms minimize a static cost function and provide an optimal route for an unrealistic uniform traffic situation with constant costs. Traffic situations are not uniform, but vary over time, e.g. at rush hour commuters cause traffic jams on streets which are almost empty at night. The integration of various sensor systems (e.g. crowdsourcing, video cameras, automatic traffic loops) in the smart city ecosystem enables incorporation of real-time measurements into intelligent traffic systems, and their future predictions.

Situation-aware route planning is gathering increasing interest. The proliferation of various sensor technologies in smart cities allows the incorporation of real-time data and its predictions into the trip planning process. In the VaVeL project, it is possible to create information systems for individual multi-modal trip planning that incorporates predictions of future (public transport) delays in routing. Future delay times are computed by a spatio-temporal prediction model. The information used by the system can be based on a stream of current vehicle positions, infrastructural data. One possible prediction model, is made possible by Spatio-Temporal Random Fields. The conditioning of spatial regression on intermediate predictions of a discrete probabilistic graphical model allows incorporation of historical data, streamed online data and a rich dependency structure at the same time.

During the transition towards smart cities, intelligent traffic systems are used to detect current traffic hazards , to predict future traffic states or to provide situation- dependent navigation suggestions to drivers . Due to the complex nature of everyday traffic, precise travel time prediction has proven to be an algorithmically challenging problem. Its accuracy is inherently dependent on various inputs, such as spatio-temporal variables, road supply, road demand, vehicle usage, and overall network quality.

The routes, however, should avoid current and upcoming traffic jams. This can easily be done individually, by a navigation device or a routing app (e.g. Google) but this could become problematic, as it does not consider greedy route choice on the part of drivers. Every driver uses comparable edge weights and optimal roads are overrepresented. This may lead to new and unexpected congestion on optimal roads during peak periods. And, in turn, optimal roads become no longer optimal. The possible benefits for the informed travellers are (see [L17]):

• smart decisions among between different modes of transportation,
• smart choice among between different transit routes,
• informed decisions between different initial walking directions, or
• different transit stops.

We will now demonstrate this in Warsaw, the capital of Poland, for different representative cases, see Figure 1. In the two subfigures on the top, the same origin/destination pairs lead to different transit suggestions. Different initial walking directions are suggested in the lower subfigures of Figure 1.

As seen in previous examples, prediction of delays supports planning of situation-aware trips in advance (not just when travelling). This enables a smart decision from the outset and even enables the decision to start a trip earlier or later (depending on expected transfer reachability). Imagine, for example, dining with your friends in the suburbs of your city. On your return, our trip planner provides you with the information that the required transfer in the city centre (from the tram in the suburbs to your means of transportation) cannot be reached. Based on this information, you might stay longer with your friends instead of uselessly waiting outside at the tram stop.

Our approach towards this situation-aware trip planner detects current and past delays of transit vehicles delays based on a comparison of their live GPS streams with the scheduled arrival times (compare [HL17]). The detected delays are used to estimate future delays by a probabilistic graphical model. These real-time predictions are incorporated into route computations generated with OpenTripPlanner, an open source trip planning tool. The data sources exploited by our approach are the street network, public transport schedules and the current positions of transit vehicles. We perform our experiments in Warsaw, Poland, and use open data provided via open geospatial consortium standardized protocols and interfaces. We speed up trip computation incorporating these dynamic public transport delays by a pre-computation of dynamic transfer patterns, compare LPGJ17. This lookup structure holds for any public transport pair a connecting route through the transit network depending on the predicted delays. Our extensions to OpenTripPlanner are publicly available at https://bitbucket.org/tliebig/developvm.

References