Dynamic trip planner for public transport using genetic algorithm
Abstract
This paper reports the development of a public transport trip planner to help the urban traveller in planning and preparing for his commute using public transportation in the city. A Genetic Algorithm (GA) approach that handles real-time Global Positioning Systems (GPS) data from buses of the Metropolitan Transport Corporation (MTC) in Chennai City (India) has been used to develop the planner. The GA has been shown to provide good solutions within the problem’s computation time constraints. The developed trip planner has been implemented for static network data first and subsequently extended to use real-time data. The “walk mode” and Chennai Mass Rapid Transit System (MRTS) have also been included in the geospatial database to extend the route-planner’s capabilities. The algorithm has subsequently been segmented to speed up the prediction process. In addition, a temporal cache has also been introduced during implementation, to handle multiple queries generated simultaneously. The results showed that there is promise for scalability and citywide implementation for the proposed real-time route-planner. The uncertainty and poor service quality perceived with public transport bus services in India could potentially be mitigated by further developments in the route-planner introduced in this paper.
Keyword : dynamic trip planner, genetic algorithm, global positioning system, public transportation, route-planner, static network, real-time data
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Borole, N.; Rout, D.; Goel, N.; Vedagiri, P.; Mathew, T. V. 2013. Multimodal public transit trip planner with real-time transit data, Procedia – Social and Behavioral Sciences 104: 775–784. https://doi.org/10.1016/j.sbspro.2013.11.172
Chen, C.; Kitamura, R.; Chen, J. 1999. Multimodal daily itinerary planner: interactive programming approach, Transportation Research Record: Journal of the Transportation Research Board 1676: 37–43. https://doi.org/10.3141/1676-05
Deng, Y.; Hu, S. 2011. Route optimization of multi-modal travel based on improved genetic algorithm, in Proceedings 2011 International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), 16–18 December 2011, Changchun, China, 1701–1704. https://doi.org/10.1109/TMEE.2011.6199539
Dibbelt, J.; Pajor, T.; Strasser, B.; Wagner, D. 2017. Connection Scan Algorithm. 49 p. Available from Internet: https://arxiv.org/abs/1703.05997v1
Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional. 432 p.
Hiu, W. 1996. Genetic Algorithms, in Surveys and Presentations in Information Systems Engineering (SURPRISE), Imperial College London, UK.
Jariyasunant, J.; Mai, E.; Sengupta, R. 2011. Algorithm for finding optimal paths in a public transit network with real-time data, Transportation Research Record: Journal of the Transportation Research Board 2256: 34–42. https://doi.org/10.3141/2256-05
Kumar, M.; Husian, M.; Upreti, N.; Gupta, D. 2010. Genetic algorithm: review and application, International Journal of Information Technology and Knowledge Management 2(2): 451–454. https://doi.org/10.2139/ssrn.3529843
Nanayakkara, S. C.; Srinivasan, D.; Lup, L. W.; German, X.; Taylor, E; Ong, S. H. 2007. Genetic algorithm based route planner for large urban street networks, in 2007 IEEE Congress on Evolutionary Computation, 25–28 September 2007, Singapore, 4469–4474. https://doi.org/10.1109/CEC.2007.4425056
Obitko, M. 1998. Genetic Algorithms. Available from Internet: https://www.obitko.com/tutorials/genetic-algorithms/index.php
Vanajakshi, L.; Subramanian, S. C.; Sivanandan, R. 2009. Travel time prediction under heterogeneous traffic conditions using global positioning system data from buses, IET Intelligent Transport Systems 3(1): 1–9. https://doi.org/10.1049/iet-its:20080013
Zhao, F.; Zeng, X. 2006. Simulated annealing–genetic algorithm for transit network optimization, Journal of Computing in Civil Engineering 20(1): 57–68. https://doi.org/10.1061/(ASCE)0887-3801(2006)20:1(57)