An ant colony optimization approach for the preference-based shortest path search

This article proposes a modified ant colony system algorithm for finding the shortest path with preferred links. Most of the shortest path search algorithms focus on finding the distance or time shortest paths. However, these shortest paths may not necessarily be the optimum path for drivers who prefer choosing a less short, yet more reliable or flexible path. Accordingly, a preference-based shortest path search algorithm is proposed that uses the properties of the links in a map, as specified by a set of data provided by the user of the car navigation system. The proposed algorithm is implemented in C and experiments are performed using maps that include 64, 128, 192, and 256 nodes with 118, 242, 362, and 484 links, respectively. The simulation results with various parameter sets confirm that the proposed algorithm is effective for finding the preference-based shortest path.