Кадура (Математическое моделирование процессов перевозки грузов железнодорожным транспортом на основе использования задачи коммивояжера), страница 8

1. Рассмотрим сначала первый маршрут из решения задачи нескольких коммивояжеров. Если Q(1) > 2, перейдем к шагу 2, иначе - на шаг 9.

2. Положим i = 1.

3. Полагаем , j=i+2.

4. Вычисляем . Если < , то присваиваем = и .

5. j = j +1. Если j < Q(1), переход к шагу 4.

6. Если < 0, меняем местами в последовательности обхода вершины , и . Соответственно длина маршрута изменится на величину .

7. i = i +1. Если , переход к шагу 3.

8. В случае, когда данный процесс (шаги со 2-го по 7-й) привел к обра­зованию нового маршрута, длина которого меньше длины старого, переход к шагу 2 (применение описанной процедуры к новому маршруту).

9. Применение изложенного алгоритма (шаги 1-8) к каждому следую­щему маршруту, входящему в решение задачи нескольких коммивояжеров.

Алгоритм №3 отличается от алгоритма №2

• Способом вычисления значения (см. рисунок 25);

• На шаге 1 неравенство Q(1)>2 заменяем на Q(1)>1;

• На шаге 3 вместо j = i + 2 пишем j = i +1;

• Шестой этап: Если < 0, в последовательности обхода ставим вер­шину за вершиной . Соответственно длина маршрута изменится на вели­чину .

• В 7-м шаге следует записать не .

Рисунок 25- Иллюстрация к перемене места вершины ,- в маршруте

Длина нового маршрута отличается от длины старого на величину

Алгоритм №4.

Применяем алгоритм только в том случае, когда количество выбранных коммивояжеров больше единицы и количество небазовых вершин в макси­мальном маршруте больше единицы.

1. В решении задачи нескольких коммивояжеров выделяем маршрут тр с максимальной длиной J₂. Если конец работы. Присвоим nfv=1.

2. Найдем в максимальном маршруте номер вершины, удаление которой из этого маршрута уменьшает его длину. Положим текущий номер вершины i=nfv-1.

3. i=i+1. Вычислим .

4. Если <0, положим nfv=i и перейдем к шагу 5. Иначе, если , переход к шагу 3, а если , конец работы - искомой вершины не существует.

5. Теперь попытаемся добавить вершину с номером nfv максимального маршрута в другой маршрут. Положим j=0. j будет представлять номер оче­редного маршрута, не являющегося максимальным.

6. i= 0 (i - номер текущей вершины не максимального маршрута), .

7. Рассматриваем j-й маршрут. Вычислим Если , присвоим .

8. . Если , перейдем на шаг 7.

9. Если <0, то удаляем из максимального маршрута вершину с номе­ром nfv, и добавляем ее в j-й маршрут между вершинами с номерами i1 и i1 + 1. Длина максимального маршрута изменится на величину Длина j-го маршрута изменится на величину . Переход к 1-му шагу.

10. Если j < т -1 (т.к. рассматриваются все маршруты, кроме одного, яв­ляющегося максимальным), переход к шагу 6.

11. В случае, когда заканчиваем работу, иначе присваиваем = +1 и переходим к шагу 2 (отправляемся искать в максимальном мар­шруте следующего кандидата на удаление).

Рисунок 26- Иллюстрация к удалению вершины из максимального маршрута

Длина нового маршрута отличается от длины старого на величину :

Рисунок 27- Иллюстрация к добавлению вершины из максимального мар­шрута в другой маршрут

Длина нового маршрута отличается от длины старого на величину :

Рассмотрим пример расчета по изложенному алгоритму при п = 8, s = 3, = 1, = 1, InterNum=500 для графа, изображенного матрицей на рисунке 28.

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

1)

2)

Суммарная длина маршрутов равна 134, длина максимального из мар­шрутов равна 73, значение критерия качества равно 9782.

