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

Можно приписать положительные числа не только дугам, но и вершинам исходного графа. Тогда длина маршрута будет складываться из произведений (либо сумм) длины каждого отрезка пути (х, у) и веса вершины. Однако в дан­ном случае наличие вершинной взвешенности не имеет большого значения. За­дача с вершинно взвешенным графом сводится к вышеуказанной постановке переходом к новому графу, в котором стоимость каждой дуги равна произведе­нию (либо сумме) веса дуги и вершины у исходного графа.

Допустимым решением задачи нескольких коммивояжёров назовём каждое n-элементное множество, с элементами, представляющи­ми собой вершинно непересекающиеся пути (между соответствующими базо­выми узлами), которые в совокупности покрывают п небазовых узлов. Допус­тимое решение с наилучшим значением некоторого критерия качества назовем точным решением. Критерием J качества решения будем считать произведение

J = ,

где J₁- сумма длин всех маршрутов в данном решении, J₂ - длина макси­мального маршрута, и - показатели важности рассматриваемых критери­ев. Определение показателей важности производится посредством опроса Е экспертов. Если Е₁экспертов считают нужным минимизировать J₁ а Е₂ экс­пертов - минимизировать J₂ (Е₁+ Е₂= Е), в качестве показателя следует взять отношение , а в качестве взять . Если же нет времени на опрос (задача должна решаться в реальном времени), можно, например, выбрать один из трех вариантов:

• = 1, = 0 соответствует минимизации суммарной длины маршру­тов;

• = 0, = 1 - минимизация длины маршрута с максимальной длиной;

- = 1, = 1 - минимизация произведения обоих, в равной степени важных, критериев.

Структуру графа задачи нескольких коммивояжеров удобно представить с помощью матрицы весов следующего вида:

Рисунок 11. Матрица графа задачи нескольких коммивояжеров при п = 3, s = 2. Диагональные элементы полагаются равными нулю, либо бесконечности.

Как известно, количество Р вариантов, подлежащих перебору в задаче коммивояжёра равно n!, или (п-1)!, в случае фиксации первоначального горо­да. Подсчитаем количество допустимых решений в сформулированной задаче нескольких коммивояжёров. Наряду с перебором всех n! перестановок номеров вершин, для каждой перестановки необходимо просмотреть и всевозможные её разбиения на т подмножеств. Рассмотрим некоторую фиксированную переста­новку п чисел:

(1 2 3 4 ... п-1 п), и вставим между числами (n-1) разделителей:

(112 | 3 | 4 \...\п-1|п).

Тогда выбор любых (т-1) разделителей будет давать требуемое разбие­ние на т групп. Следовательно, всего возможных разбиений будет

Максимальное количество коммивояжёров равно s. Задействоваться мо­гут не все из них. При фиксированном числе задействованных коммивояжёров общее количество вариантов задействования составит

Следовательно, ответом будет число

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

Таблица 4-Примеры роста С_пs

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

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

2.2 Метод полного перебора

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

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

Порядок работы метода следующий.

1. Фиксируем первого коммивояжера из б имеющихся и перестановку п чисел (1,2,... ,п-1, п), определяющую допустимое решение R задачи несколь­ких коммивояжеров: а₁ ,1,2,...,п,b₁. Подсчитываем длину этого маршрута и зна­чение критерия качества 3 решения.

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

3. Генерируем k1-ю перестановку п чисел.

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

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

6. Генерируем k2-е сочетание из s по т, т.е. выбираем т коммивояжеров из 5 имеющихся.

7. Инициируем счетчик сочетаний изn-1поm-1:k3 = 1.

8. Генерируем k3-е сочетание из п-1 по т-1, интерпретирующееся как разбиение перестановки на части. Таким образом, полученные выше данные определяют допустимое решение R^Т задачи.

9. Теперь у нас есть допустимое решение R^Т, т.е. имеются выбранные коммивояжеры и для каждого из них указан маршрут - это соответствующая часть перестановки, полученная в результате разбиения. Подсчитываем длину маршрутов, находим маршрут с максимальной длиной. Вычисляем значение критерия качества J^Т, равное произведению суммы длин маршрутов .J₁ в сте­пени на длину максимального из них J₂ степени

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

11. k3 = k3 +1. Если k3 < , переход к шагу 8.

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

13. т = т +1. Если т < min{s,n}, переходим к шагу 5.

14. k1 = k1 +1. Если k1< Р, переходим к третьему шагу.

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

Данный алгоритм позволяет - по крайней мере формально - определить точный минимум поставленной задачи. Зависимость времени работы алгоритма от количества коммивояжеров и городов отражена в таблице 5. Программное обеспечение запускалось на компьютере типа Acer. В качестве весов ре­бер брались псевдослучайные целые числа из отрезка [1, 999], коэффициенты и ₂ были взяты равными единице.

Таблица 5.

Время работы метода полного перебора при различных парах п и s.

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

Выпишем для примера все допустимые решения конкретной задачи (рисунок 11) с тремя небазовыми вершинами, двумя коммивояжерами и показателями важности, равными единице. С_т будет равно 24.