Fast and efficient real-time route discovery via modified bidirectional A* algorithm

• Proposes MBiA*, a modified bidirectional A* for real-time route discovery on road graphs. • Introduces an incumbent-bound early-termination rule with proved optimality conditions. • Supports directed networks via direction-aware backward expansion for one-way constraints. • Provides theoretical analysis: correctness, termination, and worst-case complexity bounds. • Validates on time-sliced traffic snapshots with repeated-run timing statistics and CIs. Urban mobility applications increasingly require fast and reliable route discovery under congestion and time-varying traffic conditions. This paper presents MBiA*, a modified bidirectional A* algorithm designed for low-latency routing on large urban road networks. MBiA* improves classical bidirectional heuristic search through: (i) an admissible early-termination criterion that avoids unnecessary expansions, (ii) direction-aware backward expansion to handle one-way streets correctly, and (iii) efficient open/closed-set management to reduce search overhead. The proposed framework integrates floating car data (FCD) and time-sliced traffic speeds to construct both distance-weighted and travel-time-weighted graphs, enabling computation of shortest-distance routes as well as fastest-time, recommended routes. We also provide a frontier-intersection correctness proof that rigorously justifies the early-termination criterion for admissible bidirectional heuristic search on directed road graphs. Experiments on the Thessaloniki urban road network across multiple scenarios and representative off-peak and peak conditions show that MBiA* consistently outperforms Dijkstra, classical A*, and standard bidirectional A* in query-time execution, achieving average runtime reductions of approximately 40–60% and reaching up to 81% (off-peak) and 91% (peak) in the best case. In addition, fastest-time routing reduces travel time by 8–31% during off-peak periods and by 50–90% during peak congestion compared with shortest-distance routing, demonstrating the benefit of traffic-aware route recommendation. Results indicate that MBiA* provides an efficient and practical routing backbone for real-time intelligent transportation and smart-city services operating on traffic-updated snapshots.