Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів
Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з у...
Saved in:
| Published in: | Математичне моделювання в економіці |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131773 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-131773 |
|---|---|
| record_format |
dspace |
| spelling |
Гуляницький, Л.Ф. Павленко, А.І. 2018-03-30T17:41:45Z 2018-03-30T17:41:45Z 2015 Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. 2409-8876 https://nasplib.isofts.kiev.ua/handle/123456789/131773 004.8:519.85:656.7 Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з урахуванням вартості перельоту у залежності від часу. При цьому шлях може формуватися з урахуванням обмежень за часом, вартістю, бажаними або забороненими проміжними пунктами. Для пошуку шляху мінімальної вартості розроблено і досліджено спеціальний алгоритм оптимізації мурашиними колоніями з динамічним поколінням мурах. Природний паралелізм його обчислювальної схеми дозволяє отримувати і уточнювати отриманий розв’язок із урахуванням змін в умовах перельотів. Подається математична модель задачі, а також опис загальних особливостей запропонованого алгоритму. Для оцінки практичної ефективності алгоритму проведено обчислювальні експерименти, а також порівняння з класичною схемою оптимізації мурашиними колоніями. Рассмотрена задача поиска оптимального маршрута путешественника между заданными пунктами с дополнительными условиями в сети авиасообщений определенного региона. Предлагается и исследуется подход к решению задачи поиска пути между заданными вершинами на известном графе, который представляет схему возможных авиаперелетов, с учетом стоимости перелета в зависимости от времени. При этом путь может формироваться с учетом ограничений по времени, стоимости, желательным или запрещенным промежуточным пунктам. Для поиска пути минимальной стоимости разработан и исследован специальный алгоритм оптимизации муравьиными колониями с динамическим поколением муравьев. Он позволяет оптимизировать использование ресурсов, а естественный параллелизм вычислительной схемы позволяет получать и уточнять полученное решение с учетом изменений в условиях перелетов. Приводится математическая модель задачи, а также описаны общие особенности предложенного алгоритма. Для оценки практической эффективности разработанного алгоритма проведены вычислительные эксперименты, а также сравнение с классической схемой оптимизации муравьиными колониями по времени и точности решений. 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. uk Інститут телекомунікацій і глобального інформаційного простору НАН України Математичне моделювання в економіці Математичні та інформаційні моделі в економіці Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів Динамическая задача поиска кратчайшего пути с дополнительными условиями для задачи построения маршрута авиаперелетов Dynamic problem of finding the shortest path with additional conditions for the problem of constructing flight route airplanes Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| spellingShingle |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів Гуляницький, Л.Ф. Павленко, А.І. Математичні та інформаційні моделі в економіці |
| title_short |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_full |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_fullStr |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_full_unstemmed |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| title_sort |
динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів |
| author |
Гуляницький, Л.Ф. Павленко, А.І. |
| author_facet |
Гуляницький, Л.Ф. Павленко, А.І. |
| topic |
Математичні та інформаційні моделі в економіці |
| topic_facet |
Математичні та інформаційні моделі в економіці |
| publishDate |
2015 |
| language |
Ukrainian |
| container_title |
Математичне моделювання в економіці |
| publisher |
Інститут телекомунікацій і глобального інформаційного простору НАН України |
| format |
Article |
| title_alt |
Динамическая задача поиска кратчайшего пути с дополнительными условиями для задачи построения маршрута авиаперелетов Dynamic problem of finding the shortest path with additional conditions for the problem of constructing flight route airplanes |
| description |
Розглянута задача пошуку оптимального маршруту мандрівника між заданими пунктами з додатковими умовами на мережі авіасполучень певного регіону. Пропонується і досліджується підхід до розв’язання задачі пошуку шляху між заданими вершинами на відомому графі, що подає схему можливих авіаперельотів, з урахуванням вартості перельоту у залежності від часу. При цьому шлях може формуватися з урахуванням обмежень за часом, вартістю, бажаними або забороненими проміжними пунктами. Для пошуку шляху мінімальної вартості розроблено і досліджено спеціальний алгоритм оптимізації мурашиними колоніями з динамічним поколінням мурах. Природний паралелізм його обчислювальної схеми дозволяє отримувати і уточнювати отриманий розв’язок із урахуванням змін в умовах перельотів. Подається математична модель задачі, а також опис загальних особливостей запропонованого алгоритму. Для оцінки практичної ефективності алгоритму проведено обчислювальні експерименти, а також порівняння з класичною схемою оптимізації мурашиними колоніями.
Рассмотрена задача поиска оптимального маршрута путешественника между заданными пунктами с дополнительными условиями в сети авиасообщений определенного региона. Предлагается и исследуется подход к решению задачи поиска пути между заданными вершинами на известном графе, который представляет схему возможных авиаперелетов, с учетом стоимости перелета в зависимости от времени. При этом путь может формироваться с учетом ограничений по времени, стоимости, желательным или запрещенным промежуточным пунктам. Для поиска пути минимальной стоимости разработан и исследован специальный алгоритм оптимизации муравьиными колониями с динамическим поколением муравьев. Он позволяет оптимизировать использование ресурсов, а естественный параллелизм вычислительной схемы позволяет получать и уточнять полученное решение с учетом изменений в условиях перелетов. Приводится математическая модель задачи, а также описаны общие особенности предложенного алгоритма. Для оценки практической эффективности разработанного алгоритма проведены вычислительные эксперименты, а также сравнение с классической схемой оптимизации муравьиными колониями по времени и точности решений.
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.
|
| issn |
2409-8876 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/131773 |
| citation_txt |
Динамічна задача пошуку найкоротшого шляху з додатковими умовами для задачі побудови маршруту авіаперельотів / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2015. — № 2(3). — С. 39-50. — Бібліогр.: 16 назв. — укр. |
| work_keys_str_mv |
AT gulânicʹkiilf dinamíčnazadačapošukunaikorotšogošlâhuzdodatkovimiumovamidlâzadačípobudovimaršrutuavíaperelʹotív AT pavlenkoaí dinamíčnazadačapošukunaikorotšogošlâhuzdodatkovimiumovamidlâzadačípobudovimaršrutuavíaperelʹotív AT gulânicʹkiilf dinamičeskaâzadačapoiskakratčaišegoputisdopolnitelʹnymiusloviâmidlâzadačipostroeniâmaršrutaaviapereletov AT pavlenkoaí dinamičeskaâzadačapoiskakratčaišegoputisdopolnitelʹnymiusloviâmidlâzadačipostroeniâmaršrutaaviapereletov AT gulânicʹkiilf dynamicproblemoffindingtheshortestpathwithadditionalconditionsfortheproblemofconstructingflightrouteairplanes AT pavlenkoaí dynamicproblemoffindingtheshortestpathwithadditionalconditionsfortheproblemofconstructingflightrouteairplanes |
| first_indexed |
2025-11-29T10:40:31Z |
| last_indexed |
2025-11-29T10:40:31Z |
| _version_ |
1850854795686969344 |