Дослідження систем автоматичної побудови оптимальних логістичних маршрутів

Сафронов, Святослав Андрійович

Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал: https://er.chdtu.edu.ua/handle/ChSTU/6304

Назва:	Дослідження систем автоматичної побудови оптимальних логістичних маршрутів
Автори:	Корпань, Ярослав Васильович Сафронов, Святослав Андрійович
Дата публікації:	січ-2024
Короткий огляд (реферат):	Мета кваліфікаційної роботи - розробка та дослідження систем автоматичної побудови оптимальних логістичних маршрутів шляхом алгоритмів та методів. Для досягнення поставленої мети було вирішено наступні задачі: проведено аналіз та обрано підходящий алгоритм для побудови оптимальних маршрутів; проведено аналіз та визначено доступну платформу для зручної реалізації алгоритму; досліджено сумісну програму для автоматичної візуалізації прорахованого результату алгоритму; реалізовано алгоритм та інтегровані дієві інструменти взаємодії: просту базу даних, базовий візуалізатор маршруту; створена модель системи побудови логістичного маршрут враховуючи пріоритетність.
URI (Уніфікований ідентифікатор ресурсу):	https://er.chdtu.edu.ua/handle/ChSTU/6304
Розташовується у зібраннях:	174 Автоматизація, комп'ютерно-інтегровані технології та робототехніка (Автоматизація та комп'ютерно-інтегровані системи та компоненти)

Файли цього матеріалу:

Файл	Опис	Розмір	Формат
М_151_2023_Сафронов.pdf Restricted Access		2.05 MB	Adobe PDF	Переглянути/Відкрити Запит копії

Показати повний опис матеріалу Перегляд статистики

Усі матеріали в архіві електронних ресурсів захищено авторським правом, усі права збережено.

Extracted text

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ І СИСТЕМ
КАФЕДРА РОБОТОТЕХНІКИ ТА СПЕЦІАЛІЗОВАНИХ КОМП’ЮТЕРНИХ
СИСТЕМ

Пояснювальна записка
до кваліфікаційної роботи
освітнього ступеню «магістр»

на тему: ДОСЛІДЖЕННЯ СИСТЕМ АВТОМАТИЧНОЇ ПОБУДОВИ
ОПТИМАЛЬНИХ ЛОГІСТИЧНИХ МАРШРУТІВ

Виконав: здобувач вищої освіти 2 курсу, групи
МАКІТ-2209 спеціальності 151
Автоматизація та комп’ютерно-
інтегровані технології, освітня
програма «Комп’ютерно-інтегровані
системи та компоненти»
Святослав САФРОНОВ
(ім’я, ПРІЗВИЩЕ)
Керівник Ярослав КОРПАНЬ
( ім’я, ПРІЗВИЩЕ)

Рецензент
( ім’я, ПРІЗВИЩЕ)

Черкаси 2023 року
2

ЗМІСТ

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ ....................................................... 4
РОЗДІЛ 1 ТЕОРЕТИЧНІ АСПЕКТИ ГРАФІВ ..................................................... 8
1.1. Поняття графів та сфери їх використання ..................................................... 8
1.2. Основні характеристики графів .................................................................... 21
РОЗДІЛ 2. ДОСЛІДЖЕННЯ ПРАКТИЧНИХ АСПЕКІВ ВИКОРИСТАННЯ
ГРАФІВ ТА ЇХ ЗАСТОСУВАННЯ У ЛОГІСТИЦІ ........................................... 25
2.2. Cпособи використання графів у логістиці ................................................... 30
2.3. Теоретичні аспекти пошуків оптимальних шляхів за допомогою графів 33
РОЗДІЛ 3. РОЗРОБКА МОДЕЛІ СИСТЕМИ ДЛЯ АВТОМАТИЧНОЇ
ПОБУДОВИ ОПТИМАЛЬНИХ ЛОГІСТИЧНИХ МАРШРУТІВ ................... 41
3.1. Опис функціональних можливостей ПЗ для побудови моделі системи .. 41
3.2. Аналіз існуючих систем для побудови системи автоматичної побудови
оптимальних логістичних маршрутів ................................................................. 46
3.3. Опис алгоритму створення ПЗ для побудови оптимальних логістичних
маршрутів ............................................................................................................... 49
3.4. Огляд цілей інтеграції дизайну інтерфейсу у логістичні системи ............ 53
3.5. Основні принципи дизайну інтерфейсу ....................................................... 54
3.6. Інтеграція дизайну інтерфейсу в контексті логістики ................................ 56
3.7. Висновок, щодо теоретичної імплементації інтерактивного інтерфейсу 58
РОЗДІЛ 4. РОЗРОБКА ІНТЕРАКТИВНОГО ІНТЕРФЕЙСУ ДЛЯ
ЕФЕКТИВНОГО УПРАВЛІННЯ ЛОГІСТИЧНИМИ МАРШРУТАМИ ........ 59
4.1. Аналіз потреб і вимог користувачів до інтерфейсу .................................... 59
4.2. Розробка основної концепції інтерфейсу з урахуванням функціональності
та дизайну ............................................................................................................... 59
4.3. Деталізація технічних аспектів розробки, включно з технологіями та
платформами .......................................................................................................... 60
3

4.4. Підсумки роботи та напрямки для подальших досліджень та розвитку .. 74
ВИСНОВКИ ........................................................................................................... 76
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ............................................................. 77

4

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Враховуючи сьогоднішні тенденції стрімкого
розвитку будь яких структур, будь то бізнес корпорацій, чи державних
військових структур, логістика залишається найважливішою та найбільш
відповідальною складовою дієздатності. Ба більше, зазвичай логістика є
найслабшою ланкою процесів - це можна спостерігати з 2х сторін: або коли
задачі плануються від фактичної та прогнозованої доступності ресурсів, або
коли покращення частини цієї сфери значно покращує результати.
Втім перед тим як перейти до самої теми треба розібратись, що саме
мається на увазі під словом "логістика".
Часто згадувана «логістика» походить від слова «logistique» або «loger»
французькою, що означає зберігання. В нас логістикою називають систему,
яка транспортує ресурси, товари або інформацію ресурси від місця
походження до пункту призначення відповідно до потреб кінцевого
користувача. Логістика включає інформацію, транспортування, управління
запасами, управління сировиною та пакування. Логістика є частиною
ланцюга поставок, яка використовує місцевість і час для підвищення
фактичної цінності ресурсів.
Простіше кажучи, логістика - це процес передачі, зберігання та
поширення товарів, послуг або інформації з місця їх походження до місця, де
є попит. Це здійснюється за допомогою цілісного процесу, зосередженого на
дієвості та ефективності, спрямованому на своєчасну доставку та зниження
витрат, а також підвищує задоволеність клієнтів і додає цінність товарів і
послуг.
Управління матеріально-технічним забезпеченням виникло в
британській армії задовго до початку Першої світової війни, коли військова
система ланцюга поставок була розроблена шляхом створення
інфраструктури, наприклад; дороги, залізниці, порти, аеродроми, склади
постачання та транспортні засоби для перевезення зброї та військ. У
5

Сполучених Штатах, які почали розповсюдження сільськогосподарської
продукції по всьому континенту наприкінці 19 століття, відбувся розвиток
системи розподілу промислових товарів. Це в кінцевому підсумку призвело
до початку офіційної науки управління логістикою в США в 1964 році.
Дотепер державний сектор адаптував управління логістикою у своїй діловій
практиці.
Для торгівлі та промислового сектора логістика відіграє важливу роль у
зниженні витрат, що, у свою чергу, збільшує прибуток. Він також
використовується як важливий інструмент у створенні
конкурентоспроможності, оскільки допомагає створити ефективність
обслуговування клієнтів, встановити хороші відносини як з внутрішніми, так
і зовнішніми клієнтами, а також виступає як основа для зростання бізнесу за
допомогою швидких інформаційних технологій.
Щоб мати можливість ефективно здійснювати управління логістикою,
потрібно об’єднати та використовувати різні галузі знань в одну. Ці поля
включають:
Інженерна наука в галузі промислового машинобудування
Управління бізнесом, яке допомагає піклуватися про міжнародні
перевезення, враховуючи відповідні закони, оподаткування, фрахт, різні
національні логістичні стратегії чи плани та міжнародні торгівлі. Усі ці
напрямки будуть враховані для створення плану доставки товарів у різні
країни.
Управління інформацією, яке вивчає програмне та апаратне
забезпечення та поєднує їх разом, щоб створити послугу, яка допомагає
генерувати та полегшувати логістичну діяльність з більшою гнучкістю.
Мета кваліфікаційної роботи – розробка системи автоматичної
побудови оптимальних логістичних маршрутів з покращеним алгоритмом
розрахунку.
Для досягнення поставленої мети необхідно вирішити наступні задачі:

6

- провести аналіз та обрати підходящий алгоритм для побудови
оптимальних маршрутів;
- провести аналіз та визначити доступну платформу для зручної
реалізації алгоритму;
- дослідити сумісну програму для автоматичної візуалізаці
прорахованого результату алгоритму;
- реалізувати запропонованих алгоритм та інтегрувати дієві
інструменти взаємодії: просту базу даних, базовий візуалізатор маршруту;
- побудувати маршрут враховуючи пріорітетність місць призначень:
пріорітетність буде братися як умовний показник, що може позначати
терміновість, час, або затрати на доставлення;
- побудувати маршрут враховуючи реальні можливості складів, або
перевізників.
Об'єкт дослідження – процес автоматичного визначення та побудови
оптимальних логістичних маршрутів.
Предмет дослідження - системи автоматичної побудови оптимальних
логістичних маршрутів.
Методи дослідження
Методологічними основами дослідження обраної теми були методи
аналізу, синтезу та оптимізації, порівняння, узагальнення. На різних етапах
дослідження використовувалися загальні та спеціальні методи теорії графів
Наукова новизна одержаних результатів
Проведений системний аналіз та дослідження теоретичних аспектів
графів дозволив сформулювати особливості їх застосування при створенні
систем автоматичної побудови оптимальних логістичних маршрутів.
Практичне значення одержаних результатів
Створена модель системи побудови логістичних маршрутів, яка
враховує пріоритетність. Пріоритетність виражена чисельним значенням, що
може базуватися на інших комплексних алгоритмах, що враховують
терміновість, час доставки та витрати на доставку.
7

Апробація результатів дослідження
Матеріали кваліфікаційної роботи доповідались та обговорювалися на
студентській науково-практичній конференції ЧДТУ 18–20 квітня 2023 р.
За результатами конференції опублікована в збірнику тез наукова
праця:
Сафронов С. А. Дослідження систем автоматичної побудови
оптимальних логістичних маршрутів / С. А. Сафронов, Я. В. Корпань //
Збірник тез доповідей студентської науковопрактичної конференції ЧДТУ:
18–20 квітня 2023 р. [Електронний ресурс] / [упоряд.: Єгорова О. В., Захарова
О. В., Кисельов В. Б. та ін.]; Мво освіти і науки України, Черкас. держ.
технол. унт. – Черкаси: ЧДТУ, 2023. – C. 19.
Структура та обсяг кваліфікаційної роботи
Кваліфікаційна робота магістра складається з загальної характеристики
роботи, чотирьох розділів, висновку та списку використаних джерел.
Загальний обсяг роботи складає 80 сторінки, 50 рисунків, 1 таблиці. Список
використаних джерел містить 30 найменувань.

