Ant colony optimization for time dependent shortest path problem in directed multigraph

The paper concerns the approach for searching shortest path between specified nodes in a given graph that represents scheme of possible flights and takes into account time-dependent price. The path may be constructed according to request constraints: time limits, cost, mandatory transit or prohibited items. To find the lowest path cost we developed the ant colony optimization (ACO) based algorithm. Natural parallelism and iterativity of original ACO processing scheme gives the possibility to get and update the best current solution at any moment taking into account flight data changes. The approach of single-generation ACO, that allows optimizing the use of resources and reducing the processing time is suggested and investigated. The paper presents a formal model of the problem, and describes the basic ACO scheme and properties of suggested approach. For assessment practical effectiveness of single-generation algorithm, the experiments are made. The comparison between offered and classical ACO schemes in time and accuracy is given.