Симметричная матрица маршрута

По трем наибольшим числам строки сумм строят начальный маршрут: 1 – 2 – 4. Далее, из строки сумм выбирают, из числа оставшихся, наибольшую сумму и номер пункта ей соответствующий. В данном примере сумма 58 встречается в строке сумм дважды. Можно выбирать любую из них, например 58, соответствующую пункту 7. Затем определяется место пункта 7 в начальном маршруте 1 – 2 – 4. Чтобы определить между какими пунктами его следует включить, надо поочередно его включать между каждой соседней парой пунктов 1– 2, 2 – 4. При этом для каждой пары этих пунктов находят величину прироста пробега автомобиля на маршруте при включении в начальный маршрут вновь выбранного пункта. Величину этого прироста (∆ L) находят по формуле:

, (9)

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

ί – номер первого соседнего пункта;

ј – номер второго соседнего пункта;

к – номер включаемого пункта.

В приведенном примере в начальном маршруте 1 – 2 – 4 при включении пункта 7 на участке 1 – 2:

,

на участке 2 – 4:

.

Место пункта 7 будет там, где приращение расстояния будет наименьшим. Если приращение расстояний будет одинаковым, то место пункта 7 – на любом участке.

Предположим, что место пункта 7 на участке 2 – 4, тогда первоначальный маршрут дополнится пунктом 7 и составит цепочку 1 – 2 – 7 – 4.

Вновь в симметричной матрице находят следующий пункт, имеющий в строке сумм наибольшую из оставшихся сумм по столбцу. В данном примере это пункт 0. Ему определяют место на участках 1 – 2, 2 – 7, 7 – 4, используя формулу (9). После определения места всех пунктов в маршруте, можно утверждать, что полученная последовательность объезда пунктов маршрута дает наименьший или весьма близкий к наименьшему путь движения автомобиля.

Если окажется, что пункт 0 находится в середине цепочки, например 1 – 2 – 7 - 0 – 4 – 5 – 6 – 3, то следует сделать передвижку 0 – 4 – 5 – 6 – 3 – 1 – 2 – 7 – 0, т.к. маршрут начинается и заканчивается в пункте 0.