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

Рисунок 11-Матрица конкретной задачи нескольких коммивояжеров

2.3 Метод, использующий деревья поиска

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

Первым делом рассмотрим алгоритм решения задачи с фиксированным количеством агентов, равным т. Остановимся только на изменениях, вносимых в метод в связи с рассматриваемой постановкой.

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

• элементы главной диагонали матрицы;

• веса всех дуг графа, входящих в а_i и выходящих из b_i i= все элементы столбцов а_i и строк b_i i= становятся равными бесконечности (эти строки и столбцы можно вычеркнуть);

• элементы матрицы, соответствующие дугам вида (a_i,b_j), i,j= , что­бы непосредственной связи между концевыми точками маршрутов не было.

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

• если q a_i и р b_i, i= , то следует положить элемент (р, q) равным бесконечности для предотвращения образования контура, не содержащего ни­какие из а_i и строк b_i i= ;

• равенства q a_i и р b_i, i= , означают, что получен один из мар­шрутов искомого допустимого решения. Количество сформированных маршру­тов /увеличиваем на единицу: (в начале работы ).

- теперь следует просмотреть каждый меньший бесконечности элемент (х,у) текущей подматрицы: нужно ли его запретить? Чтобы ответить на этот вопрос, необходимо знать к чему привело бы последующее присоединение дан­ного звена к частичному решению. Звено запрещается в двух случаях.

1. В случае, когда в данный момент т-f = 1, а присоединение дуги

выходящих из b_i i= дает путь между пунктами q и p, где q a_i и р b_j, j,i= j i. Равенство т-f = 1означает, что неопределенным остался единственный маршрут. Что­бы предотвратить его преждевременное образование, сформировав таким обра­зом т маршрутов, охватывающих менее п городов, полагаем вес (х,у) равным бесконечности.

1. Если в настоящее время выполнено неравенство т-f >1, а включе­ние в частичное решение звена приводит к образованию пути между пунктами q и р, причем q a_i и р b_j, j,i= j i.Так как подобные мар­шруты не являются допустимыми по условию задачи, запрещаем включение звена (х,у).

1. Опишем теперь способ вычисления нижних границ целевого функцио­нала. Возьмем произвольное допустимое решение рассматриваемой задачи с фиксированными т коммивояжерами. Как и в классической задаче коммивоя­жера, каждая строка и столбец преобразованной на первом этапе матрицы весов задачи т коммивояжеров содержат единственное звено, входящее в это допус­тимое решение. Следовательно, при вычитании из какой-либо строки или столбца преобразованной матрицы весов некоторого положительного числа, величина J₁, очевидно, изменится на то же самое число. Таким образом, ниж­ней границей величины J₁ может служить величина H - сумма констант при­ведения, подсчитываемая как в классической задаче коммивояжера: J₁> H.

Найдем теперь нижнюю границу критерия J₂. Поскольку длины маршру­тов допустимого решения задачи т коммивояжеров не превосходят J₂, выпол­нено неравенство: mJ₂>J_1.

Разделим обе части приведенных неравенств на положительное число m: , отсюда следует, что

Возведем неравенства в неотрицательные степени и соответственно: ,

Перемножив последние два неравенства, получим, что

Изложим порядок выполнения метода, использующего деревья поиска.

1. Образуем начальный рекорд - допустимое решение R задачи несколь­ких коммивояжеров. Возьмем первого коммивояжера из s имеющихся и после­довательность п чисел 1,2, определяющую допустимое решение ,1,2,…,n, Подсчитаем длину этого маршрута и значение критерия качества J.

2. Полагаем значение m (текущее количество коммивояжеров) равным 1.

3. Инициируем счетчик сочетаний из s (общее число коммивояжеров) по т: k = 1.

4. Генерируем k сочетание из s по т, т.е. выбираем т конкретных ком­мивояжеров из s имеющихся.

5. Метод ветвей и границ будем применять, используя подматрицу пре­образованной матрицы весов задачи. Подматрица образуется путем вычеркива­ния строк и столбцов, соответствующих точкам начального и конечного место­нахождения коммивояжеров, которые в данный момент не являются выбран­ными. С целью определения т требуемых маршрутов производится вычисление нижних границ и ветвление до тех пор, пока это целесообразно. Множества решений со значением критерия качества большим, чем у рекорда исключаются из рассмотрения. При определении в процессе работы метода допустимого ре­шения R^Т задачи со значением J^т критерия качества, сравниваем его с рекор­дом. Если J^т <J то рекордом становится новое решение R^т: R = R^т, J = J^т. В противном случае остается прежний рекорд R.

6. k = k +1. Если k < , переход к шагу 4.

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

8. Выводим найденное решение R и значение критерия качества J. За­вершаем работу алгоритма.

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

В таблице указано, какой максимальной размерности удалось достигнуть при нахождении точного минимума задачи нескольких коммивояжеров в зави­симости от количества коммивояжеров (показатели важности критериев равны единице). Для каждого значения s подбиралось некоторое максимальное значе­ние п по следующему правилу. Создавалось 20 произвольных задач нескольких коммивояжеров, т.е. 10 случайных графов с n+2s вершинами и 10 случайных с вершинами. Все задачи решались посредством разработанного программного обеспечения. Значение п заносилось в соответствующую клетку таблицы в случае, когда каждая задача из первой группы была решена за прак­тически приемлемое время порядка пяти минут, и существовала хотя бы одна задача из второй группы, при решении которой работа программы была оста­новлена из-за превышения лимита времени. В противном случае снова генери­ровалось 20 случайных графов с большим значением п и т.д.

Таблица 6

Максимальные размерности практически разрешаемых задач

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

К недостаткам метода можно отнести следующее:

1. Множество разрешимых задач все же недостаточно велико.

2. Ненадежность метода, трудности с прогнозированием времени работы программной реализации. Тестирование программы проводилось на случайных графах, но следует иметь ввиду, что существуют задачи куда меньших размеров, практически неразрешимые с помощью мето­да, использующего деревья поиска. Примером служат задачи с матри­цей весов, все элементы которой близки к одному и тому же числу. Рассмотрим матрицу с п=9, s=3 и матрицу n=10, s=3, при =1 и =1. Положим значения всех элементов матриц равными единице. Тогда время работы метода, использующего деревья поиска, в первом случае составит 15 минут 30 секунд, а время работы метода полного перебора - 0 минут 20 секунд. Во втором случае метод полного перебора находит решение за 4 минуты 12 секунд. Выполнение же про­граммы, реализующей метод, использующий деревья поиска по исте­чении двадцати минут пришлось прервать, так и не дождавшись отве­та.

3. Все значения минимизируемых критериев, а также показатели важно­сти и все элементы исходной матрицы должны быть строго неотрица­тельными.

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

Проиллюстрируем работу метода на уже рассматриваемой ранее задаче с матрицей на рисунке 12.

Образуем начальный рекорд R: ,1,2,3, , J=16900. Положим равными бесконечности те элементы матрицы расстояний, которые заведомо не входят в решение:

Рисунок 12-Матрица с наложенными запретами

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

Рисунок 14- а) приведенная матрица, на б) - та же матрица с указанием весов нулей.