УДК 656.135.073

ИСПОЛЬЗОВАНИЕ ПРИВЕДЕННЫХ ФИКТИВНЫХ УЗЛОВ И ВЕТВЕЙ

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

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

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


USE OF THE GIVEN DUMMY NODES AND BRANCHES

Podshivalova Kristina Sergeevna
Penza state university of architecture and building
PhD in Technical Sciences, Assistant Professor of the department is "Organization and safety of motion"

Abstract
The technique of use of the given dummy nodes and branches which is generalization of a classical method of branches and boundaries is developed. The advanced algorithm of the solution of the task of routing is provided.

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


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

Библиографическая ссылка на статью:
Подшивалова К.С. Использование приведенных фиктивных узлов и ветвей // Современные научные исследования и инновации. 2015. № 2. Ч. 2 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/02/47487 (дата обращения: 03.06.2017).

Одним из недостатков метода ветвей и границ (ВиГ) является посещение вершины транспортного графа один раз. В работе разработана методика устранения этого недостатка путем повторного использования приведенных фиктивных узлов и ветвей в процессе решения матрицы расстояний.
Приведенным фиктивным узлом называется повторно введенная, вычеркнутая в оценочной матрице вершина. Он вводится на следующем этапе. Матрица с таким узлом называется фиктивной. Принципиальная схема ввода фиктивных элементов представлена на рис. 1, где фиктивные узлы и ветви изображены пунктирной линией.

Рис. 1. Приведенные элементы графа

Рассмотрим вариант постановки задачи, не имеющей вырождения решения. Усовершенствованный алгоритм решения задачи маршрутизации метода ВиГ представим в следующем виде: 
1. Составляем исходную матрицу расстояний между пунктами: 

 (1)

В (1) буква Ч означает очень большое число.

2. Переходим к приведенной матрице – . Для этого в каждой строке находим минимальный элемент hi и вычитаем его из всех остальных элементов ij, расположенных в рассматриваемой строке:

  (2)

Затем, в полученной матрице находим минимальный элемент в каждом столбце hj и вычитаем его из всех остальных элементов ℓ′ij, расположенных в рассматриваемом столбце:

  (3)

3. Переходим к оценочной матрице – . Определяем для каждого элемента с  оценку по формуле:

 (4)

где  – наименьший элемент в строке i
 – наименьший элемент в столбце j

Находим пару k–s с максимальной оценкой:

  (5)

4. Создаем новую матрицу . Для этого вычеркиваем из матрицы строку k и столбец s с наибольшей оценкой. Блокируем ячейку на пересечении строки s и столбца k, а также ветвь, ведущую к зацикливанию цепи со звеном k–s
5. Создаем новые фиктивные матрицы Фk и Фs, вводя в  фиктивные узлы k и s
6. Выполняем над полученными матрицами , Фk и Фs операции приведения и оценки, описанные в пунктах 2–3, до тех пор, пока последняя вычеркиваемая ветвь не станет очевидной. 
7. Оптимальный маршрут устанавливается путем сравнения всех возможных вариантов вычеркивания ветвей.
Заметим, что фиктивные узлы k и s вводятся только при наличии строки и столбца с их номерами. В качестве целевой функции можно использовать расстояние, время, стоимость и т.д. Если в процессе расчета получается несколько маршрутов с одинаковым значением целевой функции, то в качестве критерия оптимальности следует принять транспортную работу.
Алгоритм используется для симметричной и не симметричной матриц расстояний. Для реализации алгоритма разработана программа, блок-схема которой приведена на рис. 2. В ней предусмотрены два режима расчета. 
В первом случае фиктивные приведенные вершины вводятся автоматически в процессе решения матрицы расстояний. Их количество равно числу хорд, входящих в действительный узел минус единица. 
Во втором случае предусмотрен контроль над вводом количества фиктивных вершин по усмотрению оператора ПК. Это позволяет сократить количество вариантов и время решения задачи, если заранее известно максимальное количество заездов в вершину транспортного графа. Кроме того, с помощью второго похода можно регулировать количество заездов в вершины транспортного графа. Такая задача называется закрытой. В результате расширяется возможности предложенной методики. Если количество приведенных фиктивных узлов равно нулю, то получаем решение задачи методом ветвей и границ. 
Методика приведенных фиктивных узлов и ветвей является обобщением алгоритма ветвей и границ.

Рис. 2. Блок-схема метода «фиктивных ветвей» (начало)

Рис. 2. Блок-схема метода «фиктивных ветвей» (продолжение)

Рис. 2. Блок-схема метода «фиктивных ветвей» (окончание)

Таким образом, разработан алгоритм, позволяющий осуществлять расчет маршрутов при неоднократном посещении вершин транспортного графа.


Библиографический список
  1. Литл, Дж. Алгоритм для решения задачи о коммивояжере. [Текст] / Дж. Литл, К. Мурти, Д. Суини, К. Карел // Экономика и математические методы. – М., 1965. – Т. 1. Вып. 1.– С. 94-107.


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


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: