Методы расчета расстояний на сети

Методы, рассмотренные ранее (метод Свира, развозка грузов по радиальному и кольцевому маршрутам, метод Кларка – Райта), можно использовать для расчета расстояний, как для пары объектов, так и внутри целого множества объектов.

Иными словами, в их основе лежит принцип аппроксимации расстояний. Вместе с тем дороги «по прямой» практически никогда не строят.

По разным причинам они отклоняются от прямой линии – из-за особенностей местности, ландшафта, транспортной сети.

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

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

Результатом расчетов расстояний являются две матрицы – матрица расстояний и матрица указателей. Для разъяснения сущности и назначения второй матрицы рассмотрим пример.

Пример 4. Транспортная сеть состоит из девяти пунктов. Расстояния между пунктами представлены на Рисунке 10.

Представим, что схема транспортной сети – это карта, на которой в одном из пунктов располагается игральная фишка, на пример, в пункте A. Необходимо передвинуть фишку из пункта 1 в пункт 7.

Необходимо выяснить:

1. Какой путь должна пройти фишка?
2. Какой маршрут для фишки является оптимальным?

Ответы на эти вопросы легко найти самостоятельно, поскольку сеть маленькая и решение определяется элементарным подсчетом.

В этом случае и применяется матрица расстояний и матрица указателей, которые для рассматриваемого случая представлены в Таблице 4 и Таблице 5.

Расстояние от пункта 1 до пункта 7 находится из матрицы расстояний – это ячейка, которая располагается на пересечении строки 1 и столбца 7. Расстояние это составляет 31 км. Для поиска оптимального маршрута используется матрица указателей. Находим ячейку на пересечении строки 1 и столбца 7. В найденной ячейке указан пункт 3.

Перемещаем фишку в пункт 3 и ставим новый вопрос: как добраться из пункта 3 в пункт 7? Находим ячейку на пересечении строки 3 и столбца 7, где указан новый пункт 8. Перемещаем фишку в пункт 8 и формулируем вопрос: как добраться из пункта 8 в пункт 7?

На пересечении строки 8 и столбца 7 указан пункт 6. Перемещаем фишку в пункт 6. На пересечении строки 6 и столбца 7 стоит число 7. Перемещаем фишку в пункт 7. Оптимальный маршрут найден: 1 – 3 – 8 – 6 – 7.

Протяженность оптимального маршрута определяется как сумма длины отдельных участков маршрута, например:

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