Симметричная матрица для маршрута АЖЗИКЛМ

По главной диагонали в ней расположены пункты, включаемые в маршрут. Цифры в табл. 8.3 показывают расстояния между этими пунктами. Дополнительно в этой матрице имеется итоговая строка – строка сумм. В ней проставляют сумму расстояния по каждому столбцу. Затем строят начальный маршрут из трех пунктов, имеющих максимальную сумму по своему столбцу. В табл. 8.3 максимальные суммы имеют столбцы А, Ж, М. Принимаем маршрут АЖМА. В него включают следующий пункт с максимальной суммой, т. е. пункт З. Чтобы определить, между какими пунктами его следует вставить, надо поочередно включать этот пункт между каждой парой АЖ,ЖМ, МА. При этом для каждой пары этих пунктов находят величину прироста пробега автомобиля на маршруте при включении в начальный маршрут вновь выбранного пункта. Величину этого прироста ∆ _кр находят по формуле

∆ _кр = L_{1 3} + L ₂₃ – L ₁₂,

где L – расстояние; 1 – первый соседний пункт; 2 – второй соседний пункт; 3 – включаемый пункт.

В рассматриваемом примере в начальном маршруте (1= А, 2= Ж, 3= З) для первых двух соседних пунктов АЖ: ∆ _АЖ = L _АЖ + L _ЗЖ – L _АЖ. Соответствующие расстояния между пунктами берем из табл. 8.3: ∆ _АЖ = 6+8-6=8; ∆ _ЖМ = 8+6-11=3; ∆ _МА = 6+6-11=1. Из всех полученных ∆ выбирают минимальное значение и между соответствующими пунктами вставляют данный пункт. В данном случае минимальный ∆ _МА, поэтому получаем маршрут АЖМЗА. Вновь в табл. 8.3 находят не принимавшийся в расчет пункт с максимальной суммой по столбцу: это пункт Л. Все дальнейшие расчеты производятся так же, как было указано выше: ∆ _АЖ = 8+6-6=8; ∆ _ЖМ = 6+7-11=2; ∆ _МЗ = 7+7-6=8; ∆ _ЗА = 7+8-6=9. Как видно из расчетов, наименьшее расстояние ∆ _ЖМ, поэтому пункт Л включается между ЖМ и получается маршрут АЖЛМЗА. Выполнив аналогичные расчеты для пунктов К и И, получаем маршрут объезда АЖИЛКМЗА, протяженность которого составляет 33 км. Можно утверждать, что полученная последовательность объезда пунктов маршрута дает меньший или весьма близкий к наименьшему путь движения. На рис. 8.5 представлены схемы движения автомобилей по маршрутам АЖИЛКМЗА и АЗМКЛИЖА. Результаты расчета грузооборота представлены в табл. 8.4.

Таблица 8.4