To Tu Cuong
ABSTRACT
Most existing algorithms assume that public transit networks are static. However in reality, a bus may be delayed or canceled, which causes routing algorithms to generate non-optimal journeys. We propose CrowdRoute, an algorithm that exploits real-time information contributed by the crowd, to solve the earliest arrival problem in public transit networks.
- General transit feed specification (GTFS). https://developers.google.com/transit/gtfs/, August 2013.Google Scholar
- Waze. www.waze.com, July 2013.Google Scholar
- Yahoo! News. http://news.yahoo.com/google-discloses-paid-966-million-waze-220918812.html, July 2013.Google Scholar
- H. Bast. Efficient Algorithms. chapter Car or Public Transport - Two Worlds, pages 355--367. Springer-Verlag, Berlin, Heidelberg, 2009. Google ScholarDigital Library
- H. Bast, E. Carlsson, and A. Eigenwillig. Fast routing in very large public transportation networks using transfer patterns. In European Symposium on Algorithms, 2010. Google ScholarDigital Library
- H. Bast, S. Funke, and D. Matijevic. Ultrafast shortest-path queries via transit nodes. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 74, 2009.Google Scholar
- J. L. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communications of the ACM, 18(9): 509--517, 1975. Google ScholarDigital Library
- J. L. Bently and H. Maurer. Efficient worst-case data structures for range searching. Acta Informatica, 13(2): 155--168, 1980.Google ScholarDigital Library
- E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '11, pages 1082--1090, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry Algorithms and Applications. Springer-Verlag, 2008. Google ScholarDigital Library
- C. Demetrescu and G. F. Italiano. Experimental Analysis of Dynamic All Pairs Shortest. ACM Transactions on Algorithms, 2(4): 578--601, 2006. Google ScholarDigital Library
- E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1): 269--271, 1959.Google ScholarDigital Library
- Y. Disser, M. Müller-Hannemann, and M. Schnee. Multi-criteria shortest paths in time-dependent train networks. In Experimental Algorithms, volume 5038 of Lecture Notes in Computer Science, pages 347--361. Springer-Verlag, 2008. Google ScholarDigital Library
- A. Doan, R. Ramakrishnan, and A. Y. Halevy. Crowdsourcing Systems on the World-Wide Web. Communications of the ACM, 54(4): 86--96, 2011. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In WEA'08 Proceedings of the 7th International Conference on Experimental Algorithm, volume 2, pages 319--333, 2008. Google ScholarDigital Library
- E. Köhler, R. H. Möhring, and H. Schilling. Acceleration of shortest path and constrained shortest path computation. In Proceedings of the 4th International Conference on Experimental and Efficient Algorithms, WEA'05, pages 126--138, Berlin, Heidelberg, 2005. Springer-Verlag. Google ScholarDigital Library
- E. M. McCreight. Priority Search Trees. SIAM Journal on Computing, 14(2): 257--276, 1985.Google ScholarCross Ref
- D. Pfoser, A. Efentakis, A. Voisard, and C. Wenk. Exploiting road network properties in efficient shortest-path computation. Technical report, International Computer Science Institute, 2009.Google Scholar
- M. Rice and V. Tsotras. Graph indexing of road networks for shortest path queries with label restrictions. Proceedings of the VLDB Endowment, pages 69--80, 2010. Google ScholarDigital Library
- D. Schultes and P. Sanders. Dynamic highway-node routing. In Proceedings of the 6th International Conference on Experimental Algorithms, WEA'07, pages 66--79, Berlin, Heidelberg, 2007. Springer-Verlag. Google ScholarDigital Library
Index Terms
- CrowdRoute: a crowd-sourced routing algorithm in public transit networks
Recommendations
A Crowdsourcing Practices Framework for Science Funding Call Processes
OpenSym '17: Proceedings of the 13th International Symposium on Open Collaboration CompanionPublic scientific research funding agencies (funding agencies) are charged with the task of implementing government science policy and identifying research projects worthy of funding. They play an important role in creating value for society through ...
Study and Application of Establishment Method Based on TransCAD for Urban Public Transit Basic Data System
ICICTA '09: Proceedings of the 2009 Second International Conference on Intelligent Computation Technology and Automation - Volume 03Public transit network has a wide range of data, its storage, display, and management process is very complicated. The use of TransCAD software contribute to establish intuitionistic public transit basic data system which would has strong ...
Value creation, ICT, and co-production in public sector: bureaucracy, opensourcing and crowdsourcing
dg.o '17: Proceedings of the 18th Annual International Conference on Digital Government ResearchThis paper contributes to the e-government literature discussing the role of ICTs as enabler of different modes of production of public services. E-government developments are often associated with organization transformations aimed to increase the ...
Comments