MUSE: Multimodal Separators for Efficient Route Planning in Transportation Networks

References

• Antsfeld L, Walsh T (2012) Finding multi-criteria optimal paths in multi-modal public transportation networks using the transit algorithm. Proc. ITS World Congress. Google Scholar
• Barrett C, Jacob R, Marathe M (2000) Formal-language-constrained path problems. SIAM J. Comput. 30(3):809–837.Crossref, Google Scholar
• Bast H (2009) Car or public transport—Two worlds. Efficient Algorithms (Springer, Berlin), 355–367.Crossref, Google Scholar
• Bast H, Funke S, Matijevic D (2006) Ultrafast shortest-path queries via transit nodes. Ninth DIMACS Implementation Challenge 175–192. http://dx.doi.org/10.1090/dimacs/074/07.Google Scholar
• Bast H, Hertel M, Storandt S (2016) Scalable transfer patterns. Proc. Meeting on Algorithm Engineering and Experiments, 15–29.Google Scholar
• Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, et al. (2016) Route planning in transportation networks. Algorithm Engineering (Springer, Berlin), 19–80.Crossref, Google Scholar
• Bauer R, Delling D, Wagner D (2011) Experimental study of speed up techniques for timetable information systems. Networks 57(1):38–52.Crossref, Google Scholar
• Baum M, Dibbelt J, Pajor T, Wagner D (2016) Dynamic time-dependent route planning in road networks with user preferences. Experimental Algorithms, 33–49.Crossref, Google Scholar
• Baum M, Buchhold V, Sauer J, Wagner D, Zündorf T (2019) Unlimited transfers for multi-modal route planning: An efficient solution. Proc. Annual Eur. Sympos. on Algorithms, vol. 144, 1–14:16.Google Scholar
• Bentley JL, Ottmann TA (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9):643–647.Crossref, Google Scholar
• Bhatia N (2010) Survey of nearest neighbor techniques. Internat. J. Comput. Sci. Inform. Security 8(2). Google Scholar
• Brodal GS, Jacob R (2004) Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes Theoretical Comput. Sci. 92:3–15.Crossref, Google Scholar
• Brüggemann-Klein A (1993) Regular expressions into finite automata. Theoretical Comput. Sci. 120(2):197–213.Crossref, Google Scholar
• Chen Y, Guizani M, Zhang Y, Wang L, Crespi N, Lee GM, Wu T (2019) When traffic flow prediction and wireless big data analytics meet. IEEE Network 33(3):161–167.Crossref, Google Scholar
• Cionini A, D’Angelo G, D’Emidio M, Frigioni D, Giannakopoulou K, Paraskevopoulos A, Zaroliagis C (2017) Engineering graph-based models for dynamic timetable information systems. J. Discrete Algorithms 46-47:40–58.Crossref, Google Scholar
• Delling D, Pajor T, Wagner D (2009) Accelerating multi-modal route planning by access-nodes. Proc. Eur. Sympos. on Algorithms, 587–598.Google Scholar
• Delling D, Pajor T, Werneck RF (2014) Round-based public transit routing. Transportation Sci. 49(3):591–604.Link, Google Scholar
• Delling D, Dibbelt J, Pajor T, Zündorf T (2017) Faster transit routing by hyper partitioning. D’Angelo G, Dollevoet T, eds. Proc. 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, vol. 59, 1–8.Google Scholar
• Delling D, Goldberg AV, Pajor T, Werneck RF (2011a) Customizable route planning. Proc. Internat. Sympos. on Experimental Algorithms, 376–387.Crossref, Google Scholar
• Delling D, Goldberg AV, Razenshteyn I, Werneck RF (2011b) Graph partitioning with natural cuts. Proc. Internat. Parallel & Distributed Processing Symposium (IEEE, New York), 1135–1146.Crossref, Google Scholar
• Delling D, Sanders P, Schultes D, Wagner D (2006) Highway hierarchies star. Ninth DIMACS Implementation Challenge, 141–174. http://dx.doi.org/10.1090/dimacs/074/06.Google Scholar
• Demetrescu C, Goldberg AV, Johnson DS (2009) The Shortest Path Problem: Ninth Dimacs Implementation Challenge (American Mathematical Society).Google Scholar
• Dibbelt J, Pajor T, Wagner D (2015) User-constrained multimodal route planning. J. Experiment. Algorithmics (JEA) 19, http://dx.doi.org/10.1145/2699886.Crossref, Google Scholar
• Dibbelt J, Pajor T, Strasser B, Wagner D (2013) Intriguingly simple and fast transit routing. Proc. Internat. Sympos. on Experimental Algorithms, 43–54.Crossref, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Math. 1(1):269–271.Crossref, Google Scholar
• Djidjev HN (1982) On the problem of partitioning planar graphs. SIAM J. Algebraic Discrete Methods 3(2):229–240.Crossref, Google Scholar
• DOT (2015) Beyond traffic 2045: Trends and choices. Technical report, US Department of Transportation, Washington, DC.Google Scholar
• Eppstein D, Goodrich MT (2008) Studying (non-planar) road networks through an algorithmic lens. Proc. ACM SIGSPATIAL Internat. Conf. on Advances in Geographic Information Systems (ACM, New York).Crossref, Google Scholar
• Falek A (2019) osm-to-graph. Accessed March 14, 2019, https://github.com/aminefalek/osm-to-graph. Google Scholar
• Falek A (2021a) Muse: Multimodal separators for efficient route planning in transportation networks Zenodo dataset, http://dx.doi.org/10.5281/zenodo.5276749.Google Scholar
• Falek A (2021b) Muse: Multimodal separators for efficient route planning in transportation networks. Accessed August 13, 2021, https://github.com/aminefalek/muse.Google Scholar
• Garey MR, Johnson DS (2002) Computers and Intractability, vol. 29 (W. H. Freeman & Co., New York).Google Scholar
• Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Proc. Internat. Workshop on Experimental and Efficient Algorithms, 319–333.Google Scholar
• Geofabrik O (2019) Openstreetmap data extract. Accessed March 14, 2019, https://download.geofabrik.de/europe/france/ile-de-france.html.Google Scholar
• Giannakopoulou K, Paraskevopoulos A, Zaroliagis C (2019) Multimodal dynamic journey-planning. Algorithms 12(10):213.Crossref, Google Scholar
• Goldberg AV, Harrelson C (2005) Computing the shortest path: A* search meets graph theory. Proc. ACM-SIAM Sympos. on Discrete Algorithms, 156–165.Google Scholar
• Goldberg AV, Kaplan H, Werneck RF (2006) Reach for a*: Shortest path algorithms with preprocessing. Ninth DIMACS Implementation Challenge, 93–140.Google Scholar
• Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• Hilger M, Köhler E, Möhring RH, Schilling H (2009) Fast point-to-point shortest path computations with arc-flags. Ninth DIMACS Implementation Challenge, vol. 74, 41–72. http://dx.doi.org/10.1090/dimacs/074/03.Google Scholar
• Huber S, Rust C (2016) Calculate travel time and distance with openstreetmap data using the open source routing machine (osrm). Stata J. 16(2):416–423.Crossref, Google Scholar
• Ile de France Mobilités (2020) Données offre de transport ile-de-france mobilités au format gtfs. https://data.iledefrance-mobilites.fr/explore/dataset/offre-horaires-tc-gtfs-idf/information/.Google Scholar
• Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Scientific Comput. 20(1):359–392.Crossref, Google Scholar
• Kaufman DE, Smith RL (1993) Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. J. Intelligent Transportation Systems 1(1). http://dx.doi.org/10.1080/10248079308903779.Google Scholar
• Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell System Technical J. 49(2):291–307.Crossref, Google Scholar
• Kirchler D, Liberti L, Pajor T, Wolfler Calvo R (2011) Unialt for regular language contrained shortest paths on a multi-modal transportation network. Proc. Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.Google Scholar
• Maue J, Sanders P, Matijevic D (2010) Goal-directed shortest-path queries using precomputed cluster distances. J. Experiment. Algorithmics (JEA)14:3–2, http://dx.doi.org/10.1007/11764298_29.Google Scholar
• Mooney P, Minghini M, Foody G, See L, Fritz S, Mooney P, Olteanu-Raimond Fonte CC, Antoniouz V (2017) Mapping and the citizen sensor. OpenStreetMap Data (Ubiquity Press), 37–59.Google Scholar
• Müller-Hannemann M, Schulz F, Wagner D, Zaroliagis C (2007) Timetable information: Models and algorithms. Algorithmic Methods for Railway Optimization, 67–90. http://dx.doi.org/10.1007/978-3-540-74247-0_3.Crossref, Google Scholar
• Nannicini G, Delling D, Liberti L, Schultes D (2008) Bidirectional a* search for time-dependent fast paths. Proc. Internat. Workshop on Experimental and Efficient Algorithms, 334–346.Google Scholar
• Navitia Open Data (2020) France public transport data. https://navitia.opendatasoft.com/explore/?refine.geographicarea=France.Google Scholar
• Orda A, Rom R (1990) Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3):607–625.Crossref, Google Scholar
• Pyrga E, Schulz F, Wagner D, Zaroliagis CD (2004) Experimental comparison of shortest path approaches for timetable information. ALENEX/ANALC (Citeseer), 88–99. Google Scholar
• Pyrga E, Schulz F, Wagner D, Zaroliagis C (2008) Efficient models for timetable information in public transportation systems. J. Experiment. Algorithmics (JEA) 12, http://dx.doi.org/10.1145/1227161.1227166.Crossref, Google Scholar
• Sanders P, Schulz C (2012) Distributed evolutionary graph partitioning. Proc. Workshop on Algorithm Engineering and Experiments (SIAM, Philadelphia), 16–29.Crossref, Google Scholar
• Sauer J, Wagner D, Zündorf T (2020) Faster multi-modal route planning with bike sharing using ULTRA. Proc. 18th Internat. Sympos. on Experimental Algorithms, vol. 160, 16:1–16:14.Google Scholar
• Schilling H (2012) Tomtom navigation: How mathematics help getting through traffic faster. Proc. Internat. Sympos. on Mathematical Programming.Google Scholar
• Sedgewick R, Vitter JS (1986) Shortest paths in euclidean graphs. Algorithmica 1:31–48.Crossref, Google Scholar
• Strasser B (2017) Dynamic time-dependent routing in road networks through sampling. Proc. Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.Google Scholar
• Thomson RC, Richardson DE (1995) A graph theory approach to road network generalisation. Proc. Internat. Cartographic Conf., 1871–1880.Google Scholar
• Ulloa L, Lehoux-Lebacque V, Roulland F (2018) Trip planning within a multimodal urban mobility. IET Intelligent Transport Systems 12(2):87–92.Crossref, Google Scholar
• Yang F, Vereshchaka A, Dong W (2018) Predicting and optimizing city-scale road traffic dynamics using trajectories of individual vehicles. Proc. IEEE Internat. Conf. on Big Data, 173–180.Google Scholar