ПРИМЕНЕНИЕ ВНЕШНИХ ФИКТИВНЫХ ВЕТВЕЙ ДЛЯ НАХОЖДЕНИЯ РАДИАЛЬНЫХ МАРШРУТОВ

Подшивалова Кристина Сергеевна
Пензенский государственный университет архитектуры и строительства
кандидат технических наук, доцент кафедры «Организация и безопасность движения»

Аннотация
Представлено совершенствование метода фиктивных узлов и ветвей, позволяющее решить задачу маршрутизации при интегрированной схеме доставки грузов. Рассмотрен пример решения задачи.

Ключевые слова: алгоритм, граф, груз, маршрутизация, перевозка, радиальный маршрут, фиктивный узел

THE USE OF EXTERNAL FICTITIOUS BRANCHES TO FIND THE RADIAL ROUTES

Podshivalova Kristina Sergeevna
Penza State University of Architecture and Construction
PhD in Technical Sciences, Assistant Professor of the department is "Organization and safety of motion"

Abstract
Presented by improving the method of fictitious nodes and branches, which allows to solve the problem with the routing of the integrated scheme of delivery. An example of solving the problem.

Keywords: algorithm, cargo, dummy node, graph, radial route, routing, transportation

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Подшивалова К.С. Применение внешних фиктивных ветвей для нахождения радиальных маршрутов // Современные научные исследования и инновации. 2014. № 12. Ч. 1 [Электронный ресурс]. URL: https://web.snauka.ru/issues/2014/12/42210 (дата обращения: 16.08.2026).

Радиальные маршруты являются составной частью интегрированной схемы доставки грузов от нескольких производителей. Решение задачи маршрутизации для нее невозможно без разработки методики определения оптимальных радиальных схем движения. Для ее решения используем методику фиктивных узлов и ветвей [1]. Однако ее следует усовершенствовать для применения к радиальным маршрутам. 
Дублирующим называется дополнительно введенный фиктивный узел Ф, имею­щий одинаковые связи с действительным D. Ветви, соединяющие его с действительным узлом, называются фиктивными ветвями: Ф-1, Ф-2 и Ф-3 (рис.1).

Рис. 1. Внешний фиктивный узел

На рис.1 фиктивные узлы и ветви обозначены пунктирными линиями. Следует отметить, что действительную и фиктивную вершины соединять нельзя. 
Ввод дублирующего узла превращает циклический контур с симметричной матрицей в разомкнутый граф одинаковой длины, рис. 2. Исходный гамильтонов контур с центральным пунктом Ц изображен на рис.2,а. Вводим в контрольную вершину К фиктивный узел – КФ. Связываем его со смежными действительными узлами фиктивными дугами равного веса а и б, как и в пункте К (рис.2,б). Получаем пару разомкнутых маршрутов из исходного центрального пункта Ц в конечные вершины К и КФ.
а б

Рис. 2. Схема ввода фиктивного узла КФ

Чтобы получить гамильтонов контур аналогично вводим фиктивный узел ЦФ в начальный узел передвижения Ц (рис.3). Соединяем контрольные вершины К и КФ с начальными пунктами маршрута Ц и ЦФ, ориентированными связующими фиктивными ветвями.

Рис. 3. Ввод ориентированных внешних фиктивных ветвей в узел Ц.

Ветви К-ЦФ и КФ-Ц удаляем в начале расчета, чтобы обеспечить заданное направление перемещения. 
Алгоритм решения заключатся в следующем.
1. Формируем фиктивный транспортный граф путем дополнительного введения в транспортную сеть дублирующих узлов.
2. Составляем фиктивную матрицу расстояний – Lф.
3. Вычисляем приведенную матрицу – Lпр.
4. Удаляем из приведенной матрицы строки и столбцы с номерами узлов, в которые входят и из которых выходят радиальные маршруты, соответственно.
5. Вычисляем новую приведенную матрицу Liпр.
6. Составляем оценочную матрицу Lio.
7. Создаем матрицу Li путем вычеркивания ячейки k – s с максимальной оценкой. Блокируем ветви, ведущие к зацикливанию, включая s – k. 
8. Переходим в пункт 5. Операции по пунктам 5-7 выполняем до тех пор, пока последняя вычеркиваемая ветвь станет очевидной.
9. При вырождении решения, устанавливаем ветви, связывающие полученные два подмножества.
10. Возвращаемся в пункт 5 и вычеркиваем на следующем шаге в приведенной матрице одну из ветвей, найденных в пункте 3. Оптимальная связующая ветвь определяется путем сравнения всех возможных вариантов по наименьшей длине маршрута. 
Рассмотрим применение разработанного алгоритма на примере. Задан транспортный граф из восьми вершин, рис.4. Требуется определить два радиальных маршрута из центра 1 до пунктов 2 и 3, чтобы их длина была минимальной. Матрица расстояний представлена в табл. 1.

Рис. 4. Исходный транспортный граф
Таблица 1. Исходная матрица расстояний
1
2
3
4
5
6
7
8
1
5
1
4
10
8
2
11
8
7
2
6
3
3
12
5
6
8
4
5
11
3
6
3
7
9
5
1
8
12
6
4
5
1
6
4
7
5
3
4
2
8
7
10
2
6
7
5
2
6
8
8
6
8
9
1
8
6

Выполняем первый этап алгоритма. Вводим в центральный пункт 1 дублирующий фиктивный узел Ф1 (рис.5).

Рис. 5. Фиктивный транспортный граф

