А.Ю. Тюрин Методы организации работы автомобильного транспорта. Методические указания к практическим занятиям по курсу Транспортно-технологические системы

10

Таблица 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
ент

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

	11
Маршрут	Объем перевозок, т
А1 – В3 – А1	41
А4 – В5 – А4	24
А1 – В1 – А1	32
А2 – В1 – А2	42
А4 – В2 – А4	28

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

В нашем случае такому контуру соответствует маршрут

А1 В1 — В1 А2 — А2 В4 — В4 А4 — А4 В7 — В7 А1.

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

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

12

13

А1 В2 — В2 А4 — А4 В7 — В7 А1 - 5т.

14

Практическое занятие № 2 Маршрутизация мелкопартионных перевозок (метод Кларка-Райта)

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

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

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

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

15

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

Рассмотрим решение данной задачи на примере: имеется 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.

Таблица 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. Этот элемент соответствует объеди-

16

нению маршрутов Р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 т). Такой автомобиль имеется, поэтому объединение возможно.

Таблица 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). Эти изменения в нашем примере вносят в исходную матрицу. Кроме того, необходимо следить за изменением числа свободных и занятых автомобилей различной грузоподъемности.

17

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

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

Теперь максимальному выигрышу (44 км) соответствует объедине-

ние маршрутов Р0 - Р6 - Р0 и Р0 - Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р6 - Р5 - Р8 - Р4 - Р0. Объем перевозок на маршруте при этом станет 0,17+2,87=

=3,04 т (табл. 2.5).

Таблица 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

Таблица 2.5

Выигрыши при объединении пунктов

Потр., т	I
0,89	2	P1
0,79	2	22	P2
0,84	2	19	27	P3
2,87	1	17	21	34	P4
2,87	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
	0	30	32	46	0	0	50	42	P8

На следующих этапах объединяют маршруты Р0 - Р2 - Р0 и Р0 - Р6 -

Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р0 (выигрыш

36

км) и Р0 - Р7 - Р0 и Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р0 в развозочный Р0 - Р2 - Р6 -

18

Р5 - Р8 - Р4 - Р7 - Р0 (выигрыш 32 км). В первом случае объем перевозок на маршруте составит 0,79+3,04= 3,83 т (табл. 2.6), а во втором случае – 0,61+3,83=4,44 т (табл. 2.7). Дальнейшее объединение маршрутов невозможно, так как отсутствует автомобиль грузоподъемностью более

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

На следующем этапе объединяют оставшиеся маршруты Р0 - Р1 - Р0

и Р0 - Р3 - Р0 в развозочный Р0 - Р1 - Р3 - Р0 (выигрыш 19 км). Объем перевозок на маршруте при этом станет 0,89+0,84= 1,73 т (табл. 2.8). Так

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

Таблица 2.6

Выигрыши при объединении пунктов

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

Таблица 2.7

Выигрыши при объединении пунктов

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

19

Таблица 2.8

Выигрыши при объединении пунктов

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

Вместо использованных выигрышей и тех, которые не удалось использовать, в табл. 2.4-2.8 проставляют нули.

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

В качестве исходных данных необходима матрица кратчайших расстояний между точками маршрута. Для маршрута № 1 (Р0 - Р2 - Р6 - Р5 - Р8 - Р4 - Р7 - Р0) она приведена в табл. 2.9.

		Матрица кратчайших расстояний					Таблица 2.9
Пункты		Кратчайшие расстояния между пунктами, км
	P0	P2	P6	P5	P8	P4		P7
P0		15	23	30	30	25		19
P2	15		2	10	13	19		7
P6	23	2		9	3	11		11
P5	30	10	9		5	4		6
P8	30	13	3	5		3		7
P4	25	19	11	4	3			12
P7	19	7	11	6	7	12
СУММА	142	66	59	64	61	74		62

В итоговой строке табл. 2.9 проставляют сумму расстояний в каждом столбце. Затем выбирают три начальных пункта, имеющих максимальные суммы в столбцах (пункты 0, 4 и 2). Они образуют кольцевой маршрут 0 - 4 - 2 - 0. В него включают следующий пункт с максимальной суммой в столбце - пункт 5. Чтобы определить, между какими пунктами его следует вставить, необходимо найти минимально воз-