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

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

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

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

 

 

Показники ефективності завантаження транспортних засобів

 

Рис. 3.7.4

 

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

Визначення загальної кількості  маршрутів R, що відповідає необхідній кількості транспортних засобів, довжини  кожного маршруту L_r, r=1,...,R, кількості перевезеного вантажу та залишкової кількості вантажу DD_r=D_max- на кожному з маршрутів, сумарну довжину всіх маршрутів L_S= _r , та при повній реалізації кожної з програм F1, F2, F3 а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:

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

 

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

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому  маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0 - 55 - 39 - 31 - 38 – 53-  35- 46 - 54 -  0	170.7219	13.8800	0.6200	515.3201
Route2	0 -  34 - 52 -57 – 45-  29 - 37 - 36 -  0	104.3153	12.8500	1.6500
Route3	0-  48 - 47 - 30 - 28 -42- 43- 41 -33 – 56- 0	158.4526	12.4300	2.0700
Route4	0 - 51 - 49 - 44 -50 -32 - 40 -  0	81.8303	10.0900	4.4100

 

 

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

 

 

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

Рис.3.8.1 

 

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

 

Таблиця 3.8.2

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому  маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0  -  29 -   37 -   36 -   48 -    0	72.9963	14.3000	0.2000	593.4975
Route2	0 -  47 - 30 -  28 -  42  -  43 -   41 -   33 -  0	118.6850	14.0600	0.4400
Route3	0 -  56 -  51 -  49  - 44  - 50 -  32 -  0	134.3900	14.5000	0
Route4	0  -  40 -  55 -  39 –  31 -  38  -  0	126.6121	13.9000	0.6000
Route5	0  - 53 -   35 -  46  -  54  -  34 -   0	81.6764	12.7900	1.7100
Route6	0 -  52 -  57 -  45  - 0	59.1377	7.2500	7.2500

 

 

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

   

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

Рис.3.8.2

 

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

 

Таблиця 3.8.3

№ маршру-та	Шлях маршруту	Довжина маршруту	К-ть товару, що можно розвести на цьому маршр.	Залишок товару	Сумарна довжину всіх маршр.
Route1	0  -  49  -  44  -  50   -  0	81.2066	11.2400	3.7600	921.143
Route2	0  -  32-  40  -   0	44.8897	13.6700	1.3300
Route3	0  -  55 -   39  -   0	87.1478	11.7100	3.2900
Route4	0  -  31 -   38 -   0	82.9017	9.1400	5.8600
Route5	0  -  53 -   35 -    0	47.6993	11.2100	3.7900
Route6	0 -   46  -  54 -  0	54.2301	13.2000	1.8000
Route7	0  -  34  -  52 -   57 -  0	58.2065	9.6700	5.3300
Route8	0  -  45 -  0	28.2843	7.8700	7.1300
Route9	0  -  29 -    0	36.8782	7.7900	7.2100
Route10	0 -   37 -    0	64.0312	8.3000	6.7000
Route11	0 -  36 -   48 -  0	66.2514	13.8700	1.1300
Route12	0 -  47 -  30 -  0	54.2820	9.3400	5.6600
Route13	0 -   28 -  42  -  0	80.6844	13.8800	1.1200
Route14	0 -   43 -   41 -   33 -   56 -   0	112.3595	11.8700	3.1300
Route15	0 -   51 -  0	22.0907	8.0300	6.9700

 

  

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

 

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

Рис.3.8.4

 

3.9. Порівняльний аналіз всіх маршрутів

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

Таблиця 3.9.1

Алгоритм формування            маршрутів	saving - алгоритм	модифікований saving - алгоритм	sweeping – алгоритм	sweeping – алгоритм
Загальних довжин всіх маршрутів, L	465.3944	466.6301	545.9569	515.3201
Показник ефективності, E	0.7073	0.9375	0.9414	0.9002

 

З табл. 3.9.1 видно, що найкращий результат для програми F₁ дав saving - алгоритм, за допомогою нього було сформовано маршрути загальною довжиною 465.3944. Ефективність перевезень найвища за зміненим sweeping алгоритмом ,а за saving алгоритмом складає 0.7073.  

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

Таблиця 3.9.2

Алгоритм  формування            маршрутів	saving - алгоритм	модифікований saving - алгоритм	sweeping – алгоритм	sweeping – алгоритм
Загальних довжин всіх маршрутів, L	551.5605	550.3604	627.3166	593.4975
Показник ефективності, E	0.9070	0.8931	0,8808	0.9593

 

З табл.3.9.2 видно, що найкращий результат для програми F₂ дав модифікований saving - алгоритм, за допомогою нього було сформовано маршрути загальною довжиною 550.3604. Ефективність перевезень найвища за зміненим sweeping алгоритмом ,а за модифікованим saving алгоритмом складає 0.9375.

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

 

 

 

 

Таблиця 3.9.3

Алгоритм формування            маршрутів	saving - алгоритм	модифікований saving - алгоритм	sweeping – алгоритм	sweeping – алгоритм
Загальних довжин всіх маршрутів, L	898.3837	895.1035	934.2895	921.143
Показник ефективності, E	0.8180	0.8180	0.7510	0.7525

 

З табл. 3.9.3 видно, що найкращий результат для програми F₃ дав модифікований saving - алгоритм, за допомогою нього було сформовано маршрути загальною довжиною 895.1035, з ефективністю перевезень 0.8180.

 

4 ОПТИМІЗАЦІЯ МАРШРУТІВ НА ОСНОВІ  РОЗВ’ЯЗАННЯ TSP ТА ВИБІР НАЙКРАЩИХ МАРШРУТІВ

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

Використовуємо такий алгоритм розрахунку:

На кожному кроці за початковими  тарифами Cij визначаємо значення величин середніх тарифів рядків (С_pi) та колонок (C_Kj) і осереднені коефіцієнти (K_ij). По найменшому значенню осередненого коефіцієнта K_ij обираємо комірку оптимального шляху комівояжера і записуємо її дані:

номер кроку;

адреса комірки оптимального шляху (i,j);

осереднений коефіцієнт K_ij;

 початковий тариф C_ij;

 заборонені рядок і комірка  (вони повторюють номери рядка  і колонки комірки оптимального  шляху). Вони закреслюються і не  використовуються у подальших  розрахунках. У результаті отримуємо  скорочену таблицю для наступного кроку;

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

2. На наступному кроці виконуємо дії п. 1. Коли для відвідин залишається лише два шляхи, то вони входять в оптимальний шлях комівояжера без розрахунків, бо інших варіантів їх обрання не існує. Практично кількість кроків через це скорочується.

Проведемо оптимізацію  маршрутів для всіх програм замовлень.

 

4.1 Програма F₁

В табл.4.1.1 наведено початкові маршрути для програми замовлень F₁.

Таблиця 4.1.1 Початкові маршрути для програми перевезень  F₁

R	Структура маршруту
Route1	0 – 42 – 41 – 43 – 56 – 49 – 50 – 55 – 31 – 38 – 53 - 0	179.2997
Route2	0 – 35 – 54 – 57 – 37 – 36 – 47 – 48 – 0	101.3233
Route3	0 – 29 – 45 – 30 – 28 – 33 – 44 – 32 – 39 – 0	117.3278
Route4	0 – 40 – 51 – 52 – 46 – 34 – 0	67.4436
	L	465.3944

 

В табл. 4.2.2 наведено інформацію про маршрути після ії оптимізації.

Таблиця 4.2.2 Інформація про маршрути для програми F₁

№	Структура маршруту
Route1	0 - 43 - 42 - 41 - 56 - 49 - 50 - 55 - 31 - 38 - 53 - 0	174.0857
Route2	0 - 35 - 54 - 57 - 37 -  36 - 47 – 48 -   0	101.3233
Route3	0 -  45-  29 - 30 - 28 - 33 - 44 - 32 - 39 -  0	113.9686
Route4	0 - 52 - 34 - 46 - 40 - 51 -  0	65.4133
	L	454.7910

 

В результаті оптимізації вдалося  скоротити відстань з 465,3944 до 454,7910, тобто на 10,6034.

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

 

 

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

 

4.2 Програма F₂

В табл. 4.2.1 наведено початкові маршрути для програми замовлень F₂.

Таблиця 4.2.1 Початкові маршрути для програми перевезень  F₂

R	Структура маршруту
Route1	0 - 42 – 41- 43 – 56 –  49 – 50 – 55 -  0	146.3046
Route2	0   - 37 -   36 -   47 -    0	73.1548
Route3	0 -  38 -  31 -  39  -  32 -  44 -   0	98.1697
Route4	0  -  54  -  57  -  29  -  48  -  28 -   33 -    0	108.1464
Route5	0 -  53 -  35 -  46 -  52 -  34 -   0	58.0880
Route6	0  -  45 -   30 -   51 -   40 -    0	66.4969
Всього		550,3604

В табл. 4.2.2 наведено інформацію про  маршрути після ії оптимізації.

Таблиця 4.2.2. Інформація про маршрути для програми F₂

№	Структура маршруту
Route1	0  -  50  -  55 -   49 -  56 -   41  -  42  -  43   -  0	142.1601
Route2	0   - 37  -  36  -  47  -   0	73.1548
Route3	0  -  38  -  31  -  39   - 32  -  44  -   0	98.1697
Route4	0 -   54  -  57  -  29  -  48  -  28 -   33   -  0	108.1464
Route5	0 -  53 -  35 -  46 -  52 -  34 -   0	58.0880
Route6	0  - 45  -  30  -  51 -   40  -   0	66.4969
	Всього	547,5941

В результаті оптимізації вдалося  скоротити відстань з 550,3604 до 547,5941тобто на 2,7663.

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

 

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

 

4.3 Програма F₃

В табл. 4.3.1 наведено початкові маршрути для програми замовлень F₃.

Таблиця 4.3.1. Початкові маршрути для програми перевезень  F₃

R	Структура маршруту
Route1	0  -  42  -  41  -  43 -   0	76.6746
Route2	0  -  31 -   55 -   0	101.3747
Route3	0  -  37 -    0	64.0312
Route4	0 -   36  -   0	66.2118
Route5	0 -   56 -   49 -   50 -    0	99.4096
Route6	0  -  48 -   47  -   0	53.8659
Route7	0  - 54 -   57 -    0	69.3387
Route8	0  -  44 -   32  -   0	47.9182
Route9	0  -  38 -   53 -   35  -   0	63.9952
Route10	0  -  45  -   0	28.2843
Route11	0 -   33  -  28 -   30  -   0	60.7400
Route12	0 -   39  -   0	44.7214
Route13	0  -  29  -  52  -   0	44.7467
Route14	0 -   34  -  46  -   0	23.4164
Route15	0 -   40  -   0	28.2843
Route16	0 -   51 -    0	22.0907
		895.1035