Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів
У статті представлена розроблена інтелектуальна підсистема вибору раціональних маршрутів вантажних поїздів на основі елітної стратегії мурашиного алгоритму в залізничній мережі Придніпровської залізниці за різними системами маршрутизації: кільцевої та маятникової....
Saved in:
| Date: | 2014 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2014
|
| Series: | Искусственный интеллект |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/85285 |
| 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: | Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів / В.М. Пахомова, Л.О. Міщанюк // Искусственный интеллект. — 2014. — № 1. — С. 119–125. — Бібліогр.: 9 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85285 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-852852015-07-25T03:01:32Z Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів Пахомова, В.М. Міщанюк, Л.О. Интеллектуальные системы планирования, управления, моделирования и принятия решений У статті представлена розроблена інтелектуальна підсистема вибору раціональних маршрутів вантажних поїздів на основі елітної стратегії мурашиного алгоритму в залізничній мережі Придніпровської залізниці за різними системами маршрутизації: кільцевої та маятникової. В статье представлена разработанная интеллектуальная подсистема выбора рациональных маршрутов грузовых поездов на основе элитной стратегии муравьиного алгоритма в железнодорожной сети Приднепровской дороги при различных системах маршрутизации: кольцевой и маятниковой. The paper presents the developed intelligent subsystem choice of rational route freight trains on the basis of an elite strategy of ant algorithm in the Dnieper railway network of the road at various routing systems: a ring and a pendulum. 2014 Article Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів / В.М. Пахомова, Л.О. Міщанюк // Искусственный интеллект. — 2014. — № 1. — С. 119–125. — Бібліогр.: 9 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/85285 656.212.5:681.3 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 |
2014 |
| topic_facet |
Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85285 |
| citation_txt |
Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів / В.М. Пахомова, Л.О. Міщанюк // Искусственный интеллект. — 2014. — № 1. — С. 119–125. — Бібліогр.: 9 назв. — укр. |
| series |
Искусственный интеллект |
| work_keys_str_mv |
AT pahomovavm íntelektualʹnapídsistemaviboruracíonalʹnihmaršrutívvantažnihpotâgív AT míŝanûklo íntelektualʹnapídsistemaviboruracíonalʹnihmaršrutívvantažnihpotâgív |
| first_indexed |
2025-07-06T12:29:41Z |
| last_indexed |
2025-07-06T12:29:41Z |
| _version_ |
1836900660929363968 |
| fulltext |
ISSN 1561-5359 «Штучний інтелект» 2014 № 1 119
3П
УДК 656.212.5:681.3
В.М. Пахомова, Л.О. Міщанюк
Дніпропетровський національний університет залізничного транспорту
ім. акад.В. Лазаряна
Україна, 49010, м. Дніпропетровськ, вул. Лазаряна, 2
Інтелектуальна підсистема вибору
раціональних маршрутів вантажних потягів
V.N. Pahomova, L.A. Mischanyuk
Dnepropetrovsky National University of Railway Transport
named after Academician Lazaryana
Ukraine, 49010, Dnepropetrovsk, st. Lazaryana, 2
Intelligent Subsystem Rational Choice of Routes
of Freight Trains
В.Н. Пахомова, Л.А. Мищанюк
Днепропетровский национальный университет железнодорожного транспорта
имени академика В. Лазаряна
Украина, 49010, г. Днепропетровск, ул. Лазаряна, 2
Интеллектуальная подсистема выбора
рациональных маршрутов грузовых поездов
У статті представлена розроблена інтелектуальна підсистема вибору раціональних маршрутів вантажних
поїздів на основі елітної стратегії мурашиного алгоритму в залізничній мережі Придніпровської залізниці
за різними системами маршрутизації: кільцевої та маятникової.
Ключові слова: залізнична мережа, інтелектуальна підсистема,
кільцева та маятникова системи маршрутизації, мурашиний алгоритм, елітна стратегія.
The paper presents the developed intelligent subsystem choice of rational route freight trains on the basis of
an elite strategy of ant algorithm in the Dnieper railway network of the road at various routing systems: a ring
and a pendulum.
Key words: railway network, the intelligent subsystem, ring and edge routing system,
the ant algorithm, an elite strategy.
В статье представлена разработанная интеллектуальная подсистема выбора рациональных маршрутов
грузовых поездов на основе элитной стратегии муравьиного алгоритма в железнодорожной сети При-
днепровской дороги при различных системах маршрутизации: кольцевой и маятниковой.
Ключевые слова: железнодорожная сеть, интеллектуальная подсистема,
кольцевая и маятниковая системы маршрутизации, муравьиный алгоритм, элитная стратегия.
Вступ
На даний час у багатьох країнах світу, в тому числі державах Євросоюзу, Росії
та Україні, зростає розуміння важливості вирішення глобальних проблем транс-
портних комплексів. Це, перш за все, пов’язано з вимогами підвищення безпеки та
ефективності перевезень, з ростом мобільності суспільства, зменшення впливу
транспорту на навколишнє середовище та інш. У вирішенні цих проблем най-
Пахомова В.М., Міщанюк Л.О.
«Искусственный интеллект» 2014 № 1 120
3П
важливіше місце займає створення та використання інтелектуальних транспортних
систем (ІТС) [1]. У наш час на українських залізницях діє понад 1000 автоматизова-
них систем, основна із них – система АСК ВП УЗ-Є (Автоматизована Система
Керування Вантажними Перевезеннями Укрзалізниці Єдина), дає можливість вести
поїзну, контейнерну, локомотивну моделі Дороги з передачею інформації в анало-
гічні моделі рівня Укрзалізниці [2]. Це дозволило проводити оперативний контроль
навантаження вагонів, дислокацію локомотивів, контроль проходження поїздів,
облік і видачу попереджень у поїзній роботі.
На залізниці існують дві основі системи маршрутизації вантажних перевезень:
маятникова та кільцева [3]. Маятникова система полягає у взаємному транспортному
зв’язку двох станцій, між якими постійно обертаються закріплені за даним маршру-
том поїзди. Кільцева система характеризується транспортним зв’язком ряду заліз-
ничних станцій з послідуючою передачею вантажів від однієї станції в іншу.
Мета даної статті – розробити алгоритм створення інтелектуальної підсистеми
вибору раціональних маршрутів вантажних потягів на основі мурашиного алгоритму
в залізничній мережі Придніпровської залізниці за різними системами маршрути-
зації: кільцевої та маятникової.
Постановка задачі. Залізничну мережу Придніпровської залізниці запро-
поновано представити у вигляді неорієнтованого графа G = (N, A) з кількістю вузлів
N і кількістю ребер А, в якому кожному ребру (i, j) призначене число ijd . Вершини
графа відповідають станціям можливого слідування потягів, а множина ребер, що
з’єднують вершини графа, відповідає прокладеним залізничним дорогам між цими
станціями. У якості ijd взята довжина залізничної дороги із станції i до станції j.
Граф розрахункової ділянки мережі Придніпровської залізниці наведений на рис. 1.
Рисунок 1 – Граф залізничної мережі Придніпровської залізниці
Примітка: довжина залізниць наведена в км
Довжина любого шляху m) l, ,k, j, (i,p im визначається як ... .ij jk lmd d d
При кільцевій схемі обороту потягів необхідно вирішити задачу комівояжера, яка
Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів
«Штучний інтелект» 2014 № 1 121
3П
полягає у знаходженні оптимального (мінімального) маршруту, що проходить через
всі станції один раз з послідуючим поверненням на станцію відправлення. При
маятниковій схемі обороту потягів необхідно визначити мінімальне остовне дерево.
Вирішення задачі
На сьогодні існує велика кількість математичних методів, за допомогою яких
можна вирішити задачу маршрутизації на залізничному транспорті, але за останні
роки при оптимізації складних систем дослідники все частіше застосовують природ-
ні механізми пошуку найкращих рішень, наприклад: Genetic Algorithms – генетичні
алгоритми; Evolution Programming – еволюційне програмування; Neural Network
Computing – нейромережні обчислення; DNA Computing – ДНК обчислення; Cellular
Automata – клітинні автомати; Ant Colony Algorithms – мурашині алгоритми [4]. Для
вирішення поставлених задач пропонується алгоритм мурашиних колоній [5].
На сьогоднішній день існує п’ять основних модифікацій мурашиного алго-
ритму: Elitist Ant System, Ant-Q, Ant Colony System, Max-min Ant System, ASrank.
Відмінними особливостями існуючих модифікацій алгоритму є введення елітних
мурах, механізм виділення та випаровування. Всі ці модифікації розроблялися на
основі класичного мурашиного алгоритму, що базується на ймовірнісному виборі [6]. Для
вирішення поставлених задач використана модифікація алгоритму ACS (Ant Colony
System).
Мураха-дослідник вибирає напрямок переміщення із i в j на основі псевдо-
випадкового правила переходу. Ймовірність переходу k-ї мурахи зі станції i на
станцію j на t-й ітерації розраховується за випадково-пропорційним правилом [7]
)(,0
)(,
)(
)(
)(
tJjякщо
tJjякщо
t
t
tP
k
i
k
i
Jl
ilil
ijij
k
ij k
i
, (1)
де ij t – кількість феромону між станціями залишеного за час t, ij t –
видимість, величина, обернена до відстані: 1
ij
ijD , де ijD – відстань між
станціями i та j, α і β – два регульовані параметри, які є вагами інтенсивності сліду
феромону та видимості. Якщо α = 0, то найвірогіднішим буде перехід у найближчу
станцію. Якщо β = 0, тоді працює лише феромонне підсилення, що призводить до
швидкого завершення роботи алгоритму.
Після завершення маршруту кожна мураха k відкладає на ребро (i, j) таку
кількість феромону [7]
)(),(,0
)(),(,
)()(
tTjiякщо
tTjiякщо
tL
Q
t
k
k
kk
ij , (2)
де Tk(t) – маршрут, зроблений мурахою k на ітерації t; Lk(t) – його довжина; Q –
регульований параметр, значення якого обирають одного порядку з довжиною
оптимального маршруту.
Пахомова В.М., Міщанюк Л.О.
«Искусственный интеллект» 2014 № 1 122
3П
Потрібно забезпечити випаровування феромону – це зменшення кількості
відкладеного на попередніх ітераціях феромону. Інтенсивність випаровування феро-
мону задається за допомогою коефіцієнта випаровування 0,1 . Кінцеве правило
оновлення феромону, яке стосується всіх ребер, приймає вигляд [7]
)()()1()1( ttt ijijij , (3)
де
m
k
k
ijij tt
1
)()( ; m – кількість мурах в колонії.
Для покращення характеристик мурашиного алгоритму використовують еліт-
них мурах, які підсилюють ребра найкращого маршруту Т*, знайденого від початку
пошуку. Якщо в мурашнику є е елітних мурах, то ребра найкращого маршруту Т*
отримають загальне підсилення
e
Qe
L
, (4)
де e – кількість елітних мурах; Q – параметр, що має значення порядку
довжини оптимального маршруту; L – довжина маршруту найкращого марш-
руту Т*.
Існує велика кількість мов програмування, на яких можна реалізувати мураши-
ний алгоритм; обрано пакет MATLAB, який у порівнянні з традиційними мовами
програмування дозволяє на порядок скоротити час вирішення типових задач і значно
спростити розробку нових алгоритмів [8]. Для створення програм з графічним інтер-
фейсом у склад MATLAB входить спеціалізоване середовище GUIDE (Graphic User
Interface Development Environment) [9]. Для вирішення поставлених задач створено
програмну модель «ACS», структура якої представлена на рис. 2.
Рисунок 2 – Структура програмної моделі «ACS»
Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів
«Штучний інтелект» 2014 № 1 123
3П
Вхідні параметри моделі: кількість залізничних станцій Ncity = 18, координати
їх розміщення xcity, ycity та відстані між ними, які представлені у вигляді матри-
ці dcity. Параметри алгоритму: кількість мурах Nants=700; видимість мурах vis=1/dcity;
параметри, що є вагами інтенсивності сліду феромону та видимості a=1, b=6;
коефіцієнт інтенсивності випаровування rr=0,5; параметр, що містить позначення
порядку довжини оптимального маршруту Q=3; кількість елітних мурах e=5; макси-
мальна кількість ітерацій алгоритму maxit=10. Рух мурах починається зі встановленої
точки, тобто зі станції навантаження та відправлення потягів – Дніпропетровськ-
Вантажний.
У результаті роботи моделі «ACS», що знаходить оптимальний маршрут у
залізничній мережі Придніпровської залізниці за кільцевою системою маршру-
тизації, на екран виводиться Figure 1 (рис. 3), що показує вершини графа та від-
повідне з’єднання станцій.
Знайдений маршрут склав 800 км, для його знаходження знадобилось 10 ітера-
цій, загальний час розрахунку складає 8,7с.
Рисунок 3 – Оптимальний маршрут у залізничній мережі Придніпровської залізниці
за кільцевою системою маршрутизації
У результаті роботи програмної моделі «ACS», що знаходить оптимальний
маршрут в залізничній мережі Придніпровської залізниці за маятникової системою
маршрутизації, на екран виводиться графік Figure 1 (рис. 4), що показує оптималь-
ний маршрут з’єднань. Довжина знайденого маршруту складає 764 км, загальний
час розрахунку програми склав 1 хв. 31 с.
Пахомова В.М., Міщанюк Л.О.
«Искусственный интеллект» 2014 № 1 124
3П
Рисунок 4 – Оптимальний маршрут у залізничній мережі Придніпровської залізниці
за маятниковою системою маршрутизації
Висновки
Розроблена програмна модель інтелектуальної підсистеми вибору раціональних
маршрутів вантажних потягів на основі мурашиного алгоритму в залізничній мережі
Придніпровської залізниці за різними системами маршрутизації: кільцевою та
маятниковою. Формування оптимального маршруту прямування вантажних потягів
може бути корисним у рамках існуючої автоматизованої системи управління
вантажними перевезеннями Укрзалізниці (АСК ВП УЗ-Є).
Список літератури
1. Пшинько А.Н. Железнодорожные интеллектуальные транспортные системы и концепция между-
народной программы подготовки магистров в области ИТС CITISET : [текст] / [А.Н. Пшинько и др.] //
Інформаційно-керуючі системи на залізничному транспорті. – 2012. – № 4. – С. 52-57.
2. Жуковицький І.В. Створення нових можливостей АСК ВП УЗ із підтримки оперативного плану-
вання призначення локомотивів до складу вантажних поїздів : [текст] / І.В. Жуковицький,
А.Б. Устенко, О.Л. Зиненко // Інформаційно-керуючі системи на залізничному транспорті. –
2011. – № 5. – С. 51-56.
3. Бутько Т.В. Розробка раціональних маршрутів прямування пасажирських поїздів на основі
системи мурашиних колоній : [текст] / Т.В. Бутько, А.В. Прохорченко, Є.В. Чеклова // Восточно-
Европейский журнал передовых технологий. – 2009. – № 3/5(39). – С. 9-13.
4. Штовба С.Д. Муравьиные алгоритмы : [текст] / С.Д. Штовба // Exponenta Pro. Математика в
приложениях. – 2003. – № 4(4). – С. 70-75.
5. Джонс М.Т. Программирование искусственного интеллекта в приложениях : [текст] /
М.Т. Джонс ; [пер. с англ. А.И. Осипов]. – М. : ДМК Пресс, 2004. – 312 с.
6. Дидук В.А. Разработка алгоритма направленной маршрутизации для беспроводных сенсорных
сетей : [текст] / В.А. Дидук, А.М. Коваленко, Е.Г. Трофименко // Праці Одеського політехнічного
Інтелектуальна підсистема вибору раціональних маршрутів вантажних потягів
«Штучний інтелект» 2014 № 1 125
3П
університету. – 2011. – Вип. 1(35). – С. 151-154.
7. Штовба С.Д. Мурашині алгоритми оптимізації : [текст] / С.Д. Штовба, О.М. Рудий // Вісник
ВПІ. – 2004. – № 4. – С. 62-69.
8. Продукты MATLAB и Simulink [Электронный ресурс]. – Режим доступа : http://www.sl-
matlab.ru/services/products/detail.php?ID=430
9. Бадриев И.Б. Разработка графического пользовательского интерфейса в среде MATLAB : [текст] /
Бадриев И.Б., Бандеров В.В., Задворнов О.А. – Казань : Казанский государственный университет,
2010. – 113 с.
References
1. Railway intelligent transport systems and the concept of an international training program for master's
degrees in ITS CITISET [Text] / A.N. Pshinko // Іnformatsіyno-keruyuchі system on the zalіznichnomu
transport. – 2012. – № 4. – P. 52-57.
2. Zhukovitsky I.V. Stvorennya novih mozhlivostey ASK VP UZ іz pіdtrimki operational planuvannya
priznachennya lokomotivіv to the warehouse vantazhnih poїzdіv [Text] / I.V. Zhukovitsky,
A.B. Ustenko, O.L. Zinenko // Іnformatsіyno-keruyuchі system on the zalіznichnomu transport. –
2011. – № 5. – P. 51-56.
3. Bucko T.V. Rozrobka ratsіonalnih marshrutіv pryamuvannya pasazhirskih poїzdіv on osnovі Sistemi
murashinih colony [Text] / T. Butko, A. Prohorchenko, E. Cheklova // East European Journal of
advanced technologies. – 2009. – № 3/5 (39). – P. 9-13.
4. Shtovba S.D. Ant Algorithms [Text] / S.D. Shtovba // Exponenta Pro. Mathematics in the Appendix. –
2003. – № 4 (4). – P. 70-75.
5. Jones M.T. Programming iskusstevennogo intelligence in Annex [Text] / M.T. Jones; trans. from
English. A.I. Osipov. – M. : DMK Press, 2004. – 312 p.
6. Diduk V.A. Development directed routing algorithm for wireless sensor networks [Text] / V.A. Diduk,
A.M. Kovalenko, E.G. Trofymenko // Pratsі Metro Manila polіtehnіchnogo unіversitetu. – 2011. –
Vip. 1(35). – P. 151-154.
7. Shtovba S.D. Murashinі algorithmic optimіzatsії [Text] / S.D. Shtovba, O.M. Rudy // News VPІ. –
2004. – № 4. – P. 62-69.
8. Products MATLAB and Simulink [Electronic resource]. – Access mode : http://www.sl-
matlab.ru/services/products/detail.php?ID=430
9. Badriev I.B. Development of a graphical user interface in the delirium of MATLAB [Text] / I. Badriev,
V. Bandera, O. Zadvornov. – Kazan : Kazan State unіversitet. – 2010. – 113 p.
RESUME
V.N. Pahomova, L.A. Mischanyuk
Intelligent Subsystem Rational Choice of Routes of Freight Trains
This paper developed an intelligent subsystem choice of rational route freight trains.
On the basis of the elite strategy of ant algorithm proposed in [7] developed a
software model «ACS» in the environment MATLAB. The input parameters of the model
are: the number of freight stations, the coordinates of their location and the distance
between them, as well as the parameters of the algorithm (the number of ants and their
visibility; initialize the pheromone, the parameters are weighted pheromone trail intensity
and visibility; evaporation intensity factor, the number of elite ants, and the maximum the
number of iterations of the algorithm).
For the Dnieper railway network based on the model of the road «ACS» the optimal
routes of freight trains at various routing systems: a ring and a pendulum.
Intelligent subsystem rational choice of routes freight trains can find the application
in the existing automation system freight.
Стаття надійшла до редакції 16.09.2013.
|