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

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

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

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

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

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

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

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

г) Для реалізації будь-якої і -програми, замовлення в j - порту буде визначатися, як = *:

Таблиця 3

№ вузла				№ вузла				№ вузла
28	2,14	3,34	7,00	38	0,42	0,65	1,35	48	1,73	2,69	5,64
29	2,39	3,72	7,79	39	2,56	3,99	8,34	49	0,09	0,15	0,31
30	0,28	0,52	1,09	40	2,53	3,93	8,23	50	2,24	3,49	7,30
31	2,39	3,72	7,79	41	1,28	1,99	4,17	51	2,46	3,84	8,03
32	1,66	2,60	5,44	42	2,11	3,29	6,88	52	1,79	2,79	5,83
33	0,26	0,40	0,84	43	0,37	0,58	1,22	53	1,99	3,11	6,51
34	0,73	1,13	2,37	44	1,11	1,73	3,63	54	1,96	3,05	6,39
35	1,44	2,25	4,70	45	2,42	3,76	7,87	55	1,03	1,61	3,37
36	2,53	3,93	8,23	46	2,09	3,25	6,81	56	1,73	2,69	5,64
37	2,54	3,96	8,30	47	2,53	3,94	8,25	57	0,45	0,70	1,47

д) Серед отриманих випадковим чином замовлень в вузлах обираємо максимальне замовлення

. Перевіряємо виконання умови , що забезпечує можливість обслуговування будь-якого вузла за один рейс транспортного засобу. Якщо умова не виконується, то необхідно самостійно скорегувати значення за формулою:

, де .

За моїм варіантом

= 8,34, отже

= 8,34.

Дані для розрахунку матриці рішень:

Вартісні параметри {C₁, C₂, C₃, C₄, C₅} для формування кількісних оцінок e_ij (i = ) альтернативних варіантів рішень Е_і при різних программах обсягу загальних вантажних перевезень {F₁, F₂, F₃}.

Таблиця 4

№ п/п	Параметр	Значення	Характеристика параметра
1	C₁	10100	Прибуткова вартість 1 т вантажу
2	C₂	35	Вартість перевезення на 1 км
3	C₃	2800	Вартість додаткових експлуатаційних витрат
4	C₄	4500	Вартість фрахту одного допоміжного транспортного засобу
5	C₅	3000	Вартість простою одного транспортного засобу

Ймовірності {q₁, q₂, q₃ } появи відповідних зовнішніх станів {F₁, F₂, F₃}:

№ варіанту	q₁	q₂	q₃
28	0,27330	0,21685	0,50985

3 Формування симетричної матриці відстаней між заданними вузлами. Графічна візуалізація простору вузлів з іх відповідною нумерацією.

Графічна візуалізація простору вузлів

Використовуючи програмне середовище Matlab отримую графічну візуалізацію простору вузлів з їх відповідною нумерацією за моїм варіантом (рис.2.1):

Симетрична матриця відстаней між заданими вузлами.

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

де X1, Y1, X2, Y2 – координати відповідних вузлів.

В таблиці 2.1 наведено симетричну матрицю відстаней між заданими вузлами.

Рис.3.1. Візуалізація простору вузлів з їх відповідною нумерацією

Таблиця 3.1. Симетрична матриця відстаней

Закінчення таблиці 3.1

3.3 Формування послідовності обходу вузлів (задача traveling salesman problem або задача комівояжера) на основі saving-алгоритму

Побудова Saving-таблиці відстаней

Матриця будується на основі формули

S_ij=l_0i+l_0j-l_ij, де l_{0i та}l_0j відстань між базовим вузлом та вузломи i та j

де l_ij відстань між вузлом j та вузлом i

Таблиця 3.3.1. Saving-матриця

