6 Мінімізація порожніх пробігів автомобілів

Припустимо, що після призначення маятникових маршрутів зі зворотнім вантажним пробігом зісталася деяка кількість вантажів, що треба доставити в одному напрямку, на підставі яких в табл. 6 (приклад 1) і табл. 7 (приклад 2) складені початкові плани їх перевезення.

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

Якщо ці вантажі перевозити маятниковими маршрутами зі зворотним порожнім пробігом, то не ефективно будуть використовуватися транспортні засоби, коефіцієнт пробігу β буде складати лише 0,5. Тому необхідно розглянути можливість формування кільцевих маршрутів.

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

6.1 Складання оптимального плану повернення порожніх автомобілів

В табл. 8 приведений вихідний план перевезення вантажів, у якому наведені ресурси постачальників і потреби споживачів, а також мінімальні відстані між пунктами транспортної мережі. Цей план одночасно є вихідним планом повернення порожніх автомобілів у пункти завантаження постачальників після розвантаження їх у вантажоприємних пунктах споживачів.

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

l_х=Σl_ij z_ij → min,

де z_ij – число їздок.

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

Таблиця 8

Вихідний план повернення порожніх автомобілів

Постачальники		Споживачі						Вивоз, т
		5	6	7	8	9	10
	Потен-ціали
1		8	20	5	15	16	9	180
2		3	11	8	11	6	14	140
3		15	4	15	9	10	17	220
4		16	12	12	4	15	11	200
Ввоз, т		140	200	220	60	40	80	740

До постачальника 1 менша за всіх відстань від споживача 7 – 5 км, тому у першому рядку весь вантажопотік порожняка 180 т відправляємо від споживача 7 до постачальника 1.

У другому рядку – до постачальника 2 всі 140 т від споживача 5, тому що між ними сама коротша відстань – 3 км.

У третьому рядку до постачальника 3 менша за всіх відстань 4 км від споживача 6, тому повертаємо максимальний вантажопотік, який прибуде до його - 200 т до постачальника 3, а недостатні 20 т до потрібних йому 220 т

Таблиця 9

Початковий план повернення порожніх автомобілів

Постачаль- ники	Потен- ціали	Споживачі						Вивоз, т
		5	6	7	8	9	10
	Стовпц Рядків	0	-6	-3	-11	0	-4
1	8	8 0	20	5 180	15	16	9	180
2	3	3 140	11	8	11	6	14	140
3	10	15	4 200	15	9	10 20	17	220
4	15	16	12	12 40	4 60	15 20	11 80	200
Ввоз, т		140	200	220	60	40	80	740

можна було б додати від споживача 8 до якого 9 км, але ресурс обсягу порожніх автомобілів споживача 8 вигідніше відправити до постачальника 4 до якого лише 4 км, тому 20 т недостатніх постачальнику 3, направляємо від споживача 9, хоча до його 10 км.

У четвертому рядку весь ресурс порожніх автомобілів споживача 8 в кількості 60 т відправлений постачальнику 4.

Від споживача 9 направлено лише 20 т до постачальника 3, а весь його ресурс - 40 т, тому останні 20 т відправимо постачальнику 4, не глядачі на те, що відстань до нього 15 км. Не використані 40 т ресурсу порожняка споживача 7, а також весь ресурс 80 т споживача 10 також відправляємо постачальнику 4. Таким образом в табл. 9 складений початковий (припустимий) план повернення порожніх автомобілів.

Перевірка на оптимальність початкового плану повернення порожняка

Тут можливі два варіанти:

1. Потенціали де яких не завантажених кліток більше відстані

u + v > c,

тоді план не оптимальний і його треба поліпшити.

2. Потенціали всіх не завантажених кліток менше відстані

u + v < c.

це означає, що план повернення порожних автомобілів оптимальний.

Розглянемо варіант 1, коли u + v > c

В цьому випадку потрібно поліпшити|покращання| план повернення порожніх автомобілів в такої послідовності.

Рішення задачі можливе при дотриманні деяких умов.

Умова 1. Число завантажених кліток|клітин| в матриці повинне бути рівне

т + п – 1,

де т, п - число рядків і стовпців.

У нашому прикладі|зразку| т = 5, п = 3, отже, т + п - 1 = 5 + 3 - 1 = 7,

а в матриці тільки|лише| 6 завантажених кліток|клітин|.

Якщо число завантажених кліток|клітин| більше (т + п –1), то план складений невірно, і завдання|задачу| вирішити|рішити,розв'язати| не можна. Потрібно скласти новий план, дотримуючись приведеного вище правила.

