Синтез СППР для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності

Автор: Пользователь скрыл имя, 23 Февраля 2013 в 16:00, курсовая работа

Описание работы

В даній курсовій роботі на прикладі розглянуто cинтез системи підтримки прийняття рішень (СППР) для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності. Для досліджень та аналізу в курсовій роботі було використано різні алгоритми формування маршрутів та різні критерії для прийняття рішень, для оптимізації парку транспортних засобів. Всі розрахунки проводились в декілька етапів :
Формування saving таблиці
Формування маршрутів на основі Saving алгоритму;

Скачать полностью (1.93 Мб) Сколько стоит заказать работу?

Работа содержит 1 файл

КР(Гнатовский В. 501м).doc

— 4.13 Мб (Скачать)

Таблиця 3.4.1

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 – 42 – 41 – 43 – 56 – 49 – 50 – 55 – 31 – 38 – 53 - 0	179.2997	13.6500	1.3500	465.3944
Route2	0 – 35 – 54 – 57 – 37 – 36 – 47 – 48 – 0	101.3233	13.1800	1.8200
Route3	0 – 29 – 45 – 30 – 28 – 33 – 44 – 32 – 39 – 0	117.3278	12.8200	2.1800
Route4	0 – 40 – 51 – 52 – 46 – 34 – 0	67.4436	9.6000	5.4000

Показник ефективності завантаження транспортних засобів при реалізації 1-ї програми: 0.7073

Графічна візуалізація простору маршрутів для 1-ї програми сумарних замовлень з їх відповідною нумерацією (Рис. 3.4.1).

Рис.3.4.1

3.4.2 Для 2-ї програми сумарних замовлень:

Таблиця 3.4.2

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 - 42 – 41- 43 – 56 – 49 – 50 – 55 - 0	146.3046	13.8000	0.7000	551.5605
Route2	0 - 31 - 38 - 53 - 35 - 54 - 57 - 0	132.3376	13.4800	1.0200
Route3	0 - 37 - 36 - 47 - 0	73.1548	11.8300	2.6700
Route4	0 - 48 - 29 - 45 - 30 - 28 - 33 - 0	85.9752	14.4300	0.0700
Route5	0 - 44 - 32 - 39 - 40 - 0	60.4868	12.2500	2.2500
Route6	0 - 51 - 52 - 46 - 34	53.3014	11.0100	3.4900

Показник ефективності завантаження транспортних засобів при реалізації 2-ї програми:

0.907

Графічна візуалізація простору маршрутів для 2-ї програми сумарних замовлень з їх відповідною нумерацією (Рис. 3.4.2).

Рис.3.4.2

3.4.3 Для 3-ї програми сумарних замовлень:

Таблиця 3.4.3

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 - 42 - 41 - 43 - 0	76.6746	12.2700	2.7300	898.3837
Route2	0 - 56 - 49 - 50 - 0	99.4096	13.2500	1.7500
Route3	0 - 55 - 31 - 38 - 0	110.0605	12.5100	2.4900
Route4	0 - 53 - 35 - 0	47.6993	11.2100	3.7900
Route5	0 - 54 - 57 - 0	69.3387	7.8600	7.1400
Route6	0 - 37 - 0	64.0312	8.3000	6.7000
Route7	0 - 36 - 0	66.2118	8.2300	6.7700
Route8	0 - 47 - 48 - 0	53.8659	13.8900	1.1100
Route9	0 - 29 - 0	36.8782	7.7900	7.2100
Route10	0 - 45 - 30 - 0	36.5222	8.9600	6.0400
Route11	0 - 28 - 33 - 44 - 0	80.5891	11.4700	3.5300
Route12	0 - 32 - 39 - 0	55.1944	13.7800	1.2200
Route13	0 - 40 - 0	28.2843	8.2300	6.7700
Route14	0 - 51 - 52 - 0	50.2075	13.8600	1.1400
Route15	0 - 46 - 34 - 0	23.4164	9.1800	5.8200

Показник ефективності завантаження транспортних засобів при реалізації 3-ї програми:

0.8180

Графічна візуалізація простору маршрутів для 3-ї програми сумарних замовлень з їх відповідною нумерацією (Рис. 3.4.3).

Рис.3.4.3

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

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

Гамільтонів цикл: (0-42-41-43-56-49-50-55-31-38-53-35-54-57-37-36-47-48-29-45-30-28-33-44-32-39-40-51-52-46-34-0)

3.5.1 Для 1-ї програми сумарних замовлень: Таблиця 3.5.1

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 – 42 – 41 – 43 – 56 – 49 – 50 – 55 – 31 – 38 – 53 - 0	179.2997	13.6500	1.3500	466.6301
Route2	0 - 37 - 36 - 47 - 48 - 29 - 57 - 54 - 0	113.1557	14.1300	0.8700
Route3	0 - 44 - 32 - 39 - 40 - 51 - 33 - 28 - 30- 0	110.7658	13.0000	2.0000
Route4	0 - 52 - 46 - 35 - 34 - 45 - 0	63.4089	8.4700	6.5300

Графічна візуалізація простору маршрутів для 1-ї програми сумарних замовлень з їх відповідною нумерацією (Рис. 3.5.1).

Рис.3.5.1

3.5.2 Для 2-ї програми сумарних замовлень:

Таблиця 3.5.2

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 - 42 – 41- 43 – 56 – 49 – 50 – 55 - 0	146.3046	13.8000	0.7000	550.3604
Route2	0 - 37 - 36 - 47 - 0	73.1548	11.8300	2.6700
Route3	0 - 38 - 31 - 39 - 32 - 44 - 0	98.1697	12.6900	1.8100
Route4	0 - 54 - 57 - 29 - 48 - 28 - 33 - 0	108.1464	13.9000	0.6000
Route5	0 - 53 - 35 - 46 - 52 - 34 - 0	58.0880	12.5300	1.9700
Route6	0 - 45 - 30 - 51 - 40 - 0	66.4969	12.0500	2.4500

Графічна візуалізація простору маршрутів для 2-ї програми сумарних замовлень з їх відповідною нумерацією (Рис. 3.5.2).

Рис.3.5.2

3.5.3 Для 3-ї програми сумарних замовлень:

Таблиця 3.5.3

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 - 42 - 41 - 43 - 0	76.6746	12.2700	2.7300	895.1035
Route2	0 - 31 - 55 - 0	101.3747	11.1600	3.8400
Route3	0 - 37 - 0	64.0312	8.3000	6.7000
Route4	0 - 36 - 0	66.2118	8.2300	6.7700
Route5	0 - 56 - 49 - 50 - 0	99.4096	13.2500	1.7500
Route6	0 - 48 - 47 - 0	53.8659	13.8900	1.1100
Route7	0 - 54 - 57 - 0	69.3387	7.8600	7.1400
Route8	0 - 44 - 32 - 0	47.9182	9.0700	5.9300
Route9	0 - 38 - 53 - 35 - 0	63.9952	12.5600	2.4400
Route10	0 - 45 - 0	28.2843	7.8700	7.1300
Route11	0 - 33 - 28 - 30 - 0	60.7400	8.9300	6.0700
Route12	0 - 39 - 0	44.7214	8.3400	6.6600
Route13	0 - 29 - 52 - 0	44.7467	13.6200	1.3800
Route14	0 - 34 - 46 - 0	23.4164	9.1800	5.8200
Route15	0 - 40 - 0	28.2843	8.2300	6.7700
Route16	0 - 51 - 0	22.0907	8.0300	6.9700

Показник ефективності завантаження транспортних засобів при реалізації кожної програми: 0.9375 0.8931 0.8180

Рис.3.5.4

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

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

Гамільтонів цикл GSw має вигляд:

GSw={44-50-32-40-55-39-31-38-53-35-46-54-34-52-57-45-29-37-36-48-47-30-28-42-43-41-33-56-51-49}.

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

Рис. 3.6.1. Графічна візуалізація Гамільтонового циклу

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

3.7.1 Для 1-ї програми сумарних замовлень:

В табл.8.1 занесена інформація про маршрути транспортних перевезень для програми F₁.

Таблиця 3.7.1.

R	Маршрут	Довжина L_i	Q_i	D
1	0 - 44 - 50 - 32 - 40 - 55 - 39 31 38 - 0	159.2453	13.9400	0.5600
2	0 - 53 - 35 46 - 54 - 34 - 52 - 57 45 - 0	121.1441	12.8700	1.6300
3	0 - 29 - 37 - 36 - 48 - 47 - 30 - 28 - 0	109.0653	14.1400	0.3600
4	0 - 42 -43 -41 33 - 56 - 51 - 49 - 0	156.5022	8.3000	6.2000
	L	545.9569

Показник ефективності завантаження транспортних засобів при реалізації програми F₁:

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

Рис. 3.7.1. Маршрути транспортних перевезень для програми F₁

3.7.2 Для 2-ї програми сумарних замовлень:

В табл. 3.7.2 занесена інформація про маршрути транспортних перевезень для програми F₂.

Таблиця 3.7.2

R	Маршрут	Довжина L_i	Q_i	D
1	0 - 44 - 50 - 32 - 40 - 55 – 0	117.4860	13.3600	1.1400
2	0 - 39 - 31 - 38 - 53 - 35 - 0	94.3292	13.7200	0.7800
3	0 - 46 - 54 - 34 - 52 - 57 - 0	92.4474	10.9200	3.5800
4	0 - 45 - 29 - 37 - 0	64.2314	11.4400	3.0600
5	0 - 36 - 48 - 47 - 30 - 28 - 0	102.3204	14.4200	0.0800
6	0 - 42 - 43 - 41 - 33 - 56 - 51 - 49 - 0	156.5022	12.9400	1.5600
	L_i	627.3166

Показник ефективності завантаження транспортних засобів при реалізації програми F₂:.

На рис 7.2. зображено маршрути транспортних перевезень для програми F_2.

Рис 3.7.2. Маршрути транспортних перевезень для програми F₂

3.7.3 Для 3-ї програми сумарних замовлень:

В табл.3.7.3 занесена інформація про маршрути транспортних перевезень для програми F₃.

Таблиця 3.7.3

R	Маршрут	Довжина L_i	Q_i	D
1	0 - 44 - 50 - 0	60.2972	10.9300	3.5700
2	0 - 32 - 40 - 0	44.8897	13.6700	0.8300
3	0 - 55 - 39	87.1478	11.7100	2.7900
4	0 - 31 - 38 - 0	82.9017	9.1400	5.3600
5	0 - 53 - 35 - 0	47.6993	11.2100	3.2900
6	0 - 46 - 54 - 0	54.2301	13.2000	1.3000
7	0 - 34 - 52 - 57 - 0	58.2065	9.6700	4.8300
8	0 - 45 - 0	28.2843	7.8700	6.6300
9	0 - 29 - 0	36.8782	7.7900	6.7100
10	0 - 37 - 0	64.0312	8.3000	6.2000
11	0 - 36 - 48	66.2514	13.8700	0.6300
12	0 - 47 - 30	54.2820	9.3400	5.1600
13	0 - 28 - 42	80.6844	13.8800	0.6200
14	0 - 43 - 41	112.3595	11.8700	2.6300
15	0 - 51 - 49	56.1461	8.3400	6.1600
	L_i	934.2895

Информация о работе Синтез СППР для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності