2.2 Проектирование развозочной транспортной системы

2.2.1. Маршрутизация методом Кларка-Райта

Мелкопартионные перевозки, как правило, выполняются при транспортном обслуживании предприятий торговли и бытовом обслуживании населения.

Особенности мелкопартионных перевозок:

- значительные затраты времени на передачу грузов и погрузочно-разгрузочные работы, часто большие, чем на движение;

- низкие техническая и эксплуатационная скорости на маршрутах, проходящих, как правило, по загруженным магистралям в густозаселенных местах;

- высокие требования к качеству перевозок: гарантия своевременной доставки ("точно в срок"), сохранность грузов;

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

Задачи планирования мелкопартионных перевозок относят к классу задач дискретной оптимизации, так как теоретически возможно перебрать все варианты решений и выбрать лучший из них. Однако, если учесть, что задача объезда 10 пунктов на маршруте будет иметь более 3,5 млн решений, естественно, такой подход к решению задачи нереален.

В связи с этим на практике разработаны и применяются методы, позволяющие сравнительно простыми способами получить решение если не оптимальное, то близкое к нему.

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

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

Δl= l₁+l₂-l₁₂>0. (2.13)

Значит, если есть маршруты, которые можно объединять в соответствии с получаемой при этом "выгодой", то в случае объединения маршрутов с наибольшей "выгодой" можно рассчитывать, что решение будет близко к оптимальному.

В1

В2

В1

В2

Рис.2.1. Эффект "выгоды" от объединения маятниковых

маршрутов в кольцевой маршрут

ООО “ТД Акватория” осуществляет доставку воды со своего склада в магазины, склады и юридическим лицам. Развоз воды осуществляется тарно упаковками по 30 л.

Таблица 2.9.

Исходные данные

Номер получателя	Наименование получателя
0	Липецкая обл., г. Елец, ул. Александровская 16
1	ООО «Аква-Блюз»
2	ООО «Тандем»
3	Магазин «Красные зори», с. Красное
4	ООО «Смак»
5	ООО «Эридан»
6	ООО «Регион-продукт»
7	Дом Быта
8	ООО «Виктория»
9	ООО «Регион-продукт»
10	ООО «Предприятие «Управляющая компания»
11	ЗАО «Липецкнефтепродукт», с. Бабарыкино

Объемы завоза грузов, расстояния от грузоотправителя до получателей и между ними представлены в табл. 3.2. Для перевозки может быть использован подвижной состав грузоподъемностью 1 и 1,5 т. Перевозки необходимо выполнить для 11 пунктов.

В случае объединения маршрутов, например первого (0-1-0) и второго (0-2-0), возможный эффект Δl = 20 + 21-1= 40 км.

Эффект от объединения всех маршрутов попарно занесем в табл.2.9.

Таблица 2.9.

Матрица кратчайших расстояний

Ввоз, л	0
160	8	1
370	45	42		2
210	44	42		54		3
132	4	7		48		40		4
478	5	4		42		39		2	5
471	2	6		48		52		5	6	6
139	4	5		47		38		1	2	4	7
181	7	6		40		40		4	3	8	4	8
684	8	5		40		41		4	3	8	5	1		9
139	42	49		83		55		43	53	40	43	55		56	10
166	43	50		84		56		44	54	41	44	56		57	1		11

Таблица 2.10.

Матрица выигрышей

Ввоз, л
160	1
370	11	2
210	10	35	3
132	5	0	8	4
478	9	8	10	7	5
471	4	-1	-6	1	1	6
139	7	2	10	7	7	2	7
181	9	12	11	7	9	1	7	8
684	11	13	11	8	10	2	7	14	9
139	1	4	31	3	-6	4	3	-6	-6	10
166	1	4	31	3	-6	4	3	-6	-6	84	11

Анализируя матрицу выигрышей, приходим к заключению, что максимальную выгоду, равную 84, можно получить, объединяя маршруты 0-10-0 и 0-11-0. При объединении первой пары маршрутов (0-10-0 и 0-11-0) суммарное количество груза по ввозу 139+ 166 = 305 л.

На данный маршрут (0-10-11-0) можем назначить автомобиль грузоподъемностью 1000 кг или 1500 кг, но следует помнить, что он при этом недогружен (1000 – 305 = 695 кг или 1500 – 305 = 1195 л). Количество ввозимого груза проставляем в соответствующих столбцах напротив пунктов 10 и 11, (табл. 2.11).

Таблица 2.11.

Объединение маршрутов 0-3-0 и 0-4-0

Ввоз, кг
	1
			2
					3
							4
								5
									6
										7
											8
													9
305	1		4		31		3	-6	4	3	-6		-6	10
305	1		4		31		3	-6	4	3	-6		-6	84		11

Далее рассмотрим возможность объединения маршрута 0-3-0 с полученным 0-10-11-0, так как в этом случае "выгода" будет максимальной (выгода от объединения маршрутов 0-3-0 и 0-11-0 равна 31). Для объединенного маршрута (0-3-10-11-0) ввоз составит 305 + 210 = 515 л (табл. 2.12).

Таблица 2.12.

Объединение маршрутов 0-3-4-0 и 0-1-0.

Ввоз, кг
	1
			2
515	10		35		3
							4
								5
									6
										7
											8
													9
515	1		4		31		3	-6	4	3	-6		-6	10
515	1		4		31		3	-6	4	3	-6		-6	84		11

При последующем рассмотрении матрицы выигрышей можно объединить маршруты 0-6-0 и 0-3-10-11-0. Для объединенного маршрута ввоз составит 210+471+139+166=986л. Присваиваем данному маршруту №1.

Ищем следующую наибольшую выгоду по матрице выигрышей (табл. 2.12), она равна 13, т.е. при объединении маятниковых маршрутов 0-2-0 и 0-9-0 в один кольцевой выигрыш составит 13 км. Далее присоединяем маршруты 0-8-0 и 0-1-0. Получаем маршрут 0-1-2-8-9-0. Объем ввоза составит 160+370+181+684=1395 л. Присваиваем маршруту №2.

Маршрут №3 получаем при объединении маршрутов 0-4-0, 0-5-0 и 0-7-0 в маршрут 0-4-5-7-0. Объем ввоза равен 132+478+181 = 791 кг.

Окончательный вариант объединения маршрутов представлен в табл. 2.13.

Таким образом, получены 2 маршрута организации перевозок:

маршрут №1: 0-3-6-10-11, объем ввоза равен 986л;

маршрут №2: 0-2-9-8-1-0. Объем ввоза составит 1395л;

маршрут №3: 0-4-5-7-0. Объем ввоза составил 749л.

Таблица 2.13.

Матрица объединенных маршрутов

Ввоз, кг	Маршрут
1395	2	1
1395	2	11		2
986	1	10		35		3
749	3	5		0		8	4
749	3	9		8		10	7	5
986	1	4		-1		-6	1	1	6
749	3	7		2		10	7	7	2	7
1395	2	9		12		11	7	9	1	7	8
1395	2	11		13		11	8	10	2	7	14	9
986	1	1		4		31	3	-6	4	3	-6	-6	10
986	1	1		4		31	3	-6	4	3	-6	-6	84	11