Мир транспорта и технологических машин 2011 УДК 656.135.073 С. Ф. ПОДШИВАЛОВ, К. С. ПОДШИВАЛОВА, Ю. В. РОДИОНОВ ПРОЕКТИРОВАНИЕ МАРШРУТОВ С КОНТРОЛЬНОЙ ВЕРШИНОЙ ИЗ РАЗНЫХ ЦЕНТРОВ Предложена методика усовершенствования метода ветвей и границ, позволяющая посещать вершины графа несколько раз. <...> Представлено решение задачи маршрутизации для определения оптимальных маршрутов из разных центров минимального суммарного веса. <...> Задана транспортная сеть с симметричной матрицей расстояний. <...> Требуется рассчитать маршруты для мелкопартионной развозки грузов с заданной контрольной вершиной, которые начинаются в разных пунктах, чтобы их суммарная длина была наименьшей. <...> В общем случае, с геометрической точки зрения, маршрут состоит из различных комбинаций радиальной и кольцевой схем передвижения. <...> В этом случае кольцевой маршрут с симметричной матрицей расстояний можно представить в виде двух радиальных схем, проходящих по этим же самым ветвям, которые будут начинаться и заканчиваться в одних и тех же вершинах. <...> Таким образом, любой маршрут геометрически представляется комбинацией только радиальных схем движения. <...> Для решения поставленной задачи усовершенствуем методику поиска радиальных маршрутов с помощью фиктивных узлов 1 . <...> Составляем исходную матрицу весов (расстояний) L между вершинами графа – аij . <...> Для этого в матрицу L добавляем в исходные и конечные вершины фиктивные узлы. <...> Их количество равно числу маршрутов, проходящих через рассматриваемую вершину, минус единица. <...> Для этого в каждой строке находим минимальный элемент ih и вычитаем его из всех остальных элементов ija , расположенных в рассматриваемой строке: aij aij hi , i 1,2,3.n. <...> и вычитаем его из всех остальных элементов aij , расположенных в рассматриваемом столбце: Затем в полученной матрице находим минимальный элемент в каждом столбце jh aij ветственно, включая фиктивные. <...> Вычеркиваем строки и столбцы с номерами конечных и исходных пунктов, соот <...>