УДК 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.
