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

	Матрица расстояний между пунктами (dij), км
Матрица километровых выигрышей (sij), км	0	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	1	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	2	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	3	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	4	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	5	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	6	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	7	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	8	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	9	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	10	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	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	12

 

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

Воспользуемся алгоритмом Кларка-Райта. Здесь приводится только пошаговое описание алгоритма. Демонстрация использования данного алгоритма применительно к рассматриваемой задаче приводится в таблице 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?	№ маршрута	Маршрут
				1	2	3
1	2	3	4	5	6	7	8	9	10	11	12
1	8	3	23,0	+	+	+	200	400	+	1	0-3-8-0
2	8	5	21,4	+	+	+	600	150	+	1	0-3-8-5-0
3	5	3	17,2	-	+	+	-	-	-	-	-
4	12	3	14,6	+	+	+	550	750	+	1	0-12-3-8-5-0
5	12	8	14,2	-	-	+	-	-	-	-	-
6	11	1	13,4	+	+	+	475	450	+	2	0-1-11-0
7	6	3	12,6	+	-	+	-	-	-	-	-
8	12	5	12,3	-	+	+	-	-	-	-	-
9	11	5	11,3	+	+	+	925	1300	-	-	-
10	8	6	11,2	+	-	+	-	-	-	-	-
11	5	1	10,8	+	+	+	1300	925	-	-	-
12	12	6	10,6	+	+	+	1300	450	-	-	-
13	11	8	8,9	+	-	+	-	-	-	-	-
14	9	4	8,8	+	+	+	450	200	+	3	0-9-4-0
15	8	1	8,8	+	-	+	-	-	-	-	-
16	6	5	8,3	+	+	+	450	1300	-	-	-
17	10	7	8,3	+	+	+	300	250	+	4	0-7-10-0
18	11	9	7,9	+	+	+	925	650	-	-	-
19	7	2	7,9	+	+	+	550	400	+	4	0-2-7-10-0
20	10	6	7,8	+	+	+	950	450	+	4	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

---

Дата добавления: 2018-06-01; просмотров: 886; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!