Якщо число завантажених кліток|клітин| менше ніж (т + п – 1), то завдання|задачу| вирішити|рішити,розв'язати| можна, завантажуючи недостатню кількість кліток|клітин| нульовим (фіктивним) завантаженням|загрузкою|. Для цього в одну або декілька не завантажених кліток|клітин| проставляють нуль.

Умова 2. Нульове завантаження|загрузку| проставляють в клітках|клітинах| рядка з|із| мінімальним обсягом вантажопотоку|тягаря| і з|із| мінімальною відстанню.

У нашому прикладі|зразку| в табл. 10 рядком з|із| мінімальною кількістю вантажу|тягаря| є рядок А₂, а кліткою|клітиною| з|із| мінімальною відстанню в цьому рядку - А₂Б₃, в яку і проставляємо нуль (нульове завантаження|загрузку|).

Початковий план перевезення вантажів, які залишилися, складений в матричному виді з|із| нульовим (фіктивним) завантаженням представлений|уявлена| в табл. 10|загрузкою|

Таблиця 10

Початковий план перевезення вантажів, які залишилися.

Матриця з|із| нульовим (фіктивним) завантаженням|загрузкою|

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців Рядків
Постачальники	А1		5	3	2 300	6	12	300
	А2		4 200	9	4 0	8	9	200
	А3		3 100	8 100	4	2 200	9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

Наступним|таким| етапом рішення задачі є|з'являється,являється| обчислення|підрахунок| потенціалів рядків і стовпців, що містять|утримують| завантажені клітки|клітини|, керуючись наступним|таким| правилом.

Правило 1. Сума потенціалів рядка і стовпця завантаженої клітки|клітини| повинна дорівнювати відстані, проставленій в цій клітці|клітині|:

u_i + v_j =с_ij

Потенціали рядків і стовпців знаходимо|находимо| так. Довільно першому стовпцю, наприклад Б_1, привласнюємо нульовий потенціал. Тоді потенціали рядків А₂ і А₃ будуть дорівнювати

u₂ = с₂₁ – v₁ = 4 – 0 = 4,

u ₃ = с₃₁ – v₁ = 3 – 0 = 3,

оскільки|тому що| відстань в клітці|клітині| А₂Б₁ 4, а в А₃Б₁ - 3. Розглядаємо|розглядуємо| наступну|таку| завантажену клітку|клітину| А₃Б₂, відстань в якій дорівнює 8. Оскільки|тому що| потенціал рядка А₃ - u₃ = 3, то потенціал стовпця Б₂ буде v₂ = 8 – 3 = 5. Аналогічно визначаємо потенціали решти стовпців і рядків, які складають: у|біля,в| стовпців Б₃ = 0; Б₄ = -1; Б₆ = 6 і у|біля,в| рядка А₁ = 2. Обчислені потенціали рядків і стовпців наведені у табл. 11 в додатковому рядку і стовпці.

Таблиця 11

Матриця з|із| визначеними потенціалами рядків і стовпців

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців	0	5	0	-1	6
		Рядків
Постачальники	А1	2	5	3	2 300	6	12	300
	А2	4	4 200	9	4 0	8	9	200
	А3	3	3 100	8 100	4	2 200	9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

Після|потім| визначення потенціалів завантажених кліток|клітин| перевіряємо матрицю на оптимальність по не завантажених клітках|клітинах|.

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

Розглядаємо|розглядуємо| послідовно не завантажені клітки|клітини|. Першою такою кліткою|клітиною| є|з'являється,являється| клітка|клітина| А₁Б₁, відстань якої рівна 5 км. Ця клітка|клітина| має потенціали рядка 2 і стовпця 0. Оскільки|тому що| 2 + 0 < 5, то клітка|клітина| не є|з'являється,являється| потенційною. Наступною|такою| не завантаженою кліткою|клітиною| є|з'являється,являється| клітка|клітина| А₁Б₂, відстань в якій 3 км., а потенціали рядка і стовпця 2 і 5, сума яких 2 + 5 = 7 буде більше відстані, проставленої в цій клітці|клітині|. Потенціал цієї клітки|клітини| буде дорівнювати різниці між сумою потенціалів рядка та стовпця і відстанню в клітці|клітині|

П₁ = (2 + 5) - 3 = 4.

Потенціал не завантаженої клітки|клітини| проставлено в клітці|клітині| в дужках.

Перевіряємо послідовно решту не завантажених кліток|клітин| і встановлюємо, що в матриці є |наявний| ще одна потенційна клітка|клітина| А₂Б₅ з|із| потенціалом

П₂ = 4 + 6 - 9 = 1.

У одній матриці може бути декілька потенційних не завантажених кліток|клітин|. Виявлені потенційні вільні клітки|клітини| представлені|уявлені| в табл. 12.

Таблиця 12

Матриця з|із| виявленими потенційними вільними клітками|клітинами| А₁Б₂ і А₂Б₅

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців	0	5	0	-1	6
		Рядків
Постачальники	А1	2	5	3 (4)	2 300	6	12	300
	А2	4	4 200	9	4 0	8	9 (1)	200
	А3	3	3 100	8 100	4	2 200	9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

Наявність потенційних кліток|клітин| в матриці свідчить про те, що складений план повернення порожніх автомобілів не є|з'являється,являється| оптимальним і може бути покращений. Поліпшення|покращання| плану повернення порожніх автомобілів проводиться|виробляється,справляється| за допомогою контурів.

Правило 3. Контур є замкнутою ламаною лінією, що складається з відрізків вертикальних і горизонтальних прямих, вершини контуру знаходяться|перебувають| в завантажених клітках|клітинах|. Спочатку складається контур для|з'являється,являється| клітки|клітина| з|із| найбільшим потенціалом.

- Відрізки контуру повинні проходити через можливо більше число завантажених кліток|клітин|, але|та| не менше трьох|клітину|;

- лінії контуру повинні замкнутися в потенційній клітці|клітині|, з|із| якої контур взяв свій початок;

- кути|роги,кутки| контуру повинні лежати тільки|лише| в завантажених клітках|клітинах|;

- кут|ріг,куток| перегину повинен бути прямим, тобто складати 90°;

- кутам|рогам,куткам| контуру поперемінно привласнюються позначки плюс і мінус, причому перший плюс ставиться в потенційній клітці|клітині|.

У матриці для|із| кожної потенційної клітки|клітини| можна побудувати|спорудити| тільки|лише| один контур. У таблиці 13 побудований|споруджений| контур для даного випадку.

Наступним|таким| етапом рішення задачі є|з'являється,являється| пошук|відшукування| мінімального завантаження|загрузки| клітки з позначкою мінус|клітинах| кута контуру. Найменше завантаження|загрузка| в 100 одиниць знаходиться|перебуває| в клітці|клітині| А₃Б₂. Мінімальне завантаження|загрузку| 100 одиниць переносимо з|із| клітки|клітини| з|із| позначкою мінус в клітку|клітину| з|із| позначкою плюс і додаємо|добавляємо| до того завантаження, яке вже там було|наявний|. Потім з|із| наступної|такої| клітки|клітини| з|із| позначкою мінус віднімаємо|відтинаємо| це число і переносимо далі по лінії контуру в клітку|клітину| з|із| позначкою плюс і так далі до потенційної клітки|клітини|.

Таблиця 13

Матриця з|із| контуром, побудованим|спорудженим| для потенційної вільної клітки|клітини| А₁Б₂

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців	0	5	0	-1	6
		Рядків
Постачальники	А1	2	5	+ 3 (4)	- 2 300	6	12	300
	А2	4	- 4 200	9	4 + 0	8	9 (1)	200
	А3	3	+ 3 100 +	- 8 100	4	2 200	9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

Перенесемо цифру 100 з|із| клітки|клітини| А₃Б₂ (-) в клітку|клітину| А₃Б₁ (+) і додамо|добавимо| її до тієї величини, яка в ній була|наявний|. Тоді завантаження|загрузка| в клітці|клітині| А₃Б₂ не буде, а в клітці|клітині| А₃Б₁ стане 200 одиниць. З|із| клітки|клітини| А₂Б₁ (-) вантаж 100 одиниць переносимо в клітку|клітину| А₂Б₃ (+), тоді в кожній з них опиниться завантаження |загрузка| 100 одиниць. З|із| клітки|клітини| А₁Бз (-) переносимо вантаж 100 одиниць в клітку|клітину| А₁Б₂. В|із| клітки|клітини| А₁Бз залишається вантаж|загрузка| 200 одиниць, а в клітці |клітину| А₁Б₂ появиться вантаж 100 одиниць.

Частково поліпшений план повернення порожніх автомобілів представлений|уявлений| в табл. 14.

