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

 

Етап 4 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів saving алгоритму для 3 х програм сумарних замовлень.

На Гамільтоновому циклу (рис.3), який створений на основі saving алгоритму, прокладемо маршрути між вузлами для кожної з 3-х програм, враховуючи вантажомісткість транспортного засобу D_max, відстань між вузлами (таблиця 3) та значення замовлень в кожному вузлі.

При визначені маршрутів було використано програму.

Також використовуючи дану програму, було підраховано значення загальної кількості маршрутів  R, що відповідає необхідній кількості транспортних засобів, довжину кожного маршруту L_r, r=1,…,R, кількості перевезеного вантажу та залишкової кількості вантажу на кожному з маршрутів, сумарну довжину всіх маршрутів , та при повній реалізації кожної з програм F₁, F₂, F₃, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:

 

Таблиця 4.1 демонструє вище перераховані значення для програми F₁.

Таблиця 4.1

R	Номери вузлів, що входять  в маршрут	Lr			Е
1	0-64-42-41-43-56-49-50-55-39-0	164,5418	19,4196	1,0804	0.9473
2	0-58-38-65-66-59-53-0	95,9885	19,0393	1,4607
3	0-54-57-60-47-61-62-0	136,2224	17,9412	2,5588
4	0-63-44-40-51-48-0	107,4414	16,9274	3,5726
5	0-45-52-46-67-0	39,2667	15,5759	4,9241
		543,6657

 

На рис.4.1 представлена графічна візуалізація маршрутів (R1, R2, R3, R4, R5) програми  F₁.

Рис.4.1

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

Таблиця-4.2

R	Номери вузлів, що входять в маршрут	Lr			Е
1	0-64-42-41-43-56-0	109,5501	13.9948	6.5052	0.6827
2	0-49-50-55-39-0	105,9071	17.9759	2.5241
3	0-58-38-65-66-0	77,7350	14.3425	6.1575
4	0-59-53-0	77,6433	17.0024	3.4976
5	0-54-57-60-47-0	108,9127	19.1407	1.3593
6	0-61-62-63-0	85,9688	19.5232	0.9768
7	0-44-40-51-48-0	87,6685	18.7409	1.7591
8	0-45-52-46-0	39,2667	19.5927	0.9073
9	0 – 67 - 0	10,7703	6,0499	14,4501
		703,4225

 

 

На рис.4.2 представлена графічна візуалізація маршрутів (R1, R2, R3, R4, R5, R6, R7, R8) програми -F₂.

 

Рис.4.2

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

Таблиця 4.3

R	Номери вузлів, що входять в маршрут	Lr			Е
1	0-64-42-41-0	92,4896	19,6133	0,8867	0,9568
2	0-43-56-49-0	85,9415	16,9387	3,5613
3	0-50-55-39-0	89,2691	18,0977	2,4023
4	0-58-38-65-0	65,8423	20,2967	0,2033
5	0-66-59-0	89,9184	18,3354	2,1646
6	0-53-0;	45,3431	14,9477	5,5523
7	0-54-57-0	69,3387	18,6029	1,8971
8	0-60-47-0	87,9969	14,1156	6,3844
9	0-61-62-0	71,8267	17,7708	2,7292
10	0-63-0	44,7214	15,6015	4,8985
11	0-44-40-0	43,9772	19,7916	0,7084
12	0-51-48-0	57,8334	12,2434	8,2566
13	0-45-0	28,2843	16,1066	4,3934
14	0-52-46-0	30,3225	17,3845	3,1155
15	0-–-67---0	10,7703	10,3415	10,1585
		913,8753

 

 

На рис.4.3 представлена графічна візуалізація маршрутів (R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14) програми  F₃.

 

Рис.4.3

Для створення графіків  маршрутів програм F₁  F₃ було використано стандартну функції обчислювального середовища Matlab:

plot (x,y),

де x – значення абсцис координат, які увійшла в маршрут;

y – значення ординат координат, які увійшла в маршрут.

 

Отже, проклавши маршрути для всіх 3 х програм можна підбити підсумки:

• загальна кількість маршрутів для 3 х програм – 29;
• на рис. 4.4 представлена графічна візуалізація показників ефективності для 3 х програм.

 

Рис.4.4

 

Блок-схема saving – алгоритму

 

 

 

 

Етап  5 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів модифікованого для задачі CVRP saving алгоритму для 3 х програм сумарних замовлень.

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

Різниця між ними полягає в тому, що на даному етапі маршрути прокладаються за допомогою модифікованого saving алгоритму.

Даний алгоритм при визначенні першого вузла на маршруті починає з найвищої пари вузлів, які ще не включені в маршрути, а першим вузлом в такій парі виступає вузол, який в saving таблиці відстаней зустрічається першим.

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

При визначені маршрутів було використано програму…..

Також використовуючи дану програму, було підраховано значення загальної кількості маршрутів R, що відповідає необхідній кількості транспортних засобів, довжину кожного маршруту L_r, r=1,…,R, кількості перевезеного вантажу та залишкової кількості вантажу на кожному з маршрутів, сумарну довжину всіх маршрутів , та при повній реалізації кожної з програм F₁, F₂, F_3, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:

 

 

Таблиця 5.1 демонструє вище перераховані значення для програми F₁.

Таблиця 5.1

R	Номери вузлів, що входять в маршрут	Lr			Е
1	0-64-42-41-43-56-49-50-55-39-0	164,542	19,4196	1,08039	0,9473
2	0-65-66-59-53-38-58-0	111,981	19,0395	1,46054
3	0-47-60-61-62-63-44-0	140,819	19,8526	0,647432
4	0-54-57-48-45-52-46-0	93,5326	19,842	0,657992
5	0-51-40-67-0	44,4759	10,75	9,75005
		555,3505

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

 

Рис.5.1

 

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

Таблиця 5.2

R	Номери вузлів, що входять в маршрут	Lr			Е
1	0-64-42-41-43-56-0	109,55	13,9948	6,50519	0,6827
2	0-65-66-59-0	92,586	12,6562	7,84383
3	0-50-55-39-58-0	96,9084	13,1256	7,37443
4	0-47-60-61-62-0	110,394	18,654	1,84605
5	0-54-57-48-0	79,8039	13,0734	7,42659
6	0-63-49-0	61,7457	16,5156	3,98439
7	0-53-38-0	61,639	16,1505	4,34947
8	0-40-44-51-0	46,4486	16,5504	3,94962
9	0-46-52-45-0	39,2667	19,5927	0,907268
10	0-67-0	10,7703	6,04993	14,4501
		709,11

На рис.5.2 представлена графічна візуалізація маршрутів (R1 – R10) програми  F₂.

Рис.5.2

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

Таблиця 5.3

R	Номери вузлів, що входять в маршрут	Lr			Е
1	0-64-42-41-0	92,4896	19,6133	0,8867	0,9568
2	0-65-66-0-	75,1382	7,5184	12,9816
3	0-43-56-49-0	85,9415	16,9386	3,5614
4	0-50-55-39-0-	89,2691	18,0978	2,4022
5	0-47-60-0	87,9969	14,1156	6,3844
6	0-53-0	45,3431	14,9477	5,5523
7	0-38-0	53,8516	12,6595	7,8405
8	0-59-0	76,8374	14,1156	6,3844
9	0-62--61-0	71,8267	17,7708	2,7292
10	0-54-57-0	69,3386	18,6028	1,8972
11	0-40-44-0	43,9772	19,7915	0,7085
12	0-48-45-0	43,9772	19,8509	0,6491
13	0-63-0	44,7213	15,6015	4,8985
14	0-52-46-0	30,3224	17,3844	3,1156
15	0-51-58-0	54,7519	12,8378	7,6622
16	0-67-0-	10,7703	10,3415	10,1585
		976,5535

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

Рис.5.3

Отже, проклавши маршрути для всіх 3 х програм, користуючись модифікованим saving алгоритмом,  можна підбити підсумки:

• загальна кількість маршрутів для 3 х програм – 30;
• на рис. 5.4 представлена графічна візуалізація показників ефективності для 3 х програм.

Рис.5.4

Блок-схема модифікованого saving алгоритму

 

 

Етап 6 Формування послідовності обходу вузлів (задача TSP-комівояжера) на основі sweeping- алгоритму з використанням полярних координат.

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

Нижче представлений Гамільтонів  цикл GSw, який отриманий за описаним вище алгоритмом для даного набору вузлів.

Він був визначений за допомогою підпрограми.

GSw={0 44 50 40 55 39 58 38 65 66 53 59 67 46 54 52 57 45 60 48 47 61 62 64 42 43 41 63 56 51 49 0}.

На рис.6 представлена графічна візуалізація Гамільтонового циклу. Нумерація  вузлів відповідає нумерації, зазначеній в завданні. Графік побудований за допомогою функції plot обчислювального  середовища Matlab.

Рис.6

Етап 7 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів sweeping-алгоритму. Графічна візуалізація простору маршрутів з їх відповідною нумерацією.

Завдання полягає у  тому, щоб для всіх програм сумарних замовлень F_i^, i = 1..3 визначити загальну кількості маршрутів R, що відповідає необхідній кількості транспортних засобів. Для кожного маршруту потрібно визначити такі характеристики:

1. довжини кожного маршруту Lr, r = 1 .. R;
2. кількості перевезеного вантажу Qr;
3. залишкову кількість вантажу Dr = Dmax - Qr.

Також при повній реалізації кожної з програми для них потрібно визначити: