Этап 3. Определение очередности объезда пунктов маршрута

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

Для каждого маршрута строят таблицу, называемую симметричной матрицей. Для маршрута 1 она приведена в табл. 3. По главной диагонали в ней размещены пункты, включаемые в маршрут. Цифры в клетках показывают кратчайшие расстояния между ними. Для примера матрица является симметричной C_ij = Cji, хотя приведенный ниже способ применим для размещения несимметричных матриц.

Начальный маршрут строим для трех пунктов матрицы А, Б, В, имеющих наибольшие значения величины, показанной в итоговой строке (41, 26, 24), т.е. маршрут АБВА.

Таблица 3 Симметричная матрица для первого маршрута

А
	Б
		В
			Г
				Д
					Е

Для включения последующих пунктов в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму, например, Е (24). Затем необходимо определить между какими пунктами начального маршрута его следует вставить. Для этого следует поочередно вставлять пункт Е между каждой соседней парой пунктов АБ, БВ, ВА.

При этом для каждой пары пунктов необходимо найти величину приращения маршрута (∆) по формуле:

∆_kp = C_ki + C_ip – C_kp,

где С – расстояние, км;

i - индекс включаемого пункта;

k – индекс первого пункта из пары;

p – индекс второго пункта из пары.

При включении пункта Е между первой парой пунктов АБ определяем размер приращения ∆АБ при условии, что i =Е, k = A, p = Б. Тогда

∆_АБ = С_АЕ + С_ЕБ – С_АБ.

Соответствующие расстояния между пунктами берутся в табл. 3 и получаем ∆_АБ = 7 + 4 – 11 = 0.

Для пунктов БВ приращение маршрута при включении пункта Е равно:

∆_БВ = С_БЕ + С_ЕВ– С_БВ,

т.е. ∆_БВ = 4 + 6 – 3 = 7.

Для пунктов ВА соответственно:

∆_ВА = С_ВЕ + С_ЕА– С_ВА,

т.е. ∆_ВА = 6 + 7 – 9 = 4.

Из полученных значений выбираем минимальное значение, т.е. ∆_АБ = 0 и между соответствующими пунктами вставляем пункт Е. Получаем маршрут АЕБВА.

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

∆_АЕ = С_АД + С_ДЕ– С_АЕ= 5 +3 – 7 = 1

∆_ЕБ = С_ЕД + С_ДБ– С_ЕБ= 3 + 6 – 4 = 5

∆_БВ = С_БД + С_ДВ– С_БВ= 6 + 4 – 3 = 7

∆_ВА = С_ВД + С_ДА– С_ВА= 4 + 5 – 9 = 0.

Так как наименьшей величиной является ∆_ВА, пункт Д включаем между ВА и получаем маршрут АЕБВДА.

Остается определить, куда следует вставить пункт Г. Производим соответствующие расчеты:

∆_АЕ= С_АГ + С_ГЕ– С_АЕ = 9 + 4 – 7 = 6

∆_ЕБ= С_ЕГ + С_ГБ– С_ЕБ= 4 + 2 – 4 = 2

∆_БВ= С_БГ + С_ГВ– С_БВ = 2 + 2 – 3 = 1

∆_ВД= С_ВГ + С_ГД– С_ВД= 2 + 4 – 4 = 2

∆_ДА= С_ДГ + С_ГА– С_ДА = 4 + 9 – 5 = 8.

Здесь наименьшее приращение ∆_БВ, поэтому получаем окончательный порядок объезда пунктов первого маршрута АЕБГВДА, длина которого составит 24 км. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.

По маршруту 2 проводятся аналогичные расчеты, исходные данные для которых представлены в табл. 4. В результате указанных расчетов порядок объезда пунктов в этом маршруте будет АЖИЛКМЗА и путь движения в данном случае составит 33 км. На рис. 3 представлена схема движения по маршрутам 1 и 2.

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

Таблица 4 Симметричная матрица для второго маршрута