A NOVEL ANT COLONY OPTIMIZATION ALGORITHM FOR THE SHORTEST-PATH PROBLEM IN TRAFFIC NETWORKS

Abstract

The Ant Colony Optimization (ACO) algorithm is a metaheuristic nature-inspired technique for solving various combinatorial optimization problems. The ACO algorithm has already shown its efficiency in many practical optimization problems. The shortest-path problem is an important combinatorial optimization problem in network optimization. In this paper, a novel algorithm based on ACO to solve the single-pair shortest-path problem in traffic networks is introduced. In this algorithm, a new strategy is developed to find the best solution in a local search, by which the ants seek the shortest path using both a pheromone-trail-following mechanism and an orientation-guidance mechanism. A new method is designed to update the pheromone trail. To demonstrate the good performance of the algorithm, an experiment is conducted on a traffic network. The experimental results show that the proposed algorithm produces good-quality solutions and has high efficiency in finding the shortest path between two nodes; it proves to be a vast improvement in solving shortest-path problems in traffic networks. The algorithm can be used for vehicle navigation in intelligent transportation systems.