ژنتیک ترکیبی و الگوریتم کلونی مورچه برای یافتن کوتاه ترین مسیر A Hybrid Genetic and Ant Colony Algorithm for Finding the Shortest Path in Dynamic Traffic Networks

1. INTRODUCTION The shortest path problem in traffic networks is a key element in intelligent traffic systems. It is of importance because of the fact that many travelers face the practical problem of identifying the most efficient route on their daily journeys. The objective of the shortest path problem is to determine the paths for travelers, which would lead to the minimum total travel time. This is a classical combinatorial optimization problem, which has recently attracted more attention from researchers because of increasing levels of traffic congestion, particularly in urban areas. The shortest path problem can be sub-classified into either the static or dynamic shortest path problem according to the characteristics of the network. The static shortest path problem is to find the shortest path between two points in a deterministic network, which is a P problem. There are many classical algorithms for solving the static shortest path problem. Dijkstra algorithm, Floyd algorithm and Dreyfus algorithm are well-known static shortest path algorithms [1–3]. Some variations of these algorithms are further discussed [4, 5]. Static shortest path algorithms are based on the Bellman optimization principle [6], namely, in the shortest path from the origin node to the destination, the path from the origin node to the intermediate node is also the shortest path to the intermediate node, that is, the sub-path of shortest path is also shortest path. However, although these classical algorithms are effective in static systems, they are not efficient to determine the shortest path in dynamic networks. This is because in dynamic networks the obtained sub-path is the shortest path at any one time and may not be the shortest path at another time. In traffic networks, shortest path problems are always dynamic. The traffic conditions always change over time (e.g., some road sections may be more crowded than usual during rush hour periods), as a result of these changes, the traveler may need to change his pre-planned shortest path to his destination due to changes in real-time road conditions. An efficient approach is needed to rapidly find the shortest path when the environment changes dynamically. Therefore, the dynamic shortest path problem in real-time traffic networks is to find an optimal path for travelers according to real-time traffic conditions, which is a NP-hard problem.