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

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

Please use this identifier to cite or link to this item: https://er.chdtu.edu.ua/handle/ChSTU/6367

Title:	Система для автоматичної побудови оптимальних логістичних маршрутів
Authors:	Корпань, Ярослав Васильович Сафронов, Святослав Андрійович
Issue Date:	Jun-2022
Abstract:	Мета кваліфікаційної роботи – створення системи для автоматичної побудови оптимальних логістичних маршрутів поєднуючи існуючі алгоритми. Для досягнення поставленої мети вирішено наступні задачі: обрано підходящий алгоритм для побудови оптимальних маршрутів; проведено аналіз та обрано доступну платформу для зручної реалізації алгоритму; проведено аналіз та обрати сумісну програму для автоматичної візуалізаці прорахованого результату алгоритму; реалізовано обраний алгоритм та інтегрувати дієві інструменти взаємодії: просту базу даних, базовий візуалізатор маршруту.
URI:	https://er.chdtu.edu.ua/handle/ChSTU/6367
Appears in Collections:	174 Автоматизація, комп'ютерно-інтегровані технології та робототехніка (Автоматизація та комп'ютерно-інтегровані системи та компоненти)

Files in This Item:

File	Description	Size	Format
Б_151_2022_Сафронов.pdf Restricted Access		1.51 MB	Adobe PDF	View/Open Request a copy

Show full item record

Extracted text

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ І СИСТЕМ
КАФЕДРА РОБОТОТЕХНІКИ ТА СПЕЦІАЛІЗОВАНИХ
КОМП’ЮТЕРНИХ СИСТЕМ
Пояснювальна записка
до кваліфікаційної роботи
освітнього ступеня «бакалавр»
на тему: СИСТЕМА ДЛЯ АВТОМАТИЧНОЇ ПОБУДОВИ
ОПТИМАЛЬНИХ ЛОГІСТИЧНИХ МАРШРУТІВ

Виконав: студент 4 курсу, групи АКІТ-187
спеціальності 151 Автоматизація та
комп’ютерно-інтегровані технології
Сафронов С.А.
(прізвище та ініціали)
Керівник Корпань Я.В.
(прізвище та ініціали)
Рецензент
(прізвище та ініціали)

Черкаси 2022

ЗМІСТ
ВСТУП ..................................................................................................................... 4
1 АНАЛІЗ ТЕХНІЧНОГО ЗАВДАННЯ ................................................................ 6
2 ТЕОРЕТИЧНІ АСПЕКТИ ГРАФІВ .................................................................... 7
2.1 Поняття графів та сфери їх використання ................................................... 7
2.2. Основні характеристики графів ................................................................. 22
3 ПРАКТИЧНІ АСПЕКТИ ВИКОРИСТАННЯ ГРАФІВ ТА ЇХ
ВИКОРИСТАННЯ У ЛОГІСТИЦІ ...................................................................... 26
3.2. Cпособи використання графів у логістиці ............................................... 31
3.3. Теоретичні аспекти пошуків оптимальних шляхів за допомогою графів
.............................................................................................................................. 34
4 ПОБУДОВА СИСТЕМИ ДЛЯ АВТОМАТИЧНОЇ ПОБУДОВИ
ОПТИМАЛЬНИХ ЛОГІСТИЧНИХ МАРШРУТІВ ........................................... 43
4.1 Опис функціональних можливостей ПЗ для побудови системи для
автоматичної побудови оптимальних логістичних маршрутів .................. 43
4.2. Аналіз існуючих систем для побудови системи автоматичної
побудови оптимальних логістичних маршрутів .......................................... 48
4.3. Опис алгоритму створення ПЗ для побудови системи для
автоматичної побудови оптимальних логістичних маршрутів .................. 51
ВИСНОВКИ ........................................................................................................... 56
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ............................................................. 57

ЧДТУ.221803.001 ПЗ
Змн. Лист № докум. Підпис Дата
Розроб. Сафронов Система для автоматичної Літ. Лист Листів
Перевір. Корпань побудови оптимальних 3 59
Реценз. логістичних маршрутів
Н. Контр. ЧДТУ, АКІТ-187
Пояснювальна записка
Затверд. Лукашенко

ВСТУП

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

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

Лист
ЧДТУ.221803.001 ПЗ
5
Змн. Лист. № докум. Підпис Дата

1 АНАЛІЗ ТЕХНІЧНОГО ЗАВДАННЯ

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

Лист
ЧДТУ.221803.001 ПЗ
6
Змн. Лист. № докум. Підпис Дата

2 ТЕОРЕТИЧНІ АСПЕКТИ ГРАФІВ

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

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

Рисунок 2.1 - Приклад графу

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

Лист
ЧДТУ.221803.001 ПЗ
8
Змн. Лист. № докум. Підпис Дата

Рисунок 2.2 - Граф

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

Лист
ЧДТУ.221803.001 ПЗ
9
Змн. Лист. № докум. Підпис Дата

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

Орієнтований граф (скорочено орграф) 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). У разі орієнтованого графа ця бієкція також має зберігати
Лист
ЧДТУ.221803.001 ПЗ
10
Змн. Лист. № докум. Підпис Дата

орієнтацію ребра. У разі зваженого графа бієкція також має зберігати вагу
ребра.
Шляхом (або ланцюгом) у графі називають кінцеву послідовність
вершин, у якій кожна вершина (крім останньої) з'єднана з наступною в
послідовності вершин ребром.
Орієнтованим шляхом в орграфі називають кінцеву послідовність
вершин v_i (i=1,\ldots,k), для якої всі пари (v_i, v_{i+1}) (i=1,\ldots k-1) є
(орієнтованими) ребрами.
Циклом називають шлях, у якому перша та остання вершини збігаються.
При цьому довжиною шляху (або циклу) називають число складових його
ребер. Зауважимо, що й вершини u і v є кінцями деякого ребра, відповідно до
даного визначення, послідовність (u,v,u) є циклом. Щоб уникнути таких
вироджених випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра у ньому не
повторюються; елементарним, якщо він простий і вершини у ньому не
повторюються. Нескладно бачити, що:
Кожен шлях, що з'єднує дві вершини, містить елементарний шлях, що
з'єднує ті самі дві вершини.
Будь-який простий неелементарний шлях містить елементарний цикл.
Будь-який простий цикл, що проходить через деяку вершину (або ребро),
містить елементарний (під-)цикл, що проходить через ту саму вершину (або
ребро).
Петля – елементарний цикл.
Бінарне відношення на безлічі вершин графа, задане як «існує шлях з u
в v», є ставленням еквівалентності і, отже, розбиває цю множину на класи
еквівалентності, які називають компонентами зв'язності графа. Якщо у графа
одно компонента зв'язності, то граф зв'язний. На компоненті зв'язності можна
запровадити поняття відстані між вершинами як мінімальну довжину шляху,
що з'єднує ці вершини.
Лист
ЧДТУ.221803.001 ПЗ
11
Змн. Лист. № докум. Підпис Дата

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

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

Тут позиції стануть вершинами, а спрямовані відрізки між ними
означатимуть, що одним ходом можна перейти від однієї позиції до іншої, у
напрямку стрілки
Лист
ЧДТУ.221803.001 ПЗ
12
Змн. Лист. № докум. Підпис Дата

2. Лабіринт (рис. 2.5).

Рисунок 2.5 - Приклад лабіринту

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

Лист
ЧДТУ.221803.001 ПЗ
13
Змн. Лист. № докум. Підпис Дата

Рисунок 2.6 - Приклад генеалогічного дерева

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

Лист
ЧДТУ.221803.001 ПЗ
14
Змн. Лист. № докум. Підпис Дата

Рисунок 2.7 - Приклад блок-схеми програми

Графами є блок - схеми програм для ЕОМ, а також будь-які електричні
ланцюги або електрична мережа.
5. Схема ланцюгів чергового освітлення (рис. 2.8).
Лист
ЧДТУ.221803.001 ПЗ
15
Змн. Лист. № докум. Підпис Дата

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

Рисунок 2.9 - Схеми авіаліній, що можуть бути представлені у вигляді графів
Лист
ЧДТУ.221803.001 ПЗ
16
Змн. Лист. № докум. Підпис Дата

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

Рисунок 2.10 - Приклад схеми Паризького метро
8. Соціограми (рис. 2.11).

Рисунок 2.11 - Приклад соціограми
Лист
ЧДТУ.221803.001 ПЗ
17
Змн. Лист. № докум. Підпис Дата

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

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

В схемах залізниць вершини – залізничні станції, а ребра – залізничні
колії.
10. Сузір'я (рис. 2.13).
Лист
ЧДТУ.221803.001 ПЗ
18
Змн. Лист. № докум. Підпис Дата

Рисунок 2.13 - Приклад сузір’я

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