i	j	S(i,j)	i	j	S(i,j)	i	J	S(i,j)	i	j	S(i,j)	i	j	S(i,j)
41	42	68.0621	29	37	36.8532	31	44	27.9913	42	48	22.9507	41	51	19.4778
41	43	63.6536	39	50	36.5181	42	47	27.9809	47	54	22.8799	45	52	19.3400
41	56	63.3972	28	47	36.4078	39	44	27.9762	31	49	22.6940	36	52	19.2480
42	43	62.8608	47	57	35.8945	30	48	27.8623	37	52	22.3880	53	57	19.2268
42	56	59.0185	33	41	35.6007	52	54	27.8190	42	55	22.2730	43	51	19.0821
31	55	57.6940	33	43	35.5528	32	40	27.8017	46	54	22.1676	47	56	18.9656
43	56	57.3903	29	36	35.4205	40	50	27.6683	42	44	22.1596	34	46	18.9443
36	37	57.3113	33	42	35.2728	32	56	27.1164	49	51	22.0873	46	57	18.8401
50	55	57.2420	44	49	35.2332	35	38	27.0650	39	49	22.0067	33	44	18.7731
36	47	53.6286	31	32	34.6134	45	57	27.0231	38	54	21.9287	50	51	18.7043
49	56	50.9153	33	56	34.5702	36	45	26.8519	51	56	21.2813	32	42	18.6498
37	47	48.9414	50	56	34.5634	41	50	26.8018	35	57	21.1259	42	51	18.4616
37	57	47.1936	55	56	34.4108	52	57	26.7638	32	41	21.0759	33	51	18.4095
31	38	45.1658	29	47	34.1846	36	41	26.7619	32	38	20.9514	33	50	18.3314
32	50	44.2695	32	39	33.9341	36	54	26.5089	45	54	20.9122	34	57	18.3286
32	55	43.8214	35	53	33.6993	28	33	26.5084	28	49	20.7590	46	53	18.3277
31	39	43.4374	29	57	33.5787	39	40	26.5028	28	57	20.7402	30	43	18.3156
41	49	43.3067	29	48	32.6515	30	37	26.0850	41	48	20.6293	30	41	18.2731
39	55	42.4264	32	49	32.2472	45	47	26.0680	40	49	20.5802	53	55	18.2578
47	48	41.2168	38	55	32.1366	28	30	26.0269	30	57	20.4731	28	45	18.1392
36	48	41.1915	37	54	32.1083	36	43	25.9451	43	48	20.4435	52	53	17.7874
31	50	41.1771	28	37	31.5109	41	55	25.6240	29	52	20.4157	38	40	17.7227
54	57	41.0544	28	56	31.3127	40	44	25.5381	30	45	20.3977	47	52	17.7227
36	57	41.0354	38	39	31.2587	45	48	25.5381	46	52	20.3225	32	51	17.5965
43	49	40.5453	28	48	31.2024	31	40	25.2309	35	46	20.2638	31	56	17.4719
28	42	40.4849	48	57	30.7658	41	47	25.1086	37	41	20.2093	51	55	17.1124
44	50	40.2972	44	56	30.3183	43	47	24.5818	35	52	20.1283	39	56	17.0843
42	49	39.9539	35	54	30.0463	41	44	24.5708	48	54	20.0478	33	36	17.0725
49	50	39.5047	36	42	29.9707	43	50	24.5586	34	54	19.9891	33	47	16.9454
37	48	39.2147	53	54	29.6901	29	54	24.2444	36	56	19.9785	34	35	16.8474
44	55	38.4452	33	49	29.2325	29	30	23.7569	30	42	19.9241	48	52	16.7299
49	55	38.4353	31	53	29.1691	42	50	23.7510	39	53	19.8529	40	56	16.6485
28	41	37.7289	40	55	28.2843	28	29	23.2313	31	35	19.7521	33	55	16.2195
32	44	37.7201	30	47	28.2052	38	50	23.0814	37	43	19.7246	38	44	15.9186
28	36	37.6963	37	45	28.1300	43	44	23.0781	34	52	19.6700	32	33	15.6770
38	53	37.5558	29	45	28.1091	37	42	23.0739	44	51	19.6193	29	42	15.6112
28	43	37.1704	30	36	28.0072	43	55	22.9651	32	43	19.5687	48	56	15.5873

Закінчення таблиці 3.1

i	j	S(i,j)	i	j	S(i,j)	i	j	S(i,j)	i	j	S(i,j)	i	j	S(i,j)
34	37	15.0898	46	48	10.5827	36	51	5.8629	30	32	2.3162	40	48	0.6256
33	48	15.0106	47	49	10.5787	31	57	5.6454	46	50	2.2356	44	45	0.6256
34	53	14.9515	33	40	10.5691	38	51	5.5212	48	50	2.1931	36	40	0.6004
30	33	14.8596	41	57	10.4782	30	35	5.5128	33	38	2.1862	34	44	0.5323
37	46	14.7355	43	57	10.4197	54	55	5.4918	52	55	2.1627	29	50	0.4867
35	37	14.6880	43	45	10.2974	48	51	5.4884	49	57	2.1199	32	37	0.4791
30	56	14.4661	41	45	10.2153	28	46	5.1670	33	54	2.1030	39	45	0.4473
29	34	14.2970	28	44	10.2023	29	38	5.0536	51	53	2.0942	40	57	0.4394
37	56	14.2593	38	49	10.1753	38	45	4.9432	38	42	1.9379	31	36	0.3211
34	45	14.1421	29	33	10.0711	29	49	4.7492	34	43	1.9280	29	39	0.3029
40	51	14.1421	31	43	10.0577	35	44	4.5845	32	47	1.9277	37	39	0.2930
31	54	13.9169	39	42	10.0462	42	54	4.4961	34	41	1.8169	35	42	0.2826
38	46	13.7751	29	53	9.9658	42	52	4.4185	34	40	1.7815	29	32	0.2818
29	41	13.6744	35	47	9.5982	28	40	4.2918	30	55	1.7442	30	39	0.2780
29	43	13.6553	29	56	9.5900	34	39	4.0764	32	36	1.7091	44	52	0.2758
29	46	13.5882	28	52	9.5886	46	55	3.9580	42	46	1.6427	46	56	0.2381
35	39	13.4626	28	50	9.4756	39	52	3.9452	32	48	1.5881	45	50	0.2233
45	46	13.2809	45	53	9.3546	37	51	3.8564	31	37	1.5810	49	52	0.2135
33	37	13.0506	30	49	9.1476	30	44	3.8207	52	56	1.5747	35	56	0.1805
30	54	13.0344	31	42	9.1461	30	53	3.7478	28	53	1.5689	41	53	0.1787
34	36	12.8404	33	39	8.9082	49	53	3.7323	37	44	1.5430	51	52	0.1675
40	41	12.7876	48	49	8.8748	44	47	3.6096	28	31	1.4901	33	53	0.1648
42	57	12.5850	31	46	8.8421	36	38	3.5959	31	45	1.4806	31	48	0.1561
37	53	12.3906	35	48	8.8104	43	52	3.5473	35	49	1.4561	31	47	0.1432
39	51	12.3822	36	53	8.7668	41	52	3.4200	40	52	1.4515	32	57	0.1322
50	53	12.3407	30	34	8.6653	36	44	3.3925	33	34	1.4037	37	55	0.1117
29	35	12.2801	44	53	8.1161	45	49	3.3805	47	55	1.3449	32	45	0.1104
38	52	12.2062	33	45	7.9258	43	54	3.3662	32	34	1.3329	43	53	0.1102
30	52	12.1811	39	54	7.7859	41	54	3.2455	29	31	1.3161	35	43	0.0985
38	57	12.1504	31	33	7.6472	28	35	3.0969	53	56	1.3099	37	40	0.0600
36	46	12.1459	30	46	7.6096	40	54	3.0818	51	57	1.2760	35	41	0.0598
40	43	12.0179	28	32	7.5016	29	51	3.0648	44	46	1.2018	50	57	0.0583
39	41	11.9806	28	55	7.4354	44	48	3.0473	34	50	1.1979	46	49	0.0471
34	47	11.9258	47	53	7.3008	30	50	2.9629	43	46	1.1900	39	47	0.0422
28	51	11.7909	35	50	7.2619	38	41	2.9449	30	40	1.1653	44	57	0.0390
42	45	11.7278	35	40	7.1699	40	46	2.8503	36	55	1.1280	29	55	0.0379
32	53	11.6336	32	35	7.0953	38	47	2.7635	54	56	1.1169	33	35	0.0272
35	45	11.5544	45	56	7.0208	47	50	2.7001	44	54	1.1045	29	40	0.0236
34	48	11.5106	33	57	6.9313	32	54	2.6496	41	46	1.0907	39	48	0.0227
31	41	11.3594	37	49	6.8610	28	39	2.5928	30	38	1.0441	46	51	0.0221
40	42	11.2115	31	52	6.8316	50	54	2.5799	29	44	1.0415	34	51	0.0216
35	55	11.2099	48	53	6.6129	33	52	2.5357	48	55	1.0339	28	38	0.0213
35	36	11.1211	31	34	6.4017	38	48	2.5302	32	52	1.0045	34	49	0.0187
31	51	11.0993	37	38	6.3107	38	43	2.5135	50	52	0.8703	42	53	0.0128
46	47	11.0877	56	57	6.3059	36	50	2.4800	35	51	0.8419	51	54	0.0113
39	43	10.9268	30	51	6.2582	34	42	2.4689	37	50	0.8203	49	54	0.0081
28	54	10.9259	28	34	6.2134	39	57	2.4346	33	46	0.8068	30	31	0.0059
40	53	10.8522	38	56	6.1049	34	55	2.4264	55	57	0.7904	36	39	0.0049
34	38	10.7533	47	51	6.0807	32	46	2.3678	40	47	0.7567	40	45	0
36	49	10.6995	39	46	5.8824	45	51	2.3402	34	56	0.6753	45	55	0

Побудова Гамільтонового циклу

Таблиця 3.3.2. Гамільтонов цикл

Вузол	X	Y
0	40	40
42	15	14
41	12	17
43	16	19
56	6	25
49	12	38
50	15	56
55	10	70
31	31	76
38	47	66
53	55	57
35	55	50
54	67	41
57	65	27
37	60	15
36	54	10
47	50	15
48	48	21
29	52	26
45	50	30
30	43	26
28	35	16
33	26	29
44	21	48
32	22	53
39	30	60
40	30	50
51	29	39
52	54	38
46	51	42
34	50	40
0	40	40

Графічне представлення Гамілтонового циклу

Рис.3.3.3.1

3.4 Формування маршрутів транспортних засобів з вантажомісткістю D_max на основі результатів 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.4.1 Для 1-ї програми сумарних замовлень:

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

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

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

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

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

Дані для розрахунку матриці рішень:

3 Формування симетричної матриці відстаней між заданними вузлами. Графічна візуалізація простору вузлів з іх відповідною нумерацією.

Графічна візуалізація простору вузлів

Побудова Saving-таблиці відстаней

Побудова Гамільтонового циклу

Графічне представлення Гамілтонового циклу

3.4 Формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі результатів saving-алгоритму

3.4 Формування маршрутів транспортних засобів з вантажомісткістю D_max на основі результатів saving-алгоритму