Comprehensive Performance Analysis and Comparison of Vehicles Routing Algorithms

Abstract—Due to the severe impact of road traffic congestion on both economy and environment, several vehicles routing algorithms have been proposed to optimize travelers itinerary based on real-time traffic feeds or historical data. However, their evaluation methodologies are not as compelling as their key design idea because none of them had been tested under both real transportation map and real traffic data. In this paper, we conduct a deep performance analysis and comparison of four typical vehicles routing algorithms under various scalability levels (i.e. trip length and traffic load) based on realistic transportation simulation. The ultimate goal of this work is to suggest the most suitable routing algorithm to use in different transportation scenarios, so that it can provide a valuable reference for both traffic managers and researchers when they deploy or optimize a large scale centralized Traffic Management System (TMS). The obtained simulation results reveal that dynamic A * is the best routing algorithm if the TMS has sufficient memory or storage capacities, otherwise static A * is also a great alternative