Лист
ЧДТУ.221803.001 ПЗ
19
Змн. Лист. № докум. Підпис Дата

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

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

Лист
ЧДТУ.221803.001 ПЗ
20
Змн. Лист. № докум. Підпис Дата

Рисунок 2.15 - Приклад графів у математиці

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

Лист
ЧДТУ.221803.001 ПЗ
21
Змн. Лист. № докум. Підпис Дата

Рисунок 2.16 - Друкована схема

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

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

кінцем. Якщо напрями ребер не вказуються, то граф називається
неорієнтованим (або графом).
Зобразимо для прикладу неорієнтований граф G = (X, A) (рис. 2.17).

Рисунок 2.17 - Приклад неорієнтованого графу

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

Рисунок 2.18 - Приклад орієнтованого графу
Лист
ЧДТУ.221803.001 ПЗ
23
Змн. Лист. № докум. Підпис Дата

X = {x1, x2, x3, x4},
A = {a1 = (x1, x2), a2 = (x1, x3), a3 = (x3, x4), a4 = (x3, x2)}..
Граф, який має як орієнтовані, і неорієнтовані ребра, називається
змішаним.
Різні ребра можуть з'єднувати ту саму пару вершин. Такі ребра
називають кратними. Граф, що містить кратні ребра, називається
мультиграфом.
Неорієнтоване ребро графа еквівалентно двом протилежно спрямованим
дугам, що з'єднують ті самі вершини.
Ребро може поєднувати вершину саму з собою. Таке ребро називається
петлею. Граф з кратними ребрами та петлями називається псевдографом.
Багато ребер графа може бути порожнім. Безліч вершин графа може бути
порожнім.
Як у випадку орієнтованого, так і у випадку неорієнтованого ребра
кажуть, що вершини 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).
Лист
ЧДТУ.221803.001 ПЗ
24
Змн. Лист. № докум. Підпис Дата

Граф G = (X, A) - симетричний, якщо для будь-якої дуги (xi, xj) існує
протилежно орієнтована дуга (xj, xi).
Граф G = (X, A) -планарний, якщо він може бути зображений на площині
так, що не буде дуг, що перетинаються.
Неорієнтований граф G = (X, A) – дводольний, якщо безліч його вершин
X можна розбити на два такі підмножини X1 і X2, що кожне ребро має один
кінець у X1, а інший у X2.
Граф, який має як орієнтовані, і неорієнтовані ребра, називається
змішаним.
Різні ребра можуть з'єднувати ту саму пару вершин. Такі ребра
називають кратними. Граф, що містить кратні ребра, називається
мультиграфом.
Неорієнтоване ребро графа еквівалентно двом протилежно спрямованим
дугам, що з'єднують ті самі вершини.
Ребро може поєднувати вершину саму з собою. Таке ребро називається
петлею. Граф з кратними ребрами та петлями називається псевдографом.
Багато ребер графа може бути порожнім. Безліч вершин графа може бути
порожнім.

Лист
ЧДТУ.221803.001 ПЗ
25
Змн. Лист. № докум. Підпис Дата

3 ПРАКТИЧНІ АСПЕКТИ ВИКОРИСТАННЯ ГРАФІВ ТА ЇХ
ВИКОРИСТАННЯ У ЛОГІСТИЦІ

3.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)| або, іншими словами, кількість ребер;
Лист
ЧДТУ.221803.001 ПЗ
26
Змн. Лист. № докум. Підпис Дата

Вершина v інцидентна (англ. incident) ребраe, якщо v ϵ e; тоді ще кажуть,
що e є ребро при v;
Кінцеві вершини (кінці) (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
Кратними ребрами називаються однакові елементи мультимножини {e,
e, ...,e} є E, тобто ребра, чиї кінцеві вершини збігаються.
Лист
ЧДТУ.221803.001 ПЗ
27
Змн. Лист. № докум. Підпис Дата

Іншими словами, якщо E не безліч, а сімейство, тобто якщо E містить
однакові елементи, такі елементи називаються кратними ребрами, а граф
називається мультиграфом.
Маршрутом у графі називають кінцеву послідовність вершин, у якій
кожна вершина (крім останньої) з'єднана з наступною у послідовності
вершиною ребром. Ланцюгом називається маршрут без повторюваних ребер.
Простим ланцюгом називається маршрут без вершин, що повторюються
(звідки слідує, що в простому ланцюгу немає повторюваних ребер).
Орієнтованим маршрутом (або шляхом) в орграфі називають кінцеву
послідовність вершин і дуг, в якій кожен елемент інцидентний попередньому
та наступному.
Циклом називають ланцюг, у якому перша та остання вершини
збігаються. При цьому довжиною шляху (або циклу) називають число
складових його ребер. Слід зауважити, що якщо вершини u і v є кінцями
деякого ребра, то згідно з цим визначенням, послідовність (u,v,u) є циклом.
Щоб уникнути таких вироджених випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра у ньому не
повторюються; елементарним, якщо він простий і вершини в ньому не
повторюються (за винятком початкової та кінцевої у разі циклу).
Найпростіші властивості шляхів та циклів:
● кожен шлях, що з'єднує дві вершини, містить елементарний шлях, що
з'єднує ті самі дві вершини;
● кожен простий неелементарний шлях містить елементарний цикл;
● всякий простий цикл, що проходить через деяку вершину (або
ребро), містить елементарний (під-)цикл, що проходить через ту саму вершину
(або ребро);
● петля – елементарний цикл.
Бінарне відношення на безлічі вершин графа, задане як «існує шлях з u
в v», є ставленням еквівалентності і, отже, розбиває цю безліч на класи
Лист
ЧДТУ.221803.001 ПЗ
28
Змн. Лист. № докум. Підпис Дата

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

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

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

3.2. Cпособи використання графів у логістиці
Якщо розглядати логістику як задачу знаходження оптимального
переміщення, то з цього погляду – кожна людина протягом дня вирішкє такі
задачі
У своїй громадсько-практичній діяльності людина також щоденно
вирішує завдання логістики оптимального переміщення:
– вантажів;
Лист
ЧДТУ.221803.001 ПЗ
31
Змн. Лист. № докум. Підпис Дата

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

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

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

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

Лист
ЧДТУ.221803.001 ПЗ
35
Змн. Лист. № докум. Підпис Дата

Рисунок 3.1 - Приклад графу

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

Лист
ЧДТУ.221803.001 ПЗ
36
Змн. Лист. № докум. Підпис Дата

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

Рисунок 3.3 - Перший крок розрахунку

Надамо значення міткам вершин, суміжних з 1.
Довжина шляху від 1 до 2 вершини = 0 +7 = 7, це менше 1000 тому мітка
вершини 2 дорівнює 7.
Аналогічну операцію проробляємо з двома іншими сусідами 1-ї
вершини - 3-ї та 6-ї.
Усі сусіди вершини 1 перевірені.
Лист
ЧДТУ.221803.001 ПЗ
37
Змн. Лист. № докум. Підпис Дата

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

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

Рисунок 3.4 - Другий крок

Знову намагаємося зменшити мітки сусідів обраної вершини,
намагаючись пройти в них через 2 вершину. Сусідами вершини 2 є вершини 1,
3 та 4.
Вершина 1 вже відвідана, тому з першою вершиною нічого не робимо.
Лист
ЧДТУ.221803.001 ПЗ
38
Змн. Лист. № докум. Підпис Дата

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

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

Рисунок 3.5 - Третій крок

Четвертий крок
Лист
ЧДТУ.221803.001 ПЗ
39
Змн. Лист. № докум. Підпис Дата

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

Рисунок 3.6 - Четвертий крок

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

Лист
ЧДТУ.221803.001 ПЗ
40
Змн. Лист. № докум. Підпис Дата

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

Рисунок 3.8 - Шостий крок

Лист
ЧДТУ.221803.001 ПЗ
41
Змн. Лист. № докум. Підпис Дата

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

Лист
ЧДТУ.221803.001 ПЗ
42
Змн. Лист. № докум. Підпис Дата

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

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

Рисунок 4.1 - Транспортна задача

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

Рисунок 4.2 – «Склади»

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

Лист
ЧДТУ.221803.001 ПЗ
43
Змн. Лист. № докум. Підпис Дата

Рисунок 4.3 – Обсяг товару

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

Рисунок 4.4 – Пункти призначення

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

Рисунок 4.5 - Потреби

Числа всередині таблиці - матриця цін, або інакше, ціни перевезення 1
одиниці вантажу з відповідних пунктів. Ці значення також можуть
інтерпретуватись як відстані між відповідними пунктами. Подробиці — за
умови вирішуваного завдання (рис. 4.6).
Лист
ЧДТУ.221803.001 ПЗ
44
Змн. Лист. № докум. Підпис Дата

Рисунок 4.6 - Подробиці

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

Рисунок 4.7 – Приклад 1

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

Рисунок 4.8 – Приклад 2

Або те саме завдання може бути задане відразу в більш зрозумілому
вигляді (рис. 4.9).
Лист
ЧДТУ.221803.001 ПЗ
45
Змн. Лист. № докум. Підпис Дата

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

Рисунок 4.9 – Таблиці опису завдання

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

Рисунок 4.10 – Визначення найменшої розцінки

Надсилаємо 100 одиниць вантажу зі складу А2 до магазину В2.
Залишки на складі А2 - 100 одиниць. Потреби магазину В2 виконані
(рис. 4.11).
Лист
ЧДТУ.221803.001 ПЗ
46
Змн. Лист. № докум. Підпис Дата

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

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

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

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

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

Лист
ЧДТУ.221803.001 ПЗ
47
Змн. Лист. № докум. Підпис Дата

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

Рисунок 4.14 - Перший опорний план

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

Рисунок 4.15 - Другий опорний план

4.2. Аналіз існуючих систем для побудови системи автоматичної
побудови оптимальних логістичних маршрутів
Найбільш простими системами для побудови системи для автоматичної
побудови оптимальних логістичних маршрутів є Microsoft Office та Microsoft
Excel та Microsoft Access (рис. 4.16).
Також для візуального представлення у якості графа можна
використовувати програму Gephi – потужний опенсорсний інструмент,
здатний обробляти графи з сотнями тисяч вершин та зв'язків. Завантажити
його можна із офіційного сайту (рис. 4.17).
Лист
ЧДТУ.221803.001 ПЗ
48
Змн. Лист. № докум. Підпис Дата

Рисунок 4.16 - Приклад побудови оптимальних логістичних маршрутів за
допомогою інстументарію Microsoft Excel.

Рисунок 4.17 - Інтерфейс системи Gephi
Лист
ЧДТУ.221803.001 ПЗ
49
Змн. Лист. № докум. Підпис Дата

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

Рисунок 4.18 - Результат роботи системи Gephi

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

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

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

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

Рисунок 4.19 - Створення нового поля

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

Рисунок 4.20 - Введення ім’я
Лист
ЧДТУ.221803.001 ПЗ
52
Змн. Лист. № докум. Підпис Дата

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

Рисунок 4.21 - Вибір типу даних

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

Рисунок 4.22 - Приклад зв’язку

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

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

Рисунок 4.23 - Зміна зв’язків

Лист
ЧДТУ.221803.001 ПЗ
55
Змн. Лист. № докум. Підпис Дата

ВИСНОВКИ
Результатом роботи створили робочу систему обрахунку маршруту з
умовно зручним інтерфейсом.
Алгоритм, що стоїть в основі системи здатний побудувати оптимальний
маршрут враховуючи пріорітетності призначень та фактичні можливості
складів.
Пріорітетність виражена чисельним значенням, що може базуватися на
інших комплексних алгоритмах, що враховують терміновість, час доставки та
витрати на доставку.
В залежності від використання той же чисельний показник може
використовуватись як лічильник спроможності складів, або перевізників, тим
самим це дозволяє використовувати систему декількома призначеннями.
В решті решт було інтегровано зручні інструменти взаємодії, Excel для
бази даних та Gepgi для візуалізації графів у разі необхідності.

Лист
ЧДТУ.221803.001 ПЗ
56
Змн. Лист. № докум. Підпис Дата

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

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 - Назва з екрану
Лист
ЧДТУ.221803.001 ПЗ
57
Змн. Лист. № докум. Підпис Дата

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 - Назва з екрану
Лист
ЧДТУ.221803.001 ПЗ
58
Змн. Лист. № докум. Підпис Дата

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. Шевченко Д. С. Транспортна задача з обмеженнями на
вантажопідйомність, час перевезення та кількість транспортних засобів
/ Шевченко Д. С., Шевченко А. С. - Режим доступу:
Лист
ЧДТУ.221803.001 ПЗ
59
Змн. Лист. № докум. Підпис Дата

https://media.neliti.com/media/publications/310787-
%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
- Назва з екрану
Лист
ЧДТУ.221803.001 ПЗ
60
Змн. Лист. № докум. Підпис Дата

30. Soren Lauesen Microsoft-Access Tutorial - Режим доступу:
https://www.itu.dk/~slauesen/UID/AccessTutorial.pdf - Назва з екрану
Лист
ЧДТУ.221803.001 ПЗ
61
Змн. Лист. № докум. Підпис Дата

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