УДК 519.8
АЛГОРИТМИ ОПТИМІЗАЦІЇ МУРАШИНИМИ КОЛОНІЯМИ З ДИВЕРСИФІКОВАНИМ
ПОШУКОМ
У ЗАДАЧІ ОПТИМІЗАЦІЇ АВІАПЕРЕЛЬОТІВ
Анотація. Сформульовано задачу пошуку оптимального шляху мандрівника в мережі авіаперельотів, яка враховує вартість побудованого маршруту та наявність користувацьких умов у випадку залежної від часу вартості сполучень. Запропоновано алгоритми систем мурашиних колоній для розв’язування залежної від часу задачі, поданої розширеним графом перельотів, які, на відміну від наявних мурашиних алгоритмів, враховують динамічність мережі (залежність наявності і вартості сполучення від часу) та користувацькі умови. Вдосконалено підхід до диверсифікації пошуку в мурашиних алгоритмах в умовах залежності від часу для щільного графу, що дало змогу підвищити якість побудованих маршрутів, які сполучають різні регіони. Ефективність запропонованих алгоритмів досліджено шляхом аналізу результатів обчислювального експерименту, виконаного з використанням реальних даних.
Ключові слова: оптимізація маршрутів, мережа авіаперельотів, мурашині алгоритми, диверсифікація пошуку, розширені мережі за часом, динамічне виявлення дискретизації.
ПОВНИЙ ТЕКСТ
Гуляницький Леонід Федорович,
доктор техн. наук, завідувач відділу Інституту кібернетики ім. В.М. Глушкова НАН України, Київ,
lh_dar@hotmail.com
Павленко Анна Ігорівна,
кандидат техн. наук, інженер з розроблення програмного забезпечення компанії «Амазон», США,
dmitrieva.anya@gmail.com
СПИСОК ЛІТЕРАТУРИ
- 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.
- Гуляницький Л.Ф. Новий алгоритм оптимізації мурашиними колоніями. Сучасна інформатика: проблеми, досягнення та перспективи розвитку. Пр. Міжн. конф., присвяченої 60-річчю заснування ІК ім. В.М. Глушкова НАН України (Київ, 13–15 грудня 2017 р.) Київ, 2017. С. 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.
- Гуляницький Л. Ф., Павленко А.І. Оптимізація шляхів у динамічному графі перельотів модифікованим алгоритмом мурашиних систем. Математичне моделювання в економіці. 2018. № 2. С. 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.
- Гуляницкий Л.Ф., Сиренко С.И. Разработка и исследование кооперативных моделе-ориентированных метаэвристик. Кибернетика и системный анализ. 2010. Т. 46, № 5. С. 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.