8

РОЗДІЛ 1 ТЕОРЕТИЧНІ АСПЕКТИ ГРАФІВ

1.1. Поняття графів та сфери їх використання
Графом називається математична абстракція реальної системи будь-
якої природи, об'єкти якої мають парні зв'язки. Граф як математичний об'єкт
є сукупністю двох множин - безлічі самих об'єктів, що називаються безліччю
вершин, і множини їх парних зв'язків, що називаються безліччю ребер.
Елементом множини ребер є пара елементів множини вершин.
Графи знаходять широке застосування у сучасній науці та техніці.
Вони використовуються і в природничих науках (фізиці та хімії) і в
соціальних науках (наприклад, соціології), але найбільших масштабів
застосування графів набуло в інформатиці та мережевих технологіях.
Як найпростіший приклад із життя можна навести схему перельотів
певної авіакомпанії, яка моделюється графом, де вершинами графа є міста, а
ребрами - рейси, що з'єднують пари міст. Дерево каталогів у комп'ютері
також є графом: диски, папки та файли є вершинами, а ребра показують
вкладеність файлів та папок у папки та диски. Так, будова Вікіпедії
моделюється орієнтованим графом, у якому статті – вершини графа, а
гіперпосилання – дуги (тематична карта).
Графи є головним об'єктом вивчення теорії графів.
Моделювані графами системи реальної природи мають велику
різноманітність, тому існують графи різних типів. Найпростішою
абстракцією систем з елементами, що мають парні зв'язки, є простий граф.
У математичній теорії графів та інформатики граф - це сукупність
непустої множини вершин і безлічі пар вершин (зв'язків між вершинами).
Приклад графу представлено на рис. 1.1.
Граф, або неорієнтований граф G - це впорядкована пара G := (V, E),
для якої виконані такі умови:
V - це непорожня безліч вершин, або вузлів,
9

E – це безліч пар (у разі неорієнтованого графа – невпорядкованих)
вершин, званих ребрами.

Рис. 1.1 Приклад графу

V (а отже, E, інакше воно було б мультимножиною) зазвичай
вважаються кінцевими множинами. Багато хороших результатів, отриманих
для кінцевих графів, неправильні (або будь-яким чином відрізняються) для
нескінченних графів. Це тому, що ряд міркувань стає хибним у разі
нескінченних множин (рис.1.2).
Вершини та ребра графа називаються також елементами графа, число
вершин у графі | V | - порядком, число ребер | E | - Розміром графа.

10

Рис. 1.2. Граф

Вершини u та v називаються кінцевими вершинами (або просто
кінцями) ребра e=\{u,v\}. Ребро, своєю чергою, з'єднує ці вершини. Дві
кінцеві вершини того самого ребра називаються сусідніми.
Два ребра називаються суміжними, якщо вони мають спільну кінцеву
вершину.
Два ребра називаються кратними, якщо множини їх кінцевих вершин
збігаються.
Ребро називається петлею, якщо його кінці збігаються, тобто e=\{v,v\}.
Ступенем \deg V вершини V називають кількість інцидентних їй ребер
(при цьому петлі вважають двічі).
Вершина називається ізольованою, якщо вона не є кінцем для жодного
ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.
Орієнтований граф представлено на рис. 2.3.

Рис. 1.3. Приклад орієнтованого графу
11

Орієнтований граф (скорочено орграф) G - це впорядкована пара G :=
(V, A), для якої виконані такі умови:
V - це непорожня безліч вершин або вузлів,
A - це безліч (упорядкованих) пар різних вершин, званих дугами або
орієнтованими ребрами.
Дуга - це впорядкована пара вершин (v, w), де вершину v називають
початком, а w - кінцем дуги. Можна сміливо сказати, що дуга v \to w веде від
вершини v до вершини w.
Змішаний граф G – це граф, у якому деякі ребра можуть бути
орієнтованими, а деякі – неорієнтованими. Записується упорядкованою
трійкою G := (V, E, A), де V, E та A визначені так само, як вище.
Орієнтований та неорієнтований графи є окремими випадками
змішаного.
Граф G називається ізоморфним графу H, якщо існує бієкція f з безлічі
вершин графа G у безліч вершин графа H, що має таку властивість: якщо у
графі G є ребро з вершини A у вершину B, то у графі H має бути ребро з
вершини f( A) у вершину f(B) і навпаки — якщо у графі H є ребро з вершини
A у вершину B, то у графі G має бути ребро з вершини f^{-1}(A) у вершину
f^{-1} (B). У разі орієнтованого графа ця бієкція також має зберігати
орієнтацію ребра. У разі зваженого графа бієкція також має зберігати вагу
ребра.
Шляхом (або ланцюгом) у графі називають кінцеву послідовність
вершин, у якій кожна вершина (крім останньої) з'єднана з наступною в
послідовності вершин ребром.
Орієнтованим шляхом в орграфі називають кінцеву послідовність
вершин v_i (i=1,\ldots,k), для якої всі пари (v_i, v_{i+1}) (i=1,\ldots k-1) є
(орієнтованими) ребрами.
Циклом називають шлях, у якому перша та остання вершини
збігаються. При цьому довжиною шляху (або циклу) називають число
складових його ребер. Зауважимо, що й вершини u і v є кінцями деякого
12

ребра, відповідно до даного визначення, послідовність (u,v,u) є циклом. Щоб
уникнути таких вироджених випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра у ньому не
повторюються; елементарним, якщо він простий і вершини у ньому не
повторюються. Нескладно бачити, що:
Кожен шлях, що з'єднує дві вершини, містить елементарний шлях, що
з'єднує ті самі дві вершини.
Будь-який простий неелементарний шлях містить елементарний цикл.
Будь-який простий цикл, що проходить через деяку вершину (або
ребро), містить елементарний (під-)цикл, що проходить через ту саму
вершину (або ребро).
Петля – елементарний цикл.
Бінарне відношення на безлічі вершин графа, задане як «існує шлях з u
в v», є ставленням еквівалентності і, отже, розбиває цю множину на класи
еквівалентності, які називають компонентами зв'язності графа. Якщо у графа
одно компонента зв'язності, то граф зв'язний. На компоненті зв'язності можна
запровадити поняття відстані між вершинами як мінімальну довжину шляху,
що з'єднує ці вершини.
Будь-який максимальний зв'язний підграф графа G називається
зв'язною компонентою (або просто компонентою) графа G. Слово
«максимальний» означає максимальний щодо включення, тобто не міститься
у зв'язному підграфі з великою кількістю елементів
Ребро графа називається мостом, якщо його видалення збільшує
кількість компонентів.
Графи будуть для того, щоб відобразити стосунки на множинах. По
суті, графи допомагають візуально уявити всілякі складні взаємодії:
аеропорти та рейси між ними, різні відділи у компанії, молекули у речовині.
Графи мають дуже широке застосування, адже з їх допомогою
вибирають найбільш вигідне розташування будівель, графами представлені
схеми метро. Так, прикладами застосування графів можна назвати:
13

1. Граф будь-якої позиційної гри: шахів, шашок, «хрестиків –
нуліків» (рис. 1.4).

Рис. 1.4. Приклад графу позиційної гри

Тут позиції стануть вершинами, а спрямовані відрізки між ними
означатимуть, що одним ходом можна перейти від однієї позиції до іншої, у
напрямку стрілки
2. Лабіринт (рис. 1.5).

Рис. 1.5. Приклад лабіринту

14

Дослідити лабіринт – це знайти шлях у цьому графі. Вершинами тут
позначені безвиході, а відрізками – проходи лабіринту.
3. Генеалогічне дерево (рис. 1.6)

Рис. 1.6. Приклад генеалогічного дерева

Граф ієрархічної системи називається деревом. Відмінною особливістю
дерева є те, що між будь-якими двома його вершинами існує єдиний шлях.
Дерево не містить циклів та петель.
Зазвичай у дерева, що становить ієрархічну систему, виділяється одна
головна вершина, яка називається коренем дерева. Кожна вершина дерева
(крім кореня) має лише одного предка – позначений нею об'єкт входить до
одного класу верхнього рівня.
Будь-яка вершина дерева може породжувати кілька нащадків – вершин,
які відповідають класам нижнього рівня.
Для кожної пари вершин дерева існує єдиний шлях, який їх сполучає.
Цією властивістю користуються при знаходженні всіх предків, наприклад, по
15

чоловічій лінії, будь-якої людини, чий родовід представлений у вигляді
генеалогічного дерева, яке є «деревом» і в сенсі теорії графів.
4. Блок-схема програми (рис. 1.7).

Рис. 1.7. Приклад блок-схеми програми

Графами є блок - схеми програм для ЕОМ, а також будь-які електричні
ланцюги або електрична мережа.
5. Схема ланцюгів чергового освітлення (рис. 1.8).
16

Рис. 1.8. Приклад схеми ланцюгів чергового освітлення

Схема ланцюгів чергового освітлення тепловоза ТЕМ2 також може
бути представлена як граф.
6. Схеми авіаліній (рис. 1.9).

Рис. 1.9. Схеми авіаліній, що можуть бути представлені у вигляді графів
17

7. Ділянка Метрополітену (рис. 1.10).

Рис. 1.10. Приклад схеми Паризького метро

8. Соціограми (рис. 2.11).

Рис. 2.11. Приклад соціограми
Соціограми (у психології щодо міжособистісних відносин у групах).
Вона також представлена за допомогою графа.
18

9. Схема залізничних доріг (рис. 12).

Рисунок 12 Схема залізничних доріг

В схемах залізниць вершини – залізничні станції, а ребра – залізничні
колії.
10. Графи є і на картах зоряного неба. Це сузір'я (рис. 2.13).

Рис. 1.13 Приклад сузір’я
19

11. Хімія
Теорія графів дозволяє точно визначити та пояснити деякі основні
поняття хімії: структуру, конфігурацію, конформацію, квантовомеханічну та
статистико-механічну взаємодії молекул, визначати число теоретично
можливих ізомерів органічних сполук, дозволяє аналізувати деякі хімічні
перетворення, описувати хімічні реакції, визначати деякі властивості
молекул. Молекулярний граф (рис. 1.14) – зв'язний неорієнтований граф, що
знаходиться у взаємно-однозначній відповідності до структурної формули
хімічної сполуки таким чином, що вершинам графа відповідають атоми
молекули, а ребрам графа — хімічні зв'язки між цими атомами.

Рис. 1.14. Приклад молекулярного графу

12. Математика
Чимало приводів появи графів й у математиці. Найбільш очевидний
приклад – будь-який багатогранник у тривимірному просторі.
Наприклад, вершини та ребра куба можна розглядати як вершини та
ребра графа. При цьому ми відволікаємось від того, як розташовані елементи
куба у просторі, залишаючи лише інформацію про те, які вершини з'єднані
ребрами. На рис. 1.15 показані три способи зобразити той самий граф -
тривимірного куба.
Графи в геометричних фігурах
Ще один спосіб утворення графів з геометричних об'єктів ілюструє
малюнком.

20

Рис. 1.15. Приклад графів у математиці

Зліва показано шість кіл на площині, а праворуч - граф, у якому кожна
вершина відповідає одному з цих кіл і дві вершини з'єднані руба.
Так само графи під іншими назвами проникли в підручники хімії,
біології, географії, де вони використані для наочного та економного опису
різних схем організацій, логічних можливостей, класифікацій, у тому й лише
тому випадку, коли відповідні кола перетинаються.
13. Фізика
Однією з найбільш складних та стомлюючих завдань для радіоаматорів
вважається конструювання друкованих плат (рис. 1.16).

Рис. 1.16. Схема друкованої плати
21

Друкована схема - це платівка з будь-якого діелектрика (ізолюючого
матеріалу), на якій у вигляді металевих смужок витравлені доріжки.
Перетинатися доріжки можуть лише у певних точках, куди встановлюються
необхідні елементи (діоди, тріоди, резистори та інші), їхнє перетинання в
інших місцях викличе замикання електричного кола.
Отже, зі всього вищесказаного незаперечно випливає практична
цінність теорії графів, доказ якої і був метою даного дослідження.

1.2. Основні характеристики графів
Граф G- це математичний об'єкт, що складається з множини вершин X
= {x1, x2,..., xn} і безлічі ребер A = {a1, a2,..., an}. Таким чином, граф
повністю визначається сукупністю множин X, A: G = (X, A).
Для багатьох завдань несуттєво, чи ребра є відрізками прямих або
криволінійними дугами; важливо лише те, які вершини з'єднує кожне ребро.
Якщо ребрам графа надано напрями від однієї вершини до іншої, такий
граф називається орієнтованим. Ребра орієнтованого графа називаються
дугами. Відповідні вершини орієнтованого графа називають початками та
кінцем. Якщо напрями ребер не вказуються, то граф називається
неорієнтованим (або графом).
Зобразимо для прикладу неорієнтований граф G = (X, A) (рис. 1.17).

Рис. 1.17. Приклад неорієнтованого графу
22

X = {x1, x2, x3, x4},
A = {a1=(x1, x2), a2=(x2, x3), a3=(x1, x3), a4=(x3, x4)}.
Зобразимо для прикладу орієнтований граф G = (X, A) (рис. 1.18).

Рис. 1.18. Приклад орієнтованого графу

X = {x1, x2, x3, x4},
A = {a1 = (x1, x2), a2 = (x1, x3), a3 = (x3, x4), a4 = (x3, x2)}..
Граф, який має як орієнтовані, і неорієнтовані ребра, називається
змішаним.
Різні ребра можуть з'єднувати ту саму пару вершин. Такі ребра
називають кратними. Граф, що містить кратні ребра, називається
мультиграфом.
Неорієнтоване ребро графа еквівалентно двом протилежно
спрямованим дугам, що з'єднують ті самі вершини.
Ребро може поєднувати вершину саму з собою. Таке ребро називається
петлею. Граф з кратними ребрами та петлями називається псевдографом.
Багато ребер графа може бути порожнім. Безліч вершин графа може
бути порожнім.
23

Як у випадку орієнтованого, так і у випадку неорієнтованого ребра
кажуть, що вершини xі yнцидентні ребра a, якщо ці вершини з'єднані a.
Дві вершини називаються суміжними, якщо вони інцидентні тому
самому ребру. Два ребра називаються суміжними, якщо вони мають спільну
вершину.
Ступінню вершини графа називається число ребер, інцидентних цій
вершині. Вершина, що має ступінь 0, називається ізольованою, а ступінь 1 –
висячою.
Для орієнтованого графа безліч вершин, які ведуть дуги, що виходять з
вершини х, позначають G(х), тобто G(х) = { y: ( x y ) G}. Множина G(x)
називають образом вершини x. Відповідно G-1(у) – безліч вершин, з яких
виходять дуги, що ведуть у вершину у, G-1(y)= {x: (x, y) G}. Безліч G-1
називають прообразом вершини y.
Граф G = (X, A) - повний, якщо для будь-якої пари вершин xi та xj існує
ребро (xi, xj).
Граф G = (X, A) - симетричний, якщо для будь-якої дуги (xi, xj) існує
протилежно орієнтована дуга (xj, xi).
Граф G = (X, A) -планарний, якщо він може бути зображений на
площині так, що не буде дуг, що перетинаються.
Неорієнтований граф G = (X, A) – дводольний, якщо безліч його
вершин X можна розбити на два такі підмножини X1 і X2, що кожне ребро
має один кінець у X1, а інший у X2.
Граф, який має як орієнтовані, і неорієнтовані ребра, називається
змішаним.
Різні ребра можуть з'єднувати ту саму пару вершин. Такі ребра
називають кратними. Граф, що містить кратні ребра, називається
мультиграфом.
Неорієнтоване ребро графа еквівалентно двом протилежно
спрямованим дугам, що з'єднують ті самі вершини.
24

Ребро може поєднувати вершину саму з собою. Таке ребро називається
петлею. Граф з кратними ребрами та петлями називається псевдографом.
Багато ребер графа може бути порожнім. Безліч вершин графа може
бути порожнім.

25

РОЗДІЛ 2. ДОСЛІДЖЕННЯ ПРАКТИЧНИХ АСПЕКІВ
ВИКОРИСТАННЯ ГРАФІВ ТА ЇХ ЗАСТОСУВАННЯ У ЛОГІСТИЦІ

2.1. Математичний апарат графів
Системи, що модулюються графами, є досить різноманітними, тому
існують графи різних типів. Найпростішою абстракцією систем з
елементами, що мають парні зв'язки, є простий граф.
Простий граф G(V,E) є сукупністю двох множин - непустої множини V
і множини E невпорядкованих пар різних елементів множини V.
Безліч V називається безліччю вершин, безліч E називається безліччю
ребер
G(V,E)={V,E},
V≠Ø
E≤V*V
{v,v}ϵ E,
v ϵ G,
тобто безліч E складається з 2-елементних підмножин безлічі V.
Теорія графів не має усталеної термінології. Тому деякі публікації
можуть використовувати терміни, що відмінними від наведених нижче.
Вершина (вузол, точка) графа G є елементом безлічі вершин v ϵ V(G)};
Ребро (лінія) графа G є елементом безлічі ребер e ϵ E(G), або e={v1,v2},
де v1 ϵ V(G), v2 ϵ V(G);
Елементами графа G називаються його вершини v ϵ V(G) і ребра e ϵ
E(G) графа;
Порядок (англ. order) графа G є кардинальне число множини вершин
n=|V(G)| або, іншими словами, кількість вершин;
Розмір (англ. size) графа G є кардинальним числом множини ребер
m=|E(G)| або, іншими словами, кількість ребер;
Вершина v інцидентна (англ. incident) ребраe, якщо v ϵ e; тоді ще
кажуть, що e є ребро при v;
26

