Report from Dagstuhl: SocioPaths - Multimodal Door-to-Door Route planning via Social Paths Thomas Liebig THOMAS . LIEBIG @ TU - DORTMUND . DE University of Dortmund, 44221 Dortmund, Germany Sabine Storandt STORANDT @ INFORMATIK . UNI - FREIBURG . DE University of Freiburg, 79110 Freiburg, Germany Peter Sanders SANDERS @ KIT. EDU University of Karlsruhe, 76128 Karlsruhe, Germany Walied Othman WALIED . OTHMAN @ GMAIL . COM Triade systems Stefan Funke FUNKE @ FMI . UNI - STUTTGART. DE University of Stuttgart, 70569 Stuttgart, Germany Abstract 1. Introduction Individual multi-modal trip planning is a ma- The upcoming means of transportation (e.g. autonomous jor task in transportation science. With increas- or flying cars) enable a more flexible individual mobility. ing availability of new means of transportation Moreover some of these transportation means can be car- personal constraints (e.g. elevator phobia or ried within the other (as we do nowadays with bikes in fear of flying) and preferences (e.g. train over buses or trains on ferries). This leads to novel options bus) gain higher impact. Existing trip planners when travelling to some location. At the same time per- are mostly based on static time-tables and road- sonal constraints (e.g. elevator phobia, fear of flying) have network data. Furthermore an objective function a stronger impact on personal route choices. The task to that covers individual constraints and preferences plan a route from one start location to a target location is on route choice is hard to find for existing trip called trip planning, when multiple means of transporta- planners. tion (also called ‘travel modes’) are involved this becomes In this position paper we present an approach multi-modal trip planning. that incorporates the ‘wisdom of the crowd’ by construction of a transfer graph based on previ- Existing trip planning algorithms operate on a graph repre- ously successfully performed trips of other per- sentation of the road network the so-called traffic network sons. By this approach personal constraints and G consisting of vertices V and connecting edges E: Every preferences may easily be taken under consider- edge e ∈ E of the traffic network represents a segment (e.g. ation by filtering those routes which were per- a street, a flight corridor, or the connection among sub- formed by people with similar restrictions. Also sequent bus stops) The vertices V represent junctions be- regular congestions may be taken into consider- tween segments and therefore locations where decisions on ation as these are already in the data. In case of travel directions can be made. A cost function maps each hazards or blockages corresponding connections edge to a positive number that denotes how much it would can be removed in the transfer graph and alter- ‘cost’ to travel the corresponding segment. The cost func- natives are provided. With a sufficiently large set tion needs to be consistent throughout the traffic network, of initial routes, we expect the method to produce but can be defined in several ways, such that it holds the reasonable route suggestions. most important aspects: for example length of the segment, travel time, or comfortableness. With a given start and end Proceedings of the 2 nd International Workshop on Mining Urban location in the traffic network, trip planning searches the Data, Lille, France, 2015. Copyright c 2015 for this paper by its path that connects start and goal and minimizes the cost. authors. Copying permitted for private and academic purposes. Ny SocioPaths - Multimodal Door-to-Door Route planning via Social Paths Many trip planning algorithms exist in literature, for a brief 2. Related Work overview we point the reader to (Bast et al., 2015) and (Delling et al., 2009). To summarize, the shortcomings of A popular algorithm for trip computation is A∗ (Hart et al., existing route planners are: 1968), this method searches the minimal connecting path iteratively, beginning at the goal. Not traversing all possi- • They are mostly based on static time-table and road ble detours, A∗ tests the most promising ones first, based on network data, a lower-bound heuristic on the cost function that estimates the minimal travel costs between any two locations. An • The objective functions to produce routes people actu- example for such a heuristic is the geographical distance, ally use are surprisingly hard to find. Current solutions which is always lower than the road based distance and either list all pareto-optimal routes, which is time con- therefore a suitable heuristic in case path length is the cost suming and results in a too large solution space for the function. In multi-modal trip planning multiple of these end user, or, use an ad-hoc restriction to some routes traffic networks (one for each mode) are linked together at without any validation via user experience. locations where it is possible to switch from one mode to • Not all public transit timetable information is avail- another (transfer vertices). Multi-modal trip planning re- able, quires a consistent cost function which is applicable to all parts of the traffic network and thus to all modes of trans- • modelling transfer buffers or walking times is hard portation. even with complete timetable information, Let us briefly highlight two currently very popular speed- • routes people prefer are often also determined by un- up techniques for queries in road networks as well as pub- known factors like traffic congestion and overcrowd- lic transportation networks. For a road network with static ing cost functions, contraction hierarchies (Geisberger et al., 2008) are a speed-up scheme that improves considerably In contrast, the hereby presented approach bases on the upon the A∗ algorithm and enables trip calculation with main idea to stitch real, recorded (historic) travel segments guaranteed optimality in large traffic networks at European of other travelers together into a travel plan. This stitching scale within few milliseconds. By augmenting the original approach poses the following challenges that are detailed road network with so-called shortcuts in a preprocessing in this paper. Initially, historical data is needed for boot- phase, the search space is restricted to a tiny fraction of the strapping. The approach has to stitch together a travel plan whole network, hence improving the query times by sev- at query time that also reflects the user’s preferences. In eral orders of magnitudes compared to Dijkstra or any A∗ addition the practicality of this plan has to be validated. variant. For public transportation networks, a very popular Historical, real-time and predicted traffic knowledge (e.g. and powerful technique is that of so-called transfer patterns blocked roads, need to be incorporated). While we identify (Bast et al., 2010). In a preprocessing step, all possible these challenges, and provide solution sketches for some sequences of transfers on optimal routes are precomputed challenges in this position paper, we leave solving of a few and based on that a condensed graph structure is created points for future work. which allows for the almost instant answering of source- Our approach constructs a transfer graph from given routes target queries. and filters the connections in case of constraints. The re- A comprehensive comparison of existing trip planning sulting transfer graph can be used for routing. This pro- methods is provided in (Bast et al., 2015). Recent work cedure is carried out in four steps: a) Sourcing routes, b) incorporates user constraints in multi-modal trip planning Constructing the transfer graph, c) Adjust in case a depar- (Dibbelt et al., 2015), in addition to their approach our ture time is specified, d) Adjust in case current traffic con- method incorporates knowledge on regularly occurring ditions make a transfer impossible. congestions. The approaches in (Niu et al., 2015) and This paper is a position paper that presents an outline of (Liebig et al., 2014) utilize predictions to avoid upcoming our approach and is an introduction to our current work on traffic hazards, but their method has no incorporation of route computations. Application of this algorithm to real user preferences nor multi-modality. In (Bast & Storandt, routes is in preparation but this description is not included 2014) trip guidebooks are created which are suitable for a in this paper. long period of time, e.g., “Take Bus 10 to the main station, from there take Tram 11 or 13 (whichever comes next) to This position paper is structured as follows. Section 2 starts your target station. Trip duration: 30 minutes. Frequency: with a brief primer on trip planning and highlights current every 20 minutes.’ literature in multi-modal trip planning. Section 3 provides details on our approach, followed by Section 4 on a discus- sion and future research directions. NR SocioPaths - Multimodal Door-to-Door Route planning via Social Paths B2 B1 T1 B3 A B C D E T2 A-B-C-D-E B4 B-C-F-G F H-F-G-I-J H T5 G I J T6 T7 Transfer Graph B1 B2 T1 T2 T5 T6 T7 B I Query: B → I B3 B4 Figure 1. Stitch Network for multi-modal trip planning. Based on sourced trips (blue,green,red) nodes are travel legs and edges are uni-modal routes. An edge exists when a transfer between legs has actually been executed (and its popularity is counted). We query this graph to obtain a travel plan from B to I (black dotted line). 3. Socio-Paths routing method these limitations anticipate delivery of route suggestions that fit to personal preferences (e.g. preference of train over In previous section we provided an introduction to trip bus) and constraints (e.g. seasickness) upon a trip calcula- planning and highlighted latest research for multi-modal tion request. and large-scale trip computation. But, as previously stated in the introduction, most of these approaches have the fol- To overcome these limitations, we propose a novel four- lowing shortcomings: (1) The computation is mostly based step method for stitching travel plans from previously on static time-table and road network data. (2) It is hard recorded and bootstrapped routes. By utilization of these to find the objective functions to produce routes people ac- heterogeneous data sources the wisdom of multiple oracles tually use. Current solutions either list all pareto-optimal (trip planners and prediction models) and local experts (e.g. routes, which is time consuming and results in a too large via crowdsourcing) can be considered. solution space for the end user, or, use an ad-hoc restric- The four steps our method comprises are (1) Sourcing tion to some routes without any validation via user expe- routes, (2) Constructing the transfer graph, (3) Adjust in rience. (3) Public transit timetable information is incom- case a departure time is specified, and (4) Adjust in case plete. (4) Even with complete timetable information, mod- current traffic conditions make a transfer impossible are elling transfer buffers or walking times is hard. (5) Of- summarized in Algorithm 1. In the following we explain ten, also unknown factors like traffic congestion and over- each step in more detail. crowding determine routes that people prefer. In practice Nk SocioPaths - Multimodal Door-to-Door Route planning via Social Paths Algorithm 1 SocioPath Algorithm edges are uni-modal routes. An edge exists iff a transfer Input: D = Source Routes between legs has actually been executed. Finally, we query Input: hazards, this transfer graph to obtain a travel plan from location B Input: query: (start, goal, constraints), to I in Figure 1. The resulting trip is marked by the black Gsource =Construct Transfer Graph(D) dotted line. Gcurrent = Adjust Transfer Graph(Gsource , hazards) Possible additions to this process is, similar to transfer pat- G = Filter Transfer Graph(Gcurrent , constraints) terns (Bast et al., 2010), the annotation with concrete time Compute Route(G, start, goal) information to provide time depending trip calculations. It is also easily possible to extend the criteria for path selec- tion in the transfer graph according to the user preferences 3.1. Sourcing routes (including length or duration, number of transfers, price, Our approach bases on some initially sourced routes. These robustness, waiting times, and, popularity) once these fea- routes are ideally real travelled routes that represent the ex- tures were annotated at the nodes during previous sourcing pert knowledge of local experts, e.g., shortcuts that avoid of the routes. congestions or possible connections among several means of public transport that are not stored in schedules and ex- 3.3. Adjustments isting trip planners. This real-world data can be obtained in The transfer graph, constructed in previous section, pro- three ways: (1) via an active participation app for a persons vides a useful data structure for trip computations from a smartphone (crowdsourcing), via a passive tracking system set of initially given routes. Based on this graph a route can (e.g. cellular phone networks (Andrienko et al., 2013)) or be stitched together from the information other people pro- via questionnaires (Janssens et al., 2012). Obviously this vided. The resulting route can be adjusted, once the exact step processes sensitive data, as personal travel plans eas- travel time is given. This comprises two cases (1) if pos- ily reveal individual habits and preferences of the person. sible, validate all transfers in the route with the data (Find Therefore these methods have to be designed such that re- a route where that transfer was possible), and, (2) if no ev- identification is prohibited and no vulnerable data can be idence is found that this transfer is possible, validate the accessed by the system. Possible approaches for protection transfers with timetable and road network data. This step of individual data in this setting are (Boutsis & Kalogeraki, leads to more data that may be added to the transfer graph, 2013) and (Liebig, 2015). in a similar way as the initially sourced routes. In case no real routes are available, or they do not provide In case current traffic conditions make a transfer impos- sufficient coverage of the traffic network, routes can also be sible, we temporarily “disable” that specific transfer node retrieved from existing route planners. This allows joining in the graph. In case of frequent problems, good alterna- the information of various special-purpose or incomplete tives should already be in the data and generated routes will trip planners in a single system. avoid the regularly occurring transfer problem. 3.2. Constructing the transfer graph 4. Conclusion and Future Work Based on previously sourced routes a transfer graph is constructed that represents travel alternatives and possible In this position paper we sketched a novel idea for route changes of transport mode. The transfer graph G consists planning based on routes people really used. The method of edges E and nodes V . The nodes are travel legs, i.e. can be bootstrapped using routes from ordinary route plan- uni-modal routes. An edge e ∈ E ⊂ V × V among two ners. We expect our approach to be particularly useful for nodes (vi , vj ) exists when a transfer from the leg vi to vj route planning with special needs (e.g. disabled persons, has actually been executed (and its popularity is counted). bikers). This transfer graph is queried to obtain a travel plan from One could remark that the provided routes have no opti- location A to B. An example for the transfer graph con- mality guarantee and detours might be provided. How- struction is provided in Figure 1. In the figure the sourced ever, if the graph construction was initially bootstrapped trips are depicted in blue, green, and red. The correspond- with ordinary trip planners or large sets of recorded routes ing multi-modal traffic network is in the upper part of the this limitation will diminish. An open issue is that the figure. At the edge the travel mode is depicted by small pic- proposed trip planner is deterministic and provides same tograms. Based on these routes and the corresponding traf- output with same queries. Though this approach provides fic network the transfer graph is constructed as described user-centric trip queries including individual preferences above. The resulting transfer graph is shown in the lower and constraints, guiding all persons selfishly to travel via part of Figure 1. Nodes of this graph are travel legs and some leg with limited capacity (e.g. a bus or a narrow Nj SocioPaths - Multimodal Door-to-Door Route planning via Social Paths street) could lead to congestions (Roughgarden & Tardos, Dibbelt, Julian, Pajor, Thomas, and Wagner, Dorothea. 2002). Future work therefore has to study how load balanc- User-constrained multimodal route planning. J. Exp. Al- ing can be included directly in trip planning without caus- gorithmics, 19:3.2:1.1–3.2:1.19, April 2015. ISSN 1084- ing too long detours for individuals, we will study usage of 6654. doi: 10.1145/2699886. auction models (Dütting et al., 2012) for this problem. Dütting, Paul, Henzinger, Monika, and Weber, Ingmar. Maximizing revenue from strategic recommendations Acknowledgments under decaying trust. In Proceedings of the 21st ACM This work results from a group discussion at Dagstuhl Sem- international conference on Information and knowledge inar 13512. The authors received funding from the Euro- management, pp. 2283–2286. ACM, 2012. pean Union’s Seventh Framework Programme under grant Geisberger, Robert, Sanders, Peter, Schultes, Dominik, and agreement number FP7-318225, INSIGHT. Delling, Daniel. Contraction hierarchies: Faster and sim- pler hierarchical routing in road networks. In Proceed- References ings of the 7th International Conference on Experimen- tal Algorithms, WEA’08, pp. 319–333, Berlin, Heidel- Andrienko, Gennady, Gkoulalas-Divanis, Aris, Gruteser, berg, 2008. Springer-Verlag. ISBN 3-540-68548-0, 978- Marco, Kopp, Christine, Liebig, Thomas, and Rechert, 3-540-68548-7. Klaus. Report from dagstuhl: the liberation of mobile location data and its implications for privacy research. Hart, Peter E., Nilsson, Nils J., and Raphael, Bertram. A ACM SIGMOBILE Mobile Computing and Communica- formal basis for the heuristic determination of minimum tions Review, 17(2):7–18, 2013. cost paths. IEEE Transactions on Systems, Science, and Cybernetics, SSC-4(2):100–107, 1968. Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., and Werneck, R. F. Janssens, Davy, Knapen, Luk, Körner, Christine, Mon- Route Planning in Transportation Networks. ArXiv e- reale, Anna, Panis, Luc Int, Rinzivillo, Salvatore, prints, April 2015. URL http://arxiv.org/abs/ Schulz, Daniel, Simini, Filippo, Ardanuy, Jesùs Fraille, 1504.05140. Dhulst, Reinhilde, Pelekis, Nikos, and Theodoridis, Yan- nis. D1.1 report on big data available and privacy Bast, Hannah and Storandt, Sabine. Flow-based guide- aspects. Technical Report D1.1, Universiteit Hasselt book routing. In McGeoch, Catherine C. and Meyer, Ul- Transportation Research Institute, 8 2012. rich (eds.), 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX Liebig, Thomas. Privacy preserving centralized counting 2014, Portland, Oregon, USA, January 5, 2014, pp. of moving objects. In Bacao, Fernando, Santos, Mari- 155–165. SIAM, 2014. ISBN 978-1-61197-319-8. doi: bel Yasmina, and Painho, Marco (eds.), AGILE 2015, 10.1137/1.9781611973198.15. Lecture Notes in Geoinformation and Cartography, pp. 91–103. Springer International Publishing, 2015. ISBN Bast, Hannah, Carlsson, Erik, Eigenwillig, Arno, Geis- 978-3-319-16786-2. berger, Robert, Harrelson, Chris, Raychev, Veselin, and Liebig, Thomas, Piatkowski, Nico, Bockermann, Christian, Viger, Fabien. Fast routing in very large public trans- and Morik, Katharina. Route planning with real-time portation networks using transfer patterns. In Algorithms traffic predictions. In Proceedings of the 16th LWA Work- - ESA 2010, 18th Annual European Symposium. Pro- shops: KDML, IR and FGWM, pp. 83–94, 2014. ceedings, Part I, pp. 290–301, 2010. Niu, Xiaoguang, Zhu, Ying, Cao, Qingqing, Zhang, Xin- Boutsis, Ioannis and Kalogeraki, Vana. Privacy preser- ing, Xie, Wei, and Zheng, Kun. An online-traffic- vation for participatory sensing data. In 2013 IEEE prediction based route finding mechanism for smart city. International Conference on Pervasive Computing and International Journal of Distributed Sensor Networks, Communications, PerCom 2013, San Diego, CA, USA, 501:970256, 2015. March 18-22, 2013, pp. 103–113. IEEE Computer Soci- ety, 2013. Roughgarden, Tim and Tardos, Éva. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236–259, Delling, Daniel, Sanders, Peter, Schultes, Dominik, and 2002. Wagner, Dorothea. Engineering route planning algo- rithms. In Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation [DFG priority pro- gram 1126], pp. 117–139, 2009. N9