Маршрутизация

10

Таблица 1.8 – План возврата порожних автомобилей

Грузопо-	Коэффи-			Грузоотправитель
лучатель	циенты	А1		А2	А3		А4
	Vj			Коэффициенты Ui
		1,9		1,85	3,33		3,02
В1	0	72	1,90	55 1,85		3,35		3,04
В2	4,76		6,66	10,01	30	8,09	34	7,78
В3	-0,68	41	1,22	2,53		2,67		2,36
В4	6,96	1	8,86	12,21	10,29		12	9,98
В5	-0,02		4,14	7,06		3,31	24 3,00
В6	1,54	48	3,44	5,81		5,69		5,38
В7	5,19	0,53	6,56	8,83	41	8,52		8,21

5. А1 В7

+30		34-
(31)			(33)
			Min = 1
-1			12+
(св)		(13)
+св		41-
(1)		(40)

A1 B7 – B7 A3 – A3 B2 – B2 A4 – А4 В4 – В4 А1

Таблица 1.9 – План возврата порожних автомобилей

Грузопо-	Коэффи-			Грузоотправитель
лучатель	циенты	А1		А2		А3			А4
	Vj			Коэффициенты Ui
		1,9		1,85		3,86			3,55
В1	0	72	1,90	55 1,85	0,51		3,35	0,51		3,04
В2	4,23		6,66	10,01		31	8,09		33	7,78
В3	-0,68	41 1,22		2,53	0,51		2,67	0,51		2,36
В4	6,43		8,86	12,21			10,29		13	9,98
В5	-0,55		4,14	7,06			3,31		24 3,00
В6	1,54	48	3,44	5,81			5,69			5,38
В7	4,66	1	6,56	8,83		40	8,52			8,21

11

6. А3 В1

-72		св+
(32)		(40)
+1		40-
(41)		(св)

Min = 40

A3 B1 – B1 A1 – A1 B7 – B7 A3

Таблица 1.10 – Оптимальный план возврата порожних автомобилей

Грузопо-			Грузоотправитель					Коэффи-
лучатель	А1		А2	А3		А4		циент
В1	32	1,90	55 1,85	40	3,35		3,04	0
В2		6,66	10,01	31	8,09	33	7,78	4,74
В3	41 1,22		2,53		2,67		2,36	-0,68
В4		8,86	12,21		10,29	13	9,98	6,94
В5		4,14	7,06		3,31	24 3,00		-0,04
В6	48	3,44	5,81		5,69		5,38	1,54
В7	41	6,56	8,83		8,52		8,21	4,66
Коэффи-	1,9		1,85	3,35		3,04
циент

Таблица 1.11 – Совмещенный план

Грузопо-			Грузоотправитель						Коэффи-
лучатель	А1		А2		А3		А4		циент
В1	32 1,90		55	1,85	40	3,35		3,04	0
		(85)		(42)
В2		6,66		10,01	31	8,09	33	7,78	4,74
		(36)						(28)
В3	41 1,22			2,53		2,67		2,36	-0,68
		(41)
В4		8,86		12,21		10,29	13	9,98	6,94
				(13)
В5		4,14		7,06		3,31	24 3,00		-0,04
								(24)
В6	48	3,44		5,81		5,69		5,38	1,54
						(48)
В7	41	6,56		8,83		8,52		8,21	4,66
						(23)		(18)
Коэффи-	1,9		1,85		3,35		3,04
циент

12

Цифры в скобках обозначают груженые ездки, цифры без скобок - порожние ездки. Из совмещенного плана выбирают маршруты перевозок грузов в такой последовательности: маятниковые, кольцевые 4-, 6- угольные и пр.

Количество тонн грузов, перевозимых на каждом маятниковом маршруте, определяется меньшей из двух цифр в соответствующих клетках, указывающих объем завоза и потребность в по-

рожних автомобилях:
Маршрут	Объем перевозок, т
А1 – В3 – А1	41
А4 – В5 – А4	24
А1 – В1 – А1	32
А2 – В1 – А2	42
А4 – В2 – А4	28

Примеры графического оформления маятниковых маршрутов показаны на рисунке 2.

1.

2.

3.

4.

5.

+41	-41
А1											В3
	1,22
+24	-24
А4											В5
	3,0
+32	-32
А1											В1
	1,9
+42	-42
А2											В1
	1,85
+28	-28
А4											В2
	7,78

А1 В3 – В3 А1 - 41 т

1,22 0,5 2,44

А4 В5 – В5 А4 - 24 т

3 0,5 6

А1 В1 – В1 А1 - 32 т

1,9 0,5 3,8

А2 В1 – В1 А2 - 42 т

1,85 0,5 3,7

А4 В2 – В2 А4 - 28 т

7,78 0,5 15,56

Рисунок 2 – Схемы маятниковых маршрутов

13

