Інтелектуальні системи та методи підтримки прийняття рішень

В табл. 9.3 зазначені методи, які дають найкращі результати в розрізі критерію та програми замовлень.

 

Таблиця 9.3. Результати порівняння

Критерій	F1	F2	F3
Загальна  довжина маршрутів	Saving-алгоритм	Saving-алгоритм	Saving-алгоритм
Ефективність маршрутів	Saving-алгоритм	Sweeping-алгоритм з іншими початковими умовами	Saving-алгоритм

 

Головним  критерієм вибору візьмемо довжину  маршруту. Тож, можемо зробити висновок, що загальна довжина маршруту найменша для всіх 3-х програм за Saving-алгоритмом.

 

Етап 10 Оптимізація маршрутів

На попередньому етапі  для кожної програми замовлень було обрано найбільш оптимальну серед трьох, отриманих різними методами.

На цьому ж етапі  буде виконана спроба ще більш оптимізувати обрані маршрути. Для цього використаємо метод оптимізації - методом усереднених коефіцієнтів.

Таблиця 10.1 демонструє Оптимізовані маршрути для програми F₁.

Таблиця 10.1

R	Номери вузлів, що входять  в маршрут	Lr
1	0 - 64 - 42 - 43 - 41 - 56 - 49 - 50 - 55	163,7363
2	0 - 58 - 38 - 65 - 66 - 59 - 53 - 0	95,9885
3	0 - 54 - 57 - 60 - 47 - 61 - 62 - 0	136,2224
4	0 - 48 - 63 - 51 - 44 - 40 - 0	98,1576
5	0 - 67 - 46 - 52 - 45 - 0	39,4715
		533,5764
Saving-алгоритмом		543,6657
Величина  оптимізації		9,8844

 

З результату таблиці 10.1 видно, що маршрути для програми F₁ вдалося оптимізувати на 9,9 км. 

На рис.10.1 представлена графічна візуалізація оптимізованих маршрутів (R1 - R5) програми F₁.

Рис.10.1 Графічна візуалізація оптимізованих маршрутів (R1 - R5) програми F₁

 

Таблиця 10.2 демонструє оптимізовані маршрути для програми F₂.

Таблиця 10.2

R	Номери вузлів, що входять  в маршрут	Lr
1	0 - 43 - 41 - 64 - 42 - 56 -0	109,1063
2	0 - 49 - 50 - 55 - 39 - 0	105,9070
3	0 - 58 - 38 - 65 - 66 - 0	77,7349
4	0 - 59 - 53 - 0	77,6432
5	0 - 54 - 57 - 60 - 47 - 0	108,9126
6	0 - 61 - 62 - 63 - 0	85,9688
7	0 - 48 - 51 - 44 - 40 - 0	82,1913
8	0 - 45 - 52 - 46 - 0	39,2667
9	0 - 67 - 0	10,7703
		697,5016
Saving-алгоритмом		703,4225
Величина  оптимізації		5,9209

 

З таблиці 10.2 видно, що маршрути для програми F₂ вдалося оптимізувати на 5,9 км.

 

На рис.10.2 представлена графічна візуалізація оптимізованих маршрутів  програми F₂.

 

Рис.10.2 Графічна візуалізація оптимізованих маршрутів програми F₂

 

Таблиця 10.3 демонструє оптимізовані маршрути  для програми F₃.

Таблиця 10.3

R	Номери вузлів, що входять  в маршрут	Lr
1	0 - 64 - 42 - 41 - 0	92,4896
2	0 - 43 - 56 - 49 - 0	85,9414
3	0 - 50 - 55 - 39 - 0	89,2690
4	0 - 58 - 38 - 65 - 0	65,8423
5	0 - 66 - 59 - 0 - 0	89,9184
6	0 - 53 - 0 - 0 - 0	45,3431
7	0 - 54 - 57 - 0 - 0	69,3386
8	0 - 60 - 47 - 0 - 0	87,9969
9	0 - 61 - 62 - 0 - 0	71,8267
10	0 - 63 - 0 - 0 - 0	44,72138
11	0 - 44 - 40 - 0 - 0	43,9772
12	0 - 51 - 48 - 0 - 0	57,8333
13	0 - 45 - 0 - 0 - 0	28,2842
14	0 - 52 - 46 - 0 - 0	30,3224
15	0 - 67 - 0 - 0 - 0	10,7703
		913,8753
Saving-алгоритмом		913,8753
Величина  оптимізації		0

 

З таблиці 10.3 видно, що маршрути для програми F₃ оптимізувати не вдалося і тому у подальших розрахунках буде використане значення загальної довжини маршрутів для даної програми, отримане за допомогою saving-алгоритму.

На рис.10.3 представлена графічна візуалізація оптимізованих маршрутів програми  F₃.

Рис.10.3 Графічна візуалізація оптимізованих маршрутів програми F₃

На цьому етапі  було виконано оптимізацію маршрутів  за допомогою методу усереднених  коефіцієнтів. Можемо зробити висновок, що вдалося оптимізувати 2 маршрути з 3-х. 
Етап 11 Формування матриці рішень

Матриця рішень формується стосовно розміру парку транспортних засобів для зовнішніх умов, представлених у вигляді різних програм вантажних перевезень F₁, F₂, F₃, ймовірність появи яких задана множиною q₁, q₂, q₃.

Множина альтернативних рішень E=E₁, E₂,… відповідає варіантам розміру парку транспортних засобів, де – максимальна кількість маршрутів при реалізації програми вантажних перевезень, яка визначається наступним чином:

 

де - максимальна кількість маршрутів при реалізації програми вантажних перевезень F₃.

Елементи  матриці рішень обчислюються за наступними алгоритмами:

8. у випадку фрахтування додаткових транспортних засобів:

;

9. у випадку простою частини транспортних засобів:

.

Тут m - кількість танкерів згідно альтернативного рішення

- кількість маршрутів  при реалізації j -ї програми вантажних перевезень;

 – загальна  довжина всіх маршрутів при  реалізації  -ї програми вантажних перевезень;

 – загальна  кількість відвантаженого вантажу  на r -му маршруті при реалізації j-ї програми вантажних перевезень;

 – загальна  кількість відвантаженого вантажу  на всіх маршрутах при реалізації j -ї програми вантажних перевезень.

Для формування матриці рішень була використана підпрограма GetEij.

 

Таблиця 11.1. Матриця рішень

E	Кількість транспорту	F1	F2	F3
1	4	0,8606	1,3982	2,3939
2	5	0,8651	1,4027	2,3984
3	6	0,8621	1,4072	2,4029
4	7	0,8591	1,4117	2,4074
5	8	0,8561	1,4162	2,4119
6	9	0,8531	1,4207	2,4164
7	10	0,8501	1,4252	2,4209
8	11	0,8471	1,4222	2,4254
9	12	0,8441	1,4192	2,4299
10	13	0,8411	1,4162	2,4344
11	14	0,8381	1,4132	2,4389

 

 

 

Етап 12 Пошук оптимальний кількості транспортних одиниць

Пошук оптимальної кількості  транспортних засобів відбувається шляхом використання класичних (MM, BL, S), похідних (HW, HL, G, P) та комбінованих (BL-MM, BL-S) критеріїв для обробки матриці рішень . Результати по кожному з критерій можна переглянути у ДОДАТКУ Б.

Таблиця 12.1. Оптимальні рішення  за ірзними критеріями

E	Кількість транспорту	MM	BL	G	HL	HW	P	S	BLM	BLS
1	4
2	5	+		+	+
3	6
4	7
5	8
6	9
7	10		+				+	+	+	+
8	11							+
9	12
10	13
11	14					+

 

З таблиці 12.1 видно, що при  застосуванні критеріїв, виявилося  декілька значень оптимальної кількості  транспортних засобів, а саме:

1. 1 критерій (S) показав – 11 одиниць;
2. 1 критерій (HW) показав – 14 одиниць;
3. 3 критерії (MM,G, HL) показали – 5 одиниць;
4. 5 критеріїв (BL, P, S, BLMM, BLS) показали – 10 одиниць

Oптимальним будемо вважати 10 одиниць транспортних засобів.

Етап 13 Розробка дружнього інтерфейсу та систематизація програмного забезпечення СППР для реалізації режимів інтерактивної взаємодії ЛПР та СППР.

Розробка дружнього інтерфейсу відбувається за допомогою програмного  середовища Matlab 7.9. На Рис.13 можемо побачити результат роботи програми. Інтерфейс складається з набору кнопок, за допомогою яких можемо переглянути:

• Візуалізацію вузлів (Рис.13.1)

                               Рис.13.1

• Saving-алгоритм: (Рис.13.2)
• Переглянути матрицю
• Гамільтонів цикл
• Переглянути маршрути
• Показники ефективності

 

 

 

 

 

 

 

 

                                                                                                                                         

                                                                      Рис.13.2

• Модифікований saving-алгоритм: (Рис.13.3)
• Переглянути маршрути
• Показники ефективності

                              Рис.13.3

• Sweeping-алгоритм (Рис.13.4)
• Переглянути маршрути
• Гамільтонів цикл
• Показники ефективності

                                Рис.13.4

 

 

• Модифікований Sweeping-алгоритм (Рис.13.5)
• Переглянути маршрути
• Гамільтонів цикл
• Показники ефективності

                                      Рис.13.5

• Оптимізація (Рис.13.6)
• Переглянути маршрути
• Значення оптимізації

                                   Рис.13.6

 

 

 

• Результуючу матрицю (Рис.13.7)

 

                          Рис.13.7

 

• Таблицю критеріїв (Рис.13.8)

 

 

Рис.13.8

Рис.13 Графічний інтерфейс  СППР

 

ВИСНОВКИ

В ході виконання даної  роботи було  розроблено власну СППР, яка дозволяє вирішувати задачу комівояжера.

Для цього дана система  розраховує відстані між вузлами  та відстані від базового вузла до кожного з вузла, який виступає в  ролі замовника. А лиш потім приступає  до прокладання маршрутів між  вузлами, застосовуючи при цьому  такі алгоритми: saving-алгоритм, модифікований saving-алгоритм, sweeping з різними початковими точками.