Інтелектуальні системи та методи підтримки прийняття рішень
Курсовая работа, 20 Февраля 2013, автор: пользователь скрыл имя
Краткое описание
Одним із способів економії ресурсів при транспортуванні вантажів є застосування систем підтримки прийняття рішень в галузі транспортної логістики. Розробка програмних пакетів, що вирішують завдання цієї галузі, вимагає проведення серйозних наукових досліджень з метою отримання ефективних алгоритмів, придатних для застосування в повсякденній практиці.
У даній роботі використовуються такі методи пошуку оптимального шляху, як saving-алгоритм, модифікований saving-алгоритм, sweeping-алгоритм.
Файлы: 1 файл
20.02.2013.docx
— 3.68 Мб (Скачать)
Етап 4 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів saving алгоритму для 3 х програм сумарних замовлень.
На Гамільтоновому циклу (рис.3), який створений на основі saving алгоритму, прокладемо маршрути між вузлами для кожної з 3-х програм, враховуючи вантажомісткість транспортного засобу Dmax, відстань між вузлами (таблиця 3) та значення замовлень в кожному вузлі.
При визначені маршрутів було використано програму.
Також використовуючи дану програму, було підраховано значення загальної кількості маршрутів R, що відповідає необхідній кількості транспортних засобів, довжину кожного маршруту Lr, r=1,…,R, кількості перевезеного вантажу та залишкової кількості вантажу на кожному з маршрутів, сумарну довжину всіх маршрутів , та при повній реалізації кожної з програм F1, F2, F3, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:
Таблиця 4.1 демонструє вище перераховані значення для програми F1.
Таблиця 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) програми F1.
Рис.4.1
Таблиця 4.2 демонструє вище перераховані значення для програми F2.
Таблиця-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) програми -F2.
Рис.4.2
Таблиця 4.3 демонструє вище перераховані значення для програми F3.
Таблиця 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) програми F3.
Рис.4.3
Для створення графіків маршрутів програм F1 F3 було використано стандартну функції обчислювального середовища Matlab:
plot (x,y),
де x – значення абсцис координат, які увійшла в маршрут;
y – значення ординат координат, які увійшла в маршрут.
Отже, проклавши маршрути для всіх 3 х програм можна підбити підсумки:
- загальна кількість маршрутів для 3 х програм – 29;
- на рис. 4.4 представлена графічна візуалізація показників ефективності для 3 х програм.
Рис.4.4
Блок-схема saving – алгоритму
Етап 5 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів модифікованого для задачі CVRP saving алгоритму для 3 х програм сумарних замовлень.
Даний схожий на попередній етап, також заключається у прокладанні маршруту на основі Гамільтонового циклу (рис.3), вантажомісткості транспортного засобу Dmax, відстань між вузлами (таблиця 3) та значення замовлень в кожному вузлі.
Різниця між ними полягає в тому, що на даному етапі маршрути прокладаються за допомогою модифікованого saving алгоритму.
Даний алгоритм при визначенні першого вузла на маршруті починає з найвищої пари вузлів, які ще не включені в маршрути, а першим вузлом в такій парі виступає вузол, який в saving таблиці відстаней зустрічається першим.
Тобто, Гамільтонів цикл визначаться заново перед пошуком кожного наступного маршруту в замовленні без урахування вже пройдених вузлів.
При визначені маршрутів було використано програму…..
Також використовуючи дану програму, було підраховано значення загальної кількості маршрутів R, що відповідає необхідній кількості транспортних засобів, довжину кожного маршруту Lr, r=1,…,R, кількості перевезеного вантажу та залишкової кількості вантажу на кожному з маршрутів, сумарну довжину всіх маршрутів , та при повній реалізації кожної з програм F1, F2, F3, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:
Таблиця 5.1 демонструє вище перераховані значення для програми F1.
Таблиця 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) програми F1.
Рис.5.1
Таблиця 5.2 демонструє вище перераховані значення для програми F2.
Таблиця 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) програми F2.
Рис.5.2
Таблиця 5.3 демонструє вище перераховані значення для програми F3.
Таблиця 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) програми F3.
Рис.5.3
Отже, проклавши маршрути для всіх 3 х програм, користуючись модифікованим saving алгоритмом, можна підбити підсумки:
- загальна кількість маршрутів для 3 х програм – 30;
- на рис. 5.4 представлена графічна візуалізація показників ефективності для 3 х програм.
Рис.5.4
Блок-схема модифікованого saving алгоритму
Етап 6 Формування послідовності обходу вузлів (задача TSP-комівояжера) на основі sweeping- алгоритму з використанням полярних координат.
Sweeping-алгоритм заснований
на використанні полярної
Нижче представлений Гамільтонів цикл 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-алгоритму. Графічна візуалізація простору маршрутів з їх відповідною нумерацією.
Завдання полягає у тому, щоб для всіх програм сумарних замовлень Fi, i = 1..3 визначити загальну кількості маршрутів R, що відповідає необхідній кількості транспортних засобів. Для кожного маршруту потрібно визначити такі характеристики:
- довжини кожного маршруту Lr, r = 1 .. R;
- кількості перевезеного вантажу Qr;
- залишкову кількість вантажу Dr = Dmax - Qr.
Також при повній реалізації кожної з програми для них потрібно визначити: