Матрица расстояний и километровых выигрышей

	Матрица расстояний между пунктами (dij), км
Матрица километровых выигрышей (sij), км		7,0	4,0	12,4	5,1	12,0	7,3	6,1	14,8	7,3	5,0	9,2	7,3
0,0		11,0	12,6	9,4	8,2	11,4	13,0	13,0	8,6	11,4	2,8	8,6
0,0	0,0		13,9	5,8	15,3	7,3	2,2	17,0	9,2	3,0	13,2	9,2
0,0	6,7	2,5		17,5	7,2	7,1	14,2	4,1	19,0	11,4	15,2	5,1
0,0	2,7	3,3	0,0		16,4	12,0	7,8	19,7	3,6	8,5	10,4	12,4
0,0	10,8	0,8	17,2	0,7		11,0	16,6	5,4	16,6	13,9	10,0	7,1
0,0	2,9	4,0	12,6	0,3	8,3		7,2	10,8	14,6	4,5	14,2	4,0
0,0	0,0	7,8	4,2	3,4	1,6	6,2		17,7	11,3	2,8	15,3	10,0
0,0	8,8	1,7	23,0	0,2	21,4	11,2	3,2		20,6	14,9	15,1	7,8
0,0	5,7	2,1	0,6	8,8	2,8	0,0	2,0	1,4		11,7	8,6	14,0
0,0	0,6	6,0	6,0	1,6	3,1	7,8	8,3	4,9	0,6		13,9	7,2
0,0	13,4	0,1	6,4	3,9	11,3	2,3	0,0	8,9	7,9	0,3		11,4
0,0	5,7	2,1	14,6	0,0	12,3	10,6	3,4	14,2	0,6	5,1	5,1

 

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

Воспользуемся алгоритмом Кларка-Райта. Здесь приводится только пошаговое описание алгоритма. Демонстрация использования данного алгоритма применительно к рассматриваемой задаче приводится в таблице 5 и соответствующих комментариях к ней.

Шаг 1. На матрице километровых выигрышей находим ячейку (i*, j*) с максимальным километровым выигрышем S_max:

,

При этом должны соблюдаться следующие три условия:

1) пункты i* и j* не входят в состав одного и того же маршрута;

2) пункты i* и j* являются начальным и/или конечным пунктом тех маршрутов, в состав которых они входят;

3) ячейка (i*, j*) не заблокирована (т.е. рассматривалась на предыдущих шагах алгоритма).

Если удалось найти такую ячейку, которая удовлетворяет трем указанным условиям, то переход к шагу 2. Если не удалось, то переход к шагу 6.

Шаг 2. Маршрут, в состав которого входит пункт i*, обозначим как маршрут 1. Соответственно, маршрут, в состав которого входит пункт j*, обозначим как маршрут 2. Введем следующие условные обозначения:

N = {1, 2, …, n} – множество получателей; N₁ (N₁ Ì N) – подмножество пунктов, входящих в состав маршрута 1; N₂ (N₂ Ì N) – подмножество пунктов, входящих в состав маршрута 2.

Очевидно, что i* Î N₁, j* Î N₂ и N₁ Ç N₂= Æ (согласно шагу 1, условие 1).

Рассчитаем суммарный объем поставок по маршрутам 1 и 2:

и ,

где q_k – объем спроса k-го пункта, шт (см табл. 3).

Шаг 3. Проверим на выполнение следующее условие:

q₁ + q₂ £ c

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

Если условие выполняется, то переход к шагу 4, если нет – к шагу 5.

Шаг 4. Производим объединение маршрутов 1 и 2 в один общий кольцевой маршрут X. Будем считать, что пункт i* является конечным пунктом маршрута 1, а пункт j* – начальным пунктом маршрута 2. При объединении маршрутов 1 и 2 соблюдаем следующие условия:

Ÿ последовательность расположения пунктов на маршруте 1 от начала и до пункта i* не меняется;

Ÿ пункт i* связывается с пунктом j*;

Ÿ последовательность расположения пунктов на маршруте 2 от пункта j* и до конца не меняется.

Шаг 5. Повторяем шаги 1-4 до тех пор, пока при очередном повторении не удастся найти S_max, который удовлетворяет трем условиям из шага 1.

Шаг 6. Рассчитываем суммарный пробег автотранспорта.

 

Теперь рассмотрим применение этого алгоритма к рассматриваемой задаче. Весь ход последовательного решения задачи представлен в таблице 5.

 

 

Таблица 3.4

Решение задачи развозки методом Кларка-Райта

№ п/п	Шаг 1	Шаг 2	Шаг 3	Шаг 4
i*	j*	Smax	Условия	q1	q2	q1+q2 £ c?	№ маршрута	Маршрут
			23,0	+	+	+			+		0-3-8-0
			21,4	+	+	+			+		0-3-8-5-0
			17,2	-	+	+	-	-	-	-	-
			14,6	+	+	+			+		0-12-3-8-5-0
			14,2	-	-	+	-	-	-	-	-
			13,4	+	+	+			+		0-1-11-0
			12,6	+	-	+	-	-	-	-	-
			12,3	-	+	+	-	-	-	-	-
			11,3	+	+	+			-	-	-
			11,2	+	-	+	-	-	-	-	-
			10,8	+	+	+			-	-	-
			10,6	+	+	+			-	-	-
			8,9	+	-	+	-	-	-	-	-
			8,8	+	+	+			+		0-9-4-0
			8,8	+	-	+	-	-	-	-	-
			8,3	+	+	+			-	-	-
			8,3	+	+	+			+		0-7-10-0
			7,9	+	+	+			-	-	-
			7,9	+	+	+			+		0-2-7-10-0
			7,8	+	+	+			+		0-2-7-10-6-0

Комментарии к таблице 5

Графа 1 – номер итерации

Графы 2, 3 – номера пунктов i* и j*, которые обозначают ячейку с максимальным километровым выигрышем S_max = s(i*,j*), найденную в результате просмотра матрицы километровых выигрышей (таблица 4).

Графа 4 – значение максимального километрового выигрыша S_max

Графы 5, 6 и 7 – результаты проверки условий 1, 2 и 3 при выполнении шага 1. “+” – положительный результат, “–” – отрицательный результат.

Графы 8 и 9 – объем перевозок по маршруту 1, в состав которого входит пункт i* (q₁), и маршруту 2, в состав которого входит пункт j* (q₂).

Графа 10 – проверка на условие q₁ + q₂ £ c, где c – грузовместимость транспортного средства. “+” – положительный результат проверки условия, “–” – отрицательный результат.

Графа 11 – порядковый номер кольцевого маршрута (всего в ходе решения получено всего четыре кольцевых маршрута, см. рис. 6).

Графа 12 – структура кольцевого маршрута, образовавшегося на данной итерации.

 

Рассмотрим, как происходит поэтапный поиск оптимального решения задачи.

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

L₀ = 2 ´ d₀₁ + 2 ´ d₀₂ + … + 2 ´ d_0,12 = 2 ´ 7,0 + 2 ´ 4,0 + … + 2 ´ 7,3 = 195 км

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

Итерация 1. Объединяем два радиальных маршрута: 0-8-0 (объем доставки 200 шт.) и 0-3-0 (объем доставки 400 шт.) в общий кольцевой маршрут (под № 1) 0-8-3-0 (объем доставки 600 шт.). При этом суммарный пробег автотранспорта сокращается на 23,0 км.

Итерация 2. К кольцевому маршруту № 1 – 0-8-3-0 (600 шт.) присоединяем радиальный маршрут 0-5-0 (150 шт.). При этом пункт 5 присоединяем к пункту 8, в результате чего получаем новую структуру кольцевого маршрута 0-5-8-3-0 (750 шт.). Суммарный пробег автотранспорта сокращается еще на 21,4 км.

Отметим важность соблюдения последовательности пунктов в кольцевом маршруте: именно 0- 5-8 -3-0, а не 0-5-3-8-0 или 0-8-3-5-0. Если i* = 5 и j* = 8, то после объединения они должны стоять на маршруте друг за другом.

Итерация 3. Объединение пунктов 3 и 5 обеспечило бы выигрыш в 17,2 км. Но это объединение невозможно, поскольку оба пункта уже входят в состав кольцевого маршрута №1 – 0-5-8-3-0, а объединять можно пункты только из разных маршрутов. Таким образом, констатируем нарушение условия 1 и переходим к следующей итерации.

Итерация 4. Ккольцевому маршруту № 1 – 0-5-8-3-0 (750 шт.) присоединяем радиальный маршрут 0-12-0 (150 шт.). При этом пункт 12 присоединяем к пункту 3, в результате чего получаем новую структуру кольцевого маршрута 0-5-8- 3-12 -0 (1300 шт.). Суммарный пробег автотранспорта сокращается на 14,6 км.

Итерация 5. Пункты 12 и 8 не объединяем, поскольку они уже входят в состав кольцевого маршрута 1 (нарушается условие 1).

Итерация 6. Объединяем два радиальных маршрута: 0-11-0 (475 шт.) и 0-1-0 (450 шт.) в общий кольцевой маршрут (под № 2) 0-11-1-0 (925 шт.). При этом суммарный пробег автотранспорта сокращается на 13,4 км.

Итерация 7. Пункты 3 и 6 нельзя объединить по причине нарушения условия 2. Пункт 3 входит в состав кольцевого маршрута 1, и в этом маршруте он занимает «промежуточное» положение, то есть он связан с пунктами 8 и 12: 0-5- 8-3-12 -0. Радиальный маршрут 0-6-0 можно было бы присоединить к кольцевому маршруту 1 со стороны его «крайних» пунктов – 5 или 12, но к «промежуточным» пунктам 3 и 8 его присоединить нельзя.

Итерации с 8 по 20 повторяют ту же логику рассуждений, что и в предыдущих 7 итерациях. Отметим только, что на итерациях 9, 11, 12, 16 и 18 объединение не производится только по причине нарушения условия q₁ + q₂ £ c.

Итерации с 21 по 60 уже не имеют смысла, поскольку их выполнение уже не повлечет за собой изменение плана развозки.

Суммарный километровый выигрыш за 20 итераций составляет:

S = 23,0 + 21,4 + 14,6 + 13,4 + 8,8 + 8,3 + 7,9 + 7,8 = 105,3 км

а общий пробег автотранспорта, соответственно:

L₁ = L₀ – S = 195 –105,3 = 89,7 км

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

,

где L_i – протяженность i-го маршрута, км; r – количество маршрутов.

Рассмотрим, например, кольцевой маршрут 0-3-8-5-12-0. Протяженность маршрута определяется по формуле (см. табл. 4):

L₁ = d_0,12 + d_12,3 + d_3,8 + d_8,5 + d_5,0 = 7,3 + 5,1 + 4,1 + 5,4 + 12,0 = 33,9 км.

Аналогично рассчитываем протяженность остальных маршрутов. Результаты расчетов сведены в таблицу 6:

 

Таблица 3.5