На втором этапе составляем фиктивную матрицу расстояний (табл. 2).

Таблица 2. Фиктивная матрица расстояний
1
2
3
4
5
6
7
8
Ф1
1
5
1
4
10
8
2
11
8
7
2
6
3
3
12
5
6
8
4
5
11
3
6
3
7
9
5
5
1
8
12
6
4
5
1
1
6
4
7
5
3
4
2
8
4
7
10
2
6
7
5
2
6
10
8
8
6
8
9
1
8
6
8
Ф1
5
1
4
10
8

На третьем этапе выполняем операцию приведения по строкам и столбцам (табл. 2). В результате получаем матрицу 1, представленную в табл. 3.
Переходим к четвертому этапу. В табл. 3 вычеркиваем строки 2 и 3 с номерами контрольных узлов, в которые должны входить радиальные маршруты. Удаляем столбцы 1 и Ф1 с номерами вершин, из которых выходят радиальные маршруты. Получаем матрицу 2 (табл. 4).

Таблица 3. Матрица 1
1
2
3
4
5
6
7
8
Ф1
1
4
0
3
9
7
2
9
6
5
0
4
3
0
9
2
3
5
4
2
8
0
3
0
4
6
2
5
0
7
11
5
3
4
0
0
6
2
5
3
1
2
0
6
2
7
8
0
4
5
3
0
6
8
8
7
5
7
8
0
7
5
7
Ф1
4
0
3
9
7
Таблица 4. Матрица 2
2
3
4
5
6
7
8
1
4
0
3
9
7
4
8
0
3
0
4
6
5
7
11
5
3
4
0
6
5
3
1
2
0
6
7
0
4
5
3
0
6
8
5
7
8
0
7
5
Ф1
4
0
3
9
7

На пятом и шестом этапах выполняем операцию приведения в столбце 4 и производим оценку элементов полученной приведенной матрицы. В результате получаем оценочную матрицу L1o (табл. 5), где вычеркиваем ячейку 5-8 с наибольшей оценкой 9.

Таблица 5. Матрица L1o
2
3
4
5
6
7
8
1
3
03
3
9
7
4
8
03
3
00
4
6
5
7
11
4
3
4
09
6
5
3
03
2
04
6
7
05
4
4
3
00
6
8
5
7
7
05
7
5
Ф1
3
03
3
9
7

Получаем новую матрицу 3 размером 66, где блокируем звено 8-5 против зацикливания, табл. 6. Результат оценки элементов матрицы 3 представлен в табл. 7.

Таблица 6. Матрица 3
2
3
4
5
6
7
1
3
0
3
9
4
8
0
3
0
4
6
5
3
0
2
0
7
0
4
4
3
0
8
5
7
7
∞
7
5
Ф1
3
0
3
9
Таблица 7. Матрица L2o
2
3
4
5
6
7
1
3
03
3
9
4
8
02
3
00
4
6
5
3
02
2
00
7
00
4
4
3
00
8
00
2
2
2
00
Ф1
3
03
3
9

В результате две ячейки 1-5 и Ф1-5 имеют одинаковую оценку 3. В качестве примера рассмотрим случай вычеркивания ветви 1-5 в матрице L2o. Получаем новую матрицу 4 размером 55, представленную в табл. 8.

Таблица 8. Матрица 4
2
3
4
6
7
4
8
0
0
4
6
5
3
0
0
7
0
4
4
0
8
0
2
2
2
0
Ф1
3
3
9

После оценки элементов табл.8, получаем матрицу L3o, в которой вычеркиваем ветвь 4-3 (табл. 9).

Таблица 9. Матрица L3o
2
3
4
6
7
4
8
02
00
4
6
5
3
00
00
7
00
4
4
00
8
00
2
2
2
00
Ф1
00
00
6

Новая оценочная матрица L4o имеет размер 44 и представлена в табл. 10, в которой блокируется ветвь 8-4 против зацикливания. Как показала оценка ее нулевых элементов, в восьми из них она одинакова. Можно вычеркивать любую ветвь. Оптимальное звено устанавливается из сравнения вариантов.

Таблица 10. Матрица L4o
2
4
6
7
6
5
00
00
7
00
4
00
8
00
∞
2
00
Ф1
00
00
6

Приводим решение для одного оптимального маршрута. Вычеркиваем в матрице L4o ячейку 6-4 и получаем табл. 11 с оценочной матрицей L5o, где блокируем звено 8-6 и вычеркиваем ветвь 8-7.

Таблица 11.Матрица L5o
2
6
7
7
00
00
8
00
∞
06
Ф1
06
6

Получаем оценочную матрицу L6o размером 22, в которой удаляем 7-2 и Ф1-6 (табл.12). Вырождения решения нет.

Таблица 12. Матрица L6o
2
6
7
0∞
Ф1
0∞

В результате расчетов получается фиктивный кольцевой маршрут: 1-5-8-7-2-Ф1-6-4-3-1 (рис. 6).

Рис. 6. Схема передвижения по кольцевому фиктивному маршруту

Из него следуют две радиальные схемы движения: 1-5-8-7-2 и 1-6-4-3, каждый длиной по 10 км.


Библиографический список
  1. Подшивалова, К.С. Повышение эффективности перевозок мелкопартионных грузов автомобильным транспортом [Текст]: автореф. дис.... канд. техн. наук / К.С. Подшивалова – Волгоград. 2007. – С.16.

Все статьи автора «Подшивалова Кристина Сергеевна»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте.