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

⇐ ПредыдущаяСтр 2 из 2

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

Построим симметричную матрицу для маршрута 1.

Таблица 3 – Матрица для маршрута 1

А	5,4	10,7	4,4	9,8	5,2
5,4	Б	5,3	3,7	9,1	10,6
10,7	5,3	В			15,9
4,4	3,7		Г	5,4	9,6
9,8	9,1		5,4	Д	7,2
5,2	10,6	15,9	9,6	7,2	Ж
35,5	34,1	52,9	32,1	43,5	48,5

Начальный маршрут построим для трех пунктов матрицы В, Ж, Д, имеющих наибольшие значения величины, показанной в итоговой строке (52,9;48,5;43,5). Получим маршрут ВЖДВ.

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

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

∆_kp = C_ki + C_ip – C_kp, где С – расстояние, км;

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

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

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

∆_ВЖ = С_АВ + Саж – С_ВЖ= 10,7+5,2-15,9=0;

∆_ЖД = С_АЖ + С_АД– С_ЖД= 5,2+9,8-7,2=7,8;

∆_ДВ = С_ДА + С_АВ– С_ДВ= 9,8+10,7-12=8,5.

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

Таким же образом рассчитываем приращение маршрута для Б.

∆_ВА= С_ВБ + С_АБ– С_АВ =5,3+5,4-10,7=0;

∆_АЖ= С_БА + С_БЖ– С_АЖ= 5,4+10,6-5,2=10,8;

∆_ЖД= С_БЖ + С_БД– С_ЖД = 10,6+9,1-7,2=12,5;

∆_ДВ= Сбд + С_БВ– С_ДВ=9,1+5,3-12=2,4.

Получаем маршрут ВБАЖДВ.

Далее рассчитываем приращение маршрута для Г:

∆_ВБ= С_ГВ + С_БГ– С_БВ = 9,0+3,7-5,3=7,4;

∆_БА= С_БГ + С_АГ– С_БА= 3,7+4,4-5,4=2,7;

∆_АЖ= С_АГ + С_ГЖ– С_АЖ= 4,4+9,6-5,2=8,8;

∆_ЖД= Сгж + С_ДГ– С_ДЖ =9,6+5,4-7,2=7,8;

∆_ДВ= Сгд + С_ГВ– С_ДВ= 5,4+9,0-12=2,4.

Окончательный порядок объезда пунктов первого маршрута ВБАЖДГ, длина которого составит 37,5 км. Полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов по маршруту 1.

Аналогично рассчитали очередности объезда пунктов маршрута №2.

Таблица 4 – Матрица для маршрута 2

А	11,4	15,2	8,5	11,9
11,4	Е	3,8	6,2	2,8
15,2	3,8	З	9,2	5,8
8,5	6,2	9,2	И	3,4
11,9	2,8	5,8	3,4	К
	24,2		27,3	23,9

Начальный маршрут построили для трех пунктов матрицы А, З, И, имеющих наибольшие значения величины, показанной в итоговой строке (47;34;27,3), т.е. маршрут АЗИА.

Величина приращения маршрута для пункта Е:

∆_АЗ= С_АЕ + С_ЕЗ– С_АЗ = 11,4+3,8-15,2=0;

∆_ЗИ= С_ЕЗ + С_ЕИ– С_ЗИ=3,8+ 6,2-9,2=0,8;

∆_ИА= С_ЕИ+ С_ЕА– С_ИА=6,2+11,4-8,5=9,1.

Получим маршрут АЕЗИА.

Величина приращения маршрута для пункта К: