Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів
Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з у...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2015
|
| Назва видання: | Математичне моделювання в економіці |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/131773 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-131773 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1317732018-03-31T03:03:02Z Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів Гуляницький, Л.Ф. Павленко, А.І. Математичні та інформаційні моделі в економіці Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з урахуванням вартості перельоту у залежності від часу. При цьому шлях може формуватися з урахуванням обмежень за часом, вартістю, бажаними або забороненими проміжними пунктами. Для пошуку шляху мінімальної вартості розроблено і досліджено спеціальний алгоритм оптимізації мурашиними колоніями з динамічним поколінням мурах. Природний паралелізм його обчислювальної схеми дозволяє отримувати і уточнювати отриманий розв’язок із урахуванням змін в умовах перельотів. Подається математична модель задачі, а також опис загальних особливостей запропонованого алгоритму. Для оцінки практичної ефективності алгоритму проведено обчислювальні експерименти, а також порівняння з класичною схемою оптимізації мурашиними колоніями. Рассмотрена задача поиска оптимального маршрута путешественника между заданными пунктами с дополнительными условиями в сети авиасообщений определенного региона. Предлагается и исследуется подход к решению задачи поиска пути между заданными вершинами на известном графе, который представляет схему возможных авиаперелетов, с учетом стоимости перелета в зависимости от времени. При этом путь может формироваться с учетом ограничений по времени, стоимости, желательным или запрещенным промежуточным пунктам. Для поиска пути минимальной стоимости разработан и исследован специальный алгоритм оптимизации муравьиными колониями с динамическим поколением муравьев. Он позволяет оптимизировать использование ресурсов, а естественный параллелизм вычислительной схемы позволяет получать и уточнять полученное решение с учетом изменений в условиях перелетов. Приводится математическая модель задачи, а также описаны общие особенности предложенного алгоритма. Для оценки практической эффективности разработанного алгоритма проведены вычислительные эксперименты, а также сравнение с классической схемой оптимизации муравьиными колониями по времени и точности решений. In this paper we introduce a travel planning problem between specified points with additional constraints in a particular region of air transportation network. The research concerns the approach for searching shortest path between specified nodes in a given graph that represents scheme of possible flights with time-dependent price. The path can be formed taking into account the constraints of time, cost, desired or prohibited points. Described shortest path problem is solved by developed and investigated sophisticated ant colony optimization based algorithm with dynamic population size. It allows to optimize the use of resources and reduce the processing time. Natural parallelism of ant colony optimization scheme allows to receive and update the obtained solution with respect to flights conditions changes. The paper includes mathematical model of the problem, as well as describes the general features of the proposed algorithm. To assess the practical effectiveness of the algorithm some computational experiments and comparison with classical ant colony optimization scheme on time and solutions accuracy were held. 2015 Article Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. 2409-8876 http://dspace.nbuv.gov.ua/handle/123456789/131773 004.8:519.85:656.7 uk Математичне моделювання в економіці Інститут телекомунікацій і глобального інформаційного простору НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці |
| spellingShingle |
Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці Гуляницький, Л.Ф. Павленко, А.І. Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів Математичне моделювання в економіці |
| description |
Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з урахуванням вартості перельоту у залежності від часу. При цьому шлях може формуватися з урахуванням обмежень за часом, вартістю, бажаними або забороненими проміжними пунктами. Для пошуку шляху мінімальної вартості розроблено і досліджено спеціальний алгоритм оптимізації мурашиними колоніями з динамічним поколінням мурах. Природний паралелізм його обчислювальної схеми дозволяє отримувати і уточнювати отриманий розв’язок із урахуванням змін в умовах перельотів. Подається математична модель задачі, а також опис загальних особливостей запропонованого алгоритму. Для оцінки практичної ефективності алгоритму проведено обчислювальні експерименти, а також порівняння з класичною схемою оптимізації мурашиними колоніями. |
| format |
Article |
| author |
Гуляницький, Л.Ф. Павленко, А.І. |
| author_facet |
Гуляницький, Л.Ф. Павленко, А.І. |
| author_sort |
Гуляницький, Л.Ф. |
| title |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_short |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_full |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_fullStr |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_full_unstemmed |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_sort |
динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| publisher |
Інститут телекомунікацій і глобального інформаційного простору НАН України |
| publishDate |
2015 |
| topic_facet |
Математичні та інформаційні моделі в економіці |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/131773 |
| citation_txt |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. |
| series |
Математичне моделювання в економіці |
| work_keys_str_mv |
AT gulânicʹkijlf dinamíčnazadačapošukunajkorotšogošlâhuzdodatkovimiumovamidlâzadačípobudovimaršrutuavíaperelʹotív AT pavlenkoaí dinamíčnazadačapošukunajkorotšogošlâhuzdodatkovimiumovamidlâzadačípobudovimaršrutuavíaperelʹotív |
| first_indexed |
2023-10-18T21:02:56Z |
| last_indexed |
2023-10-18T21:02:56Z |
| _version_ |
1796151788647219200 |