Проектирование маршрутов методом сумм

Метод сумм является одним из наиболее простых приближенных методов решения задачи рационального объезда точек на маршруте (эта задача еще называется задачей коммивояжера).

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

На транспортной сети находят наименьшее звено. Затем рассматривают все звенья, связанные с одной из своих вершин с выбранным звеном.

При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины.

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

Далее все пункты маршрута, начиная с А, связываются такой замкнутой линией, которая соответствует кратчайшему пути объезда этих пунктов. Первоначально при использовании метода сумм строится таблица, называемая симметричной матрицей.

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

включении в начальный маршрут вновь выбранного пункта. Величину этого прироста ∆ _кр находят по формуле

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

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