Аннотация: В статье рассматриваются методы моделирование движения транспорта на перекрестках для оптимизации процесса регулирования с помощью алгоритмов Дейкстры и Форда – Фалкерсона.
Ключевые слова: транспортная сеть, оптимальный маршрут, максимальный поток, алгоритмы на графах.
Математика
УДК 57.087
Лимар Борис Олегович
бакалавр прикладної математики,
Національний технічний університет України
«Київський політехнічний інститут»
Лымар Борис Олегович
бакалавр прикладной математики,
Национальный технический университет Украины
«Киевский политехнический институт»
Lymar B.
Bachelor of applied mathematics
The National Technical University of Ukraine
«Kyiv Polytechnic Institute»
МОДЕЛЮВАННЯ РУХУ ТРАНСПОРТУ НА ПЕРЕХРЕСТЯХ У ЗАДАЧАХ ОПТИМІЗАЦІЇ ПРОЦЕСУ РЕГУЛЮВАННЯ
МОДЕЛИРОВАНИЕ ДВИЖЕНИЯ ТРАНСПОРТА НА ПЕРЕКРЕСТКАХ В ЗАДАЧАХ ОПТИМИЗАЦИИ ПРОЦЕССА РЕГУЛИРОВАНИЯ
TRANSPORT TRAFFIC AT CROSSROADS MODELING FOR REGULATION PROCESS OPRIMISATION
Анотація: В статті розглядаються методи моделювання руху транспорту на перехрестях для оптимізації процесу регулювання за допомогою алгоритмів Дейктри та Форда – Фалкерсона.
Ключові слова: транспортна мережа, оптимальний маршрут, максимальний потік, алгоритми на графах.
Аннотация: В статье рассматриваются методы моделирование движения транспорта на перекрестках для оптимизации процесса регулирования с помощью алгоритмов Дейкстры и Форда – Фалкерсона.
Ключевые слова: транспортная сеть, оптимальный маршрут, максимальный поток, алгоритмы на графах.
Abstract: This paper concerns methods of control transport traffic at crossroads modeling for regulation process optimization by Dijkstra’s algorithm and Ford–Fulkerson.
Keywords: transport network, optimal root, maximum flow, algorithms on graph.
На сьогоднішній день затори складають невід’ємну частину життя кожного водія і мають багато негативних наслідків. Наприклад, збільшення аварійності на дорозі, шуму, зносу автомобіля, порушення роботи екстрених і оперативних служб і т.д.. Тому створення систем для розв’язання даних проблем є важливим на теперішній час [1, с. 15].
Для дослідження процесу регулювання проводилось моделювання руху транспорту по оптимальному маршруту. Потік машин моделювався як пуассонівський із заданою інтенсивністю.
Як математичну модель карти дорожнього руху транспорту було обрано орієнтований граф з невід’ємними дугами. На вершинах графа розташовані світлофори, які регулюють рух транспорту, і можуть бути червоного, жовтого, зеленого кольорів. Вони вмикаються у випадковий момент часу по черзі та працюють за фіксований та нефіксований час. Після цього починається рух транспорту по дорозі. Необхідно знайти найкоротший маршрут від початкової вершини до кінцевої, яку вибирає користувач, та розрахувати маршрут з врахуванням потоку машин на дорогах та роботи світлофорів.
Для розв’язку поставленої задачі було проведено порівняльний аналіз алгоритму Дейкстри та метод Форда – Фалкерсона [2, с. 410].
Оптимальний маршрут розглядається за двома критеріями: критерій мінімального часу та критерій мінімальної відстані. Довжину між початковими та кінцевими вершинами знаходять за допомогою алгоритмів Дейкстри і Белмана – Форда. Алгоритм Белмана – Форда працює із дугами , які мають від’ємну вагу. Таким чином, в графі, який містить цикл з від’ємною сумарною вагою, існує короткий шлях від однієї вершини цього циклу до іншої.
Складність алгоритму Белмана – Форда дорівнює порівняно з алгоритмом Дейкстри – ), де – кількість ребер, – кількість вершин. Число , тому складність алгоритму Белмана-Форда є кубічною. Час роботи алгоритму Дейкстри залежить від реалізації неспадної черги з пріоритетами і складає ), якщо неспадна черга з пріоритетами реалізується за допомогою фібоначчевої піраміди. Реалізація фібоначчевої піраміди дозволяє досягнути меншої складності алгоритму Дейкстри ніж Белмана – Форда.
Таким чином, для реалізації пошуку оптимального маршруту було обрано алгоритм Дейкстри.
Для розв’язання задачі про максимальний потік застосовується метод Форда – Фалкерсона. Він базується на трьох важливих ідеях: залишкові мережі, збільшуючи шляхи і розрізи. Метод застосовується в багатьох потокових алгоритмах і задачах.
При невдалому виборі методу пошук максимального потоку може не закінчитись: величина потоку буде послідовно збільшуватись, але необов’язково буде сходитись до максимального значення потоку. Тому може бути таке, що алгоритм працюватиме нескінченно, якщо значення пропускної здатності ребер є ірраціональними числами.
Алгоритмічна складність алгоритму складає де – кількість ребер у графі, а – максимальний потік. На кожному кроці алгоритму додається потік збільшуваного шляху до вже існуючого потоку. Якщо пропускна здатність всіх ребер – цілі числа, то можна довести методом математичної індукції, що і потоки через всі ребра будуть завжди цілими числами. Відповідно, на кожному кроці алгоритм збільшує потік хоча б на одиницю. Отже, він зійдеться не більше ніж за кроків. Також можна виконати кожен крок за час , тоді загальний час алгоритму обмежений .
За допомогою алгоритму Форда – Фалкерсона відбувається оптимізація процесу регулювання. Програма обраховує максимальний потік, та обраховує завантаженість ребра відносно максимального потоку. Зелене світло завжди буде горіти в напрямку найбільшого завантаження на перехресті. Максимальний потік перераховується через певний інтервал часу.
Потік машин у даній роботі моделюється за законом Пуассона. Ймовірність подій, розподілених за цим законом має наступний вигляд:
де - ймовірність появи події при заданому значені параметра а дорівнює раз; - математичне очікування (середнє число подій за даний відрізок часу); - випадкова величина, число подій за даний відрізок часу; - відрізок часу, за який розглядається поведінка випадкової величини; =2,71 ... – основа натурального логарифма [3, с. 212].
В таблиці 5.1 наведені результати розв’язку контрольних прикладів.
Таблиця 5.1 – Результати роботи контрольний прикладів
|
Робота світлофорів |
Фіксований час |
Нефіксований час |
|
|
Критерій |
Мінімальної відстані |
Мінімального часу |
Мінімального часу |
|
Час поїздки(с) |
75.339 |
73.514 |
64.077 |
|
Відстань(м) |
798.56 |
1189.0 |
1189.0 |
На рис. 1 наведений оптимальний маршрут за критерієм мінімального часу за нефіксований час роботи світлофорів. Критерій мінімальної відстані за нефіксований час роботи світлофорів не зменшив час поїздки автомобіля за рахунок низької завантаженості дороги тому і не був наведений в таблиці. Маршрут зафарбований зеленим, жовтим і червоним і показує завантаженість дороги в напрямку її збільшення потоку машин.
Рис 1. Оптимальний маршрут за критерієм мінімального часу за нефіксований час роботи світлофорів
Література:
