Метод Кларка - Райта

Метод Кларка-Райта был разработан двумя британскими учеными Г. Кларком (G. Clarke) и Дж.В. Райтом (J.W. Right). Несмотря на давность разработки (метод опубликован в 1963 г.), он до сих пор остается самым популярным методом для решения данной задачи, о чем свидетельствует практика его применения.

Метод Кларка-Райта относится к числу приближенных, итерационных методов и предназначается для компьютерного решения задачи развозки. Погрешность решения не превосходит в среднем 5-10%. Достоинствами метода являются его простота, надежность и гибкость, что позволяет учитывать целый ряд дополнительных факторов, влияющих на конечное решение задачи.

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

Рис.. Схемы развозки А и B

На рисунке отображены две схемы развозки. Схема развозки А (слева) обеспечивает доставку грузов в пункты 1 и 2 по радиальным маршрутам. В этом случае суммарный пробег автотранспорта равен:

L_А = l _01­ + l ₁₀ + l ₀₂ + l ₂₀ = 2 l ₀₁ + 2 l ₀₂

Схема развозки B предполагает доставку грузов в пункты 1 и 2 по кольцевому маршруту. Тогда пробег автотранспорта составляет:

L_B = l ₀₁ + l ₁₂ + l ₀₂

Схема В по показателю пробега автотранспорта дает, как правило, лучший результат, чем схема А. И поэтому при переходе от схемы А к схеме В получаем следующий километровый выигрыш:

f ₁₂ = L_A – L_B = l ₀₁ + l ₀₂ – l ₁₂

В общем случае мы имеем километровый выигрыш:

f_ij = l_0i + l_j0 - l_ij

где l_0i - расстояние от центрального пункта до пункта i; l_j0 - расстояние от пункта j до центрального пункта; l_ij - расстояние между пунктами i и j.

Действительно, в результате объединения двух маршрутов отпадает необходимость возврата с i -го маршрута на центральный пункт и подачи автомобиля с центрального пункта на j-й маршрута (т.е. из пробега автомобиля вычитаются расстояния l_оi и l_jо). Но вместо этого появляется пробег от последней точки i -го маршрута до первой точки j-го маршрута (т.е. к пробегу автомобиля добавляется расстояние l_ij).

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

Решение заканчивается, когда дальнейшее объединение маршрутов станет невозможно. Это может быть по двум причинам: либо не осталось ни одного положительного значения выигрыша (т. е. объединять невыгодно), либо при объединении превышается грузовместимость автомобиля.

Рассмотрим следующий пример.

Пусть необходимо развезти от ГО продукцию нескольким ГП, забрать и доставить ГО возвратную тару от ГП. Для обслуживания маршрутов используется автомобиль грузовместимостью 240 единиц груза. Количество ввозимого и вывозимого груза для каждого ГП, кратчайшие расстояния между пунктами представлены в табл. 3.14.

Таблица 3.14

ГП

Ввоз груза,ед.

Вывоз груза,ед.

ГО

ГП

-

-

-

-

-

-

-

-

-

Таким образом, на начальном этапе имеется 9 маятниковых маршрутов, суммарный пробег по которым равен 228 км.

Рассчитаем выигрыши от объединения всех пар маршрутов, результаты занесем в табл. 3.15 (Таблица «выигрышей»). Например, для пунктов 2 и 5 получаем выигрыш:

f_2,5 = l_ГО,2 + l_ГО,5 – l_2,5 = 4 + 10 – 6 = 8 км

Таблица 3.15 Таблица «выигрышей»т
ГП	Ввоз груза,ед.	Вывоз груза,ед.	ГП
			-
				-
					-
						-
							-
								-
									-
										-
											-

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

Формируем маршрут №1:

Шаг 1. В таблице выигрышей (см. табл. 3.16) находим ячейку с максимальным выигрышем f _max. В нашем примере это ячейки{6;4} и {9;4}, т.е. наибольший выигрыш, равный 27, получается при объединении маршрутов ГО – 4 – ГО и ГО – 6 – ГО и маршрутов ГО – 4 – ГО и ГО – 9 – ГО.

Шаг 2. Производим объединение маршрутов 6, 4 и 9 в один общий кольцевой маршрут и запишем как …- 6 - 4 - 9…. Проверим на выполнение следующее условие:

Q₆ + Q₄ + Q₄£ q

где Q – объем перевозок на маршруте, ед.

q – грузовместимость автомобиля, ед.

Суммарное количество ввозимого груза для объединенного маршрута равно 230 ед. (95 ед. + 75 ед. +60 ед.), а вывозимого груза 75 ед. (30 ед. + 45 ед. + 10 ед.). Так как ∑Q < q переходим к следующему шагу.

Шаг 3. Вычеркиваем строку 6, столбец 4 и строку 4 и столбец 9, а также значение выигрыша на пересечении столбца 6 и строки 9. Ищем следующее наибольшее значение выигрыша в столбце 6 и в строке 9.

Как видно, наибольшее значение соответствует маршруту 7, причем ГП7 может быть обслужен как перед ГП6, так и после ГП9 (ячейки{7;6} и {9;7}).

Суммарное количество ввозимого груза при объединении этих маршрутов составит 290 ед., при этом будет превышена грузовместимость имеющихся в распоряжении автомобилей. Следовательно, от объединения этих маршрутов необходимо отказаться. Так как объемы по ввозу по всем ГП превышают 10ед. (остаток грузовместимости) то формирование первого кольцевого маршрута заканчиваем. В табл. 3.16 вычеркиваем столбец 6 и строку 9, и при формировании следующих маршрутов отмеченные строки и столбцы не рассматриваем.

Таблица 3.16
ГП	Ввоз груза,ед.	Вывоз груза,ед.	ГП
			-
				-
					-
						-
							-
								-
									-
										-
											-

Сформированный кольцевой маршрут №1: ГО - 6 - 4 – 9 – ГО.

Формируем следующий маршрут:

Наибольшее значение выигрыша равно 25 (см. табл. 3.17). Это выигрыш, который получается при объединении маршрутов ГО – 7 – ГО и ГО – 8 – ГО. Суммарное количество ввозимого груза для этого объединенного маршрута составит 130 ед., а суммарное количество вывозимого груза - 30 ед. Вычеркиваем строку 7 и столбец 8, а также значение выигрыша на пересечении столбца 7 и строки 8. Ищем следующее наибольшее значение выигрыша в столбце 7 и в строке 8.

Значение следующего наибольшего выигрыша равно 20. Объединяем маршруты ГО – 5 – ГО и ГО – 7 – 8 – ГО. Суммарное количество ввозимого груза для маршрута ГО – 7 – 8 – 5 – ГО составит 210 ед., а вывозимого - 50 ед. Вычеркиваем строку 8 и столбец 5, а также значение выигрыша на пересечении столбца 7 и строки 5. Ищем следующее наибольшее значение выигрыша в столбце 7 и в строке 5.

Маршрут ГО – 3 – ГО включаем в формируемый маршрут, так как наибольший выигрыш в столбце 7 соответствует ему.

Суммарное количество ввозимого груза – 240ед., вывозимого – 80ед. Грузовместимость автомобиля исчерпана. Исключаем из рассмотрения строки и столбцы, соответствующие пунктам 3,7, 8 и 5.

Сформированный маршрут №2 выглядит как: ГО – 3 – 7 – 8 – 5 – ГО.

Таблица 3.17
ГП	Ввоз груза,ед.	Вывоз груза,ед.	ГП
			-
				-
					-
						-
							-
								-
									-
										-
											-

Таким образом, остается последнее объединение маршрутов ГО – 1 – ГО и ГО – 2 – ГО с выигрышем 6 в маршрут №3 - ГО – 1 – 2 – ГО.

На этом построение маршрутов методом Кларка - Райта закончено.

Суммарный пробег по сформированным кольцевым маршрутам равен 107км. Пробег автомобилей сократился на 121 км.

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