Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів
Математичне моделювання в економіці. – 2015. – № 2 (3). – С. 39–50.
Анотація:
Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з урахуванням вартості перельоту у залежності від часу. При цьому шлях може формуватися з урахуванням обмежень за часом, вартістю, бажаними або забороненими проміжними пунктами. Для пошуку шляху мінімальної вартості розроблено і досліджено спеціальний алгоритм оптимізації мурашиними колоніями з динамічним поколінням мурах. Природний паралелізм його обчислювальної схеми дозволяє отримувати і уточнювати отриманий розв’язок із урахуванням змін в умовах перельотів. Подається математична модель задачі, а також опис загальних особливостей запропонованого алгоритму. Для оцінки практичної ефективності алгоритму проведено обчислювальні експерименти, а також порівняння з класичною схемою оптимізації мурашиними колоніями.
Ключові слова: планування маршруту авіаперельотів, динамічна задача пошуку найкоротшого шляху, оптимізація мурашиними колоніями.