Efficient Data Structure and Algorithms for Minimum Transfers in Public Transportation Network
Srikanth Mithinti, Aditya Pandey, G. Ramakrishna · 2024
This paper explores the min-transfers problem, defined as the minimum number of vehicle transfers needed to travel from one location to all locations in a public transportation network, represented using a temporal graph. Solving this problem is crucial because transfers, which involve switching vehicles, add complexity and may extend journey times. This is especially important for elderly, disabled individuals, women, children, and anyone traveling with heavy luggage, as minimizing transfers can significantly ease their travel experience. While previous studies have focused on minimizing the number of edges rather than vehicle transfers. To address this, we introduce a novel data structure Temporal Paths Preservation (tpp)-graph, to calculate the minimum number of transfers from a source location to all the locations efficiently. We present five algorithms tailored for solving the one-to-all min-transfers problem using tpp-graph: the Single Queue Algorithm, the No Queue Algorithm, the Multiple Queue Algorithm, the Priority Queue Algorithm and the Multiple Priority Queue Algorithm. We assess the performance of these algorithms through experiments on real-world public transportation datasets, providing insights into their running times and efficiency.