Запланированные на маятниковых маршрутах перевозки (завоз грузов и возврат порожних автомобилей) исключают из матрицы и продолжают составление маршрутов. Когда все маятниковые маршруты найдены, в матрице строят замкнутый контур, все вершины которого лежат в šзагруженныхŸ клетках. Вершины, находящиеся в клетках, где стоят цифры, обозначающие груженые ездки, должны чередоваться с вершинами в клетках, где есть цифры, указывающие на количество порожних ездок.

В нашем случае такому контуру соответствует маршрут А1 В1 – В1 А2 – А2 В4 – В4 А4 – А4 В7 – В7 А1.

Пример графического оформления первого кольцевого маршрута показан на рисунке 3.

6.

+13													-13
А1														В1
					1,9
	6,56												1,85
В7																							А4
-13																							+13
8,21													12,21										9,98
									А2														В4
+13																							-13

А1 В1 – В1 А2 – А2 В4 – В4 А4 – А4 В7 – В7 А1 - 13 т

	1,9 12,21 8,21
	0,55

1,9 1,85 12,21 9,98 8,21 6,56

Рисунок 3 – Схема первого кольцевого маршрута

На нем каждому потребителю должно быть завезено 13 т грузов, так как минимальное значение загрузок по вершинам

14

контура составляет именно 13. Уменьшив цифры в клетках, составляющих выбранный маршрут, на 13 единиц, получим данные для выбора второго кольцевого маршрута. Процесс составления маршрутов считается законченным, когда в матрице не остается ни одной загрузки.

Пример графического оформления второго кольцевого маршрута показан на рисунке 4.

7.

+5														-5
А1															В2
					6,66
		6,56			8,21						7,78
В7															А4
-5														+5
А1 В2 – В2 А4 – А4 В7 – В7 А1 - 5 т
					6,66 8,21										0,51

6,66 7,78 8,21 6,56

Рисунок 4 – Схема второго кольцевого маршрута

Для каждого маршрута необходимо определить коэффициент использования пробега. Если на кольцевом маршруте коэффициент использования пробега = 0,5, то такой маршрут не целесообразен, соответствующие перевозки лучше осуществлять на маятниковых маршрутах.

Примеры графического оформления третьего и четвертого кольцевых маршрутов показаны на рисунке 5, а пятого кольцевого маршрута – на рисунке 6.

15

8.

+40												-40
А1												В1
					1,9
	3,44				5,69				3,35
В6												А3
-40												+40

А1 В1 – В1 А3 – А3 В6 – В6 А1 - 40 т

1,9		5,69
			0,53
1,9 3,35		5,69 3,44

9.

+23														-23
А3															В7
						8,52
	8,09					6,66				6,56
В2															А1
-23														+23
А3 В7 – В7 А1 – А1 В2 – В2 А3 - 23 т
						8,52 6,66
															0,51

8,52 6,56 6,66 8,09

Рисунок 5 – Схемы третьего и четвертого кольцевых маршрутов

16

10.

+8														-8
А3															В6
					5,69
		8,09			6,66						3,44
В2															А1
-8														+8
А3 В6 – В6 А1 – А1 В2 – В2 А3 - 8 т
					5,69 6,66										0,52

5,69 3,44 6,66 8,09

Рисунок 6 – Схема пятого кольцевого маршрута

2.2. Маршрутизация мелкопартионных перевозок (метод Кларка-Райта)

Цель: определить рациональные маршруты при доставке грузов мелкими партиями.

При маршрутизации перевозок с использованием кратчайшей связывающей сети задачи выбора очередности объезда пунктов и их набора, включаемого в маршруты, для перевозки груза автомобилями заданной грузоподъемности решают последовательно. Алгоритм Кларка и Райта предусматривает совмещенное решение задачи маршрутизации перевозок, осуществляемых в общем случае парком автомобилей различной грузоподъемности.

Первым этапом является построение плана, состоящего из маятниковых маршрутов, на каждом из которых предполагается обслуживать одного потребителя. Для каждого такого маршрута назначают автомобиль возможно минимальной грузоподъемности (условно предполагается, что наличный парк автомобилей позволяет это сделать).

17

На каждом последующем шаге два маршрута объединяют в один. В результате объединения двух маятниковых маршрутов появляется один развозочный. Из полученных маятниковых и развозочных маршрутов выбирают такие два, которые после объединения обеспечивают наибольшее сокращение суммарных затрат.

Процесс заканчивают, когда не остается ни одной пары маршрутов, которые целесообразно объединить в один (поскольку в результате объединения уменьшится значение суммарного показателя, либо нет соответствующего для объединения автомобиля).

Рассмотрим решение данной задачи на примере: имеется 8 потребителей груза, потребности завоза которых указаны в первом столбце таблицы 2.1. Выделено пять автомобилей грузоподъемностью 4,5 т (Луаз-890Б) и три автомобиля грузоподъемностью 1,75 т (ГЗСА-3702).

