Одним из недостатков метода ветвей и границ (ВиГ) является посещение вершины транспортного графа один раз. В работе разработана методика устранения этого недостатка путем повторного использования приведенных фиктивных узлов и ветвей в процессе решения матрицы расстояний.
Приведенным фиктивным узлом называется повторно введенная, вычеркнутая в оценочной матрице вершина. Он вводится на следующем этапе. Матрица с таким узлом называется фиктивной. Принципиальная схема ввода фиктивных элементов представлена на рис. 1, где фиктивные узлы и ветви изображены пунктирной линией.
 |
 |
Рассмотрим вариант постановки задачи, не имеющей вырождения решения. Усовершенствованный алгоритм решения задачи маршрутизации метода ВиГ представим в следующем виде:
1. Составляем исходную матрицу расстояний L между пунктами:
(1)
В (1) буква Ч означает очень большое число.
2. Переходим к приведенной матрице – 
. Для этого в каждой строке находим минимальный элемент hi и вычитаем его из всех остальных элементов ℓij, расположенных в рассматриваемой строке:
.gif){kind=small}
(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. Блок-схема метода «фиктивных ветвей» (продолжение)
Таким образом, разработан алгоритм, позволяющий осуществлять расчет маршрутов при неоднократном посещении вершин транспортного графа.
Библиографический список
- Литл, Дж. Алгоритм для решения задачи о коммивояжере. [Текст] / Дж. Литл, К. Мурти, Д. Суини, К. Карел // Экономика и математические методы. – М., 1965. – Т. 1. Вып. 1.– С. 94-107.
Количество просмотров публикации: Please wait