В результаті|унаслідок,внаслідок| проведених дій відбулося наступне|слідуюче|: при перенесенні|переносі| 100

Таблиця 14

Частково поліпшений план повернення порожніх автомобілів

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців
		Рядків
Постачальники	А1		5	3 100	2 200	6	12	300
	А2		4 100	9	4 100	8	9 (1)	200
	А3		3 200	8	4	2 200	9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

одиниць з|із| клітки|клітини| А₃Б₂ в клітку|клітину| А₃Б₁ відстань перевезення зменшилася на 5 км (8 – 3 = 5); при перенесенні|переносі| цифри 100 з|із| клітки|клітини| А₂Б₁ в клітку|клітину| А₂Б₃ відстань не змінилася; при перенесенні|переносі| 100 одиниць з|із| клітки|клітини| А₁Б₃ в клітку|клітину| А₁Б₂ відстань збільшилася на 1 км.: 3 - 2 = 1. Таким чином, загальне|спільне| зменшення відстані перевезення 100 одиниць вантажу|тягаря| склало 5 – 1 = 4 км., тобто воно чисельно рівне величині потенціалу потенційної клітки|клітини|, з|із| якої контур узяв свій початок.

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

Продовжуємо поліпшення|покращання| план повернення порожніх автомобілів. Перевіряємо число завантажених кліток|клітин|. Воно дорівнюе 7, тобто відповідає правилу

m + n – 1 = 3+5 – 1 = 7.

Аналогічно попередньому порядку|ладу| обчислюємо потенціали рядків і стовпців завантажених кліток|клітин| за формулою

u_i + v_j = a_ij

і заносимо їх в матрицю табл. 15. Змінився потенціал лише у|біля,в| стовпця Б₂.

Знову перевіряємо матрицю на потенційність і встановлюємо, що в ній є|наявний| тільки|лише| одна потенційна клітка|клітина| А₂Б₅ з|із| потенціалом, рівним 1 (табл. 15 ). Будуємо контур, який вийде з клітки|клітини| А₂Б₅, піде в клітки|клітини| А₃Б₅, А₃Б₁, А₂Б₁ і замкнеться в клітці|клітині| А₂Б₅. На вершинах контуру проставляємо знаки плюс і мінус, причому перший плюс ставиться в потенційній клітці|клітині|.

Таблиця 15

Матриця з|із| контуром, побудованим|спорудженим| для потенційної вільної клітки|клітини| А₂Б₅.

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу|тягаря|, т
Потенці- али		Стовпців	0	1	0	-1	6
		Рядків
Постачальники	А1	2	5	3 100	2 200	6	12	300
	А2	4	_ 4 100	9	4 100	8	+ 9 (1)	200
	А3	3	+ 3 200	8	4	2 200	_ 9 100	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000

Розглядаємо|розглядуємо| вершини контуру з|із| позначкою мінус. Встановлюємо величину мінімального завантаження|загрузки|, яке складає 100 одиниць в клітках А₂Б₁ і А₃Б₅. З|із| однієї будь-якої клітки|клітини| з|із| позначкою мінус (наприклад|нехай| А₂Б₁) переносимо вантаж|тягар| 100 в клітку|клітину| А₂Б₅ (+), тоді завантаження|загрузка| в ній буде 100 одиниць. З|із| клітки|клітини| А₃Б₅ (-) завантаження 100 одиниць переносимо в клітку|клітину| А₃Б₁ |клітинах|

Новий план повернення порожніх автомобілів показаний в матриці 16. Перевіряємо його число завантажених кліток|клітин|. У зв'язку з тим, що число завантажених кліток|клітин| на одиницю менше за необхідне, вводимо|запроваджуємо| нульове завантаження|загрузку| в клітку|клітину| А₂Б₁. Визначаємо потенціали рядків і стовпців. Перевіряємо матрицю на оптимальність. У табл. 16 немає потенційних кліток|клітин|, що свідчить про отримання|здобуття| оптимального плану повернення порожніх автомобілів.

Таблиця 16

Оптимальний план повернення порожніх автомобілів

Споживачі			Б1	Б2	Б3	Б4	Б5	Вивоз вантажу,|тягаря| т
Потенці- али		Стовпц.	0	1	0	-1	6
		Рядків
Постачальники	А1	2	5	3 100	2 200	6	12	300
	А2	4	4 0	9	4 100	8	9 100	200
	А3	3	3 300	8	4	2 200	9	500
Ввоз вантажу|тягарі|, т			300	100	300	200	100	1 000