Кінцеві вершини (кінці) (endvertices, ends) є дві вершини, інцидентні
ребру. Ребро з'єднує (англ. joins) свої кінцеві вершини;
Сусідні (суміжні) вершини (англ. neighbours, adjacent) є такі вершини v1
і v2, що {v1,v2} ϵ E(G) або, іншими словами обидві вершини є кінцевими
одного ребра;
Суміжні ребра (англ. adjacent edges) це ребра, інцидентні одній вершині
або e1={v, v1} і e2={v, v2} - суміжні;
Ступінь (валентність) вершини (англ. degree, valency) є кількість
інцидентних їй ребер. Ступінь вершини позначається як d(v);
Ізольованою вершиною (англ. isolated) називається вершина зі
ступенем d(v)=0 , тобто не є кінцем для жодного ребра;
Висячою вершиною (англ. leaf) називається вершина зі ступенем
d(v)=1, тобто яка є кінцем рівно одного ребра.
Зазвичай граф є діаграмою: вершини – точками, ребра – лініями.
Псевдографом G(V,E) є сукупність двох множин - непустої множини V
і множини E невпорядкованих пар елементів множини V

G(V,E)= (V, E), V≠Ø, E≤ V * V.

У багатьох ребер псевдографа дозволено елемент {v,v} ϵ E(G).
Петлею (англ. loop) називається елемент e = {v,v}, що є рубом, у якого
кінцеві вершини збігаються.
Іншими словами, якщо елементами множини E можуть бути петлі, то
граф називається псевдографом.
Мультиграфом G (V, E) є сукупність двох множин - непустої множини
V і мультимножини E невпорядкованих пар різних елементів множини V

G (V, E) = (V, E), V ≠ Ø, E ≤ V * V, {v,v} ≠ E, v є V.

27

Кратними ребрами називаються однакові елементи мультимножини {e,
e, ...,e} є E, тобто ребра, чиї кінцеві вершини збігаються.
Іншими словами, якщо E не безліч, а сімейство, тобто якщо E містить
однакові елементи, такі елементи називаються кратними ребрами, а граф
називається мультиграфом.
Маршрутом у графі називають кінцеву послідовність вершин, у якій
кожна вершина (крім останньої) з'єднана з наступною у послідовності
вершиною ребром. Ланцюгом називається маршрут без повторюваних ребер.
Простим ланцюгом називається маршрут без вершин, що повторюються
(звідки слідує, що в простому ланцюгу немає повторюваних ребер).
Орієнтованим маршрутом (або шляхом) в орграфі називають кінцеву
послідовність вершин і дуг, в якій кожен елемент інцидентний попередньому
та наступному.
Циклом називають ланцюг, у якому перша та остання вершини
збігаються. При цьому довжиною шляху (або циклу) називають число
складових його ребер. Слід зауважити, що якщо вершини u і v є кінцями
деякого ребра, то згідно з цим визначенням, послідовність (u,v,u) є циклом.
Щоб уникнути таких вироджених випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра у ньому не
повторюються; елементарним, якщо він простий і вершини в ньому не
повторюються (за винятком початкової та кінцевої у разі циклу).
Найпростіші властивості шляхів та циклів:
• кожен шлях, що з'єднує дві вершини, містить елементарний
шлях, що з'єднує ті самі дві вершини;
• кожен простий неелементарний шлях містить елементарний
цикл;
• всякий простий цикл, що проходить через деяку вершину (або
ребро), містить елементарний (під-)цикл, що проходить через ту саму
вершину (або ребро);
• петля – елементарний цикл.
28

Бінарне відношення на безлічі вершин графа, задане як «існує шлях з u
в v», є ставленням еквівалентності і, отже, розбиває цю безліч на класи
еквівалентності, які називають компонентами зв'язності графа. Якщо у графа
одна компонента зв'язності, то граф зв'язний. На компоненті зв'язності можна
запровадити поняття відстані між вершинами як мінімальну довжину шляху,
що з'єднує ці вершини.
Будь-який максимальний зв'язковий підграф графа G називається
зв'язковим компонентом (або просто компонентом) графа G. Слово
«максимальний» означає максимальний щодо включення, тобто не міститься
у зв'язному підграфі з великою кількістю елементів.
Ребро графа називається мостом, якщо його видалення збільшує
кількість компонентів.
Граф називається:
• зв'язаним, якщо для будь-яких вершин u, v є шлях з u до v.
• сильно зв'язаним чи орієнтовано зв'язковим, якщо він
орієнтований, і з будь-якої вершини в будь-яку іншу є орієнтований шлях.
• деревом, якщо він зв'язний і не містить нетривіальних циклів.
• повним, якщо будь-які дві (різні, якщо не допускаються петлі)
вершини з'єднані руба.
• дводольним, якщо його вершини можна розбити на два
непересічні підмножини V1 і V2 так, що всяке ребро з'єднує вершину з V1 з
вершиною з V2.
• k-дольним, якщо його вершини можна розбити на k непересічних
підмножин V1, V2, …, Vk отже не буде ребер, що з'єднують вершини однієї й
тієї ж підмножини.
• повним дводольним, якщо кожна вершина одного підмножини
з'єднана ребром з кожною вершиною іншого підмножини.
• планарним, якщо граф можна зобразити діаграмою на площині
без перетинів ребер.
29

• зваженим, якщо кожному ребру графа поставлено у відповідність
деяке число, яке називається вагою ребра.
• хордальним, якщо граф не містить індукованих циклів із
довжиною більше трьох.
Характеризуючи проблематику теорії графів, можна назвати, деякі
напрями носять більш комбінаторний характер, інші - більш геометричний.
До перших відносяться, наприклад, задачі про підрахунок та перерахування
графів з фіксованими властивостями, задачі про побудову графів із заданими
властивостями. Геометричний (топологічний) характер носять багато циклів
завдань теорії графів, наприклад, графів обходів, графів укладання. Існують
напрями, пов'язані з різними класифікаціями графів, наприклад, за
властивостями їхнього розкладання.
Теоретично у графів існують специфічні методи вирішення
екстремальних завдань. Один з них заснований на теоремі про максимальний
потік і мінімальний розріз, що стверджує, що максимальний потік, який
можна пропустити через мережу з вершини U до вершини V, дорівнює
мінімальній пропускній здатності розрізів, що розділяють вершини U і V.
Були побудовані різні ефективні алгоритми знаходження максимального
потоку.
Результати та методи теорії графів застосовуються при вирішенні
транспортних завдань про перевезення, для знаходження оптимальних
рішень задачі про призначення, для виділення "вузьких місць" при
плануванні та управлінні розробок проектів, при складанні оптимальних
маршрутів доставки вантажів, а також при моделюванні складних технологій,
процесів, у побудові різних дискретних пристроїв, у програмуванні тощо.
Можна сказати, що мережевим графом - графічне зображення
послідовності виконуваних операцій, що показує взаємозв'язок окремих
робіт, виконання яких забезпечує досягнення мети процесу. З ним пов'язані
три основні поняття: робота, подія, шлях.
30

Робота – будь-який процес чи дія, що супроводжується витратами часу
та ресурсів для її виконання. Як ресурси виступають: люди, кошти, тощо.
Ресурси можуть бути: однорідними та неоднорідними.
Робота на графі відображається спрямованою дугою .
До поняття роботи також входять: очікування – це робота, яка потребує
витрат ресурсів, але займає деякий час, і фіктивна робота, що вказує на
топологічну зв'язок між роботами, але не вимагає ні витрат часу ні ресурсів.
Подія – це результат виконання однієї або кількох робіт, що не вимагає
витрат часу та ресурсів (факт закінчення). Подія на графі позначається:
Ранній термін настання події – максимальна тривалість шляху, що веде
від вихідної події до цього. Тр(ij) = max{Тр(i) + tij}, де tij – тривалість роботи
між подіями
Пізній термін настання події – це термін пізніше якого подія наступити
не повинно. Інакше збільшується час усієї операції. Тп(i) = min{Тп(j) – tij}, де
Тп(j) – наступна подія.
Повний резерв роботи Rп = Тп(j) – Тр(i) – tij.
Шлях – будь-яка послідовність робіт, яка веде від однієї події до
іншого, в якій кінцева подія кожної безпосередньо попередньої роботи,
збігається з початковою подією безпосередньо наступної за нею роботи. На
графі позначаються:
Повний шлях – це шлях від вихідної події до завершальної.
Тривалість шляху - сума тривалості складових його робіт.
Критичний шлях - шлях найбільшої тривалості (найбільших витрат
ресурсів).

2.2. Cпособи використання графів у логістиці
Якщо розглядати логістику як задачу знаходження оптимального
переміщення, то з цього погляду – кожна людина протягом дня вирішкє такі
задачі
31

У своїй громадсько-практичній діяльності людина також щоденно
вирішує завдання логістики оптимального переміщення:
– вантажів;
– військ;
– готової продукції та комплектуючих у процесі її виробництва;
– пасажирів та багато іншого.
Логістика - як наука відома з часів Римської імперії, де: "Логіст" -
постачальник в армії.
В даний час - основне завдання логістики, це:
Лінійне транспортне завдання знаходження способів та шляхів
найбільш оптимальної та швидкої доставки вантажів, товарів, пасажирів
тощо. до пунктів призначення.
На початку 20 століття логістика, як наука, отримала в арсенал своїх
наукових засобів новий математичний апарат – теорію графів
Датою народження теорії графів прийнято вважати 1736 рік, коли
Леонард Ейлер сформулював перші теореми нової теорії, вирішуючи
завдання "Про кенігсберзьки мости", і написав про це в листі італійському
математику та інженеру Маріоні 13 березня 1736 р., чим і закріпив за собою
нову теорію.
Термін «граф» уперше ввів у математику угорський математик Денеш
Кеніг у 1936 році.
В даний час:
– у деяких галузях прикладної діяльності замість поняття "граф"
використовується термін "мережа": мережевий графік; мережа залізниць
тощо;
- замість терміна "вершина графа" при використанні "мережевої"
термінології використовується термін "мережевий вузол" або просто -
"вузол".
32

До початку 20-го століття теорія графів розвивалася переважно у
вигляді формулювання нових теорем, сформованих за результатами
розв'язання різних "головоломних завдань".
Серйозний розвиток теорія графів отримала у зв'язку з виникненням
масового великосерійного виробництва, загальним сплеском науки та
технологій у першій половині 20 століття.
Під час розробки схем маршрутів та їх оптимізації застосовують
математичний апарат теорії графів, тобто графоаналітичні методи. Головне
завдання при цьому полягає у побудові графу логістики.
Аналіз графів здійснюють за допомогою топологічних мір, які
показують множину зв'язків між елементами графу. Вирізняють такі міри:
- концентрації та диференціації, за якими оцінюють положення вершин
у графі (до них належать показники центральності та ієрархічності);
- інтеграції та композиції, що дають змогу оцінити граф у цілому
(показники цілісності та зв'язності).
Гамільтонів шлях – шлях через усі вершини графа найкоротшим
шляхом. Пошук такого замкнутого Гамільтонова шляху – це і є головне
завдання сучасної логістики.
Сьогодні теорія графів має досить розвинений специфічний апарат.
Методи теорії графів знаходять широке застосування в логістиці, зокрема, як
системи мережевого планування і управління. За допомогою мережевого
планування та управління досягається раціональне використання
матеріальних ресурсів, здійснюється надійне та ритмічне матеріально-
технічне забезпечення.
Суть завдань на побудову транспортної мережі може полягати,
наприклад, у знаходженні оптимального (у сенсі якогось показника) шляху з
початкового пункту до кінцевого, у побудові кільцевого маршруту
мінімальної протяжності тощо. У другому випадку шукається гамільтонів
цикл мінімальної довжини. Це пов'язано з тим, що доставка вантажу має
здійснитись у пункти призначення (споживачам) за один раз, із поверненням
33

до початкового пункту відправлення. При цьому треба мати на увазі, що
транспортна мережа враховує лише ті шляхи, якими можна організувати рух.
Тут враховуються такі фактори як обмеження руху за швидкістю, заборони
на рух вантажного транспорту, односторонній рух, обмеження на масу
транспортних засобів та інші параметри.

2.3. Теоретичні аспекти пошуків оптимальних шляхів за
допомогою графів
Побудова транспортної мережі починається із вибору вершин графа. У
товарних перевезеннях таку роль виконують логістичні центри, склади,
пункти знаходження виробника товарів. У цивільних перевезеннях таку роль
відіграють великі центри торгівлі, університети, інститути, спортивні центри
та інші місця з високою прохідністю. Усі вершини повинні бути пов'язані
орієнтованими дугами. Це означає, що граф, що вийшов, повинен бути
орієнтованим та пов'язаним (зв'язним). Якщо граф, що вийшов, не є
пов'язаним, то він може представляти транспортну мережу. Також виділяють
дві вершини – джерело (витік) та стік. Джерелом називають вершину, з якої
виходять дуги, стоком є вершина, куди входять дуги, тобто. будь-яка інша
вершина транспортної мережі лежить на шляху із джерела в стік
Оцінка (вага) кожного ребра мережі визначається залежно від мети
дослідження, мірою досягнення якої є певний критерій ефективності. Але в
основному як ваги вибирають час (критерій – мінімальний час), який буде
витрачено на рух, або відстань (критерій – мінімальна відстань). Дуги
(орієнтовані ребра) мають пропускну здатність і потоком. Пропускна
здатність дуги характеризує число одиниць транспорту, який може пройти за
одиницю часу. Потоком є спрямований рух транспорту через мережу,
причому потік по дузі не може перевищувати її пропускну спроможність.
Можна сказати, що пошук завдання про найкоротший шлях є одним із
найважливіших класичних завдань теорії графів.
34

Значимість цього завдання визначається її різними практичними
застосуваннями. Наприклад, у GPS-навігаторах здійснюється пошук
найкоротшого шляху між двома перехрестями. Як вершини виступають
перехрестя, а дороги є ребрами, які лежать між ними. Якщо сума довжин
доріг між перехрестями мінімальна, тоді знайдений шлях найкоротший.
Існують різні постановки задачі про найкоротший шлях:
• Завдання про найкоротший шлях до заданого пункту
призначення.
• Завдання про найкоротший шлях між заданою парою вершин.
• Завдання про найкоротший шлях між усіма парами вершин.
Найбільш відомим алгоритмом, що вирішує це завдання, є алгоритм
Дейкстри.
Алгоритм Дейкстри - алгоритм на графах, винайдений нідерландським
ученим Едсгер Дейкстрой в 1959 році. Знаходить найкоротші шляхи від
однієї з вершин графа до решти. Алгоритм працює лише для графів без ребер
негативної ваги. Алгоритм широко застосовується у програмуванні та
технологіях.
Розглянемо виконання алгоритму з прикладу графа, показаного
рисунку 2.1.
Нехай потрібно знайти найкоротші відстані від 1-ї вершини до решти.
Кружками позначені вершини, лініями – шляхи між ними (ребра
графа).
У кружках позначено номери вершин, над ребрами позначено їхню
вагу — довжину шляху.
Поруч із кожною вершиною червоним позначено мітку — довжину
найкоротшого шляху до цієї вершини з вершини 1.

35

Рис. 2.1. Приклад графу

Спочатку позначаємо знаком нескінченність (чи дуже великим
недосяжним числом, наприклад, у прикладі -1000) відстань від вершини 1 до
інших вершин (рис. 2.2). Вершина має 1 довжину шляху 0.

Рис. 2.2. Приклад розрахунку
36

Перший крок
Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 та 6 (рис.
2.3).
При цьому слід звернути увагу, що на кожному кроці слід обирати
вершину з мінімальним значенням мітки, тому що шлях до цієї вершини з
вершини А мінімальний (тому і мітка, що відображає відстань до цієї
вершини мінімальна). І з цієї вершини будуємо відстань до решти
"невідвіданих" вершин.

Рис. 2.3. Перший крок розрахунку