В каждом столбце Рi (таблица 2.1) указывают расстояние от i- го пункта до любого другого (Рi+1, Рi+2...). Так как матрица кратчайших расстояний симметрична, то достаточно одной половины матрицы.

Таблица 2.1 – Расстояния между пунктами

Потр.,	P0
т
0,89	10	P1
0,79	15	3	P2
0,84	20	11	8	P3
0,96	25	18	19	11	P4
1	30	2	10	15	4	P5
0,17	23	6	2	10	11	9	P6
0,61	19	8	7	5	12	6	11	P7
0,91	30	10	13	4	3	5	3	7	P8

Рассчитывают величины, характеризующие выигрыши в расстоянии, которые получают в результате объединения соответствующих маршрутов в один, и заносят их в таблицу 2.2.

18

Таблица 2.2 – Выигрыши при объединении пунктов

Потр.,	P0
т
0,89	10	P1
0,79	15	22	P2
0,84	20	19	27	P3
0,96	25	17	21	34	P4
1	30	38	35	35	51	P5
0,17	23	27	36	33	37	44	P6
0,61	19	21	27	34	32	43	31	P7
0,91	30	30	32	46	52	55	50	42	P8

Расчет выигрыша в расстоянии рассмотрим на примере элемента, стоящего в столбце Р4 и строке Р8. Этот элемент соответствует объединению маршрутов Р0 - Р4 - Р0 и Р0 - Р8 - Р0, в результате которого получается маршрут Р0 - Р4 - Р8 - Р0 .

В новом маршруте вместо расстояния от пункта Р4 к пункту Р0 и от пункта Р0 к пункту Р8 (25 + 30 = 55 км) используют расстояние от пункта Р4 к пункту Р8 (3 км). Следовательно, выигрыш от объединения этих маршрутов в один составляет 55 – 3 = 52 км, что и указано в рассматриваемой клетке.

Поскольку для дальнейших расчетов необходимо знать только величины выигрышей, представляют их отдельно (см. таблицу 2.2). Кроме того, присоединяют к матрице выигрышей отдельный столбец индикаторов (I) пунктов Рi. Величины, стоящие в этом столбце, принимают значения 0; 1 или 2. Индикатор строки Рi показывает, является пункт внутренним (0), первым или последним (1) в некотором развозочном маршруте, или он включается в маятниковый маршрут (2), т.е. маршрут вида Р0 - Рi - Р0.

Из табл. 2.2 видно, что наибольший выигрыш (55 км) достигается при преобразовании (объединении) маятниковых маршру-

тов Р0 - Р5 - Р0 и Р0 - Р8 - Р0 в развозочный Р0 - Р5 - Р8 - Р0 (таблица 2.3). Для развозочного маршрута Р0 - Р5 - Р8 - Р0 требуется ав-

томобиль грузоподъемностью 1,91 т и более (1 + 0,91 = 1,91 т). Такой автомобиль имеется, поэтому объединение возможно.

19

Таблица 2.3 – Выигрыши при объединении пунктов

Потр.,	I
т
0,89	2	P1
0,79	2	22	P2
0,84	2	19	27	P3
0,96	2	17	21	34	P4
1	2	38	35	35	51	P5
0,17	2	27	36	33	37	44	P6
0,61	2	21	27	34	32	43	31	P7
0,91	2	30	32	46	52	55	50	42	P8

После объединения в соответствующих строках меняют элементы первого и второго столбцов. В первых клетках обеих строк записывают число 1,91 (загрузка автомобиля на маршруте Р0 - Р5 - Р8 - Р0). Индикаторы строк Р5 и Р8 примут значение 1 (вместо 2). Эти изменения в нашем примере вносят в исходную матрицу. Кроме того, необходимо следить за изменением числа свободных и занятых автомобилей различной грузоподъемности.

На следующем этапе объединяют в маршрут Р0 - Р5 - Р8 - Р4 - Р0 маршруты Р0 - Р4 - Р0 и Р0 - Р5 - Р8 - Р0. Это объединение дает наибольший теперь выигрыш - 52 км (таблица 2.4). При этом вместо двух автомобилей используют один грузоподъемностью 4,5 т (0,96 + 1,91 = 2,87 т).

Таблица 2.4 – Выигрыши при объединении пунктов

Потр.,	I
т
0,89	2	P1
0,79	2	22	P2
0,84	2	19	27	P3
0,96	2	17	21	34	P4
1,91	1	38	35	35	51	P5
0,17	2	27	36	33	37	44	P6
0,61	2	21	27	34	32	43	31	P7
1,91	1	30	32	46	52	0	50	42	P8

Пункт Р8 является внутренним в принятом маршруте, поэтому в дальнейшем при поиске новых вариантов объединений он не рассматривается, а в столбце индикатора против соответствую-