Trip Timing Algorithm for GTFS Data with Redis Model to Improve the Performance
Subject Areas : IT Strategy
Mustafa
Alzaidi
1
Aniko
Vagner
2
Keywords: GTFS, RMH, Redis, NoSQL, Trip Planning,
Abstract :
Accessing public transport plays an essential role in the daily life productivity of people in urban regions. Therefore, it is necessary to represent the spatiotemporal diversity of transit services to evaluate public transit accessibility appropriately. That can be accomplished by determining the shortest path or shortest travel time trip plan. Many applications like ArcGIS provide tools to estimate the trip time using GTFS data. They can perform well in finding travel time. Still, they can be computationally inefficient and impractical with increasing the data dimensions like searching all day time or in case of huge data. Some research proposed recently provides more computationally efficient algorithms to solve the problem. This paper presents a new algorithm to find the timing information for a trip plan between two start and destination points. Also, we introduce RMH (Range Mapping Hash) as a new approach using Redis NoSQL to find and calculate the accessibility of a trip plan with fixed time complexity of O(2) regardless of the city size (GTFS size). We experimented with the performance of this approach and compared it with the traditional run-time algorithm using GTFS data of Debrecen and Budapest. This Redis model can be applied to similar problems where input can be divided into ranges with the same output.
[1] T. Litman, “Integrating Public Health Objectives in Transportation Decision-Making,” American Journal of Health Promotion, vol. 18, no. 1, pp. 103–108, 2003, doi: 10.4278/0890-1171-18.1.103.
[2] T. Litman, “Exploring the Paradigm Shifts Needed To Reconcile Transportation and Sustainability Objectives,” Transp Res Rec, vol. 1670, no. 1, pp. 8–12, Jan. 1999, doi: 10.3141/1670-02.
[3] J. F. Sallis, L. D. Frank, B. E. Saelens, and M. K. Kraft, “Active transportation and physical activity: opportunities for collaboration on transportation and public health research,” Transp Res Part A Policy Pract, vol. 38, no. 4, pp. 249–268, 2004, doi: https://doi.org/10.1016/j.tra.2003.11.003.
[4] T. Shannon, B. Giles-Corti, T. Pikora, M. Bulsara, T. Shilton, and F. Bull, “Active commuting in a university setting: Assessing commuting habits and potential for modal change,” Transp Policy (Oxf), vol. 13, no. 3, pp. 240–253, 2006, doi: https://doi.org/10.1016/j.tranpol.2005.11.002.
[5] A. Golub and K. Martens, “Using principles of justice to assess the modal equity of regional transportation plans,” J Transp Geogr, vol. 41, pp. 10–20, 2014, doi: https://doi.org/10.1016/j.jtrangeo.2014.07.014.
[6] K. Martens, A. Golub, and G. Robinson, “A justice-theoretic approach to the distribution of transportation benefits: Implications for transportation planning practice in the United States,” Transp Res Part A Policy Pract, vol. 46, no. 4, pp. 684–695, 2012, doi: https://doi.org/10.1016/j.tra.2012.01.004.
[7] K. Coffel et al., “Guidelines for Providing Access to Public Transportation Stations,” 2012. [8] M. Catala, S. Dowling, and D. M. Hayward, “Expanding the Google Transit Feed Specification to Support Operations and Planning,” 2011.
[9] J. Wong, “Leveraging the General Transit Feed Specification for Efficient Transit Analysis,” Transportation Research Record: Journal of the Transportation Research Board, vol. 2338, pp. 11–19, Dec. 2013, doi: 10.3141/2338-02.
[10] J. Wong, L. Reed, K. Watkins, and R. Hammond, “Open Transit Data: State of the Practice and Experiences from Participating Agencies in the United States,” 2013.
[11] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer Math (Heidelb), vol. 1, no. 1, pp. 269–271, 1959, doi: 10.1007/BF01386390.
[12] R. Bellman, “On a routing problem,” Q Appl Math, vol. 16, no. 1, pp. 87–90, 1958.
[13] R. W. Floyd, “Algorithm 97: Shortest path,” Commun ACM, vol. 5, no. 6, p. 345, 1962, doi: http://doi.acm.org/10.1145/367766.368168.
[14] D. B. Johnson, “Efficient Algorithms for Shortest Paths in Sparse Networks,” J. ACM, vol. 24, no. 1, pp. 1–13, Jan. 1977, doi: 10.1145/321992.321993.
[15] J. Mote, I. Murthy, and D. L. Olson, “A parametric approach to solving bicriterion shortest path problems,” Eur J Oper Res, vol. 53, no. 1, pp. 81–92, 1991, doi: https://doi.org/10.1016/0377-2217(91)90094-C.
[16] J. C. Namorado Climaco and E. Queirós Vieira Martins, “A bicriterion shortest path algorithm,” Eur J Oper Res, vol. 11, no. 4, pp. 399–404, 1982, doi: https://doi.org/10.1016/0377-2217(82)90205-3.
[17] E. Q. V. Martins, “On a multicriteria shortest path problem,” Eur J Oper Res, vol. 16, no. 2, pp. 236–245, 1984, doi: https://doi.org/10.1016/0377-2217(84)90077-8.
[18] C. Tung Tung and K. Lin Chew, “A multicriteria Pareto-optimal path algorithm,” Eur J Oper Res, vol. 62, no. 2, pp. 203–209, 1992, doi: https://doi.org/10.1016/0377-2217(92)90248-8.
[19] J. Brumbaugh-Smith and D. Shier, “An empirical investigation of some bicriterion shortest path algorithms,” Eur J Oper Res, vol. 43, no. 2, pp. 216–224, 1989, doi: https://doi.org/10.1016/0377-2217(89)90215-4.
[20] H. W. Corley and I. D. Moon, “Shortest Paths in Networks with Vector Weights,” J. Optim. Theory Appl., vol. 46, no. 1, pp. 79–86, May 1985, doi: 10.1007/BF00938761.
[21] H. G. Daellenbach and C. A. De Kluyver, “Note on Multiple Objective Dynamic Programming,” Journal of the Operational Research Society, vol. 31, no. 7, pp. 591–594, Jul. 1980, doi: 10.1057/jors.1980.114.
[22] A. J. V Skriver and K. Andersen, “A label correcting approach for solving bicriterion shortest-path problems,” Comput Oper Res, vol. 27, pp. 507–524, May 2000, doi: 10.1016/S0305-0548(99)00037-4.
[23] P. Dell’Olmo, M. Gentili, and A. Scozzari, “On Finding Dissimilar Pareto-Optimal Paths,” Eur J Oper Res, vol. 162, pp. 70–82, Apr. 2005, doi: 10.1016/j.ejor.2003.10.033.
[24] E. Machuca, L. Mandow, and J. Cruz, “An evaluation of heuristic functions for bicriterion shortest path problems,” New Trends in Artificial Intelligence. Proceedings of EPIA’09, Jan. 2009.
[25] L. Mandow and J. L. de la Cruz, “Frontier Search for Bicriterion Shortest Path Problems,” in Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence, NLD: IOS Press, 2008, pp. 480–484.
[26] L. Mandow and J. L. Pérez de la Cruz, “Path recovery in frontier search for multiobjective shortest path problems,” J Intell Manuf, vol. 21, no. 1, pp. 89–99, 2010, doi: 10.1007/s10845-008-0169-2.
[27] R. Mart\’\i, J. Luis González Velarde, and A. Duarte, “Heuristics for the Bi-Objective Path Dissimilarity Problem,” Comput. Oper. Res., vol. 36, no. 11, pp. 2905–2912, Nov. 2009, doi: 10.1016/j.cor.2009.01.003.
[28] A. Raith and M. Ehrgott, “A comparison of solution strategies for biobjective shortest path problems,” Comput Oper Res, vol. 36, pp. 1299–1331, Apr. 2009, doi: 10.1016/j.cor.2008.02.002.
[29] J. Widuch, “A Label Correcting Algorithm for the Bus Routing Problem,” Fundam Inform, vol. 118, pp. 305–326, Aug. 2012, doi: 10.3233/FI-2012-716.
[30] C.-L. Liu, T.-W. Pai, C.-T. Chang, and C.-M. Hsieh, “Path-planning algorithms for public transportation systems,” in ITSC 2001. 2001 IEEE Intelligent Transportation Systems. Proceedings (Cat. No.01TH8585), 2001, pp. 1061–1066. doi: 10.1109/ITSC.2001.948809.
[31] A. V. MUSTAFA ALZAIDI, “Trip Planning Algorithm For Gtfs Data With Nosql Structure To Improve The Performance,” J Theor Appl Inf Technol, vol. Vol.99. No, no. 10 31st May 2021, pp. 2290–2300, May 2021.
[32] S. Farber, B. Ritter, and L. Fu, “Space–time mismatch between transit service and observed travel patterns in the Wasatch Front, Utah: A social equity perspective,” Travel Behav Soc, vol. 4, pp. 40–48, 2016, doi: https://doi.org/10.1016/j.tbs.2016.01.001.
[33] S. K. Fayyaz S., X. C. Liu, and G. Zhang, “An efficient General Transit Feed Specification (GTFS) enabled algorithm for dynamic transit accessibility analysis,” PLoS One, vol. 12, no. 10, pp. e0185333-, Oct. 2017, [Online]. Available: https://doi.org/10.1371/journal.pone.0185333.
[34] S. Motamed, A. Broumandnia, and A. Nourbakhsh, “Multimodal biometric recognition using particle swarm optimization-based selected features,” Journal of Information Systems and Telecommunication, vol. 1, pp. 79–87, Mar. 2013, doi: 10.7508/jist.2013.02.002.
[35] P. Goli and M. M. R. KARAMI, “Speech Intelligibility Improvement in Noisy Environments for Near-End Listening Enhancement,” 2016.
[36] G. M. Saeed, H. B. N. Babak, and L. Mojtaba, “Achieving Better Performance of S-MMA Algorithm in the OFDM Modulation,” 2013.
[37] Q. Zervaas, The Definitive Guide to GTFS (Consuming open public transportation data with the General Transit Feed Specifcation), First Edit. 2014. [Online]. Available: http://gtfsbook.com/gtfs-book-sample.pdf.
[38] N. Amirah, D. Mohamad, and A. Hilmy, Acceptable walking distance accessible to the nearest bus stop considering the service coverage. 2021. doi: 10.1109/ICOTEN52080.2021.9493435. [39] “Introduction to Redis – Redis.” https://redis.io/topics/introduction (accessed Jan. 18, 2021).
[40] S. Tapia-Fernández, D. García-García, and P. García-Hernandez, “Key Concepts, Weakness and Benchmark on Hash Table Data Structures,” Algorithms, vol. 15, no. 3, 2022, doi: 10.3390/a15030100.