Optimizing Public Transit Route Recommendation Systems Using Time-based Dijkstra Algorithm: A Case Study

Shortest-distance public transit route recommendations (classic Dijkstra) do not reflect real traffic conditions. This study proposes a time-based Dijkstra variant that folds a traffic-speed variable into the graph's edge weights, then compares it against distance-based Dijkstra on a simulated Malang City transit map.

Shortest-distance route recommendations can direct passengers to a route that is shorter in distance but slower in actual travel time due to congestion, because real traffic speed is not factored in.

Each graph edge's weight is computed from travel time (distance divided by traffic speed) rather than raw distance. Four congestion scenarios were simulated using four speed tiers (40, 20, 10, and 5 km/h), and time-based Dijkstra's output was compared against distance-based Dijkstra across 35 data points.

Four distance/congestion scenario combinations were tested (short-normal, short-congested, long-normal, long-congested), comparing the estimated time of arrival (ETA) produced by both algorithms in each scenario.

Under congested conditions, time-based Dijkstra produced a much lower ETA than distance-based Dijkstra even when the chosen route was longer in distance — e.g. in the short-congested scenario, 4.14 minutes versus 12.83 minutes for the distance-based route.

Demonstrates that folding a traffic-speed variable into Dijkstra significantly improves travel-time estimation accuracy for public transit route recommendation compared to a purely distance-based approach.

The study remains at the simulation stage; the traffic speeds used are simulated tier values, not real-time vehicle speeds from field data.