ChSTU repository
ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets
Learn More
Please use this identifier to cite or link to this item:
https://er.chdtu.edu.ua/handle/ChSTU/6039| Title: | Система вибору оптимального маршруту доставки пасажирів м.Черкас |
| Authors: | Підгорний, Микола Володимирович Повєтьєв-Софієнко, Міхаіл Сергійович |
| Keywords: | МАРШРУТИЗАЦІЯ,;ГРОМАДСЬКИЙ ТРАНСПОРТ,;ДЕЙКСТРА,;A*,;СИСТЕМА ОПТИМІЗАЦІЇ. |
| Issue Date: | 12-Jun-2025 |
| Abstract: | У сучасних умовах розвитку міської інфраструктури особливої актуальності набуває проблема ефективного планування маршрутів громадського транспорту. Зростання населення, транспортні затори, зношеність автопарку та відсутність централізованої системи управління призводять до погіршення якості перевезень. В місті Черкаси ці проблеми є вкрай нагальними. Автоматизована система вибору оптимального маршруту дозволяє підвищити ефективність перевезень, зменшити час очікування пасажирів та знизити витрати на транспортні ресурси. Метою кваліфікаційної роботи є створення системи вибору оптимального маршруту доставки пасажирів у місті Черкаси. Об’єкт дослідження: процеси планування та оптимізації маршрутів пасажирського транспорту в умовах міської транспортної системи. Предмет дослідження: методи, алгоритми та програмні засоби автоматизації процесів вибору оптимальних маршрутів доставки пасажирів у транспортній мережі м. Черкаси. |
| URI: | https://er.chdtu.edu.ua/handle/ChSTU/6039 |
| Appears in Collections: | 124 Системний аналіз (Штучний інтелект) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Пояснювальна записка_Повєтьєв Міхаіл_СА-2102_2024-2025.pdf Restricted Access | 1.01 MB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Extracted text
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Факультет інформаційних технологій і систем
Кафедра комп’ютерних наук та системного аналізу
Пояснювальна записка
до кваліфікаційної роботи
бакалавра
(освітньо-кваліфікаційний рівень)
на тему: «Система вибору оптимального маршруту доставки пасажирів
м.Черкас»
Виконав: студент 4 курсу, групи СА-2102
спеціальності 124 − «Системний аналіз»
(шифр і назва спеціальності)
освітня програма «Системний аналіз і
прикладна логістика»
(назва освітньої програми)
Повєтьєв-Софієнко Міхаіл Сергійович
Керівник _____Підгорний М.В.
(прізвище та ініціали)
Рецензент____Мельник В.П. __
(прізвище та ініціали)
Черкаси 2025 року
7
Бланк завдання на кваліфікаційну роботу бакалавра студенту
Черкаський державний технологічний університет
Факультет Інформаційних технологій і систем
Кафедра Комп’ютерних наук та системного аналізу
Освітньо-кваліфікаційний рівень Бакалавр
Спеціальність 124 – Системний аналіз
Освітня програма «Системний аналіз і прикладна логістика
ЗАТВЕРДЖУЮ
Завідувач кафедри КНСА
_______________ Юрій
ТРИУС
«____» _____________
2025 р.
ЗАВДАННЯ
на кваліфікаційну роботу бакалавра студенту
Повєтьєву - Софієнко Міхаілу
(прізвище, ім‘я, по батькові)
«Створення системи вибору оптимального маршруту доставки
1. Тема роботи пасажирів м.Черкас»
Керівник роботи Підгорний М.В., к.т.н., доцент
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом університету від «25» лютого 2025 р. №53/03-03.
2. Строк подання студентом роботи до 12 червня 2025 року
3. Вихідні дані до роботи:
Мова програмування CSS3, JavaScript.
4. Зміст пояснювальної записки (перелік питань, що їх належить розробити):
Вступ
4. Реалізація програмного продукту
4.1 Вибір технологій та інструментів розробки
4.2 Реалізація ключових модулів
4.3 Пр иклади роботи програми та інтерфейсу
Висно вки.
5. Пер елік додатків:
5.1. Код програми
4.3 Приклади роботи програми та інтерфейсу
5 .2. Презентація у вигляді 21 слайду.
6. Консультанти розділів роботи
8
Підпис, дата
Прізвище, ініціали та
Розділ завдання
посада консультанта завдання видав
прийняв
7. Дата видачі завдання 15.01.2025
КАЛЕНДАРНИЙ ПЛАН
Строк виконання
№ з/п Назва етапів кваліфікаційної роботи бакалавра Примітка
етапів роботи
1 Видача завдання на кваліфікаційну роботу
15.01.2025 Виконано
бакалавра.
2 Аналіз літературних джерел, об’єкту та предмету
до 13.02.2025 Виконано
дослідження.
3 Написання теоретичного розділу кваліфікаційної
до 15.03.2025 Виконано
роботи бакалавра.
4 Написання аналітичного розділу кваліфікаційної
до 01.04.2025 Виконано
роботи бакалавра.
5 Написання практичних розділів й висновків до
до 01.05.2025 Виконано
кваліфікаційної роботи бакалавра.
6 Передзахист кваліфікаційної роботи бакалавра
03.06.2025 Виконано
на засіданні кафедри КНСА.
7 Подання роботи завідувачу кафедри КНСА. до 10.06.2025 Виконано
8 Захист кваліфікаційної роботи бакалавра. 12.06.2025 Виконано
Студент _____________________________ Міхаіл ПОВЄТЬЄВ-СОФІЄНКО
(підпис)
Керівник роботи ____________________________ Микола ПІДГОРНИЙ
(підпис)
9
РЕФЕРАТ
Кваліфікаційна робота бакалавра містить: 71 с., 8 рис., 3 таблиці, 19
використаних джерел, 1 додаток.
Актуальність теми. У сучасних умовах розвитку міської інфраструктури
особливої актуальності набуває проблема ефективного планування маршрутів
громадського транспорту. Зростання населення, транспортні затори, зношеність
автопарку та відсутність централізованої системи управління призводять до
погіршення якості перевезень. В місті Черкаси ці проблеми є вкрай нагальними.
Автоматизована система вибору оптимального маршруту дозволяє підвищити
ефективність перевезень, зменшити час очікування пасажирів та знизити витрати
на транспортні ресурси.
Мета роботи і задачі дослідження. Метою кваліфікаційної роботи є
створення системи вибору оптимального маршруту доставки пасажирів у місті
Черкаси.
Для досягнення поставленої мети були сформульовані такі задачі
• проаналізувати стан міської транспортної системи та проблеми
маршрутизації;
• дослідити існуючі алгоритми оптимізації маршрутів (Дейкстра, A*);
• побудувати математичну модель транспортної мережі;
• провести тестування системи в умовах моделювання трафіку;
Об’єкт дослідження: процеси планування та оптимізації маршрутів
пасажирського транспорту в умовах міської транспортної системи.
Предмет дослідження: методи, алгоритми та програмні засоби
автоматизації процесів вибору оптимальних маршрутів доставки пасажирів у
транспортній мережі м. Черкаси.
Методи дослідження:
• системний аналіз транспортної інфраструктури міста;
• методи теорії графів і дискретної оптимізації;
10
• алгоритми пошуку (Дейкстра, A*);
• програмування на HTML/CSS/JS;
• експериментальна перевірка у вигляді прототипу;
Перелік ключових слів: МАРШРУТИЗАЦІЯ, ГРОМАДСЬКИЙ
ТРАНСПОРТ, A*, ДЕЙКСТРА, СИСТЕМА ОПТИМІЗАЦІЇ.
11
ABSTRACT
The bachelor's qualification work contains: 71 pages, 8 figures, 3 tables, 19
references, 1 appendice.
Actuality of theme. Ukrainian cities face serious challenges in organizing public
transport. The lack of centralized route optimization causes inefficient transport
services. In Cherkasy, the development of an intelligent routing system is a relevant
task that can significantly improve logistics and user experience.
The purpose of the work and research tasks. The aim of this work is to
develop a prototype system for optimal passenger route selection in the city of
Cherkasy.
Purpose and research objectives. The purpose of the qualification work is to
create a prototype of a system for selecting the optimal passenger delivery route in the
city of Cherkasy.
To achieve this goal, the following tasks were formulated:
• analyze the state of the urban transport system and routing problems;
• investigate existing route optimization algorithms (Dijkstra, A*);
• test the system in traffic modeling conditions;
Object of research: processes of planning and optimizing passenger transport
routes in the conditions of the urban transport system.
Subject of research: methods, algorithms and software tools for automating the
processes of selecting optimal passenger delivery routes in the transport network of the
city of Cherkasy.
Research methods:
• system analysis of the city's transport infrastructure;
• search algorithms (Dijkstra, A*);
• programming in HTML/CSS/JS;
• experimental testing in the form of a prototype;
Keywords: ROUTING, PUBLIC TRANSPORT, A*, DIJKSTRA,
OPTIMIZATION SYSTEM
12
ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, СКОРОЧЕНЬ І 9
ТЕРМІНІВ
ВСТУП 10
1 АНАЛІЗ ПРОБЛЕМИ ТА ОГЛЯД ІСНУЮЧИХ РІШЕНЬ 12
1.1 Аналіз сучасного стану транспортної системи м. Черкаси 12
1.2 Проблеми маршрутизації пасажирського транспорту 14
1.3 Огляд існуючих методів та алгоритмів оптимізації маршрутів 15
1.4 Аналіз програмних рішень для транспортної логістики 17
Висновки до розділу 1 19
2 МАТЕМАТИЧНЕ ТА АЛГОРИТМІЧНЕ ЗАБЕЗПЕЧЕННЯ СИСТЕМИ 21
2.1 Математична модель задачі оптимізації маршрутів 21
2.2 Алгоритм Дейкстри для пошуку найкоротшого шляху 25
2.3 Алгоритм A* для оптимізації пошуку маршруту 28
2.4 Врахування факторів трафіку та часових обмежень 31
2.5 Алгоритми машинного навчання для прогнозування завантаженості 33
Висновки до розділу 2 34
3 АРХІТЕКТУРА СИСТЕМИ 35
3.1 Функціональні вимоги до системи 35
3.2 Вимоги та обмеження 36
3.3 Архітектура програмного забезпечення системи 37
Висновки до розділу 3 38
4 РЕАЛІЗАЦІЯ ПРОГРАМНОГО ПРОДУКТУ 41
4.1 Вибір технологій та інструментів розробки 41
4.2 Реалізація ключових модулів 42
4.3 Приклади роботи програми та інтерфейсу 43
Висновки до розділу 4 45
ВИСНОВКИ 48
13
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 49
Додаток А. Специфікація 57
Додаток Б. СИСТЕМА ВИБОРУ ОПТИМАЛЬНОГО МАРШРУТУ 59
ДОСТАВКИ ПАСАЖИРІВ М.ЧЕРКАС
14
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, СКОРОЧЕНЬ І
ТЕРМІНІВ
АПІ – інтерфейс програмування застосувань (Application Programming
Interface)
БД – база даних
ГІС – геоінформаційна система
ДП – дипломний проект
ІС – інформаційна система
КТЗ – комунальне транспортне підприємство
МКАТ – міський комунальний автотранспорт
ОС – операційна система
ПЗ – програмне забезпечення
СУБД – система управління базами даних
ТЗ – технічне завдання
УМЛ – уніфікована мова моделювання (Unified Modeling Language)
AJAX – асинхронний JavaScript та XML
API – Application Programming Interface
CSS – Cascading Style Sheets
GPS – Global Positioning System
HTML – HyperText Markup Language
HTTP – HyperText Transfer Protocol
JavaScript – мова програмування
JSON – JavaScript Object Notation
REST – Representational State Transfer
SQL – Structured Query Language
UI – User Interface
UX – User Experience
XML – eXtensible Markup Language
15
ВСТУП
Сучасні міста України стикаються з серйозними викликами у сфері
організації громадського транспорту. Зростання населення, збільшення кількості
транспортних засобів та обмеженість інфраструктурних ресурсів призводять до
утворення транспортних заторів, підвищення витрат на паливо та погіршення
екологічної ситуації. Місто Черкаси, як обласний центр з населенням понад 280
тисяч мешканців, не є винятком у цьому контексті.
За даними департaмeнту транспорту Черкаської міської ради, щодня
послугами громадського транспорту міста користується близько 150-180 тисяч
пасажирів. Транспортна мережа міста включає 42 автобусні маршрути, 8
тролейбусних та понад 20 маршрутів комерційних перевізників. Однак
відсутність єдиної системи координації та оптимізації маршрутів призводить до
неефективного використання транспортних ресурсів, збільшення часу
очікування пасажирів та підвищення собівартості перевезень.
Проблема оптимізації маршрутів пасажирського транспорту є особливо
гострою у контексті цифровізації транспортної галузі України. Відповідно до
Національної транспортної стратегії України на період до 2030 року,
пріоритетним напрямом розвитку є впровадження інтелектуальних
транспортних систем (ІТС) та цифрових технологій для підвищення
ефективності громадського транспорту.
Створення автоматизованої системи вибору оптимального маршруту
доставки пасажирів дозволить значно покращити якість транспортного
обслуговування населення, зменшити витрати на утримання транспортного
парку та знизити негативний вплив на довкілля. Особливо актуальним це
питання стає в умовах посткризового відновлення економіки України та
необхідності ефективного використання бюджетних коштів.
Метою роботи є розробка та створення інформаційної системи для
оптимізації маршрутів пасажирського транспорту м. Черкаси з використанням
сучасних алгоритмів та технологій веб-розробки.
16
Для досягнення поставленої мети необхідно вирішити наступні завдання:
1. Проаналізувати сучасний стан транспортної системи м. Черкаси та
виявити основні проблеми маршрутизації пасажирського транспорту;
2. Дослідити існуючі методи та алгоритми оптимізації маршрутів,
провести порівняльний аналіз програмних рішень для транспортної логістики;
3. Розробити математичну модель транспортної мережі міста та обрати
оптимальні алгоритми для розв'язання задачі маршрутизації;
4. Спроектувати архітектуру інформаційної системи, створити
структуру бази даних та визначити основні модулі системи;
5. Реалізувати програмний продукт з використанням сучасних веб-
технологій;
6. Оцінити економічну ефективність впровадження системи та
розробити рекомендації щодо її практичного використання.
Об'єкт дослідження - процеси планування та оптимізації маршрутів
пасажирського транспорту в умовах міської транспортної системи.
Предмет дослідження - система автоматизації процесів вибору
оптимальних маршрутів доставки пасажирів у транспортній мережі м. Черкаси.
Методи дослідження. У роботі використовуються такі методи
дослідження:
• системний аналіз для дослідження транспортної системи міста;
• методи теорії графів для моделювання транспортної мережі;
• алгоритми дискретної оптимізації (алгоритм Дейкстри, генетичні
алгоритми);
• методи об'єктно-орієнтованого програмування для реалізації
системи;
• статистичні методи для аналізу результатів експериментальних
досліджень;
• методи економічного аналізу для оцінки ефективності
впровадження.
17
1 АНАЛІЗ ПРОБЛЕМИ ТА ОГЛЯД ІСНУЮЧИХ РІШЕНЬ
1.1 Аналіз сучасного стану транспортної системи м. Черкаси
Транспортна система міста Черкаси (рис.1.1) є ключовим елементом його
інфраструктури, що забезпечує мобільність населення, зв’язок між районами та
доступ до соціально значущих об’єктів. Проте на сьогоднішній день ця система
характеризується низкою проблем, що ускладнюють ефективне функціонування
пасажирських перевезень.
Рисунок 1.1 - Транспортна система міста Черкаси
Станом на 2025 рік, у місті функціонують три основні види громадського
транспорту: автобуси, маршрутні таксі та тролейбуси. Загальна кількість
маршрутів - понад 60, з яких більшість обслуговуються приватними
перевізниками. За інформацією департаменту транспорту, щоденно на маршрути
виходить понад 300 одиниць транспорту. Дорожнє покриття в місті у значній мірі
зношене: за офіційними даними, понад 40% міських доріг потребують
капітального ремонту. Відсутність смуг для громадського транспорту,
18
нерівномірне освітлення та поганий стан зупинок створюють умови, які
негативно впливають на безпеку і швидкість перевезень.
Більшість маршрутів проходить через центральну частину міста, що
призводить до її перенавантаження. Натомість віддалені райони (Луначарського,
Казбет) мають обмежене транспортне сполучення, особливо у вечірній час.
Головними викликами є відсутність стабільного графіку руху, великі інтервали
між рейсами у непікові години та низька передбачуваність прибуття транспорту.
Відсутні офіційні електронні сервіси для моніторингу транспорту в реальному
часі. Більшість маршрутних таксі - це мікроавтобуси типу «Богдан», які
експлуатуються понад 10 років. Тролейбусний парк також потребує оновлення:
середній вік машин перевищує 20 років. Системи кондиціювання, електронні
табло та засоби адаптації для маломобільних груп – відсутні. Старий автопарк
сприяє збільшенню викидів у повітря, особливо в умовах заторів. Частка
електротранспорту недостатня для забезпечення екологічного балансу, а
використання електробусів - епізодичне.
Аналіз показує, що існуюча транспортна система міста Черкаси не
відповідає сучасним вимогам ефективності, зручності та екологічності.
Відсутність централізованого управління транспортними потоками, застаріла
інфраструктура та технічна база, а також нерівномірний розподіл маршрутів
вказують на потребу у впровадженні інтелектуальних систем оптимізації
маршрутів, здатних адаптуватися до поточного трафіку, потреб пасажирів та
змін у міській структурі.
1.2 Проблеми маршрутизації пасажирського транспорту
Сучасна система маршрутизації пасажирського транспорту в місті Черкаси
характеризується низкою організаційних та технічних обмежень, які
унеможливлюють ефективне планування та регулювання руху громадського
транспорту. Попри наявність загальної маршрутної мережі, яка охоплює основні
напрямки міста, відсутність алгоритмічного підходу до її побудови призводить
19
до дисбалансу між реальними потребами пасажирів та наявною пропозицією з
боку перевізників.
Актуальні схеми руху, як правило, залишаються статичними, незважаючи
на зміни у міському середовищі, забудові та щоденних транспортних звичках
мешканців. Маршрути переважно прокладаються без попереднього аналізу
навантаження на окремі ділянки дорожньої мережі, без урахування щільності
населення, наявності комерційних, освітніх або медичних об'єктів, які генерують
постійний пасажиропотік. Як зазначено у «Стратегії розвитку міста Черкаси до
2032 року», на сьогодні відсутні прозорі критерії визначення ефективності
маршрутів, а планування виконується в ручному режимі, без застосування
цифрових моделей міської мобільності.
Проблемним залишається й питання дублювання маршрутів - на багатьох
напрямках одночасно працюють кілька перевізників, що виконують рейси із
незначними відмінностями в зупинках або траєкторії руху. Така практика
спричиняє перевантаження окремих ділянок вулично-дорожньої мережі,
особливо в центрі міста, водночас залишаючи периферійні райони без належного
транспортного покриття. У звіті комунального підприємства
«Черкасиелектротранс» за 2023 рік також вказується, що понад 30% маршрутів
мають критично низьку завантаженість у непікові години, що свідчить про
неефективне використання рухомого складу.
Ще однією суттєвою проблемою є відсутність координації між
маршрутами різних видів транспорту. У місті не реалізовано єдину систему
пересадок або зональну модель маршрутної сітки, яка дозволила б зменшити
дублювання та зробити поїздки швидшими за рахунок інтеграції тролейбусних,
автобусних і маршрутних ліній. Натомість мешканці змушені використовувати
прямі, але довші за часом поїздки, уникаючи пересадок через їх незручність і
непередбачуваність.
Також відсутній динамічний моніторинг роботи транспортної мережі, що
обмежує можливість адаптації маршрутів до поточної ситуації на дорогах. З
огляду на регулярні зміни дорожніх умов, затори, аварії чи перекриття -
20
маршрути залишаються незмінними, що спричиняє затримки та зменшення
регулярності руху. У 2022 році Черкаська міська рада анонсувала впровадження
інтелектуальної транспортної системи (ІТС), однак на момент підготовки цієї
роботи відповідний функціонал (аналіз трафіку, адаптивна маршрутизація)
реалізовано лише частково - у вигляді GPS-трекінгу деяких одиниць транспорту.
Таким чином, проблеми маршрутизації в місті Черкаси зводяться до
неструктурованості процесу планування, відсутності цифрових інструментів,
неузгодженості маршрутної мережі з реальними потребами населення та
обмеженими можливостями адаптації до змін. Для забезпечення якісного
обслуговування пасажирів та зниження навантаження на транспортну систему в
цілому, необхідно перейти до інтегрованого підходу, що ґрунтується на аналізі
даних, моделюванні попиту та використанні алгоритмів оптимізації.
1.3 Огляд існуючих методів та алгоритмів оптимізації маршрутів
У сфері пасажирських перевезень питання оптимізації маршрутів є одним
із ключових для підвищення ефективності функціонування транспортної
системи, особливо в умовах обмежених ресурсів та динамічного міського
середовища. Наукова та прикладна практика пропонує низку підходів до
побудови оптимальних маршрутів, які поділяються за методами розв’язання,
видом використаних даних та ступенем адаптивності до зміни умов.
Найбільш поширеними є алгоритми, засновані на класичних моделях
теорії графів, зокрема на рішенні задачі пошуку найкоротшого шляху. У цьому
контексті активно застосовуються алгоритми Дейкстри, Беллмана-Форда, A* (A-
star), які дозволяють обчислювати найменшу відстань або найкоротший час руху
між заданими точками в мережі з урахуванням вагових коефіцієнтів (Таблиця
1.3). Дані методи широко використовуються у навігаційних системах, таких як
Google Maps, OpenStreetMap або Here, а також у транспортному моделюванні на
рівні міст.
21
Таблиця 1.3 - Таблиця-порівняння методів
Метод Тип задачі Швидкість Переваги Недоліки
Найкоротший Точний, Не працює з
Дейкстра Висока
шлях простий трафіком
Орієнтовані Ефективний з Вимагає
A* Дуже висока
маршрути евристикою доброго графа
Гнучкий, Довгий
Генетичний VRP, TSP Середня
адаптивний розрахунок
Імітація
Низька– Вимагає
Мурашиний TSP колективної
середня калібрування
поведінки
Окрему групу становлять евристичні та метаевристичні підходи, які
застосовуються для задач маршрутизації з великою кількістю змінних. Зокрема,
алгоритми генетичного програмування, мурашиного колоніального оптимізації,
табу-пошуку та симульованого відпалу демонструють високу ефективність у
розв’язанні задач типу VRP (Vehicle Routing Problem), TSP (Traveling Salesman
Problem) та їх варіацій. Ці методи дозволяють формувати оптимальні або близькі
до оптимальних маршрути з урахуванням багатьох обмежень: часу очікування,
завантаження транспорту, розкладу, пасажирських потоків тощо.
У сучасних міських умовах також активно впроваджуються системи
динамічного маршрутування, які враховують поточну ситуацію на дорогах у
режимі реального часу. Такі системи ґрунтуються на інтеграції транспортної
аналітики з GPS-даними, сенсорами трафіку, камерами відеонагляду та
цифровими мапами. Прикладами таких рішень є міські ІТС (інтелектуальні
транспортні системи), що застосовуються у Києві, Львові, а також у містах
Європейського Союзу. У цих системах алгоритми оптимізації взаємодіють із
модулями прогнозування трафіку, що дозволяє не лише оперативно реагувати на
зміни, але й прогнозувати майбутні затори та заздалегідь перебудовувати
маршрути.
22
Ще одним напрямом є застосування машинного навчання та штучного
інтелекту, зокрема методів кластеризації та нейронних мереж, для аналізу
історичних даних про пасажиропотік, визначення типових маршрутів та
прогнозування поведінки пасажирів. Такі технології активно використовуються
у великих містах із високою щільністю населення та складною транспортною
структурою, однак перспективи їх адаптації до середніх міст, таких як Черкаси,
також є значними.
Загалом, вибір конкретного методу оптимізації залежить від технічних
можливостей міської інфраструктури, доступності актуальних даних,
обчислювальних ресурсів та цілей планування. Комбіноване використання
класичних алгоритмів та інтелектуальних технологій створює умови для
розбудови гнучких, адаптивних транспортних систем нового покоління.
1.4 Аналіз програмних рішень для транспортної логістики
Ефективне функціонування міської транспортної системи у значній мірі
залежить від програмних засобів, які забезпечують планування, моніторинг і
оптимізацію маршрутів. На сучасному етапі транспортна логістика дедалі більше
інтегрується з цифровими технологіями, що дозволяє реалізовувати принципи
«розумного транспорту» навіть у середніх містах.
Існує кілька основних категорій програмного забезпечення для
транспортної логістики: системи управління парком (Fleet Management Systems),
системи GPS-моніторингу, модулі планування маршрутів, а також платформи з
відкритими даними, що забезпечують прозорість та взаємодію з пасажирами. На
глобальному рівні лідерами у галузі маршрутного планування є такі рішення як
PTV Visum, TransCAD, Optibus, Trapeze Group, які забезпечують побудову
маршрутних сіток, прогнозування пасажиропотоків і симуляцію транспортних
моделей з урахуванням міських обмежень. Такі системи переважно
застосовуються у великих мегаполісах або у рамках національних транспортних
стратегій.
23
У контексті України широкого розповсюдження набула система Dozor, яка
використовується для моніторингу громадського транспорту в реальному часі. У
місті Черкаси ця система функціонує вже кілька років і забезпечує базовий рівень
контролю за переміщенням маршрутних таксі та тролейбусів. Через веб-
інтерфейс або мобільний застосунок пасажири можуть переглядати
розташування транспорту на мапі, час прибуття на зупинку та номер маршруту.
Разом із тим, функціональність Dozor (Рис 1.4.) залишається обмеженою:
система не пропонує побудову персонального маршруту, не інтегрується з
іншими видами транспорту та не здійснює прогнозування затримок або
адаптацію маршрутів.
Рисунок 1.4 - Приклад роботи сайту Dozor
У Черкасах також ведеться робота зі створення муніципального
транспортного порталу, проте наразі він не надає динамічної інформації для
автоматизованої маршрутизації. Крім того, відсутня централізована система
збору й аналізу даних про навантаження на маршрути, що обмежує можливість
впровадження складніших алгоритмічних моделей.
Серед інших локальних ініціатив варто відзначити впровадження GPS-
моніторингу приватними перевізниками. Однак такий облік переважно закритий,
недоступний для публічного аналізу й не інтегрується з міською ІТ-
інфраструктурою. Водночас у ряді міст України вже працюють більш комплексні
рішення - наприклад, EasyWay, CityBus, WayMaps, що пропонують не лише
24
трекінг транспорту, а й функції побудови маршруту з урахуванням пересадок,
часу очікування, пішохідних відрізків та погодинного трафіку (Таблиця 1.5).
Таблиця 1.5 - Порівняння існуючих систем
Назва Персоналізовані
Функції Доступність Прогнозування
системи маршрути
GPS-
Dozor Web, App Ні Ні
моніторинг
CityBus GPS, маршрут App Частково Так
Симуляція,
PTV Visum Ні Так Ні
аналітика
Навігація,
Moovit Так Так Так
планування
На світовому рівні активний розвиток отримують SaaS-рішення для
розумного транспорту, що базуються на хмарних технологіях. Наприклад,
Moovit, HERE Mobility або Swiftly забезпечують адаптивне планування руху,
враховуючи зміни в реальному часі, зворотний зв’язок від користувачів та
екологічні параметри. Їхня інтеграція з місцевими транспортними системами
дозволяє значно підвищити точність та зручність планування поїздок для
пасажирів. У місті Черкаси вже функціонують базові цифрові рішення, що
забезпечують моніторинг громадського транспорту, однак відсутні повноцінні
аналітичні платформи для автоматизованого планування, оптимізації та
прогнозування. Подальший розвиток у цій сфері вимагає впровадження
інтегрованих програмних засобів, що дозволяють не лише відстежувати
транспорт, а й динамічно перебудовувати маршрути відповідно до зміни умов.
Висновки до розділу 1
У першому розділі було проведено всебічний аналіз проблем, пов’язаних
із організацією пасажирських перевезень у місті Черкаси, а також здійснено
огляд сучасних методів і засобів оптимізації транспортних маршрутів.
25
Аналіз транспортної системи м. Черкаси показав наявність суттєвих
інфраструктурних, організаційних та технічних проблем: нерівномірне
охоплення районів міста, зношеність автопарку, відсутність централізованого
управління рухом, дублювання маршрутів і відсутність адаптації до змінних
умов трафіку. Особливо критичною є відсутність інтелектуальних систем
маршрутизації та засобів прогнозування навантаження на маршрути.
Розгляд існуючих методів маршрутизації показав, що найефективнішими
для задач міського планування є поєднання класичних алгоритмів (Дейкстра, A*)
з евристичними й метаевристичними підходами (генетичні, мурашині
алгоритми). Актуальним є використання систем динамічного маршрутування в
реальному часі, зокрема на основі GPS-даних, прогнозів трафіку та машинного
навчання.
Аналіз програмного забезпечення у сфері транспортної логістики
засвідчив, що хоча існує багато готових рішень світового рівня, більшість з них
орієнтовані на великі мегаполіси або потребують значної інфраструктурної
підтримки. У місті Черкаси вже використовуються базові системи моніторингу
(наприклад, Dozor), однак відсутні інструменти оптимізації маршрутів та
прогнозування перевантажень.
Таким чином, результати першого розділу підтверджують доцільність
розробки інтегрованої інформаційної системи, що дозволить автоматизувати
процес вибору оптимального маршруту з урахуванням реального трафіку,
інфраструктури та потреб пасажирів.
26
2 МАТЕМАТИЧНЕ ТА АЛГОРИТМІЧНЕ ЗАБЕЗПЕЧЕННЯ СИСТЕМИ
2.1 Математична модель задачі оптимізації маршрутів
Задача оптимізації маршрутів пасажирського транспорту може бути
формалізована як задача пошуку найефективнішого шляху у зваженому графі з
урахуванням різноманітних обмежень: довжини маршруту, часу в дорозі,
завантаженості вузлів (зупинок), розкладу, трафіку тощо. Математична модель,
що описує дану задачу, дозволяє побудувати алгоритмічне рішення, яке здатне
обробляти вхідні дані й знаходити оптимальні варіанти руху.
Нехай міська транспортна мережа моделюється у вигляді орієнтованого
графа (Рис 2.1.) �� = (��, ��) де:
• V - множина вершин, що відповідає зупинкам громадського
транспорту;
• �� ⊆ �� × �� - множина дуг (ребер), кожна з яких описує наявність
можливого прямого сполучення між зупинками.
Рисунок 2.1 - Умовна схема орієнтованого графа транспортної мережі
Кожному ребру (��, ��) ∈ �� відповідає вага wij, що може відображати:
• відстань між зупинками (у кілометрах);
• або орієнтовний час у дорозі;
27
• або узагальнену вартість пересування (час + трафік + завантаження
транспорту).
Таким чином, вагова функція визначається як ������ = ��(������, ������, ������, ������)
де:
• dij - географічна відстань між вузлами i і j
• tij - середній час проходження між i та j
• τij - ймовірна затримка (на основі історичних даних)
• ρij - коефіцієнт завантаженості маршруту або трафіку.
Задача полягає в пошуку оптимального маршруту з початкової точки �� ∈ ��
до кінцевої точки �� ∈ ��, який мінімізує сумарну вагу шляху:
��(��, ��) = ∑ ��_����, де (��, ��) ∈ ��
де P - маршрут як впорядкована послідовність дуг (i,j) , що з'єднують
вершини від s до t.
Додатково можуть вводитися обмеження, що відображають реальні умови:
• Обмеження на час виконання маршруту: ∑������ ≤ ��������
• Обмеження на кількість пересадок: ∣ �� ∣≤ ��������
• Обмеження за типом транспорту (наприклад, лише тролейбуси).
Модель допускає як статичну постановку задачі (фіксовані ваги), так і
динамічну (ваги змінюються в реальному часі відповідно до стану трафіку). У
випадку динамічного моделювання вага ребра wij є функцією часу: де t -
������(��) = ��(������, ������(��), ������(��)) поточний момент часу.
Для розв’язання такої задачі можуть використовуватись алгоритми пошуку
найкоротшого шляху (Дейкстра, A*), а також евристичні та стохастичні підходи
для задач з великою кількістю обмежень. Створення адекватної математичної
моделі дозволяє перейти від емпіричних рішень до обґрунтованої, аналітично
точної системи побудови маршрутів.
Для реалізації наведеної моделі оптимізації маршрутів у реальних умовах
необхідно детально продумати як структуру вхідних даних, так і алгоритмічну
частину. Оскільки ми працюємо з транспортною мережею, що моделюється як
28
орієнтований зважений граф, важливо враховувати не лише геометричну
структуру міста, а й параметри маршруту, що можуть змінюватися з часом:
завантаженість, затримки, розклад тощо.
Кожне ребро графа (��, ��) ∈ �� описує маршрут між зупинками i та j і має
вагу wᵢⱼ, яка може залежати від кількох параметрів:
• dᵢⱼ - географічна відстань між зупинками (у кілометрах);
• tᵢⱼ - середній час у дорозі між зупинками;
• τᵢⱼ - очікувана затримка (на основі історичних або поточних даних);
• ρᵢⱼ - коефіцієнт завантаженості маршруту або транспорту.
Узагальнену вагу можна описати так:
��ᵢⱼ = ��(��ᵢⱼ, ��ᵢⱼ, ��ᵢⱼ, ��ᵢⱼ)
де функція f залежить від того, яку мету ми ставимо: мінімізувати час,
затримки, уникати переповнених маршрутів тощо.
Пошук оптимального маршруту
Нехай задано початкову зупинку s ∈ V та цільову зупинку t ∈ V. Необхідно
знайти шлях �� = {��, … , ��}, який мінімізує сумарну вагу:
��(��) = ∑ ��ᵢⱼ, де (��, ��) ∈ ��
Тобто, ми шукаємо маршрут з найменшою сумарною вартістю часу, яка
враховує всі ключові параметри.
Алгоритм Дейкстри - це класичний метод пошуку найкоротшого шляху в
графі з невід’ємними вагами. Його ідея полягає в поступовому «розширенні»
зони досяжності з початкової вершини, постійно вибираючи ту вершину, до якої
можна дістатися з найменшою накопиченою вагою.
Основні кроки:
1. Ініціалізуємо відстань до всіх вершин як нескінченність, крім
початкової (її - нуль).
2. Додаємо початкову вершину до множини оброблених.
3. Для кожного сусіда оновлюємо відстані, якщо через поточну
вершину можна дістатись швидше.
4. Переходимо до вершини з найменшою оцінкою.
29
5. Повторюємо до досягнення цільової вершини або поки всі вершини
не будуть оброблені.
Цей алгоритм працює швидко при фіксованих значеннях wᵢⱼ, тобто в
статичному графі.
Алгоритм A* є модифікацією алгоритму Дейкстри, але із використанням
евристики - додаткової функції h(n), яка оцінює «відстань» від поточної вершини
n до цільової вершини t. У нашому випадку це може бути, наприклад, пряма
географічна відстань між зупинками.
Замість простої оцінки накопиченої ваги, як у Дейкстрі, A* використовує
суму:
��(��) = ��(��) + ℎ(��)
де:
• g(n) - вже накопичена вартість до вершини n;
• h(n) - оцінка вартості від n до цілі t.
Перевага A* у тому, що алгоритм пріоритетно досліджує ті маршрути, які
не лише короткі, але й ймовірно ведуть у правильному напрямку, завдяки
евристичній функції. Якщо ця функція допустима (тобто ніколи не переоцінює
реальну вартість), A* гарантує знаходження оптимального рішення.
У реальній транспортній системі значення wᵢⱼ можуть змінюватися в
залежності від часу доби, погодних умов або аварійних ситуацій. Тому граф стає
залежним від часу:
��(��) = (��, ��(��)), де вага кожного ребра також функція часу: wᵢⱼ(t).
У такому випадку, після побудови маршруту, система має:
• або періодично перевіряти актуальність маршруту (наприклад, кожні
5 хвилин),
• або перебудовувати маршрут при зміні ключових параметрів
(наприклад, затримка більше 10 хвилин або раптова зупинка).
У деяких випадках використовується так зване перепланування
(replanning) - повторний запуск алгоритму A* з новими вхідними даними.
30
Таким чином, застосування алгоритмів Дейкстри та A* дозволяє
ефективно вирішувати задачу оптимізації маршрутів у транспортній мережі.
Алгоритм Дейкстри є надійним у статичних умовах, а A* дає вищу
продуктивність у великих графах завдяки евристичному прискоренню. В умовах
реального часу та змінного трафіку необхідно доповнити ці методи механізмами
адаптації та оновлення даних, що дозволяє підвищити точність і надійність
маршрутизації для пасажирів.
2.2 Алгоритм Дейкстри для пошуку найкоротшого шляху
Один із найпоширеніших алгоритмів для задач пошуку найкоротшого
шляху в зваженому графі - це алгоритм Дейкстри. Він дозволяє знайти маршрут
із мінімальною сумарною вагою від заданої початкової вершини до всіх інших
вершин графа. У задачах транспортної логістики цей підхід дозволяє ефективно
визначати оптимальні маршрути з урахуванням відстаней або часу.
Алгоритм Дейкстри працює за принципом поширення хвилі від початкової
вершини, поступово оновлюючи найкоротші відстані до інших вершин. На
кожному кроці він вибирає ту вершину, до якої вже знайдено найкоротший шлях
серед усіх ще не оброблених. Завдяки цьому забезпечується поступове
розширення області відомих оптимальних маршрутів.
Щоб краще зрозуміти механіку, уявімо транспортну мережу міста як карту
доріг, де зупинки - це точки на карті, а дуги - це дороги з певною тривалістю
переїзду. Алгоритм починає з однієї зупинки (наприклад, зупинки A) і
«перевіряє» всі безпосередньо досяжні з неї варіанти (B, C тощо), обчислює
відстані до них, а потім переходить до наступної вершини з найменшою
проміжною відстанню.
Уявімо, що є шлях A → B (3 хвилини) і шлях A → C (2 хвилини). Спочатку
алгоритм обере C, оскільки вона має меншу вартість. Потім з C може бути,
наприклад, ще один переїзд до D тривалістю 2 хвилини, тобто загальний час A
→ C → D = 4 хвилини. Якщо на той час ще існує прямий, але довший шлях A →
31
D (наприклад, 6 хвилин), то алгоритм вибере коротший - через C. Саме так
працює перевірка умов:
<div align="center"><b>якщо d[u] + w(u, v) < d[v], тоді d[v] := d[u] + w(u,
v]</b></div>
Ця перевірка гарантує, що з усіх можливих шляхів до вершини v буде
вибрано той, який на поточному етапі дає найменшу сумарну вартість.
Алгоритм припиняє роботу, коли всі вершини опрацьовані, тобто коли
знайдено найкоротший шлях до кожної з них. На практиці це означає, що
система, яка використовує алгоритм Дейкстри, може побудувати карту
доступності з заданої точки: скільки часу (або кілометрів) потрібно, щоб доїхати
до кожної зупинки.
У транспортному моделюванні це дозволяє:
• знаходити маршрути з мінімальним часом пересування;
• оцінювати доступність районів міста;
• моделювати транспортне навантаження на вузли мережі;
• перевіряти, як зміни (наприклад, перекриття дороги) впливають на
загальну ефективність перевезень.
Проте важливо враховувати обмеження методу. Алгоритм Дейкстри не
враховує змінні умови руху, такі як пробки, погодні затримки або графіки руху
транспорту. Тому він найчастіше використовується як основа для побудови
більш складних систем, які адаптуються до реального часу або поєднуються з
іншими підходами (наприклад, A*, генетичні алгоритми, машинне навчання).
Нехай міську транспортну мережу задано у вигляді орієнтованого графа
�� = (��, ��),
де V - множина вершин (зупинок), а E - множина дуг (сполучень між зупинками).
Кожному ребру (i, j) призначається вага w(i, j), що відображає вартість
переміщення між вершинами (наприклад, час у хвилинах або відстань у
кілометрах).
Формалізація задачі
Початкова вершина - �� ∈ ��
32
Потрібно знайти найкоротшу відстань до кожної вершини �� ∈ ��
Кроки алгоритму:
1. Для всіх вершин �� ∈ �� встановлюється початкова відстань:
��[��] ∶= ∞, а для стартової ��[��] ∶= 0
2. Ініціалізується множина �� ∶= �� - всі вершини графа.
3. Поки �� ≠ ∅, виконується:
o вибирається вершина �� ∈ �� з мінімальним значенням d[u]
o видаляється u з множини Q
o для кожного сусіда v вершини u, якщо (��, ��) ∈ ��:
якщо ��[��] + ��(��, ��) < ��[��], тоді ��[��] ∶= ��[��] + ��(��, ��)
У транспортній мережі Черкас вершини - це зупинки, а дуги - це можливі
переїзди між зупинками з певною тривалістю. Наприклад, якщо зупинка A
з’єднана з B, а далі з D, то алгоритм Дейкстри дозволить знайти маршрут �� →
�� з мінімальним часом поїздки, уникаючи зайвих або довших шляхів.
Наприклад, у графі, зображеному на рисунку 2.1, при стартовій вершині A
алгоритм Дейкстри дає змогу знайти мінімальний час у дорозі до зупинки G,
враховуючи усі варіанти маршруту та їх вагу.
Рисунок 2.1 - Візуалізація найкоротшого маршруту (A → G) у графі
транспортної мережі
33
Результатом роботи алгоритму є таблиця найкоротших відстаней до
кожної вершини, що дає змогу не лише знайти оптимальний маршрут, а й
створити карту доступності міста.
Алгоритм працює лише на графах з невід’ємними вагами. Він не враховує
динамічні зміни (наприклад, затори), тому його зазвичай застосовують у
поєднанні з іншими методами або як частину складніших систем.
2.3 Алгоритм A* для оптимізації пошуку маршруту
На відміну від алгоритму Дейкстри, який обов’язково розглядає всі
досяжні вершини до того, як досягне цілі, алгоритм A* спрямовує пошук саме в
бік цільової точки, завдяки чому кількість непотрібних обчислень може бути
значно меншою. Це особливо важливо для реальних задач, де граф може містити
тисячі або навіть мільйони вершин і ребер, як-от у моделюванні доріг у місті чи
міжміських мереж.
Особливістю реалізації A* є використання структури даних черги з
пріоритетом (зазвичай - бінарна купа або двійкова черга), яка дозволяє
ефективно отримувати вершину з найменшим значенням функції f(n). Це значно
впливає на загальну складність алгоритму. У найгіршому випадку часова
складність алгоритму A* дорівнює O(E), де E - кількість ребер у графі, однак на
практиці завдяки евристиці він працює набагато швидше.
Ще однією перевагою A* є те, що алгоритм не лише обчислює мінімальну
вартість маршруту, а й зберігає інформацію про послідовність вершин на шляху.
Це дає змогу без додаткових обчислень реконструювати оптимальний маршрут
одразу після завершення пошуку.
У випадку з транспортною мережею міста, евристична функція може бути
адаптована до різних типів даних: географічних координат, середньої швидкості
транспорту, дорожніх умов, часу доби тощо. Наприклад, якщо маршрути
громадського транспорту Черкас мають різний режим руху вдень і вночі,
34
функцію h(n) можна змінювати динамічно, що дозволить алгоритму формувати
більш актуальні рішення.
Крім того, у практичних системах побудови маршрутів часто
застосовується модифікація A* із обмеженням глибини пошуку або з
додатковими правилами фільтрації (наприклад, виключення розворотів або
пріоритизація магістральних доріг). Такі адаптації дозволяють ще більше
скоротити час відповіді системи та підвищити її точність.
Таким чином, алгоритм A* не лише ефективний, а й гнучкий з точки зору
інтеграції в складні програмні рішення, що працюють у реальному часі та
використовують просторові дані. Саме тому він широко застосовується у
транспортних планувальниках, GPS-навігаторах, системах розумного міста та
інших сферах, де важливо швидко знаходити найоптимальніші шляхи з
урахуванням великої кількості змінних.
На відміну від алгоритму Дейкстри, який розширює вершини лише за
відомими поточними відстанями g(n), алгоритм A* використовує оцінку
майбутніх витрат за допомогою евристичної функції h(n) - наближеної відстані
від поточної вершини n до цільової вершини t. В результаті, пріоритет
розширення вершини базується на загальній оцінці:
��(��) = ��(��) + ℎ(��)
де:
• g(n) - відома вартість шляху від початкової вершини до n;
• h(n) - евристична оцінка шляху від n до мети (наприклад, евклідова
або мангеттенська відстань).
Щоб алгоритм A* гарантовано знаходив оптимальний шлях, евристика
h(n) повинна бути:
• допустимою: ніколи не переоцінює справжню відстань до цілі;
• бажано також монотонною (узгодженою):
ℎ(��) ≤ ��(��, ��′) + ℎ(��′) для будь-якої пари суміжних вершин n і n′.
Опис алгоритму
35
1. Ініціалізація:
– Open: черга пріоритету, початково містить стартову вершину s з оцінкою
��(��) = ℎ(��)
– Closed: множина вже оброблених вершин
2. Поки Open не порожній:
o вибрати вершину n з найменшим f(n)
o якщо �� = �� - завершити (шлях знайдено)
o для кожного сусіда n′:
▪ обчислити нове значення g(n′)
▪ оновити ��(��′) = ��(��′) + ℎ(��′)
3. Повернути шлях за збереженими попередниками
У контексті міської транспортної мережі, де зупинки можуть бути
розташовані на географічній мапі, функція h(n) може базуватися на евклідовій
відстані між координатами GPS зупинки n і цільової зупинки t:
ℎ(��) = √[(��ₙ − ��ₜ)² + (��ₙ − ��ₜ)²]
Це дозволяє A* ефективно просувати пошук у бік цільового пункту,
мінімізуючи кількість перевірених вершин. У порівнянні з Дейкстрою, A*
істотно пришвидшує пошук маршруту в умовах великої кількості варіантів,
особливо якщо мережа має щільну структуру та складну геометрію (Рис 2.3).
Рисунок 2.3 Порівняння роботи алгоритмів Дейкстри та A* на сітковому
графі
36
Для міста Черкаси, де частина маршрутів може дублюватися або мати
неоднозначні траєкторії, застосування A* дозволяє зменшити обсяг обчислень і
швидше формувати рекомендації для побудови персонального маршруту, якщо
задати координати початкової та кінцевої зупинок.
Алгоритм A* є ефективним лише за наявності хорошої евристики. Якщо
h(n) неінформативна або занадто слабка (наприклад, завжди дорівнює нулю), A*
перетворюється на алгоритм Дейкстри. Якщо ж h(n) переоцінює вартість,
оптимальний шлях може бути втрачено. Тому для реального застосування в
транспортних системах необхідна точна географічна інформація і калібрована
модель відстаней.
2.4 Врахування факторів трафіку та часових обмежень
У реальних умовах роботи міського транспорту побудова маршруту не
може обмежуватися лише геометрією шляху чи номінальними відстанями.
Важливу роль відіграють динамічні фактори, зокрема інтенсивність трафіку,
затори, дорожні роботи, погодні умови та часові обмеження щодо виконання
перевезень. Для адекватного моделювання транспортних процесів необхідне
врахування цих змінних у математичній моделі.
У графовій моделі транспортної мережі кожне ребро (i, j) повинно мати
змінну вагу залежно від поточної ситуації на дорозі. Відповідно, вагова функція
набуває вигляду:
��(��, ��, ��) = ��(��, ��) × ��(��, ��, ��)
де:
• d(i, j) - базова відстань або час між вузлами
• τ(i, j, t) - коефіцієнт трафіку, що змінюється в часі t
Цей коефіцієнт може будуватись на основі:
• даних GPS-трекінгу
• камер дорожнього моніторингу
37
• історичної статистики руху
• аналітики за погодинною сіткою (години пік, нічний період тощо)
Часові вікна (time windows)
Для певних категорій пасажирських перевезень існує обмеження за часом
прибуття або виконання маршруту. Це часто зустрічається у транспорті до шкіл,
лікарень, на підприємства. У таких випадках задача оптимізації маршруту
набуває форми "TSP з часовими вікнами" (TSP-TW), де кожна вершина має
допустимий інтервал:
[aᵢ, bᵢ] - час, у який транспорт має прибути до зупинки i
При порушенні цього обмеження може нараховуватись штраф або така
траєкторія виключається з розгляду. Крім часових вікон на окремі точки, часто
вводиться глобальне обмеження:
∑ ��(��, ��, ��) ≤ ��ₘₐₓ
де Tₘₐₓ - допустима максимальна тривалість маршруту. Це обмеження
особливо актуальне для міського транспорту з фіксованими розкладами або
інтервалами руху.
Сучасні ІТС (інтелектуальні транспортні системи) дозволяють інтегрувати
модель маршрутизації з потоками даних у реальному часі. На практиці це може
бути реалізовано шляхом періодичного оновлення ваг ребер у графі та
повторного обчислення маршруту, наприклад:
• при перевищенні порогового значення затримки на ділянці;
• при виникненні надзвичайної події (ДТП, перекриття, затор);
• при зміні погодних умов, які впливають на швидкість руху.
Такі системи використовуються, наприклад, у Києві (система управління
дорожнім рухом), у Львові (Lviv Smart Transport), а також у низці європейських
міст.
Для підвищення точності використовуються комбіновані моделі, що
поєднують:
• історичні дані (наприклад, середній трафік у понеділок о 8:00);
• оперативну інформацію (GPS, інциденти);
38
• прогнозні моделі (машинне навчання для передбачення заторів).
Такі підходи дозволяють адаптувати маршрутизацію до реальних умов із
мінімальним запізненням і підвищити надійність виконання графіків руху.
2.5 Алгоритми машинного навчання для прогнозування
завантаженості
У системах міського транспорту важливо не лише прокладати найкоротші
маршрути, а й передбачати рівень завантаженості окремих ділянок маршрутної
мережі. Це дозволяє уникати перевантаження, формувати адаптивні графіки
руху та балансувати пасажиропотоки. Сучасні підходи до вирішення цього
завдання базуються на алгоритмах машинного навчання, які здатні аналізувати
великі масиви даних і робити точні прогнози на основі закономірностей.
Завантаженість транспортної ділянки можна визначити як відношення
фактичного потоку пасажирів або транспортних одиниць до її максимальної
пропускної здатності. У формалізованому вигляді це:
��(��, ��) = ��(��, ��) / ��(��)
де:
• L(i, t) - рівень завантаженості ділянки i у момент часу t,
• F(i, t) - кількість пасажирів або машин за певний період,
• C(i) - максимальна пропускна здатність цієї ділянки.
Основні типи моделей
Для прогнозування ��(��, �� + ����) - тобто рівня завантаженості у
майбутньому - застосовуються такі групи алгоритмів машинного навчання:
1. Регресійні моделі
• Лінійна регресія
• Регресія з регуляризацією (Ridge, Lasso)
Ці моделі добре підходять для початкового аналізу й можуть враховувати
сезонність, час доби, день тижня.
2. Дерева рішень та ансамблі
39
• Random Forest
• Gradient Boosting (XGBoost, LightGBM)
Ці методи забезпечують високу точність при прогнозуванні складних
залежностей, таких як зв’язок між погодою, подіями в місті та трафіком.
Загальна архітектура системи прогнозування завантаженості включає такі
модулі:
• Збір даних: GPS-дані, валідатори, камери, історія поїздок.
• Попередня обробка: очищення, нормалізація, часове згладжування.
• Модель ML: навчання на розмічених даних з періодичним
оновленням.
• Прогноз: побудова теплових карт завантаження, адаптація
маршрутів.
У містах із розвиненою ІТ-інфраструктурою, таких як Київ або Львів, вже
реалізовані модулі прогнозування перевантажень на маршрутах за допомогою
даних з GPS і валідаторів. Наприклад, у Києві прогноз трафіку на наступну
годину використовується для коригування інтервалів руху тролейбусів і
автобусів.
У Черкасах подібні системи ще не впроваджені повною мірою, однак
наявність GPS-моніторингу (система Dozor) може стати джерелом навчальних
даних для побудови першої версії прогнозної моделі. Простий варіант - навчання
моделі на основі пари "час доби → завантаження маршруту" для оптимізації руху
в години пік.
Висновки до розділу 2
У другому розділі було розглянуто математичну та алгоритмічну основу
функціонування системи оптимізації маршрутів пасажирського транспорту на
прикладі міста Черкаси. Представлено формалізовану модель міської
транспортної мережі у вигляді орієнтованого зваженого графа, де ваги ребер
40
відображають комплексну вартість переміщення між зупинками з урахуванням
відстані, часу в дорозі, затримок та завантаженості.
Проаналізовано класичні алгоритми пошуку найкоротшого шляху -
Дейкстри та A*. Алгоритм Дейкстри показав ефективність у статичних умовах
без змін ваг, тоді як A* забезпечує швидший пошук за рахунок евристичної
оцінки відстані до цілі, що дозволяє зменшити кількість оброблених вершин. A*
особливо доцільно використовувати у великих міських мережах із складною
географією.
Показано, що динамічне оновлення ваг на основі змін трафіку в реальному
часі потребує впровадження адаптивних моделей, у яких вага ребра залежить від
поточного моменту часу. У цьому контексті розглянуто поняття часових
обмежень та коефіцієнтів трафіку, які дозволяють реалізовувати транспортну
логістику більш точно та реалістично.
Крім того, детально описано можливості застосування алгоритмів
машинного навчання для прогнозування завантаженості окремих ділянок
транспортної мережі. Регресійні моделі, дерева рішень і ансамблеві методи
можуть ефективно аналізувати історичні дані, здійснювати прогноз
навантаження та допомагати у плануванні адаптивних графіків руху.
Таким чином, розділ закладає теоретичну та практичну основу для
розробки інтелектуальної системи маршрутизації громадського транспорту, яка
здатна враховувати широкий спектр параметрів, адаптуватися до змін у міському
середовищі та забезпечувати високий рівень точності та ефективності побудови
маршрутів.
41
3 АРХІТЕКТУРА СИСТЕМИ
3.1 Функціональні вимоги до системи
Система оптимізації маршрутів пасажирського транспорту має
забезпечити базову функціональність для демонстрації можливості
інтелектуального підходу до формування маршрутів у межах міської мережі. З
огляду на обмеження ресурсів, обсяг роботи та реалістичність впровадження.
Система повинна забезпечити такі функціональні можливості:
• Візуалізація маршрутної мережі міста у вигляді графа, де зупинки -
це вузли, а сполучення - ребра з вагами (час або відстань).
• Вибір початкової та кінцевої зупинки користувачем через веб-
інтерфейс.
• Розрахунок найкоротшого маршруту між вибраними зупинками за
допомогою одного з реалізованих алгоритмів (наприклад, Дейкстри або A*).
• Відображення шляху на мапі або схемі з інформацією про довжину,
кількість зупинок, загальний час.
• Можливість зміни ваг ребер вручну або за умовною “годиною пік” -
як демонстрація впливу трафіку на вибір маршруту.
Також передбачено базовий модуль для імітації прогнозного завантаження
маршрутів - у вигляді попередньо заданих коефіцієнтів на деяких ділянках
маршруту.
Система не ставить за мету повне відтворення роботи міських ІТС або
інтеграцію з реальними транспортними даними, однак її архітектура закладена
таким чином, щоб у майбутньому дозволити масштабування, зокрема:
• додавання нових алгоритмів оптимізації;
• обробку реальних GPS-даних;
• впровадження баз даних користувацької активності.
42
3.2 Вимоги та обмеження
Окрім основної функціональності, система повинна відповідати низці
нефункціональних вимог, які визначають загальні характеристики застосунку,
що впливають на його якість, зручність використання та придатність до
подальшого розширення. У межах цієї роботи ставляться помірні, реалістичні
вимоги, які відповідають обсягу проекту та наявним технічним ресурсам.
Інтерфейс має бути простим і зрозумілим для користувача. Ключові дії
(вибір точок маршруту, запуск пошуку, перегляд результату) повинні
виконуватись інтуїтивно. У системі не планується складної реєстрації,
персоналізації чи багаторівневої навігації - лише базовий, зручний для
демонстрації функціонал.
Очікується, що система обробляє запити на побудову маршруту протягом
1–2 секунд для графа з кількома десятками вершин. Оскільки мова йде про
спрощену модель, не передбачається оптимізація для роботи з великими
обсягами даних або високими навантаженнями.
Застосунок має коректно обробляти типові помилки користувача -
наприклад, вибір недійсних зупинок або відсутність шляху між ними. У разі
помилки система повинна виводити повідомлення без аварійного завершення
роботи. Архітектура застосунку повинна допускати можливість подальшого
розширення функціоналу - наприклад, додавання нових алгоритмів, інтеграцію з
API, використання баз даних. У даному проекті закладено базу для цього через
чітке розділення логіки обробки маршруту та інтерфейсної частини.
Серед основних обмежень, притаманних цій версії реалізації:
• Відсутність підключення до реальних джерел даних (трафік, GPS,
API перевізників).
• Статичний набір маршрутних даних, що задається вручну або через
файли.
• Відсутність багатокористувацького доступу або серверної обробки
запитів.
43
• Робота системи відбувається в одному середовищі (локально або у
простому веб-деплойменті без хмарної інфраструктури).
Ці обмеження не суперечать меті роботи, яка полягає не у впровадженні
повноцінного транспортного рішення, а у демонстрації принципів маршрутизації
та побудови архітектурної моделі, придатної для подальшого розвитку.
3.3 Архітектура програмного забезпечення системи
Архітектура системи спроектована таким чином, щоб забезпечити
гнучкість, модульність та можливість поступового розширення функціоналу.
Застосунок реалізується як веб-система з поділом на клієнтську (frontend) та
серверну (backend) частини. Основні логічні компоненти взаємодіють через API.
Опис компонентів:
• User Interface (Frontend) - інтерфейс користувача для вибору
початкової та кінцевої зупинок, запуску пошуку маршруту та перегляду
результату на мапі або схемі. Реалізується з використанням
HTML/CSS/JavaScript або бібліотек типу React/Vue.
• Web Server (Backend API) - обробляє запити від користувача, передає
параметри до модуля обчислення маршрутів, повертає результат.
• Route Calculation Module - основний логічний блок, який реалізує
алгоритми маршрутизації (Дейкстра, A*) на основі графової структури
транспортної мережі.
• Graph Data (Stops & Edges) - зберігає структуру зупинок та
маршрутів, у вигляді графа з вагами. На цьому етапі граф може задаватися
вручну або через файл.
• Traffic Adjustment Engine - блок, що імітує вплив трафіку, змінюючи
ваги ребер у графі на основі заданих сценаріїв (наприклад, години пік).
• Prediction Module (Optional ML Block) - опціональний модуль, у
якому можлива реалізація простих моделей прогнозування завантаженості
44
окремих маршрутів. Цей компонент не є обов’язковим для базової роботи
системи, але передбачений для потенційного розширення.
1. User Interface (Frontend)
Клієнтська частина реалізована у вигляді веб-інтерфейсу, що дозволяє
користувачеві взаємодіяти із системою через браузер. Інтерфейс побудовано за
допомогою технологій HTML5, CSS3, JavaScript.
Ключові елементи:
• Випадаючі списки для вибору початкової та кінцевої зупинки;
• Кнопка запуску обчислення маршруту;
• Блок виводу результату з описом шляху (кількість зупинок, загальний час);
• Канвас або вбудована мапа для візуалізації маршруту.
2. Web Server (Backend API)
Серверна частина реалізована на основі Flask (Python) як легкий фреймворк
для обробки HTTP-запитів.
Функції:
• Приймає дані з frontend (id зупинок);
• Передає параметри в модуль обчислення маршруту;
• Повертає маршрут у форматі JSON для відображення.
API побудований за принципами REST і складається з таких маршрутів:
• /get_stops - повертає список доступних зупинок;
• /calculate_route - обробляє запит маршруту, повертає список зупинок і
параметри маршруту.
3. Route Calculation Module
Цей модуль реалізує алгоритми маршрутизації - зокрема, алгоритм Дейкстри
або A*.
Для цього:
• Граф представлено як словник суміжності: graph = { 'A': {'B': 3, 'C': 1}, ... }
• Зберігається інформація про вагу (час у хвилинах або узагальнена
вартість).
45
• У модулі реалізована функція find_shortest_path(start, end), що повертає
найкоротший маршрут і загальну вартість.
4. Graph Data (Stops & Edges)
Дані про зупинки та сполучення зберігаються у форматі JSON або CSV.
Кожна зупинка має унікальний ID, назву та координати (для візуалізації).
Кожне ребро містить:
• зупинку-відправлення,
• зупинку-призначення,
• вагу (час або функціональна вартість).
5. Traffic Adjustment Engine
Цей компонент імітує трафік, змінюючи вагу ребер у графі.
Передбачено:
• ручне встановлення коефіцієнтів для окремих з’єднань (наприклад,
"ділянка A→C × 1.5 у годину пік");
• сценарії, що змінюють ваги за умовами (час доби, день тижня).
6. Prediction Module (Optional ML Block)
Модуль прогнозування є експериментальним компонентом.
У базовому вигляді:
• використовує набір історичних значень коефіцієнтів трафіку;
• оцінює ймовірну завантаженість окремих ділянок маршруту;
• надає зворотний зв’язок модулю ваг, впливаючи на маршрутний вибір.
Можливе майбутнє розширення через використання бібліотек scikit-learn або
pandas.
Висновки до розділу 3
У третьому розділі було спроєктовано архітектуру системи оптимізації
маршрутів громадського транспорту, яка реалізується у вигляді веб-застосунку.
Архітектура розділена на окремі модулі, кожен з яких виконує свою функцію та
дозволяє досягти гнучкості і масштабованості.
46
Запропонована система забезпечує ключовий функціонал: побудову графа
транспортної мережі, вибір зупинок, обчислення маршруту з урахуванням ваг,
відображення результату та можливість врахування умовного трафіку.
Особливу увагу приділено реалізації алгоритмів пошуку маршруту
(Дейкстра, A*), побудові графової структури даних, механізму взаємодії між
клієнтською і серверною частинами. Також описано можливість інтеграції
модуля машинного навчання для прогнозування завантаженості в перспективі.
Таким чином, створена архітектура відповідає меті роботи - продемонструвати
можливість побудови інтелектуальної системи маршрутизації, яка може бути
адаптована для використання в реальних умовах міста Черкаси або подібного
урбаністичного середовища.
47
4 РЕАЛІЗАЦІЯ ПРОГРАМНОГО ПРОДУКТУ
4.1 Вибір технологій та інструментів розробки
Вибір технологій для реалізації програмного продукту обумовлюється
декількома факторами: простота розгортання, можливість швидкої розробки,
підтримка алгоритмічної логіки та доступність широкої бази бібліотек. Оскільки
у межах роботи створюється демонстраційна версія веб-застосунку з обмеженим
функціоналом, було обрано інструменти, які дозволяють ефективно реалізувати
основну ідею з мінімальними витратами на інфраструктуру.
Python обрано як основну мову розробки серверної частини завдяки її
зручності, гнучкості та наявності численних бібліотек для роботи з графами,
алгоритмами та обробкою даних. Зокрема, використовуються такі бібліотеки:
• networkx - для побудови, візуалізації та аналізу графів;
• Flask - легкий веб-фреймворк для створення API та обробки HTTP-
запитів.
Веб-сервер реалізується на основі Flask - мікрофреймворку, що дозволяє
швидко створити REST API. Це дозволяє з’єднати клієнтську частину з
алгоритмічною логікою без складних рішень на рівні інфраструктури.
Інтерфейс реалізовано з використанням базових технологій веб-розробки:
• HTML - структура сторінок;
• CSS - базове стилізування елементів;
• JavaScript - обробка подій, взаємодія з сервером через fetch-запити.
Для мапи або схематичного зображення маршруту можлива інтеграція з
бібліотеками типу Leaflet.js або використання умовної 2D-сітки.
Для локального тестування застосунку використовуються:
• Jupyter Notebook - для прототипування логіки маршрутизації;
• Postman або curl - для перевірки API;
• Google Chrome/Firefox - для візуального перегляду результатів
роботи інтерфейсу.
48
Вибраний стек технологій дозволяє забезпечити реалізацію ключового
функціоналу без необхідності в складних налаштуваннях або хмарній
інфраструктурі. Це відповідає цільовому формату роботи - створенню
практичного, компактного веб-застосунку, орієнтованого на демонстрацію ідей
маршрутизації, а не на повномасштабне промислове рішення.
4.2 Реалізація ключових модулів
У рамках реалізації програмного забезпечення було розроблено низку
основних модулів, які забезпечують функціональність демонстраційного веб-
застосунку для пошуку оптимального маршруту пасажирського транспорту.
Реалізація орієнтована на клієнт-сайд архітектуру з можливістю масштабування
у майбутньому. Усі компоненти реалізовані з використанням веб-технологій
HTML5, CSS3, JavaScript та SVG для інтерактивної візуалізації.
Модуль побудови графа транспортної мережі представляє структуру
зупинок та маршрутів у вигляді неорієнтованого зваженого графа міста Черкаси.
Граф реалізовано у вигляді об'єктних структур JavaScript, де зупинки
зберігаються як асоціативний масив з географічними координатами,
ідентифікаторами та назвами, а сполучення між зупинками представлені
масивом об'єктів з вагами для різних режимів трафіку. Кожне ребро графа
містить два значення ваги: для звичайного режиму руху та для години пік, що
дозволяє моделювати різні транспортні умови.
Модуль пошуку маршруту реалізує алгоритм A* для знаходження
найкоротшого шляху між двома зупинками. Алгоритм використовує евклідову
відстань між координатами зупинок як евристичну функцію, що значно
підвищує ефективність пошуку порівняно з класичним алгоритмом Дейкстри.
Функція враховує поточний режим трафіку при обчисленні ваг ребер та повертає
оптимальний маршрут у вигляді послідовності ідентифікаторів зупинок із
загальним часом проходження.
49
Модуль візуалізації забезпечує інтерактивне відображення транспортної
мережі засобами SVG. Зупинки представлені у вигляді кольорових кіл з
підписами, сполучення відображаються лініями різної товщини залежно від ваги
ребра. Знайдений маршрут виділяється контрастним кольором з анімованим
ефектом. Модуль підтримує інтерактивність: користувач може обирати зупинки
безпосередньо на карті або через випадаючи списки.
Модуль користувацького інтерфейсу реалізує сучасний веб-інтерфейс з
адаптивним дизайном. Інтерфейс включає панель керування з елементами
вибору початкової та кінцевої зупинок, перемикач режимів трафіку, кнопки
управління та область відображення результатів. Усі елементи інтерфейсу
реагують на дії користувача в реальному часі без перезавантаження сторінки.
Модуль обробки змін трафіку дозволяє перемикатися між двома
режимами: звичайний трафік та година пік. При активації режиму години пік
автоматично застосовуються підвищені ваги для певних ребер графа, що імітує
збільшення часу проїзду через затори. Це дозволяє продемонструвати
адаптивність системи до змінних транспортних умов та вплив трафіку на вибір
оптимального маршруту.
Реалізовані модулі забезпечують повний цикл роботи застосунку від
вибору початкової та кінцевої точки до побудови маршруту та візуалізації
результату. Модульна архітектура системи дозволяє незалежно оновлювати
окремі компоненти та додавати новий функціонал, зокрема інтеграцію з базами
даних, обробку реальних GPS-даних або впровадження прогнозування
завантаженості маршрутів.
4.3 Приклади роботи програми та інтерфейсу
Після завершення реалізації ключових модулів було проведено
комплексне тестування роботи системи в локальному веб-середовищі. Усі
функціональні компоненти від вибору зупинок до побудови та візуалізації
50
маршруту працюють через єдиний інтерактивний веб-інтерфейс з
використанням клієнт-сайд технологій.
При запуску застосунку користувач отримує доступ до головної сторінки з
інтуїтивно зрозумілим інтерфейсом. Ліва панель містить елементи керування:
випадаючи списки для вибору початкової та кінцевої зупинок, перемикач
режимів трафіку та кнопки управління пошуком. Права частина екрану
відображає інтерактивну карту транспортної мережі Черкас з позначеними
зупинками та сполученнями між ними. (Рис 4.3).
Рисунок 4.3 - Вигляд головної сторінки застосунку у браузері
Процес пошуку маршруту ініціюється вибором зупинок через випадаючи
списки або безпосереднім кліком по відповідних точках на карті. Після
натискання кнопки "Знайти маршрут" система активує алгоритм A* та
51
відображає індикатор завантаження. Обчислення оптимального маршруту
відбувається протягом 1-2 секунд, після чого результат автоматично
відображається на карті та в інформаційній панелі.
Наприклад, при виборі маршруту від зупинки "Центральний ринок" до
зупинки "Мікрорайон Дахнівка" в звичайному режимі система знаходить
оптимальний шлях: Центральний ринок → Дніпро Плаза → Мікрорайон
Дахнівка з загальним часом проїзду 17 хвилин та проходженням через 3 зупинки.
Знайдений маршрут виділяється на карті яскравою лінією, а детальна інформація
відображається в спеціальному блоці (Рис 4.4).
Рисунок 4.4 - Вигляд результату роботи
Для демонстрації впливу трафіку на маршрутизацію було протестовано
той самий маршрут в режимі години пік. При активації цього режиму ваги
окремих ребер графа автоматично збільшуються, що призводить до перерахунку
оптимального шляху. У результаті система може запропонувати альтернативний
маршрут, який в умовах заторів виявляється більш ефективним за часом, навіть
якщо він довший за відстанню.
Інтерфейс забезпечує миттєвий зворотний зв'язок на всі дії користувача.
Зміна режиму трафіку, очищення результатів, вибір нових зупинок відбуваються
без затримок та перезавантаження сторінки. Система коректно обробляє
помилкові ситуації, наприклад, вибір однакових початкової та кінцевої зупинок
52
або відсутність зв'язку між обраними точками, відображаючи відповідні
повідомлення користувачу.
Візуальне оформлення застосунку відповідає сучасним стандартам веб-
дизайну з градієнтними фонами, округленими елементами, тіньовими ефектами
та плавними анімаціями переходів. Адаптивний дизайн забезпечує коректне
відображення на різних розмірах екранів від настільних комп'ютерів до
мобільних пристроїв.
Архітектура застосунку створює надійну основу для майбутніх розширень,
включаючи інтеграцію з реальними транспортними API, впровадження баз даних
користувацьких переваг та розробку мобільних додатків.
Висновки до розділу 4
У четвертому розділі було здійснено практичну реалізацію системи
маршрутизації пасажирського транспорту у вигляді веб-застосунку. Робота
охопила всі етапи розробки - від вибору технологій до створення ключових
модулів і тестування їх роботи в інтерактивному інтерфейсі. Для обробки
графових структур та реалізації алгоритмів маршрутизації використано
бібліотеку NetworkX. Клієнтська частина розроблена з використанням HTML,
CSS, JavaScript та SVG, що дозволило створити адаптивний і зручний інтерфейс
для користувача.
Основні модулі системи - побудова графа, обчислення маршруту за
допомогою алгоритму A*, візуалізація результату, обробка режимів трафіку -
реалізовані як самостійні компоненти, що забезпечує можливість подальшого
масштабування.
Проведене тестування показало, що система коректно виконує всі
заплановані функції: обчислення оптимального маршруту, динамічну зміну ваг
при моделюванні трафіку, обробку помилок введення та миттєвий вивід
результатів. Реалізація дозволяє продемонструвати ключові принципи
інтелектуального вибору маршрутів навіть у спрощеній, локальній моделі.
53
Таким чином, розділ підтверджує практичну реалізованість теоретичної
моделі, обґрунтованість архітектурних рішень та ефективність обраних
алгоритмів у задачі транспортної маршрутизації. Створена система є
повноцінним демонстраційним продуктом, який можна надалі розширювати у
бік повноцінного міського транспортного застосунку з підтримкою реальних
даних.
54
ВИСНОВКИ
У межах роботи на тему «Створення системи вибору оптимального
маршруту доставки пасажирів м. Черкаси» було розроблено прототип
інтелектуальної системи, яка ілюструє принципи побудови оптимальних
маршрутів у транспортній мережі міста. Робота поєднує аналітичне дослідження,
математичне моделювання, розробку програмного забезпечення та тестування.
На першому етапі було проведено аналіз сучасного стану транспортної
інфраструктури м. Черкаси, виявлено основні проблеми маршрутизації -
фрагментарність даних, відсутність оптимізації руху в години пік, нерівномірне
навантаження на ділянки міста. Проведено огляд існуючих алгоритмів
оптимізації маршрутів, таких як Дейкстра та A*, а також розглянуто приклади
реальних ІТ-рішень у транспортній логістиці.
У другому розділі була побудована математична модель графа
транспортної мережі, визначені вагові коефіцієнти, враховано часові обмеження
та змінну завантаженість. Застосовано алгоритми пошуку найкоротшого шляху
з урахуванням трафіку та потенційного використання моделей машинного
навчання для прогнозування навантаження.
У третьому розділі описано архітектуру майбутнього застосунку,
визначено функціональні та нефункціональні вимоги, а також спроектовано веб-
інтерфейс, який реалізовано засобами HTML, CSS, JavaScript і Python (Flask,
NetworkX). Застосунок побудовано у вигляді модульної системи, яку можна
запускати як локально, так і через браузер без сервера.
У четвертому розділі було реалізовано повноцінний прототип - веб-
застосунок із візуальним інтерфейсом та алгоритмічною логікою. Проведено
приклади запуску, скріншоти інтерфейсу, а також показано, як змінюється
маршрут при моделюванні трафіку. Система демонструє правильну роботу
алгоритму і є повністю функціональною в межах заданої моделі.
55
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. Кормен Т. Х., Лейзерсон Ч. Е., Рівест Р. Л., Штайн К. Алгоритми: побудова
та аналіз. - К.: Вільямс, 2010. - 1312 с.
2. Дейкстра Е. Вирішення задачі про найкоротший шлях // Numerische
Mathematik. - 1959. - № 1. - С. 269–271.
3. Харт П. Е., Нільсен Б., Рафаель Ф. A Formal Basis for the Heuristic
Determination of Minimum Cost Paths // IEEE Transactions on Systems Science
and Cybernetics. - 1968. - Т. 4, № 2. - С. 100–107.
4. Ситник О. М., Карпенко О. А. Моделювання транспортних систем. - К.:
НАУ, 2018. - 144 с.
5. Гребеник В. А. Оптимізація маршрутів пасажирського транспорту в
умовах міста. - Дніпро: ДНУЗТ, 2020. - 108 с.
6. Черкаська міська рада. Система GPS-моніторингу «Dozor» [Електронний
ресурс]. - Режим доступу: https://transport.dozor.tech/cherkasy
7. NetworkX Documentation - Python graph library [Електронний ресурс]. -
Режим доступу: https://networkx.org/documentation/stable/
8. Flask Documentation - Lightweight web framework [Електронний ресурс]. -
Режим доступу: https://flask.palletsprojects.com/
9. Postman API Platform [Електронний ресурс]. - Режим доступу:
https://www.postman.com/
10. Leaflet.js - JavaScript library for interactive maps [Електронний ресурс]. -
Режим доступу: https://leafletjs.com/
11. OpenStreetMap. Відкриті геодані [Електронний ресурс]. - Режим доступу:
https://www.openstreetmap.org
12. Власна розробка автора: демонстраційний веб-застосунок для
маршрутизації пасажирського транспорту. - 2025. - [Авторський код,
реалізований у Flask + NetworkX + HTML/JS].
13. Мартиненко В. В. Транспортна логістика: теорія та практика. - Харків:
ХНАМГ, 2016. - 180 с.
56
14. Пронін С. В., Кравчук І. І. Основи логістики: навч. посіб. - К.: Центр
учбової літератури, 2017. - 256 с.
15. Постанова Кабінету Міністрів України №1081 від 30.12.2015 «Про
затвердження Порядку організації пасажирських перевезень на
автобусному транспорті».
16. Google Maps Platform Documentation [Електронний ресурс]. - Режим
доступу: https://developers.google.com/maps
17. Мельник С. Ю. Теорія графів та її застосування в ІТ. - К.: НТУУ «КПІ»,
2021. - 124 с.
18. O’Reilly. Learning Flask. - Sebastopol: O’Reilly Media, 2020. - 198 p.
19. Якимчук С. Г., Бєлявцев С. І. Комп’ютерне моделювання процесів
логістики. - Львів: Видавництво Львівської політехніки, 2019. - 152 с.
57
ДОДАТОК А
Затверджую
Зав. кафедри КНСА,
______________ Юрій ТРИУС
«____»____________2025 р.
СИСТЕМА ВИБОРУ ОПТИМАЛЬНОГО МАРШРУТУ ДОСТАВКИ
ПАСАЖИРІВ М.ЧЕРКАС
482.ЧДТУ. 52119-01
Листів 2
Розробник ____________________ Міхаіл ПОВЄТЬЄВ-СОФІЄНКО
Керівник ____________________ Микола ПІДГОРНИЙ
Черкаси – 2025
58
482.ЧДТУ. 52119-01
Позначення Найменування Примітка
Документація
482.ЧДТУ. 52119-01 12 01 Текст програми
59
ДОДАТОК Б
СИСТЕМА ВИБОРУ ОПТИМАЛЬНОГО МАРШРУТУ ДОСТАВКИ
ПАСАЖИРІВ М.ЧЕРКАС
Текст програми
482.ЧДТУ. 52119-01 12 01
Листів 20
Розробник _____________ Міхаіл ПОВЄТЬЄВ-СОФІЄНКО
Черкаси – 2025
60
Код головної сторінки
<!DOCTYPE html>
<html lang="uk">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Оптимізація маршрутів - Черкаси</title>
<style>
* {
margin: 0;
padding: 0;
box-sizing: border-box;
}
body {
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
color: #333;
min-height: 100vh;
}
.container {
max-width: 1400px;
margin: 0 auto;
padding: 20px;
}
.header {
text-align: center;
color: white;
margin-bottom: 30px;
}
.header h1 {
61
font-size: 2.5rem;
margin-bottom: 10px;
text-shadow: 2px 2px 4px rgba(0,0,0,0.3);
}
.header p {
font-size: 1.1rem;
opacity: 0.9;
}
.main-content {
display: grid;
grid-template-columns: 350px 1fr;
gap: 20px;
height: calc(100vh - 200px);
}
.control-panel {
background: rgba(255, 255, 255, 0.95);
border-radius: 15px;
padding: 25px;
box-shadow: 0 8px 32px rgba(0,0,0,0.1);
backdrop-filter: blur(10px);
border: 1px solid rgba(255,255,255,0.2);
overflow-y: auto;
}
.map-container {
background: white;
border-radius: 15px;
padding: 20px;
box-shadow: 0 8px 32px rgba(0,0,0,0.1);
position: relative;
overflow: hidden;
}
62
.form-group {
margin-bottom: 20px;
}
label {
display: block;
margin-bottom: 8px;
font-weight: 600;
color: #555;
}
select, button {
width: 100%;
padding: 12px;
border: 2px solid #e1e5e9;
border-radius: 10px;
font-size: 16px;
transition: all 0.3s;
}
select:focus {
outline: none;
border-color: #667eea;
box-shadow: 0 0 0 3px rgba(102, 126, 234, 0.1);
}
.btn-primary {
background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
color: white;
border: none;
font-weight: 600;
cursor: pointer;
margin-bottom: 15px;
}
63
.btn-primary:hover {
transform: translateY(-2px);
box-shadow: 0 4px 15px rgba(102, 126, 234, 0.4);
}
.btn-secondary {
background: #f8f9fa;
color: #6c757d;
border: 2px solid #e9ecef;
cursor: pointer;
font-weight: 500;
}
.btn-secondary:hover {
background: #e9ecef;
}
.traffic-mode {
display: flex;
gap: 10px;
margin-top: 10px;
}
.traffic-btn {
flex: 1;
padding: 8px;
border: 2px solid #e1e5e9;
border-radius: 8px;
background: white;
cursor: pointer;
font-size: 14px;
transition: all 0.3s;
}
64
.traffic-btn.active {
background: #667eea;
color: white;
border-color: #667eea;
}
.svg-map {
width: 100%;
height: 100%;
border-radius: 10px;
}
.stop-circle {
cursor: pointer;
transition: all 0.3s;
}
.stop-circle:hover {
r: 8;
stroke-width: 3;
}
.stop-circle.selected {
fill: #ff6b6b;
stroke: #e55353;
stroke-width: 3;
r: 8;
}
.route-line {
stroke: #4ecdc4;
stroke-width: 4;
fill: none;
opacity: 0.8;
stroke-linecap: round;
65
stroke-linejoin: round;
}
.connection-line {
stroke: #ddd;
stroke-width: 2;
fill: none;
opacity: 0.6;
}
.stop-text {
font-family: Arial, sans-serif;
font-size: 12px;
fill: #333;
text-anchor: middle;
pointer-events: none;
}
.route-info {
background: rgba(78, 205, 196, 0.1);
border: 2px solid #4ecdc4;
border-radius: 10px;
padding: 15px;
margin-top: 20px;
}
.route-info h3 {
color: #2c5aa0;
margin-bottom: 10px;
}
.route-stats {
display: grid;
grid-template-columns: 1fr 1fr;
gap: 10px;
66
margin-top: 10px;
}
.stat-item {
text-align: center;
padding: 8px;
background: rgba(255,255,255,0.7);
border-radius: 8px;
}
.stat-value {
font-weight: bold;
color: #2c5aa0;
font-size: 1.2em;
}
.algorithm-info {
background: rgba(255, 243, 224, 0.8);
border: 2px solid #ffa726;
border-radius: 10px;
padding: 15px;
margin-top: 20px;
font-size: 14px;
}
.loading {
display: none;
text-align: center;
padding: 20px;
color: #667eea;
}
.loading.show {
display: block;
}
67
@media (max-width: 1200px) {
.main-content {
grid-template-columns: 1fr;
grid-template-rows: auto 1fr;
}
.control-panel {
height: auto;
}
}
</style>
</head>
<body>
<div class="container">
<div class="header">
<h1> Система оптимізації маршрутів</h1>
<p>Інтелектуальна система пошуку оптимальних маршрутів у Черкасах</p>
</div>
<div class="main-content">
<div class="control-panel">
<div class="form-group">
<label for="startStop"> Початкова зупинка:</label>
<select id="startStop">
<option value="">Оберіть зупинку...</option>
</select>
</div>
<div class="form-group">
<label for="endStop"> Кінцева зупинка:</label>
<select id="endStop">
<option value="">Оберіть зупинку...</option>
</select>
68
</div>
<div class="form-group">
<label> Режим трафіку:</label>
<div class="traffic-mode">
<button class="traffic-btn active" data-mode="normal">Звичайний</button>
<button class="traffic-btn" data-mode="peak">Година пік</button>
</div>
</div>
<button class="btn-primary" onclick="findRoute()">
Знайти маршрут
</button>
<button class="btn-secondary" onclick="clearRoute()">
Очистити
</button>
<div class="loading" id="loading">
<div> Обчислення оптимального маршруту...</div>
</div>
<div id="routeInfo"></div>
<div class="algorithm-info">
<h4> Алгоритм A*</h4>
<p>Система використовує алгоритм A* для пошуку найкоротшого
маршруту. Алгоритм враховує як фактичну відстань, так і евристичну оцінку до цілі, що
забезпечує оптимальний результат.</p>
</div>
</div>
<div class="map-container">
<svg class="svg-map" id="cityMap" viewBox="0 0 800 600">
69
<!-- Тут буде відображена карта Черкас -->
</svg>
</div>
</div>
</div>
<script>
// Дані про зупинки громадського транспорту в Черкасах
const stops = {
1: { name: "Центральний ринок", x: 400, y: 300, id: 1 },
2: { name: "Площа Героїв Майдану", x: 350, y: 250, id: 2 },
3: { name: "Автовокзал", x: 200, y: 350, id: 3 },
4: { name: "Залізничний вокзал", x: 150, y: 400, id: 4 },
5: { name: "Університет", x: 500, y: 200, id: 5 },
6: { name: "Лікарня", x: 600, y: 300, id: 6 },
7: { name: "Парк Хіміків", x: 450, y: 450, id: 7 },
8: { name: "Мікрорайон Митниця", x: 650, y: 150, id: 8 },
9: { name: "Соборна вулиця", x: 300, y: 200, id: 9 },
10: { name: "Дніпро Плаза", x: 550, y: 350, id: 10 },
11: { name: "Спорткомплекс", x: 100, y: 250, id: 11 },
12: { name: "Мікрорайон Дахнівка", x: 700, y: 400, id: 12 },
13: { name: "Хрещатик", x: 380, y: 180, id: 13 },
14: { name: "Каштанова алея", x: 250, y: 450, id: 14 },
15: { name: "Благовіщенський собор", x: 330, y: 320, id: 15 }
};
// Сполучення між зупинками (граф)
const connections = [
{ from: 1, to: 2, normal: 5, peak: 8 },
{ from: 1, to: 15, normal: 3, peak: 5 },
{ from: 2, to: 9, normal: 4, peak: 6 },
{ from: 2, to: 13, normal: 6, peak: 9 },
{ from: 3, to: 4, normal: 7, peak: 10 },
{ from: 3, to: 14, normal: 8, peak: 12 },
{ from: 4, to: 11, normal: 6, peak: 8 },
70
{ from: 5, to: 8, normal: 9, peak: 13 },
{ from: 5, to: 13, normal: 7, peak: 10 },
{ from: 6, to: 10, normal: 4, peak: 6 },
{ from: 7, to: 10, normal: 6, peak: 9 },
{ from: 7, to: 14, normal: 12, peak: 18 },
{ from: 8, to: 12, normal: 8, peak: 11 },
{ from: 9, to: 11, normal: 10, peak: 15 },
{ from: 10, to: 12, normal: 9, peak: 13 },
{ from: 1, to: 10, normal: 8, peak: 12 },
{ from: 2, to: 15, normal: 4, peak: 6 },
{ from: 3, to: 15, normal: 6, peak: 9 },
{ from: 5, to: 6, normal: 7, peak: 10 },
{ from: 9, to: 13, normal: 5, peak: 8 },
{ from: 6, to: 8, normal: 10, peak: 14 },
{ from: 7, to: 1, normal: 9, peak: 13 },
{ from: 11, to: 3, normal: 8, peak: 11 },
{ from: 4, to: 14, normal: 11, peak: 16 }
];
let currentRoute = [];
let trafficMode = 'normal';
let selectedStart = null;
let selectedEnd = null;
// Ініціалізація
function init() {
populateStopSelects();
drawMap();
setupEventListeners();
}
function populateStopSelects() {
const startSelect = document.getElementById('startStop');
const endSelect = document.getElementById('endStop');
71
Object.values(stops).forEach(stop => {
const option1 = new Option(stop.name, stop.id);
const option2 = new Option(stop.name, stop.id);
startSelect.add(option1);
endSelect.add(option2);
});
}
function setupEventListeners() {
// Обробка перемикання режиму трафіку
document.querySelectorAll('.traffic-btn').forEach(btn => {
btn.addEventListener('click', (e) => {
document.querySelectorAll('.traffic-btn').forEach(b =>
b.classList.remove('active'));
e.target.classList.add('active');
trafficMode = e.target.dataset.mode;
});
});
// Обробка вибору зупинок через селекти
document.getElementById('startStop').addEventListener('change', (e) => {
selectedStart = e.target.value ? parseInt(e.target.value) : null;
updateMapSelection();
});
document.getElementById('endStop').addEventListener('change', (e) => {
selectedEnd = e.target.value ? parseInt(e.target.value) : null;
updateMapSelection();
});
}
function drawMap() {
const svg = document.getElementById('cityMap');
svg.innerHTML = '';
72
// Додаємо назву міста
const title = document.createElementNS('http://www.w3.org/2000/svg', 'text');
title.setAttribute('x', '400');
title.setAttribute('y', '30');
title.setAttribute('text-anchor', 'middle');
title.setAttribute('font-size', '24');
title.setAttribute('font-weight', 'bold');
title.setAttribute('fill', '#2c5aa0');
title.textContent = 'Черкаси - Транспортна мережа';
svg.appendChild(title);
// Малюємо сполучення
connections.forEach(conn => {
const from = stops[conn.from];
const to = stops[conn.to];
const line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
line.setAttribute('x1', from.x);
line.setAttribute('y1', from.y);
line.setAttribute('x2', to.x);
line.setAttribute('y2', to.y);
line.setAttribute('class', 'connection-line');
svg.appendChild(line);
});
// Малюємо зупинки
Object.values(stops).forEach(stop => {
// Коло зупинки
const circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
circle.setAttribute('cx', stop.x);
circle.setAttribute('cy', stop.y);
circle.setAttribute('r', '6');
circle.setAttribute('fill', '#667eea');
circle.setAttribute('stroke', '#4a5c8a');
circle.setAttribute('stroke-width', '2');
73
circle.setAttribute('class', 'stop-circle');
circle.setAttribute('data-stop-id', stop.id);
// Обробка кліків по зупинках
circle.addEventListener('click', () => {
if (!selectedStart) {
selectedStart = stop.id;
document.getElementById('startStop').value = stop.id;
} else if (!selectedEnd && selectedStart !== stop.id) {
selectedEnd = stop.id;
document.getElementById('endStop').value = stop.id;
} else if (selectedStart && selectedEnd) {
// Скидаємо вибір
selectedStart = stop.id;
selectedEnd = null;
document.getElementById('startStop').value = stop.id;
document.getElementById('endStop').value = '';
}
updateMapSelection();
});
svg.appendChild(circle);
// Назва зупинки
const text = document.createElementNS('http://www.w3.org/2000/svg', 'text');
text.setAttribute('x', stop.x);
text.setAttribute('y', stop.y - 12);
text.setAttribute('class', 'stop-text');
text.textContent = stop.name;
svg.appendChild(text);
});
}
function updateMapSelection() {
// Оновлюємо візуальний стан зупинок
74
document.querySelectorAll('.stop-circle').forEach(circle => {
const stopId = parseInt(circle.getAttribute('data-stop-id'));
circle.classList.remove('selected');
circle.setAttribute('fill', '#667eea');
if (stopId === selectedStart) {
circle.classList.add('selected');
circle.setAttribute('fill', '#28a745');
} else if (stopId === selectedEnd) {
circle.classList.add('selected');
circle.setAttribute('fill', '#dc3545');
}
});
}
// Алгоритм A*
function aStar(start, goal) {
const openSet = [start];
const cameFrom = {};
const gScore = {};
const fScore = {};
// Ініціалізація
Object.keys(stops).forEach(id => {
gScore[id] = Infinity;
fScore[id] = Infinity;
});
gScore[start] = 0;
fScore[start] = heuristic(start, goal);
while (openSet.length > 0) {
// Знаходимо вузол з найменшим fScore
let current = openSet.reduce((min, node) =>
fScore[node] < fScore[min] ? node : min
75
);
if (current == goal) {
return reconstructPath(cameFrom, current);
}
openSet.splice(openSet.indexOf(current), 1);
// Перевіряємо сусідів
getNeighbors(current).forEach(neighbor => {
const tentativeGScore = gScore[current] + getDistance(current, neighbor.id);
if (tentativeGScore < gScore[neighbor.id]) {
cameFrom[neighbor.id] = current;
gScore[neighbor.id] = tentativeGScore;
fScore[neighbor.id] = gScore[neighbor.id] + heuristic(neighbor.id, goal);
if (!openSet.includes(neighbor.id)) {
openSet.push(neighbor.id);
}
}
});
}
return null; // Шлях не знайдено
}
function heuristic(from, to) {
// Евклідова відстань як евристика
const fromStop = stops[from];
const toStop = stops[to];
return Math.sqrt(
Math.pow(fromStop.x - toStop.x, 2) +
Math.pow(fromStop.y - toStop.y, 2)
) / 20; // Масштабуємо для відповідності часовим метрикам
76
}
function getNeighbors(stopId) {
const neighbors = [];
connections.forEach(conn => {
if (conn.from == stopId) {
neighbors.push(stops[conn.to]);
} else if (conn.to == stopId) {
neighbors.push(stops[conn.from]);
}
});
return neighbors;
}
function getDistance(from, to) {
const conn = connections.find(c =>
(c.from == from && c.to == to) ||
(c.from == to && c.to == from)
);
return conn ? conn[trafficMode] : Infinity;
}
function reconstructPath(cameFrom, current) {
const path = [current];
while (cameFrom[current]) {
current = cameFrom[current];
path.unshift(current);
}
return path;
}
function findRoute() {
if (!selectedStart || !selectedEnd) {
alert('Будь ласка, оберіть початкову та кінцеву зупинки');
return;
77
}
if (selectedStart === selectedEnd) {
alert('Початкова та кінцева зупинки не можуть бути однаковими');
return;
}
const loading = document.getElementById('loading');
loading.classList.add('show');
// Симулюємо затримку обчислення
setTimeout(() => {
const route = aStar(selectedStart.toString(), selectedEnd.toString());
loading.classList.remove('show');
if (route) {
currentRoute = route;
displayRoute(route);
drawRoute(route);
} else {
alert('Маршрут не знайдено');
}
}, 800);
}
function displayRoute(route) {
if (!route || route.length === 0) return;
let totalTime = 0;
let totalDistance = 0;
// Обчислюємо загальні показники
for (let i = 0; i < route.length - 1; i++) {
const distance = getDistance(route[i], route[i + 1]);
totalTime += distance;
78
totalDistance += distance;
}
const routeInfo = document.getElementById('routeInfo');
routeInfo.innerHTML = `
<div class="route-info">
<h3> Знайдений маршрут</h3>
<p><strong>Шлях:</strong> ${route.map(stopId => stops[stopId].name).join('
→ ')}</p>
<div class="route-stats">
<div class="stat-item">
<div class="stat-value">${totalTime}</div>
<div>хвилин</div>
</div>
<div class="stat-item">
<div class="stat-value">${route.length}</div>
<div>зупинок</div>
</div>
</div>
<p style="margin-top: 10px; font-size: 14px; color: #666;">
Режим: ${trafficMode === 'peak' ? ' Година пік' : '✅ Звичайний трафік'}
</p>
</div>
`;
}
function drawRoute(route) {
// Видаляємо попередній маршрут
document.querySelectorAll('.route-line').forEach(line => line.remove());
const svg = document.getElementById('cityMap');
// Малюємо лінії маршруту
for (let i = 0; i < route.length - 1; i++) {
const from = stops[route[i]];
79
const to = stops[route[i + 1]];
const line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
line.setAttribute('x1', from.x);
line.setAttribute('y1', from.y);
line.setAttribute('x2', to.x);
line.setAttribute('y2', to.y);
line.setAttribute('class', 'route-line');
svg.appendChild(line);
}
}
function clearRoute() {
currentRoute = [];
selectedStart = null;
selectedEnd = null;
document.getElementById('startStop').value = '';
document.getElementById('endStop').value = '';
document.getElementById('routeInfo').innerHTML = '';
// Видаляємо маршрут з карти
document.querySelectorAll('.route-line').forEach(line => line.remove())
// Скидаємо виділення зупинок
updateMapSelection();
}
// Запуск після завантаження сторінки
document.addEventListener('DOMContentLoaded', init);
</script>
</body>
</html>