Рисунок 28- Пример матрицы весов задачи нескольких коммивояжеров при п = 8,5 = 3

Поскольку эвристический алгоритм имеет случайную составляющую, за­пустив программное обеспечение несколько раз, мы совсем не обязательно при­дем к одинаковым и тем более точным решениям рассматриваемой задачи. Тем не менее, в данном случае, как правило, выпадало вышеуказанное оптимальное решение. При InterNum = 500 программа, применяемая к задачам с количеством небазовых вершин порядка 50-ти и количеством коммивояжеров порядка 10-ти, работает меньше секунды. Таким образом, при небольшом количестве итераций о времени работы алгоритма беспокоиться не стоит. С увеличением InterNum до нескольких миллионов время может увеличиться до пяти-шести минут, но и качество приближения решения тоже возрастает. В общем случае оценить по­грешность приближения не представляется возможным. Приведем приблизи­тельную оценку погрешности решения задач, точный минимум которых мы способны определить. Положим InterNum = 1000000, а₁= 1, а₂ = 1 и сгенериру­ем для каждой рассматриваемой пары п, s 10 различных матриц с элементами из отрезка [1, 999]. Найдем процентное выражение погрешности по формуле

, где - значение критерия качества точного решения i-й задачи, полученного посредством метода, использующего деревья поиска; - значение критерия качества приближенного решения i-й задачи, полученного по эвристическому алгоритму.

Таблица 7-Погрешность работы эвристического алгоритма в процентах

Прочерки соответствуют задачам, не поддающимся решению точными методами. Когда п достигает сорока, величина критерия качества аппроксими­рующего решения превосходит значение критерия качества точного в среднем более чем в полтора раза. Тем не менее, рекомендации, которые дает эвристи­ческий алгоритм, намного лучше произвольного, наугад взятого множества маршрутов.

2.5 Комбинированный алгоритм

Комбинированный алгоритм предназначен для нахождения точных ми­нимумов и представляет собой комбинацию метода, использующего деревья поиска и эвристического алгоритма. Сначала находится приближенное решение задачи нескольких коммивояжеров посредством разработанного эвристическо­го алгоритма. Это решение подается на вход метода, использующего деревья поиска. В результате классы допустимых решений с большим значением крите­рия качества сразу отбрасываются, благодаря чему в некоторых случаях дости­гается экономия времени поиска. Иногда обсуждаемый алгоритм позволяет определить минимум задачи, выходящей за рамки множества разрешимых с по­мощью метода, использующего деревья поиска задач. Он особенно важен в тех случаях, когда не все допустимые решения задачи нескольких коммивояжеров удовлетворяют требованиям специфической прикладной задачи.

Выводы по второй главе:

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

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

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

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

5. Рассмотрен комбинированный алгоритм, который является совокупно­стью эвристического алгоритма и метода, использующего деревья поиска. В некоторых случаях комбинированный алгоритм позволяет быстрее находить точное решение сформулированной задачи нескольких коммивояжеров.

3 Использование разработанных методов при моделировании специфических транспортных процессов

3.1 Предварительное преобразование исходного графа

Рассматриваемая ранее постановка задачи нескольких коммивояжеров предполагает полноту графа G(X,U). На практике данное условие, как прави­ло, не выполняется. Большинство реальных транспортных сетей не являются полными графами. Решить эту проблему позволяет преобразование исходного графа транспортной сети к полному G(X,U). Опишем, каким об­разом осуществляется такое преобразование. Рассмотрим пример исходного графа , не являющегося полным, изображенный на рисунке 29. Пусть для простоты веса всех его ребер будут равны единице. Посещения требуют вершины с первой по восьмую. В каждой точке а_i находится коммивояжер, завершающий обход в соответствующей точке .

Рисунок 29- Пример непреобразованнного графа

Тогда матрица весов примет вид:

Рисунок 30- Матрица весов графа