Building the Shortest Path Database in Urban Traffic Network Using RAO Algorithm

Building the Shortest Path Database in Urban Traffic Network Using RAO Algorithm

연구 분야: Databases

학회: International Conference on Mobile, Secure, and Programmable Networking

In urban environments, traffic networks are characterized by fixed distances between nodes, representing intersections or landmarks. Efficiently identifying the shortest path between any two nodes is crucial for various applications, such as route optimization for emergency services, ride-sharing algorithms, and general traffic management. Traditional methods like Dijkstra’s algorithm are computationally intensive, especially for large-scale networks. To address this challenge, we propose a novel approach that precomputes and stores the shortest paths in a dedicated database hosted on a server system. Our methodology leverages the RAO algorithm, an advanced optimization technique, to solve the shortest path problem. Unlike conventional methods, the RAO algorithm adapts to varying conditions and constraints, making it highly suitable for dynamic urban traffic networks. We construct a comprehensive database that contains pre-calculated shortest paths between any two nodes, thereby significantly reducing real-time computational load. To validate the effectiveness of our approach, we conducted experiments on networks of varying complexities: 6-node, 8-node, and 20-node configurations. These experiments serve to emulate different scales of urban traffic networks. We compared the performance of our RAO-based solution with the Particle Swarm Optimization (PSO) algorithm, using Dijkstra’s algorithm as a baseline for evaluation. Our results indicate a marked improvement in computational efficiency and accuracy when using the RAO algorithm. Specifically, the RAO-based solution outperformed the PSO algorithm across all test cases, thereby confirming its suitability for real-world applications. Our research introduces a scalable and efficient solution for precomputing shortest paths in urban traffic networks using the RAO algorithm.