Надамо значення міткам вершин, суміжних з 1.
Довжина шляху від 1 до 2 вершини = 0 +7 = 7, це менше 1000 тому
мітка вершини 2 дорівнює 7.
Аналогічну операцію проробляємо з двома іншими сусідами 1-ї
вершини - 3-ї та 6-ї.
Усі сусіди вершини 1 перевірені.
Викреслимо її з графа, щоб відзначити, що ця вершина відвідана (такі
вершини помічатимемо коричневим кольором, зараз це вершина 1).
37

Відвідана вершина - це вершина, мінімальна відстань до якої
обчислено та не підлягає зміні. У який момент вершина стає "відвіданою",
описано в алгоритмі.

Другий крок.
Невідвідана вершина з мінімальною вагою – це вершина 2, її вага
дорівнює 7 (рис. 2.4). Розглянемо мінімальну відстань від неї до суміжних із
нею вершин.

Рис. 2.4. Другий крок

Знову намагаємося зменшити мітки сусідів обраної вершини,
намагаючись пройти в них через 2 вершину. Сусідами вершини 2 є вершини
1, 3 та 4.
Вершина 1 вже відвідана, тому з першою вершиною нічого не робимо.
Вершина 3, якщо йти в неї через 2, то довжина такого шляху
дорівнюватиме 17 (7 + 10 = 17). Але поточна мітка третьої вершини дорівнює
9, а це менше 17, тому мітка не змінюється.
Ще один сусід вершини 2 – вершина 4.
38

Якщо йти в неї через 2-у, то довжина такого шляху дорівнюватиме сумі
найкоротшої відстані до 2-ї вершини і відстані між вершинами 2 і 4, тобто 22
(7 + 15 = 22). 22<1000, мітка вершини приймає значення мінімального шляху
до неї і це значення 22.
Усі сусіди вершини 2 переглянуті, помічаємо її як відвідану.

Третій крок.
Повторюємо крок алгоритму, обравши вершину з мінімальною вагою –
це вершина 3. Після її «обробки» отримаємо такі результати для суміжних із
нею вершин 4 та 6 (рис. 2.5).

Рис. 2.5. Третій крок

Четвертий крок
Повторюємо крок алгоритму, обравши вершину з мінімальною вагою –
це вершина 6. Після її «обробки» отримаємо такі результати для суміжної з
нею невідвіданої вершини 6 (рис. 2.6).
39

Рис. 2.6. Четвертий крок

П’ятий крок
Вершини 5 і 4, що залишилися, мають однакові мітки, рівні 20.
Виберемо для аналізу вершину 20. Після її «обробки» отримаємо такі
результати для суміжної з нею невідвіданої вершиною 4 (рис. 2.7).

Рис. 3.7. П'ятий крок
40

Шостий крок
Алгоритм закінчує роботу, коли відвідані всі вершини (рис. 3.8).

Рис. 3.8. Шостий крок

Результат роботи алгоритму видно на останньому малюнку:
найкоротший шлях від вершини 1 до 2-ї становить 7, до 3-ї - 9, до 4-ї - 20, до
5-ї - 20, до 6-ї - 11.
Алгоритм може бути завершений достроково, якщо граф незв'язний,
відповідно до ізольованих вершин не можна порахувати шлях.

41

РОЗДІЛ 3. РОЗРОБКА МОДЕЛІ СИСТЕМИ ДЛЯ АВТОМАТИЧНОЇ
ПОБУДОВИ ОПТИМАЛЬНИХ ЛОГІСТИЧНИХ МАРШРУТІВ

3.1. Опис функціональних можливостей ПЗ для побудови моделі
системи
Транспортна задача задається наступною таблицею, яка зображена на
рис. 3.1

Рис. 3.1. Транспортна задача

Розглянемо постановку транспортного завдання, тобто. що дано за
умови і перекладемо її з математичної мови на мову, зрозумілу нам.
На рис. 3.2 виділено "склади" - пункти відправлення: два склади з
товаром: А1 та А2

Рис. 3.2. «Склади»

На рис. 3.3. виділено обсяг товару - кількість вантажу, відповідно на
складах А1 та А2:

42

Рис. 3.3. Обсяг товару

Далі маємо справу з пунктами призначення – з "магазинами" (рис. 3.4).
У нашому випадку їх 4 штуки: В1, В2, В3 та В4.

Рис. 3.4. Пункти призначення

І відповідно потреби кожного з магазинів – потреби пунктів
призначення (рис. 4.5).

Рис. 3.5. Потреби

Числа всередині таблиці - матриця цін, або інакше, ціни перевезення 1
одиниці вантажу з відповідних пунктів. Ці значення також можуть
інтерпретуватись як відстані між відповідними пунктами. Подробиці — за
умови вирішуваного завдання (рис. 3.6).

43

Рис. 3.6. Подробиці

Наприклад, для перевезення 1 одиниці вантажу з пункту відправлення
("складу") А2 до пункту призначення ("магазин") В3 треба заплатити 4
умовні одиниці вартості, наприклад 4 дол (рис. 3.7).

Рис. 3.7 Приклад 1

Аналогічно, ми заплатимо 6 доларів за перевезення 1 одиниці вантажу
зі "складу" А1 до "магазину" В4 (рис. 3.8).

Рис. 3.8. Приклад 2

Або те саме завдання може бути задане відразу в більш зрозумілому
вигляді (табл. 3.1).

44

Таблиця 3.1
Опис завдання
Пункти Пункт призначення
відправлення В1 В2 В3 В4 Запас
А1 4 3 5 6 100
А2 8 2 4 7 200
Потреби 50

1 4 3 5 6 100 50 100 75 75
2 8 2 4 7 200

В кваліфікаційній роботі використовується метод мінімальних
вартостей отримання опорного плану.
Суть методу полягає в тому, щоб насамперед спрямовувати вантаж у ті
пункти, де "розцінки" в матриці цін мінімальні. Якщо клітин із найменшими
тарифами кілька, то заповнюється кожна з них (рис. 3.9).

Рис. 3.9. Визначення найменшої розцінки

Надсилаємо 100 одиниць вантажу зі складу А2 до магазину В2.
Залишки на складі А2 - 100 одиниць. Потреби магазину В2 виконані
(рис. 3.10).

Пункт
відправл
ення
Пункт
признач
ення В1
Пункт
признач
ення В2
Пункт
признач
ення В3
Пункт
признач
ення В4
Запас
Потреби
В1
Потреби
В2
Потреби
В3
Потреби
В4
45

Рис. 3.10 Виконання потреб магазину В2

Вантаж зі складу А2 відправимо в магазин, у якого вартість
перевезення нижче - магазин В3, так як хв (4; 7) = 4
Розмір постачання дорівнює потреби магазину - 75. Залишки зі складу
200-100-75 = 25 перенесемо в магазин В4 (рис. 3.11).

Рис. 3.11. Розкидання вантажу зі складу А2

Залишається тільки розкидати вантаж зі складу А1 по магазинах: В1 -
50 одиниць, В4 - 75-25 = 50 одиниць (рис. 3.12).

Рис. 3.12. Розкидання вантажу зі складу А1

Отримали два опорні плани: методом північно-західного кута та
методом мінімальних вартостей.
Перший опорний план (за методом північно-західного кута) (рис. 3.13).
46

Рис. 3.13. Перший опорний план

Другий опорний план (за методом мінімальних цін) (рис. 3.14).

Рис. 3.14. Другий опорний план

3.2. Аналіз існуючих систем для побудови системи автоматичної
побудови оптимальних логістичних маршрутів
Найбільш простими системами для побудови системи для автоматичної
побудови оптимальних логістичних маршрутів є Microsoft Office та Microsoft
Excel та Microsoft Access (рис. 3.15).
Також для візуального представлення у якості графа можна
використовувати програму Gephi – потужний опенсорсний інструмент,
здатний обробляти графи з сотнями тисяч вершин та зв'язків. Завантажити
його можна із офіційного сайту (рис. 3.16).
47

Рис. 3.15. Приклад побудови оптимальних логістичних маршрутів

Рис. 3.16. Інтерфейс системи Gephi

48

В результаті використання системи Gephi граф буде приблизно в
такому вигляді, який представлено на рис. 3.17.

Рис. 3.17. Результат роботи системи Gephi

Одним з досить поширених рішень для дозволів завдань теорії графів у
логістиці та побудови транспортних мереж є система комп'ютерної
математики Maple. Система Maple віддає перевагу використанню алгоритму
Дейкстри.
Maple – програмний пакет, система комп'ютерної алгебри (точніше,
система комп'ютерної математики). Є продуктом фірми Waterloo Maple Inc.,
яка з 1984 року випускає програмні продукти, орієнтовані на складні
математичні обчислення, візуалізацію даних та моделювання. Система Maple
призначена для символьних обчислень, хоча має низку коштів для
чисельного розв'язання диференціальних рівнянь і знаходження інтегралів.
Має розвинені графічні засоби. Має власний інтерпретований мову
програмування, що синтаксисом частково нагадує Паскаль.
49

Компанія Maple займається програмним забезпеченням та послугами
на основі математики для освіти, інженерії та досліджень.
Ще однією системою для побудови графів є Графоаналізатор –
середовище для візуалізації графів та обробки із застосуванням різних
алгоритмів, всього близько 20 різних алгоритмів. Програма нагладяно
зобразить результат алгоритму, за допомогою програми можна вирішити
безліч прикладних задач детальніше про програму Графоаналізатор.
Основні особливості:
1. 20 алгоритмів обробки графа.
2. Можливість візуального всього процесу роботи з графом.
3. Підтримка допоміжних функцій за створеною графою по карті.
4. Довідка містить опис основних завдань, що вирішуються за
допомогою програмного продукту.
5. Детальна довідка, підтримка та зворотний зв'язок з автором.

3.3. Опис алгоритму створення ПЗ для побудови оптимальних
логістичних маршрутів
Створення ПЗ для побудови системи для автоматичної побудови
оптимальних логістичних маршрутів починається зі створення бази даних в
Microsoft Access. Для цього слід
1. Відкрити Access.
Якщо програма Access вже відкрита, на вкладці Файл вибрати
Створити.
Вибрати пусту базу даних або шаблон.
Ввести ім'я бази даних, обрати розташування, а потім натиснути
кнопку Створити.
Коли база даних відкриється, натиснути кнопку Увімкнути вміст на
жовтій панелі повідомлень.
Таблиці є основою бази даних, оскільки у них зберігаються дані. У
кожній таблиці міститься інформація з будь-якої теми.
50

Перша таблиця у новій базі даних робочого стола за умовчанням має
имя Таблица1. Це ім'я бажано змінити на більш зрозуміле.
На панелі швидкого доступу слід обрати Зберегти
У полі Ім'я таблиці ввести ім'я опису.
При необхідності також можна додати додаткові таблиці до бази даних,
навіть якщо вона була створена на основі шаблону.
На вкладці Створення слід натиснути кнопку Таблиця.
Access додасть нову таблицю з ім'ям Таблиця<#>, де <#> буде
наступним постійним, невикористаним числом.
Для додавання поля шляхом введення даних у режимі таблиці слід
ввести дані у стовпці Клацніть, щоб додати. Access створить нове поле (рис.
3.18).

Рис. 3.18. Створення нового поля

У заголовку стовпця ввести нове ім'я поля (рис. 3.19).

