UDC 519.8
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 lh_dar@hotmail.com
|
|
ANT COLONY OPTIMIZATION ALGORITHMS WITH DIVERSIFIED SEARCH
IN THE PROBLEM OF OPTIMIZATION OF AIRTRAVEL ITINERARY
Abstract. The formulated problem is to find optimal traveler’s path in airline networks, which takes into account cost of the constructed route and user conditions with time-dependent cost of connections. Ant colony system algorithms are proposed to solve the time-dependent problem represented by an extended flight graph. Unlike the available ant algorithm implementations, the developed algorithms take into account the properties of dynamic networks (time-dependent availability and connections cost) and user conditions. The improved approach to the diversification of search in ant colony system algorithms in terms of time dependence for a dense graph increased the quality of the constructed routes from different regions. The proposed algorithms are analyzed for efficiency based on the analysis of the results of a computational experiment from real data.
Keywords: route optimization, flight network, ant algorithms, search diversification, time-expanded networks, dynamic discretization discovery.
FULL TEXT
REFERENCES
- Foschini L., Hershberger J., Suri S. On the complexity of time-dependent shortest paths. Algorithmica. 2014. Vol. 68, N 4. P. 1075–1097.
- Dorigo M., Sttzle T. Ant Colony Optimization. Cambridge, MA: MIT Press, 2004. 319 p.
- Dorigo M., Sttzle T. Ant colony optimization: overview and recent advances. In: Handbook of Metaheuristics. Third Edition. Gendreau V., Potvin J.-Y. (Eds). Cham: Springer, 2019. P. 311–351.
- Hulyanytskyi L.F. New Ant Colony Optimization Algorithm. Modern informatics: problems, achievements and prospects of development. Proc. Int. conf., dedicated to the 60th anniversary of the V.M. Glushkov Institute of Cybernetics of NAS of Ukraine (Kyiv, December 13–15, 2017) Kyiv, 2017. P. 41–43.
- He E., Boland N., Nemhauser G., Savelsbergh M. A dynamic discretization discovery algorithm for the minimum duration time-dependent shortest path problem. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Proc. of 15th Int. Conf. CPAIOR 2018 (Delft, The Netherlands, June 26–29, 2018). Delft, 2018. P. 289–297.
- Hulyanitskyi L.F., Pavlenko A.I. Optimization of paths in the dynamic flight graph by a modified algorithm of ant systems. Mathematical modeling in economics. 2018. N 2. P. 26–39.
- Thomas S., Dorigo M. A short convergence proof for a class of ant colony optimization algorithms. IEEE Transactionson Evolutionary Computation. 2002. Vol. 6, N 4. P. 358–365.
- Hulyanitskyi L.F., Sirenko S.I. Development and research of cooperative model-oriented metaheuristics. Kibernetika i sistemnyj analiz. 2010. Vol. 46, N 5. P. 31–39.
- Hulianytskyi L.F., Sirenko S.I. Cooperative model-based metaheuristics. Electronic Notes in Discrete Mathematics. 2010. Vol. 36. P. 33–40.
- Yakovlev S., Kartashov O., Yarovaya O. On class of genetic algorithms in optimization problems on combinatorial configurations. Proc. of IEEE 13th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2018). 2018. Vol. 1. P. 374–377. https://doi.org/10.1109/STC-CSIT.2018.8526746.
- Hulianytskyi L.F., Riasna I.I. Formalization and classification of combinatorial optimization problems. In: Optimization Methods and Applications. Butenko S., Pardalos P. M., Shylo V. (Eds). Cham: Springer International Publishing AG, 2017. P. 239–250.
