A Non-Greedy Spatially Indexed Route-Finding Algorithm for Public Transit in Kathmandu Valley

Abstract

Navigating informal public transit networks in developing urban regions presents unique challenges absent from systems served by established platforms such as Google Maps. In the Kathmandu Valley—encompassing Kathmandu, Lalitpur, and Bhaktapur—public transportation operates across heterogeneous route topologies, including linear bidirectional, circular unidirectional (e.g., Ring Road), and hybrid “lollipop” configurations, none of which are indexed by mainstream navigation services. This paper presents a client-side, offline-first route finding system that combines spatial grid indexing with a non-greedy, penalty-weighted search algorithm specifically engineered for fixed-route transit networks. The system partitions the geographical space into 500 m × 500 m grid cells, enabling amortized O(1) stop lookups, and employs a graduated radius search strategy to identify candidate boarding and alightings stops while accounting for multi-lane road configurations. A weighted scoring function S = 40T + t + 12W balances transfer penalties (T), total travel time (t), and walking distance (W) to rank route options. The algorithm handles both direct and single-transfer routes, with directional constraints on transfer candidate selection to prevent incorrect path selection on circular routes. Performance benchmarking on a physically collected dataset of 55 routes and over 600 GPS-mapped bus stops demonstrates direct route resolution in 0.15 ms and transfer route resolution in 5.37 ms, well within the 200 ms real-time threshold. Scalability experiments on a 5,000-stop network simulation confirm that performance scales sub-linearly with network size. The system is deployed as a cross-platform mobile application, serving an active user base in the Kathmandu Valley. This work contributes a domain-specific alternative to graph-based shortest-path algorithms for transit networks where fixed-route constraints, topology heterogeneity, and infrastructure data scarcity render classical approaches impractical.