Рис. 3.19. Введення ім’я
51

Якщо поле в Access додається шляхом введення даних до нього, тип
даних поля встановлюється відповідно до вмісту. Тип даних можна побачити
на вкладці Поля у полі Тип даних (рис. 3.20).

Рис. 3.20. Вибір типу даних

Щоб змінити тип даних, виконайте наведені нижче дії.
Виберіть поле.
На вкладці "Поля" відкрийте список Тип даних та виберіть тип даних
Головною перевагою реляційних баз даних полягає у можливості
використовувати інформацію з різних таблиць. Для цього спочатку потрібно
створити між ними зв'язки. Після цього ви зможете об'єднувати ці дані у
запитах, формах та звітах.
Лінії у поданні "Відносини" вказують на зв'язок між таблицями. На
малюнку нижче таблиця ліворуч є батьківською. Таблиця праворуч є
дитячою. Лінія між ними з'єднує поля, що використовуються для збігу даних.
По лініях та символах можна визначити параметри зв'язку (рис. 3.21).
Товста сполучна лінія означає, що включено забезпечення цілісності
даних. Це добре. Дані синхронізуватимуться.
На наведеному зображенні цифра 1 означає, що в таблиці зліва може
бути лише один зв'язаний запис. У таблиці "Замовлення" кожному
замовленню може відповідати лише один запис.
52

Рис. 3.21. Приклад зв’язку

Піктограма "∞" означає, що в декількох записах може бути вказаний
однаковий номер або код. Замовлення з таблиці ліворуч, яке визначається
номером замовлення, може бути вказано в таблиці "Відомості про
замовлення" кілька разів, оскільки в одному замовленні може бути кілька
продуктів.
Між таблицями можуть бути встановлені зв'язки трьох видів:
• Один до одного. Кожен елемент використовується у кожній
таблиці лише один раз. Наприклад, кожен співробітник може
використовувати лише один службовий автомобіль. Для отримання
додаткових відомостей див. статтю Створення зв'язків типу один до одного
• Один-багатьом. Для одного елемента з першої таблиці можна
створити зв'язок із декількома елементами з другої таблиці. Наприклад, у
кожній накладній може бути зазначено кілька продуктів
• Багато хто до багатьох. Для одного або декількох елементів з
першої таблиці можна створити зв'язок з одним або кількома елементами
53

другого таблиці. Наприклад, кожне замовлення може входити кілька
продуктів, і кожен продукт може бути вказаний у кількох замовленнях.
Щоб змінити зв'язок потрібним чином необхідно
Обрати Використання баз даних > Схема даних.
Обрати лінію, яка з'єднує дві зв'язані таблиці.
На вкладці Конструктор натиснути кнопку Змінити зв'язки (рис. 3.22).

Рис. 3.22. Зміна звязків

3.4. Огляд цілей інтеграції дизайну інтерфейсу у логістичні системи
У сучасному світі логістика є критично важливою для ефективності
бізнесу. Центральним елементом логістичних систем є їхні інтерфейси, які
забезпечують взаємодію користувача зі складними даними та процесами.
Інтеграція вдумливо спроектованого інтерфейсу є ключовою для
забезпечення інтуїтивно зрозумілої, ефективної та безпечної взаємодії
користувачів з системою. Цей розділ має на меті дослідити, як дизайн
інтерфейсу може бути оптимізований для підвищення продуктивності
логістичних операцій, забезпечуючи при цьому легкість використання та
гнучкість.
54

Значущість інтеграції ефективного дизайну інтерфейсу в логістичні
системи полягає не лише у покращенні візуального сприйняття, але й у
забезпеченні чіткості, точності та швидкості обробки інформації. Це
особливо важливо у логістиці, де рішення часто приймаються на основі
складних даних та аналітики. Ефективний інтерфейс дозволяє користувачам
легко інтерпретувати ці дані, сприяючи кращому прийняттю рішень та
плануванню маршрутів. Отже, мета цього розділу – вивчити, як дизайн
інтерфейсу може бути інтегрований у логістичні системи таким чином, щоб
він відповідав як функціональним, так і естетичним вимогам, підвищуючи
загальну ефективність та зручність використання системи.

3.5. Основні принципи дизайну інтерфейсу
У цій частині розглядаються ключові принципи дизайну інтерфейсу,
які є важливими для створення ефективних логістичних систем. До таких
принципів належать:
Ясність та простота: Інтерфейс повинен бути інтуїтивно зрозумілим, з
мінімальною кількістю відволікаючих елементів, щоб користувачі могли
легко знаходити необхідну інформацію.
• Консистентність: Елементи дизайну повинні бути послідовними
по всій системі для забезпечення звичного і зручного досвіду користувача.
• Відгук та зворотний зв'язок: Інтерфейс повинен надавати
відповідні сигнали та відгуки на дії користувача, щоб вони могли розуміти
наслідки своїх дій у системі.
• Доступність та універсальність: Інтерфейс має бути доступним
для людей з різними здібностями та зручним для різних категорій
користувачів.
• Ефективність використання: Інтерфейс повинен сприяти
швидкому та ефективному виконанню завдань. Ці принципи допомагають
забезпечити, що дизайн інтерфейсу сприяє підвищенню продуктивності та
зниженню помилок у логістичних процесах.
55

• Гнучкість та ефективність для досвідчених користувачів: Дизайн
інтерфейсу має задовольняти потреби як новачків, так і досвідчених
користувачів, надаючи додаткові функції та швидкісні команди для
підвищення продуктивності досвідчених користувачів.
• Естетичний та мінімалістичний дизайн: Забезпечення візуально
привабливого та не перевантаженого зайвими деталями інтерфейсу сприяє
зручності використання та зменшує когнітивне навантаження на
користувача.
• Врахування контексту використання: Дизайн інтерфейсу має
бути адаптованим до різних умов використання, включаючи різні пристрої та
умови середовища. Застосування цих принципів дозволяє створити дизайн
інтерфейсу, який не лише виглядає добре, але й функціонально відповідає
потребам користувачів у логістичних системах.
Як приклади ефективно імплементованих дизайнів інтерфейсу можна
розглянути:
• Google Maps: Простий та інтуїтивний інтерфейс, який надає
користувачам потужні інструменти для планування маршрутів та навігації.
• Salesforce CRM: Інтерфейс Salesforce забезпечує зручний доступ
до складних даних та аналітики, забезпечуючи високу ефективність
управління відносинами з клієнтами.
• Slack: Цей інструмент для командної роботи вирізняється своїм
чітким та ефективним інтерфейсом, що сприяє легкій комунікації та обміну
файлами.
Ці приклади демонструють, як правильно розроблений інтерфейс може
покращити взаємодію з користувачем, підвищуючи продуктивність та
задоволення від роботи з системою.

56

3.6. Інтеграція дизайну інтерфейсу в контексті логістики
Інтеграція дизайну інтерфейсу в контексті логістики включає
створення систем, які ефективно відображають та управляють логістичними
даними. Це вимагає розробки інтерфейсів, які:
• Оптимізують Візуалізацію Даних: Інтерфейси мають ефективно
відображати складні логістичні дані, такі як маршрути, запаси, та час
доставки.
• Підтримують Багаторівневу Взаємодію: Дозволяють користувачам
легко переходити між різними рівнями деталізації, від загального огляду до
детального аналізу конкретних операцій.
• Інтегрують Автоматизацію та Рішення Штучного Інтелекту:
Включають інтелектуальні функції, такі як прогнозування та оптимізація
маршрутів, для підвищення ефективності логістичних процесів.
Інтеграція дизайну інтерфейсу в контексті логістики включає
створення систем, які ефективно відображають та управляють логістичними
даними. Це вимагає розробки інтерфейсів, які:
• Оптимізують Візуалізацію Даних: Інтерфейси мають ефективно
відображати складні логістичні дані, такі як маршрути, запаси, та час
доставки.
• Підтримують Багаторівневу Взаємодію: Дозволяють
користувачам легко переходити між різними рівнями деталізації, від
загального огляду до детального аналізу конкретних операцій.
• Інтегрують Автоматизацію та Рішення Штучного Інтелекту:
Включають інтелектуальні функції, такі як прогнозування та оптимізація
маршрутів, для підвищення ефективності логістичних процесів.
Така інтеграція вимагає глибокого розуміння як логістичних процесів,
так і принципів дизайну інтерфейсу, щоб створити системи, які є одночасно
потужними, інтуїтивно зрозумілими та легкими у використанні.
При інтеграції дизайну інтерфейсу у логістичні системи можуть
виникнути такі проблеми:
57

• Складність Візуалізації Даних: Важко збалансувати між
детальністю інформації та її зрозумілістю, особливо при великих обсягах
даних.
• Відсутність Стандартизації: Різноманітність даних і процесів у
логістиці ускладнює створення універсального інтерфейсу.
• Складність Інтеграції з Існуючими Системами: Злиття нових
інтерфейсів з існуючими IT-системами може бути технічно складним.
• Користувацьке Прийняття: Зміни в інтерфейсі можуть викликати
опір з боку користувачів, звиклих до старих систем.
• Технічні Обмеження: Обмеження апаратного забезпечення та
програмного середовища можуть обмежувати можливості дизайну. Ці
проблеми вимагають глибокого розуміння як логістичних процесів, так і
принципів дизайну інтерфейсу для ефективного рішення.
При розгляді теми інтеграції дизайну інтерфейсу в логістичні системи,
важливо також враховувати:
• Безперервне Тестування та Оптимізація: Регулярне тестування
інтерфейсу з участю кінцевих користувачів допомагає виявляти та
виправляти проблеми.
• Адаптивність до Змін у Технологіях та Бізнес-Процесах:
Інтерфейси повинні бути гнучкими, щоб адаптуватися до нововведень у
технологіях та змін у бізнес-операціях.
• Охорона Персональних Даних та Кібербезпека: Потрібно
забезпечити високий рівень безпеки даних, особливо в умовах зростаючих
кіберзагроз. Ці аспекти допомагають забезпечити, що інтеграція дизайну
інтерфейсу буде не тільки ефективною, але й безпечною та відповідною до
поточних викликів бізнесу та технологій.

58

3.7. Висновок, щодо теоретичної імплементації інтерактивного
інтерфейсу
У висновках цього розділу можна підкреслити, що інтеграція дизайну
інтерфейсу в логістичні системи є ключовим елементом для підвищення
ефективності та зручності використання. Важливість збалансування
функціональності, доступності та естетики інтерфейсу, а також адаптації до
змінних умов та потреб користувачів, була підкреслена. Далі, у наступному
розділі буде зосереджено увагу на практичному аспекті - розробці та
імплементації інтерактивного інтерфейсу, який відповідатиме виявленим
потребам та викликам.

59

РОЗДІЛ 4. РОЗРОБКА ІНТЕРАКТИВНОГО ІНТЕРФЕЙСУ ДЛЯ
ЕФЕКТИВНОГО УПРАВЛІННЯ ЛОГІСТИЧНИМИ МАРШРУТАМИ

