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

Сумма констант приведения Н₁=79. Критерий J ограничивает снизу величина Н₁ (J) =6241. Лучшим кандидатом на ветвление является элемент (а₁,2). Включая данное звено в частичное решение необходимо наложить запрет для предотвращения преждевременного образования маршру­та.

Рисунок 15-Матрица после приведения и подсчета нулей

Производя дальнейшее ветвление по элементу (1, ) и запрещая недопус­тимый элемент (2,1), приходим к матрице 2 на 2 (рисунок 15, в)) и новому рекорду R: ,2,3,1, , со значением критерия качества J=7396. Весь процесс ветвле­ния изображен на рисунке 16. Ветвление из узлов 2 и 4 не производится, т.к. и

Рисунок 16- Первое дерево вариантов решений рассматриваемого примера

Возьмем теперь второго коммивояжера. Матрица соответствующей зада­чи будет выглядеть так:

После приведения (сумма констант равна 79) и подсчета весов нулей име­ем соответственно рисунок 17, а) и б).

Рисунок 17-Матрица после приведения

Произведем ветвление с использованием элемента (3,1). Вычеркнем стро­ку 3 и столбец 1. Запретим элемент (1,3) чтобы не прийти к недопустимому циклу 3,1,3. В результате получим матрицу на рисунке 18.

Рисунок 18- Матрица с ветвлением

Выполнив приведение (сумма констант равна 14) получим матрицу на рисунке 18 (б). Дерево поиска изображено на рисунке 19.

Рисунке 19-Второе дерево вариантов решений рассматриваемого примера

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

Осталось рассмотреть последний случай - когда т = 2, т.е. задействуются оба коммивояжера.

Приводим матрицу на рисунке 12, сумма констант приведения равна 95. На­ходим веса нулей (рисунок 20).

Рисунок 20-Приведенная матрица

Нуль ( ,2) с весом 11 выбирается для ветвления. Соответственно ниж­няя граница множества увеличивается на 11. Оценку снизу множества ( ,2) можно увеличить на 3, вычеркнув соответствующие строку и столбец, и запретив элемент (2,b₂) чтобы исключить возможность формирования не удовлетворяющего условию маршрута ,2,b₂. В результате будет образована матрица на рисунке 21.

Рисунок 21-Матрица с подсчетом веса ее нулей

Далее проведем ветвление по нулю (а₂,3), имеющему наибольший вес 28. При этом следует запретить элемент (ЗД) по той же причине, что и в про­шлый раз. Получим матрицу, которая не требует приведения. По­сле подсчета весов нулей имеем рисунке 21(б).

Остановимся теперь на кандидате (1, ) для последующего разбиения на подмножества. Делая необходимые вычеркивания и полагая (3,1) = , прихо­дим к матрице 2 на 2, и проводим исчерпывающую оценку. Те­кущий рекорд заменяется новым значением R с меньшим значением критерия качества:

2. J=6076.

Рисунок 22-Третье дерево примера

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

Выпишем матрицу в узле 6, а затем приведем ее и подсчита­ем веса нулей.

Рисунок 23-Матрица для узла 2

Выбираем элемент (1 , ) и разбиваем подмножество в узле 6 на два под­множества: и В вершине 8¹ порядок матрицы, на элемент (2,1) которой наложен запрет, равен 2, а значит можно сформировать очередное до­пустимое решение:

1. , 2, ,

2. , 3, 1, , , J=5100

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

2.4 Эвристический алгоритм

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

Приведем сначала порядок работы предлагаемого эвристического метода, затем подробно опишем составляющие его алгоритмы.

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

2. Полагаем номер итерации k равным 0. Будем обозначать через R^Т и J^т решение задачи и значение критерия качества соответственно, полученные на текущей итерации, а через J и R - значение критерия качества и решение, лучшее из встретившихся (ближайшее к оптимальному), используемое как эта­лон для сравнения с другими решениями в процессе работы алгоритма. В дан­ный момент эталоном является решение, полученное на первом шаге алгорит­ма.

3. Начало итерационного процесса. Если k< IterNum, то k = k +1. Ина­че, когда в течение IterNum итераций улучшения решения не произошло, пере­ход к шагу 11.

4. С вероятностью одна вторая формируем новое решение задачи, либо улучшаем ранее полученное. Генерируем вероятность - случайное число Р_х в интервале (0,1). Если Р_х >0,5, переходим к шагу 5 (формируем новое решение), иначе к шагу 7 (улучшаем имеющееся решение).

5. Случайным образом выбираем т<min{п,s} коммивояжеров из 5 имеющихся и количество городов для каждого маршрута, т - текущее количе­ство коммивояжеров. Генерируем случайную последовательность городов.

6. Генерируем случайное число Р₂ в интервале (0,1). Если Р₂>0,1, при­меняем Алгоритм №1 (метод ближайшего соседа). В противном случае исполь­зуем модифицированный прием метода статистических испытаний решения за­дачи коммивояжера - формируем новое произвольное решение R задачи, ис­пользуя данные, полученные на шаге 5. Переход к шагу 8.

7. Генерируем вероятность Р₃. Если 0 < Р₃ < 0,3, то применяем Алго­ритм №2; если 0,3 <Р₃ <0,6, применяется Алгоритм №3. Иначе выполняется Алгоритм №4.

8. Подсчитываем длину каждого маршрута решения R^т, находим сумму длин, выделяем максимальную длину. Вычисляем значение J^т.

9. Сравниваем J и J^T. Если J< J^T , то k = 0, и эталоном для сравнения

становится новое решение R^т: R = R^Т, J = J^Т. В противном случае остается прежний эталон R.

1. Переход к шагу 3.

2. Выводим результат - решение Я и значение критерия качества 3, за­канчиваем работу алгоритма.

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

Алгоритм №1 (развитие метода ближайшего соседа)

1. На пятом этапе вышеизложенного алгоритма были выбраны несколь­ко коммивояжеров из s имеющихся, было определено, сколько пунктов посетит каждый коммивояжер. Теперь для каждого коммивояжера следует определить, в каких именно пунктах он должен побывать, а также последовательность по­сещения указанных пунктов (небазовых вершин). Далее будем рассматривать поочередно i-го выбранного коммивояжера, i = 1..m. Начальное значение i = 0.

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

2. Если , переход к шагу 4. В противном случае - к шагу 5.

3. Если i<m, переход к шагу 2; иначе решение задачи нескольких ком­мивояжеров по методу ближайшего соседа сформировано, заканчиваем работу.

4. j = j + 1. Среди еще не содержащихся в маршрутах небазовых вершин находим вершину y, такую, что длина дуги (х,у), где х - последний выбран­ный пункт, наименьшая. Расположим вершину у в маршруте сразу после вер­шины х. Переход к шагу 3.

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

Алгоритм №2.

Этот алгоритм, являясь развитием эвристики Лина-Кернигана, использует перестановки вершин маршрутов (см. рис. 2.17). Адаптация данной эвристики заключается в ее применении к каждому маршруту в составе допустимого ре­шения задачи нескольких коммивояжеров. Из всевозможных перестановок мес­тами вершин в маршруте выбираем приводящую к максимальному уменыне- нию его длины. Будем повторять процедуру поиска оптимальной перестановки до тех пор, пока удается выделить таковую.

Рисунок 24- Иллюстрация к перестановке вершин Vi и Vj маршрута

Пусть представляет длину дуги .

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