Individual multi-modal trip planning is a major task in transportation science. With increasing availability of new means of transportation personal constraints (e.g. elevator phobia or fear of flying) and preferences (e.g. train over bus) gain higher impact. Existing trip planners are mostly based on static time-tables and roadnetwork data. Furthermore an objective function that covers individual constraints and preferences on route choice is hard to find for existing trip planners. In this position paper we present an approach that incorporates the 'wisdom of the crowd' by construction of a transfer graph based on previously successfully performed trips of other persons. By this approach personal constraints and preferences may easily be taken under consideration by filtering those routes which were performed by people with similar restrictions. Also regular congestions may be taken into consideration as these are already in the data. In case of hazards or blockages corresponding connections can be removed in the transfer graph and alterProceedings of the 2 nd International Workshop on Mining Urban
natives are provided. With a sufficiently large set of initial routes, we expect the method to produce reasonable route suggestions. authors. Copying permitted for private and academic purposes.
The upcoming means of transportation (e.g. autonomous or flying cars) enable a more flexible individual mobility. Moreover some of these transportation means can be carried within the other (as we do nowadays with bikes in buses or trains on ferries).
This leads to novel options when travelling to some location. At the same time personal constraints (e.g. elevator phobia, fear of flying) have a stronger impact on personal route choices. The task to plan 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.
Existing trip planning algorithms operate on a graph representation of the road network the so-called traffic network G consisting of vertices V and connecting edges E: Every edge e ∈ E of the traffic network represents a segment (e.g. a street, a flight corridor, or the connection among subsequent bus stops) The vertices V represent junctions between segments and therefore locations where decisions on travel directions can be made. A cost function maps each edge to a positive number that denotes how much it would ‘cost’ to travel 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. With a given start and end location in the traffic network, trip planning searches the path that connects start and goal and minimizes the cost. Many trip planning algorithms exist in literature, for a brief overview we point the reader to (Bast et al., 2015) and (Delling et al., 2009). To summarize, the shortcomings of existing route planners are: • They are mostly based on static time-table and road network data, able, ing • The objective functions to produce routes people actually use are surprisingly hard to find. Current solutions either list all pareto-optimal routes, which is time consuming and results in a too large solution space for the end user, or, use an ad-hoc restriction to some routes without any validation via user experience. • Not all public transit timetable information is avail• modelling transfer buffers or walking times is hard even with complete timetable information, • routes people prefer are often also determined by unknown factors like traffic congestion and overcrowdIn contrast, the hereby presented approach bases on the main idea to stitch real, recorded (historic) travel segments of other travelers together into a travel plan. This stitching approach poses the following challenges that are detailed in this paper. Initially, historical data is needed for bootstrapping. The approach has to stitch together a travel plan at query time that also reflects the user’s preferences. In addition the practicality of this plan has to be validated. Historical, real-time and predicted traffic knowledge (e.g. blocked roads, need to be incorporated). While we identify these challenges, and provide solution sketches for some challenges in this position paper, we leave solving of a few points for future work.
Our approach constructs a transfer graph from given routes and filters the connections in case of constraints. The resulting transfer graph can be used for routing. This procedure is carried out in four steps: a) Sourcing routes, b) Constructing the transfer graph, c) Adjust in case a departure time is specified, d) Adjust in case current traffic conditions make a transfer impossible.
This paper is a position paper that presents an outline of our approach and is an introduction to our current work on route computations. Application of this algorithm to real routes is in preparation but this description is not included in this paper.
This position paper is structured as follows. Section 2 starts with a brief primer on trip planning and highlights current literature in multi-modal trip planning. Section 3 provides details on our approach, followed by Section 4 on a discussion and future research directions. A popular algorithm for trip computation is A∗ (Hart et al., 1968), this method searches the minimal connecting path iteratively, beginning at the goal. Not traversing all possible detours, A∗ tests the most promising ones first, based on a lower-bound heuristic on the cost function that estimates the minimal travel costs between any two locations. An example for such a heuristic is the geographical distance, which is always lower than the road based distance and therefore a suitable heuristic in case path length is the cost function. In multi-modal trip planning multiple of these traffic networks (one for each mode) are linked together at locations where it is possible to switch from one mode to another (transfer vertices). Multi-modal trip planning requires a consistent cost function which is applicable to all parts of the traffic network and thus to all modes of transportation.
Let us briefly highlight two currently very popular speedup techniques for queries in road networks as well as public transportation networks. For a road network with static cost functions, contraction hierarchies (Geisberger et al., 2008) are a speed-up scheme that improves considerably upon the A
∗ algorithm and enables trip calculation with guaranteed optimality in large traffic networks at European scale within few milliseconds. By augmenting the original road network with so-called shortcuts in a preprocessing phase, the search space is restricted to a tiny fraction of the whole network, hence improving the query times by several orders of magnitudes compared to Dijkstra or any A ∗ variant. For public transportation networks, a very popular and powerful technique is that of so-called transfer patterns (Bast et al., 2010). In a preprocessing step, all possible sequences of transfers on optimal routes are precomputed and based on that a condensed graph structure is created which allows for the almost instant answering of sourcetarget queries.
A comprehensive comparison of existing trip planning methods is provided in (Bast et al., 2015). Recent work incorporates user constraints in multi-modal trip planning (Dibbelt et al., 2015), in addition to their approach our method incorporates knowledge on regularly occurring congestions.
The approaches in (Niu et al., 2015) and (Liebig et al., 2014) utilize predictions to avoid upcoming traffic hazards, but their method has no incorporation of user preferences nor multi-modality. In (Bast & Storandt, 2014) trip guidebooks are created which are suitable for a long period of time, e.g., “Take Bus 10 to the main station, from there take Tram 11 or 13 (whichever comes next) to your target station. Trip duration: 30 minutes. Frequency: every 20 minutes.’ A
B1 A-B-C-D-E B-C-F-G H-F-G-I-J
B
B2
B4 H Transfer Graph
B1
B2
B Query: B → I T1 B3
C G
T1 T2
T2
T5
T6
I T5 B4
D
B3
E T7
J T6
I
T7
In previous section we provided an introduction to trip planning and highlighted latest research for multi-modal and large-scale trip computation. But, as previously stated in the introduction, most of these approaches have the following shortcomings: (1) The computation is mostly based on static time-table and road network data. (2) It is hard to find the objective functions to produce routes people actually use. Current solutions either list all pareto-optimal routes, which is time consuming and results in a too large solution space for the end user, or, use an ad-hoc restriction to some routes without any validation via user experience. (3) Public transit timetable information is incomplete. (4) Even with complete timetable information, modelling transfer buffers or walking times is hard. (5) Often, also unknown factors like traffic congestion and overcrowding determine routes that people prefer. In practice these limitations anticipate delivery of route suggestions that fit to personal preferences (e.g. preference of train over bus) and constraints (e.g. seasickness) upon a trip calculation request.
To overcome these limitations, we propose a novel fourstep method for stitching travel plans from previously recorded and bootstrapped routes. By utilization of these heterogeneous data sources the wisdom of multiple oracles (trip planners and prediction models) and local experts (e.g. via crowdsourcing) can be considered.
The four steps our method comprises are (1) Sourcing routes, (2) Constructing the transfer graph, (3) Adjust in case a departure time is specified, and (4) Adjust in case current traffic conditions make a transfer impossible are summarized in Algorithm 1. In the following we explain each step in more detail.
Gsource =Construct Transfer Graph(D) Gcurrent = Adjust Transfer Graph(Gsource, hazards) G = Filter Transfer Graph(Gcurrent, constraints)
3.1. Sourcing routes
Our approach bases on some initially sourced routes. These
routes are ideally real travelled routes that represent the
expert knowledge of local experts, e.g., shortcuts that avoid
congestions or possible connections among several means
of public transport that are not stored in schedules and
existing trip planners. This real-world data can be obtained in
three ways: (1) via an active participation app for a persons
smartphone (crowdsourcing), via a passive tracking system
(e.g. cellular phone networks (Andrienko et al., 2013)) or
via questionnaires (Janssens et al., 2012). Obviously this
step processes sensitive data, as personal travel plans
easily reveal individual habits and preferences of the person.
Therefore these methods have to be designed such that
reidentification is prohibited and no vulnerable data can be
accessed by the system. Possible approaches for protection
of individual data in this setting are (Boutsis & Kalogeraki,
2013) and
In case no real routes are available, or they do not provide sufficient coverage of the traffic network, routes can also be retrieved from existing route planners. This allows joining the information of various special-purpose or incomplete trip planners in a single system. 3.2. Constructing the transfer graph Based on previously sourced routes a transfer graph is constructed that represents travel alternatives and possible changes of transport mode. The transfer graph G consists of edges E and nodes V . The nodes are travel legs, i.e. uni-modal routes. An edge e ∈ E ⊂ V × V among two nodes (vi, vj ) exists when a transfer from the leg vi to vj has actually been executed (and its popularity is counted). This transfer graph is queried to obtain a travel plan from location A to B. An example for the transfer graph construction is provided in Figure 1. In the figure the sourced trips are depicted in blue, green, and red. The corresponding multi-modal traffic network is in the upper part of the figure. At the edge the travel mode is depicted by small pictograms. Based on these routes and the corresponding traffic network the transfer graph is constructed as described above. The resulting transfer graph is shown in the lower part of Figure 1. Nodes of this graph are travel legs and edges are uni-modal routes. An edge exists iff a transfer between legs has actually been executed. Finally, we query this transfer graph to obtain a travel plan from location B to I in Figure 1. The resulting trip is marked by the black dotted line.
Possible additions to this process is, similar to transfer patterns (Bast et al., 2010), the annotation with concrete time information to provide time depending trip calculations. It is also easily possible to extend the criteria for path selection in the transfer graph according to the user preferences (including length or duration, number of transfers, price, robustness, waiting times, and, popularity) once these features were annotated at the nodes during previous sourcing of the routes. 3.3. Adjustments The transfer graph, constructed in previous section, provides a useful data structure for trip computations from a set of initially given routes. Based on this graph a route can be stitched together from the information other people provided. The resulting route can be adjusted, once the exact travel time is given. This comprises two cases (1) if possible, validate all transfers in the route with the data (Find a route where that transfer was possible), and, (2) if no evidence is found that this transfer is possible, validate the transfers with timetable and road network data. This step leads to more data that may be added to the transfer graph, in a similar way as the initially sourced routes.
In case current traffic conditions make a transfer impossible, we temporarily “disable” that specific transfer node in the graph. In case of frequent problems, good alternatives should already be in the data and generated routes will avoid the regularly occurring transfer problem.
In this position paper we sketched a novel idea for route planning based on routes people really used. The method can be bootstrapped using routes from ordinary route planners. We expect our approach to be particularly useful for route planning with special needs (e.g. disabled persons, bikers).
One could remark that the provided routes have no optimality guarantee and detours might be provided. However, if the graph construction was initially bootstrapped with ordinary trip planners or large sets of recorded routes this limitation will diminish.
proposed trip planner is deterministic and provides same output with same queries. Though this approach provides user-centric trip queries including individual preferences and constraints, guiding all persons selfishly to travel via some leg with limited capacity (e.g. a bus or a narrow street) could lead to congestions (Roughgarden & Tardos, 2002). Future work therefore has to study how load balancing can be included directly in trip planning without causing too long detours for individuals, we will study usage of auction models (Du¨tting et al., 2012) for this problem.
This work results from a group discussion at Dagstuhl Seminar 13512. The authors received funding from the European Union’s Seventh Framework Programme under grant agreement number FP7-318225, INSIGHT. ACM SIGMOBILE Mobile Computing and Communications Review, 17(2):7–18, 2013.
Bast, H., Delling, D., Goldberg, A., Mu¨ller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., and Werneck, R. F. Route Planning in Transportation Networks. ArXiv eprints, April 2015. URL http://arxiv.org/abs/ 1504.05140.
Bast, Hannah and Storandt, Sabine. Flow-based guidebook routing. In McGeoch, Catherine C. and Meyer, Ulrich (eds.), 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, pp. 155–165. SIAM, 2014. ISBN 978-1-61197-319-8. doi: 10.1137/1.9781611973198.15.
Bast, Hannah, Carlsson, Erik, Eigenwillig, Arno, Geisberger, Robert, Harrelson, Chris, Raychev, Veselin, and Viger, Fabien. Fast routing in very large public transportation networks using transfer patterns. In Algorithms - ESA 2010, 18th Annual European Symposium. Pro
In 2013 IEEE International Conference on Pervasive Computing and Communications, PerCom 2013, San Diego, CA, USA, March 18-22, 2013, pp. 103–113. IEEE Computer Soci
rithms. In Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation [DFG priority progorithmics, 19:3.2:1.1–3.2:1.19, April 2015. ISSN 10846654. doi: 10.1145/2699886.
Du¨tting, Paul, Henzinger, Monika, and Weber, Ingmar.
Maximizing revenue from strategic recommendations under decaying trust. In Proceedings of the 21st ACM international conference on Information and knowledge Delling, Daniel. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Conference on Experimenberg, 2008. Springer-Verlag. ISBN 3-540-68548-0, 9783-540-68548-7.
Hart, Peter E., Nilsson, Nils J., and Raphael, Bertram. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems, Science, and
D1.1 report on big data available and privacy 2002.