Ant colony optimization applied to route planning using link travel time predictions

摘要

Finding the shortest path in a road network is a well known problem. Various proven static algorithms such as Dijkstra and A* are extensively evaluated and implemented. When confronted with dynamic costs, such as link travel time predictions, alternative route planning algorithms have to be applied. This paper applies Ant Colony Optimization combined with link travel time predictions to find routes that reduce the time spend by travels by taking into account link travel time predictions. The presented algorithm is evaluated using simulations in real world traffic networks.