This paper proposes a method of path search that is based on the ant colony algorithm. It aims to obtain a path that is as close as possible to the optimum solution, in a shorter time than existing algorithms, even when the route network has thousands of nodes.
The ant colony algorithm, on which the proposed algorithm is based, is “inspired [by] an analogy with real life behavior of a colony of ants when looking for food” [1]. The ant colony algorithm is used to solve the shortest path problem for vehicle navigation, where there is usually a large search space. Dijkstra’s algorithm, for example, searches for an optimal path with minimum cost, but algorithms such as these suffer from low search efficiency and long search time. Experiments are conducted on two traffic networks and by means of a simulation. The results are compared to those of Dijkstra’s algorithm, showing that the obtained path is near optimal and the time is considerably shorter, even for large networks. Thus, these properties make the algorithm suitable for real-time applications.
Other algorithms, such as A* and genetic algorithms, are also presented in the paper, but no comparison is made to them. In the A* algorithm, based on Dijkstra’s algorithm, fruitless paths are removed from the search space, which is promising for a shorter search time. It is not clear how much better than A* the proposed algorithm performs. In future work, more realistic characteristics of the vehicle navigation systems in traffic networks should be considered.