4.1. Аналіз потреб і вимог користувачів до інтерфейсу
У розробці інтерактивного інтерфейсу для ефективного управління
логістичними маршрутами ключовим є зосередження на розумінні та аналізі
користувацьких потреб. Це означає ідентифікацію ключових функцій, які
необхідні для забезпечення гладкого та ефективного процесу логістики, а
також врахування специфічних вимог користувачів, що можуть включати
інтуїтивність використання, швидкість обробки даних та здатність легко
адаптуватися до змінних умов.
Аналіз потреб користувачів також охоплює вивчення їхніх робочих
процесів, умов використання системи та вимог до інформаційної безпеки.
Важливо визначити, як користувачі взаємодіють з даними, які помилки вони
найчастіше роблять, і які функції можуть їх мінімізувати. Це дозволить
розробити інтерфейс, який буде не тільки функціональним і ефективним, але
й зручним та безпечним для кінцевих користувачів.

4.2. Розробка основної концепції інтерфейсу з урахуванням
функціональності та дизайну
Після аналізу потреб користувачів, наступний крок - розробка
концептуального дизайну інтерфейсу. Цей процес включатиме вибір
оптимального способу візуалізації даних, розробку навігаційної схеми, та
інтеграцію ключових функцій для забезпечення плавної взаємодії
користувача з системою. Важливо також врахувати адаптивність інтерфейсу
під різні пристрої та умови використання.
Під час концептуального проектування інтерфейсу, я також звертав
увагу на ергономічність та естетику. Це означало вибір кольорів, шрифтів та
розташування елементів, щоб вони були зрозумілими та приємними для
користувача. Я приділив значну увагу забезпеченню, щоб інтерфейс був не
60

лише функціональним, але й мав привабливий вигляд. Важливим аспектом
було також створення логічної структури даних, щоб користувачі могли
легко отримувати необхідну інформацію.
При розробці концептуального дизайну інтерфейсу для логістичних
систем, деталізація включає такі елементи:
Вибір Візуалізації Даних: Визначення найбільш ефективних способів
візуального представлення логістичних даних, таких як картографічні
зображення, графіки та інтерактивні діаграми.
• Навігаційна Схема: Розробка інтуїтивно зрозумілої навігаційної
структури, що сприяє легкому доступу до всіх необхідних функцій
та інформації.
• Інтеграція Функцій: Включення важливих функціональних
можливостей, таких як пошук маршрутів, управління ресурсами та
аналітика.
• Адаптивність: Забезпечення гнучкості інтерфейсу для адаптації під
різні пристрої та умови використання, включаючи мобільні та
настільні пристрої. Цей етап є важливим для створення зручного,
ефективного та візуально привабливого інтерфейсу, який відповідає
конкретним вимогам логістичної сфери.

4.3. Деталізація технічних аспектів розробки, включно з
технологіями та платформами
Для розробки інтерактивного інтерфейсу для управління логістичними
маршрутами я обрав такий технологічний стек:
1. Frontend (Клієнтська Частина):
o HTML5: Для структури веб-сторінок.
o CSS3 і Bootstrap: Для стилізації та адаптивного дизайну, що
забезпечує коректне відображення на різних пристроях.
61

o JavaScript (JS): Для динамічної взаємодії на клієнтській стороні. JS
також може використовуватися для асинхронних запитів до сервера
через AJAX.
o React.js або Vue.js: Ці сучасні JavaScript фреймворки зазвичай
використовуються для побудови більш інтерактивних UI елементів,
що сприяє підвищенню продуктивності та поліпшенню
користувацького досвіду.
2. Додаткові Інструменти та Технології:
o Git для контролю версій: Забезпечує ефективне управління кодом та
співпрацю між розробниками.
o Browser-sync для бандлінгу: Оптимізація та упаковка ресурсів та
асетів для швидшого завантаження веб-сторінки.
Результатом цього підходу є гнучкий, адаптивний інтерфейс, що
дозволяє користувачам ефективно керувати логістичними процесами. Він
забезпечує зручну навігацію, чітку візуалізацію даних та швидкий доступ до
необхідних функцій, сприяючи зниженню часу на виконання задач та
підвищенню загальної продуктивності.

HTML код програми має вигляд:

<!DOCTYPE html>
<html>

<head>
<title>Логістичний Планувальник Маршрутів</title>
<link href="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.css"
rel="stylesheet" type="text/css" />
<link rel="stylesheet"
href="https://fonts.googleapis.com/icon?family=Material+Icons">
<link rel="stylesheet"
62

href="https://cdn.jsdelivr.net/npm/material-components-
web@latest/dist/material-components-web.min.css">
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.js"></script>
<link rel="stylesheet"
href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css">
<meta name="viewport" content="width=device-width, initial-scale=1">
<style>
body,
html {
height: 100%;
margin: 0;
padding: 0;
position: relative;
}

#graph {
position: absolute;
z-index: -1;
top: 0;
left: 0;
width: 100vw;
height: 100vh;
}

.container {
width: 100%;
margin: 0 0;
text-align: center;
position: relative;
z-index: 1;
63

}

.mdc-text-field {
margin: 10px;
}

body {
font-family: Arial, sans-serif;
background-color: #f4f4f4;
margin: 0;
padding: 0;
}

#plan-route {
display: inline-block;
padding: 10px 20px;
margin: 20px;
font-size: 18px;
color: #fff;
background-color: #007BFF;
border: none;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
cursor: pointer;
transition: background-color 0.3s ease;
}

#plan-route:hover {
background-color: #0056b3;
64

}

@media (max-width: 768px) {
#plan-route {
font-size: 16px;
padding: 10px;
margin: 10px;
}
}

#sidebar {
display: flex;
flex-direction: column;
justify-content: center;
align-items: center;
padding: 20px;
border-right: 1px solid #dee2e6;
backdrop-filter: blur(5px);
background-color: rgba(255, 255, 255, 0) !important;
}

@media (min-width: 769px) {
#sidebar {
position: fixed;
top: 0;
left: 0;
height: 100vh;
width: 300px;
}
}

65

@media (max-width: 768px) {
#sidebar {
position: fixed;
bottom: 0;
left: 0;
width: 100%;
height: auto;
}
}
</style>
</head>

<body>
<div class="container">
<div id="sidebar" class="d-flex flex-column justify-content-center align-items-
center p-3 bg-light">
<h1 class="mdc-typography--headline4 text-center mb-4">Логістичний
Планувальник Маршрутів</h1>
<div class="custom-file mb-3">
<input type="file" class="custom-file-input" id="file-input" accept=".csv">
<label class="custom-file-label" for="file-input">Оберіть файл</label>
</div>
<input type="text" value="Ternopil" id="start-point" class="form-control mb-
3"
placeholder="Початкова точка">
<input type="text" value="Kherson" id="end-point" class="form-control mb-3"
placeholder="Кінцева точка">
<button id="plan-route" class="btn btn-primary">Планувати
маршрут</button>

66

</div>
<div id="graph"></div>
</div>

window.onload = function () {
fetch('graph.csv')
.then(response => response.text())
.then(data => {
csvData = data;
graphData = createGraphFromCSV(data);
createGraphVisualization(graphData);
});
};

document.getElementById('file-input').addEventListener('change', function (event)
{
const file = event.target.files[0];
if (!file) {
return;
}

67

const reader = new FileReader();
reader.onload = function (event) {
csvData = event.target.result;
graphData = createGraphFromCSV(csvData);
createGraphVisualization(graphData);
};

reader.readAsText(file);
});

function createGraphFromCSV(csvData) {
nodes = new vis.DataSet();
edges = new vis.DataSet();
const nodeSet = new Set();
const lines = csvData.split('\n');

lines.forEach((line) => {
const [source, target, weight] = line.split(',');
if (!nodeSet.has(source)) {
nodes.add({ id: source, label: source });
nodeSet.add(source);
}
if (!nodeSet.has(target)) {
nodes.add({ id: target, label: target });
nodeSet.add(target);
}
edges.add({ id: `${source}-${target}`, from: source, to: target, label:
weight });
});

68

return { nodes, edges };
}

// Алгоритм Дейкстри
function findShortestPath(graph, start, end) {
let shortestDistances = {};
let parents = {};
let unvisitedNodes = Object.keys(graph);

for (let node of unvisitedNodes) {
shortestDistances[node] = Infinity;
}
69

shortestDistances[start] = 0;

while (unvisitedNodes.length > 0) {
let closestNode = null;

for (let node of unvisitedNodes) {
if (closestNode === null || shortestDistances[node] <
shortestDistances[closestNode]) {
closestNode = node;
}
}

let currentNodeDist = shortestDistances[closestNode];
for (let neighbor in graph[closestNode]) {
let distanceToNeighbor = graph[closestNode][neighbor];
let totalDistance = currentNodeDist + distanceToNeighbor;

if (totalDistance < shortestDistances[neighbor]) {
shortestDistances[neighbor] = totalDistance;
parents[neighbor] = closestNode;
}
}

unvisitedNodes = unvisitedNodes.filter(node => node !== closestNode);
}

let shortestPath = [end];
70

let parent = parents[end];
while (parent) {
shortestPath.push(parent);
parent = parents[parent];
}
shortestPath.reverse();
return {
distance: shortestDistances[end],
path: shortestPath
};
}

function csvToGraph(csvData) {
let graph = {};
for (let row of csvData) {
let [pointA, pointB, distance] = row.split(',');
distance = Number(distance);

if (!graph[pointA]) {
graph[pointA] = {};
}
graph[pointA][pointB] = distance;

if (!graph[pointB]) {
graph[pointB] = {};
}
graph[pointB][pointA] = distance;
}
return graph;
}
71

document.getElementById('plan-route').addEventListener('click', function () {
let start = document.getElementById('start-point').value;
let end = document.getElementById('end-point').value;

let graph = csvToGraph(csvData.split('\n'));

let result = findShortestPath(graph, start, end);
highlightPath(result.path);
});
</script>
</body>

</html>

72

На рис. 4.1 представлено приклад роботи розробленої системи.

Рис. 4.1. Вигляд браузера персонального комп’ютера з запущеною
програмою

На рис. 4.2 представлено приклад роботи розробленої системи
запущеної на мобільному пристрої.
73

Рис. 4.2. Вигляд браузера системи на смартфоні
74

У процесі розробки інтерактивного інтерфейсу для логістичних систем
я зіткнувся з рядом технічних та дизайнерських викликів. Першим завданням
було ефективно імпортувати та обробити дані з CSV файлів, що вимагало
точного парсингу та обробки рядків. Другим викликом стала візуалізація
даних у вигляді графу з використанням бібліотеки vis.js. Цей процес включав
кастомізацію вигляду та поведінки вузлів і ребер для досягнення бажаного
візуального стилю.
Значні складнощі виникли також при реалізації алгоритму пошуку
найкоротшого шляху, де допускалися помилки в логіці, призводячи до
невірних результатів або зайвої складності обчислень. Іншою проблемою
була адаптація інтерфейсу під різні пристрої та роздільні здатності екрану,
що вимагало гнучкості та ретельного планування дизайну.
Адаптивність також була доволі складним моментом: забезпечення
коректного відображення інтерфейсу на різних пристроях та екранах було
складно. Інша проблема - інтуїтивність взаємодії користувача з системою, де
було важливо створити чітку та зручну навігацію. Останнім важливим
аспектом була оптимізація продуктивності, особливо при обробці великих
даних, для забезпечення швидкої та стабільної роботи інтерфейсу.

4.4. Підсумки роботи та напрямки для подальших досліджень та
розвитку
У висновках цього проекту можна підкреслити декілька ключових
аспектів та рекомендацій для подальшого розвитку системи та напрямків
майбутніх досліджень.
По-перше, проект дозволив розробити і успішно імплементувати
інтерактивний інтерфейс для управління логістичними маршрутами. Цей
інтерфейс став ефективним інструментом для планування та моніторингу
маршрутів, що поліпшило продуктивність логістичних процесів. Завдяки
його впровадженню, компанія зазнала зниження часу на виконання завдань
та оптимізації витрат.
75

До важливих аспектів інтерфейсу належать адаптивність до різних
типів пристроїв та інтуїтивна взаємодія. Проте завданням на майбутнє є
постійне вдосконалення інтерфейсу для ще більшої зручності користувачів та
більшої кількості функцій, що можуть сприяти легкості використання.
Поряд із зазначеними досягненнями, є декілька напрямків для
майбутніх досліджень та розвитку цієї системи. По-перше, можна розглядати
можливість інтеграції системи зі сторонніми сервісами та API для отримання
додаткових даних та функцій. Це може розширити можливості системи та
підвищити її функціональність.
Додатковою перспективою є розвиток алгоритмів планування
маршрутів та оптимізації, щоб забезпечити ще більшу точність та швидкість
визначення найкращих маршрутів. Також важливо проводити постійний
моніторинг і аналіз використання системи користувачами для ідентифікації
можливих покращень та оптимізації.
Також у висновках можна додати, що інтерактивний інтерфейс для
управління логістичними маршрутами є ефективним інструментом, який
сприяє оптимізації логістичних процесів. Постійний розвиток та
вдосконалення системи є ключовим завданням для забезпечення високої
ефективності та задоволення потреб користувачів.

76

ВИСНОВКИ

Основною метою кваліфікаційної роботи магістра бела розробка та
дослідження систем автоматичної побудови оптимальних логістичних
маршрутів шляхом алгоритмів та методів
Для досягнення поставленої мети було вирішено наступні задачі.
1. Проведено аналіз та обрано підходящий алгоритм для побудови
оптимальних маршрутів.
2. Проведено аналіз та визначено доступну платформу для зручної
реалізації алгоритму.
3. Досліджено сумісну програму для автоматичної візуалізаці
прорахованого результату алгоритму
4. Реалізовано алгоритм та інтегровані дієві інструменти взаємодії:
просту базу даних, базовий візуалізатор маршруту. Алгоритм, що стоїть в
основі системи здатний побудувати оптимальний маршрут враховуючи
пріорітетності призначень та фактичні можливості складів.
5. Створена модель системи побудови логістичного маршрут
враховуючи пріорітетність. Пріорітетність виражена чисельним значенням,
що може базуватися на інших комплексних алгоритмах, що враховують
терміновість, час доставки та витрати на доставку.
Побудова маршрут враховує реальні можливості складів, або
перевізників. В залежності від використання той же чисельний показник
може використовуватись як лічильник спроможності складів, або
перевізників, тим самим це дозволяє використовувати систему декількома
призначеннями.
Здійснено програмну реалізацію системи обрахунку оптимального
маршруту з зручним інтерфейсом.

77

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Derek Farren Analysis of Networks in Chess / Derek Farren, Daniel
Templeton, Meiji Wang - Режим доступу:
https://snap.stanford.edu/class/cs224w-2013/projects2013/cs224w-023-
final.pdf - Назва з екрану.
2. Keith McNulty The king that graph theory discovered (2018) - Режим
доступу: https://towardsdatascience.com/the-king-that-graph-theory-
discovered-8cce31a3cd26 - Назва з екрану
3. T. Cadman Design of Printed Circuit Board Layouts using Graph Theoretic
Methods - Режим доступу:
https://era.ed.ac.uk/bitstream/handle/1842/13290/Cadman1974.Pdf?sequenc
e=1 - Назва з екрану
4. Aida Abiad Printed circuit boards isomorphism: An experimental study /
Aida Abiad, Alexander Grigoriev, Stefanie Niemzok (2020) - Режим
доступу:
https://www.sciencedirect.com/science/article/pii/S036083522030440X -
Назва з екрану
5. threenplusone Calculating the number of paths through graph - Режим
доступу: https://stackoverflow.com/questions/4929090/calculating-the-
number-of-paths-through-graph - Назва з екрану
6. Graph Theory for Metro Traffic Modelling / Bruno Scalzo Dees, Yao Lei
Xu, Anthony G. Constantinides, Danilo P. Mandic (2021) - Режим доступу:
https://arxiv.org/pdf/2105.04991.pdf - Назва з екрану
7. Khalid Bekkaoui A Robust Scheme to Improving Security of Data using
Graph Theory / Khalid Bekkaoui, Soumia Ziti, Fouzia Omary - Режим
доступу:
https://www.researchgate.net/publication/341876278_A_Robust_Scheme_to
_Improving_Security_of_Data_using_Graph_Theory - Назва з екрану
78

8. Analysis of Airline Connectivity System using Graph Theory / Mukkamala
S N V Jitendra [та ін.] - Режим доступу:
https://www.researchgate.net/publication/343254274_Analysis_of_Airline_
Connectivity_System_using_Graph_Theory - Назва з екрану
9. Nick Kearns Analysis of Airline Connectivity System using Graph Theory -
Режим доступу: https://medium.com/@nick.kearns_74871/graph-theory-
and-flight-maps-df2e9f7fa684 - Назва з екрану
10. P. Lalitha Analysis of Psychology of Students by Graphical Representation /
P. Lalitha, L. Tamilselv - Режим доступу:
https://iopscience.iop.org/article/10.1088/1742-6596/1377/1/012029/pdf -
Назва з екрану
11. Тарануха В. Ю. Задачі на графах для курсу Алгоритміка - Режим
доступу: http://csc.knu.ua/media/filer_public/85/05/850574f0-fe7a-4eb4-
9a3f-1f99e18dd8bf/algorithmicsgraph.pdf - Назва з екрану
12. Горковлюк Д. Ю. Оцінка екстремальних значень показника
асортативності еластичних мереж - Режим доступу:
https://openarchive.nure.ua/bitstream/document/11229/1/Gorkovlyuk_DYu_
2019.pdf - Назва з екрану
13. Карнаух Т. О. Теорія графів у задачах / Карнаух Т.О., Ставровський
А.Б. - Режим доступу:
http://www.cyb.univ.kiev.ua/library/books/karnaukh-23.pdf - Назва з
екрану
14. Мартинюк А. О. Спектральні характеристики графів із досконалим
паруванням - Режим доступу:
http://ekmair.ukma.edu.ua/bitstream/handle/123456789/22549/Martyniuk_B
akalavrska_robota.pdf?sequence=1&isAllowed=y - Назва з екрану
15. Бондаренко Є. В. Теоріня графів: експандери - Режим доступу:
http://www.mechmat.univ.kiev.ua/wp-
content/uploads/2020/10/expanders.pdf - Назва з екрану
79

16. Гак А. О. Графи перетинiв - Режим доступу:
http://ekmair.ukma.edu.ua/bitstream/handle/123456789/22072/Hak_Bakalav
rska_robota.pdf?sequence=1&isAllowed=y - Назва з екрану
17. Олег Гутік Графи, зображувальні словами - Режим доступу:
http://prima.lnu.edu.ua/faculty/mechmat/Departments/Topology/Gutik.files/
Words-and-Graphs.pdf - Назва з екрану
18. Бартіш М. Я. Дослідження операцій / Бартіш М. Я., Дудзяний І. М. -
Режим доступу:
http://prima.lnu.edu.ua/faculty/mechmat/Departments/Topology/Gutik.files/
Words-and-Graphs.pdf - Назва з екрану
19. Воробієнко П. П. Телекомунікаційні та інформаційні мережі /
Воробієнко П. П., Нікітюк Л. А.,Резніченко П. І. - Режим доступу:
https://ktpu.kpi.ua/wp-content/uploads/2014/02/Vorobiyenko-P.P.-
Telekomunikatsijni-ta-informatsijni-merezhi.pdf - Назва з екрану
20. Погорілий С. Д. Формування та аналіз паралельних систем алгоритму
Дейкстри / Погорілий С. Д., Бойко Ю. В., Білоус Р. В.- Режим доступу:
http://dspace.nbuv.gov.ua/bitstream/handle/123456789/46824/05-
Pogoryliy.pdf?sequence=1 - Назва з екрану
21. Олександр Зеленський Алгоритм Дейкстри - Режим доступу:
http://choippo.cn.sch.in.ua/Files/downloadcenter/%D0%90%D0%BB%D0%
B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%20%D0%94%D0%B
5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D0%B8.%20%D0%A2
%D0%B5%D0%BE%D1%80%D1%96%D1%8F.pdf - Назва з екрану
22. Іксанов О. М. Транспортна задача, її властивості та методи
розв’язування / Іксанов О. М., Шевченко В. І. - Режим доступу:
http://www.cyb.univ.kiev.ua/library/books/iksanov-26.pdf - Назва з екрану
23. Шевченко Д. С. Транспортна задача з обмеженнями на
вантажопідйомність, час перевезення та кількість транспортних засобів
/ Шевченко Д. С., Шевченко А. С. - Режим доступу:
https://media.neliti.com/media/publications/310787-
80

%D1%82%D1%80%D0%B0%D0%BD%D1%81%D0%BF%D0%BE%D1
%80%D1%82%D0%BD%D0%B0-
%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-%D0%B7-
%D0%BE%D0%B1%D0%BC%D0%B5%D0%B6%D0%B5%D0%BD%D
0%BD%D1%8F%D0%BC%D0%B8-%D0%BD%D0%B0-
%D0%B2%D0%B0%D0%BD%D1%82-e2ee4d8a.pdf - Назва з екрану
24. Моклячук М. П. Достлідження операцій / Моклячук М. П., Ямненко Р.
Є. - Режим доступу:
https://probability.knu.ua/userfiles/mmp/OperationResearch2020UK.pdf -
Назва з екрану
25. A. Hadachi Transportation Theory and Applications - Режим доступу:
https://courses.cs.ut.ee/MTAT.08.043/2017_fall/uploads/Main/Lecture1TTA
.pdf - Назва з екрану
26. Seon Jeong Lee Enhancing online consumers' anticipatory behavior: An
application of transportation theory - Режим доступу:
https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1158&context=
dissertations_2 - Назва з екрану
27. Joseph Monteiro Networks in transportation - theory / Joseph Monteiro,
Gerald Robertson, Ben Atkinson - Режим доступу: https://ctrf.ca/wp-
content/uploads/2014/07/33MonteiroRobertsonAtkinsonNETWORKSINTR
ANSPORTATIONTHEORY.pdf - Назва з екрану
28. Derek Sheward Introduction to Microsoft Access 2007 / Derek Sheward,
Claire Napier - Режим доступу:
https://www.staffs.ac.uk/images/user163_access_intro_tcm68-28394.pdf -
Назва з екрану
29. CustomGuide, Inc. Access Quick Reference - Режим доступу:
https://www.customguide.com/cheat-sheet/microsoft-access-cheat-sheet.pdf
- Назва з екрану
30. Soren Lauesen Microsoft-Access Tutorial - Режим доступу:
https://www.itu.dk/~slauesen/UID/AccessTutorial.pdf - Назва з екрану

Репозиторій ЧДТУ