Задача о коммивояжере

Задача о коммивояжере – одна из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы решения.

Постановка задачи. Коммивояжер должен объехать N городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i – м и j – м городом, которые заданы в виде матрицы . Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты были минимальными.

Если затраты на переезд между каждой парой городов не зависят от направления движения, то задача называется симметричной, в проивном случае – несимметричной.

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

Математическая модель задачи. В качестве переменных выбираются элементы матрицы переездов: .

Пусть .

Модель задачи:

()

Первые n ограничений задают условие: в каждый город коммивояжер въезжает только один раз. Следующие n ограничений задают условие: из каждого города коммивояжер выезжает только один раз.

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

Методы решения. Как задача булева программирования может быть решена методом ветвей и границ – в этом методе уже заложено условие связанности полного цикла []; венгерским методом с модификацией, отвергающей решения с неполными замкнутыми циклами [] и рядом других методов.

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

()

()

()

Условия блока () не допускают появления неполных замкнутых циклов между парами городов. Условия блока () не допускают появления неполных замкнутых циклов между тремя городами. Аналогичный блок условий () вводится для всех четверок городов. Кроме того, добавляются ограничения:

()

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

Метод ветвей и границ ("поиск с возвратом", "backtracking"). Метод ветвей и границ – один из наиболее эффективных и быстрых методов решения задачи о коммивояжере, разработан Литтлом, Мерти, Суини, Кэрелом [] в 1963 г. Представляет собой итеративную схему неявного (улучшенного) перебора, который состоит в отбрасывании заведомо неоптимальных решений.

Идея метода. Пусть – множество всех допустимых замкнутых маршрутов (циклов) задачи о коммивояжере с n городами и матрицей затрат . Множество состоит из (n-1)! циклов. Метод Литтла основан на разбиении множества на два непересекающихся подмножества и на вычислении оценок каждого из них. Далее подмножество с минимальной оценкой (стоимостью) разбивается на два подмножества и вычисляются их оценки. На каждом шаге выбирается подмножество с наименьшей из всех полученных на этом шаге оценок и производится его разбиение на два подмножества. В конце концов получаем подмножество, содержащее один цикл (замкнутый маршрут, удовлетворяющий наложенным ограничениям), стоимость которого минимальна.

Алгоритм метода.

1.  Приведение матрицы затрат , вычисление нижней оценки стоимости маршрута r.

1.1.  Вычисление наименьшего элемента по каждой строке (константы приведения):

, . ()

1.2.  Переход к новой матрице с элементами:

. ()

1.3.  Вычисление наименьшего элемента по каждому столбцу (константы приведения):

, . ()

1.4.  Переход к новой матрице с элементами:

. ()

1.5.  Вычисление нижней оценки стоимости маршрута (сумма констант приведения):

. ()

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

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

Если ребро (h, k) не включается в маршрут, то в него входит некоторый элемент строки h и столбца k. Следовательно, стоимость «неиспользования» (h, k) во всяком случае, не меньше суммы минимальных элементов строки h и столбца k, исключая сам элемент . Отсюда

. ()

3.  Выбор нулевого элемента, которому соответствует максимальный штраф. Если таких элементов несколько, то выбирается любой из них. Разбиение множества всех допустимых маршрутов на два подмножества: подмножество содержащее ребро (h, k) – ; подмножество, не содержащее ребро (h, k) – .

4.  Вычисление оценок затрат по всем маршрутам, входящим в каждое подмножество

4.1.  Для оценка затрат:

. ()

4.2.  При вычислении оценки затрат для учитывают, что если ребро (h, k) входит в маршрут, то ребро (k, h) не может входить в маршрут, поэтому принимаем: ; если в маршрут включено ребро (h, k), то ни одно другое ребро, начинающееся в h или заканчивающееся в k не может входить в маршрут, поэтому строка h и столбец k вычеркиваются. В полученной матрице нужно выбрать элемент из каждого столбца и каждой строки таким образом, чтобы суммарная стоимость выбранных элементов была не меньше суммы приводящих констант матрицы . Тогда оценка затрат:

. ()

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

Алгоритм продолжается до тех пор, пока в подмножестве маршрутов с наименьшей оценкой не останется всего один маршрут.

Пример. Рассмотрим пример решения задачи о коммивояжере методом ветвей и границ. В табл. 1 приведена матрица затрат С размерностью 5´5. Элементы матрицы С, стоящие на главной диагонали, равны: , так как переезд из i-го города в i-ый невозможен.

Таблица 1.

1

2

3

4

5

1

¥

14

9

16

7

2

20

¥

9

19

14

3

18

15

¥

12

12

4

23

10

13

¥

17

5

7

6

6

6

¥

На первом шаге выполняют приведение матрицы затрат, для чего вычисляют константы приведения по строкам (табл. 2).

Таблица 2.

1

2

3

4

5

a

1

¥

14

9

16

7

7

2

20

¥

9

19

14

9

3

18

15

¥

12

12

12

4

23

10

13

¥

17

10

5

7

6

6

6

¥

6

Затем переходят к новой матрице затрат с элементами , которые получены в результате вычитания из всех элементов исходной матрицы констант приведения (табл. 3). Далее вычисляются константы приведения по столбцам (табл. 3).

Таблица 3.

1

2

3

4

5

1

¥

7

2

9

0

2

11

¥

0

10

5

3

6

3

¥

0

0

4

13

0

3

¥

7

5

1

0

0

0

¥

b

1

0

0

0

0

Выполняют переход к новой матрице затрат с элементами , полученными путем вычитания из элементов матрицы (табл. 3) констант приведения . В результате матрица затрат приведена (табл. 4) – в каждой строке и в каждом столбце есть хотя бы один нулевой элемент. Нижняя оценка стоимости маршрута равная сумме констант приведения по строкам и столбцам составляет: r=45. Оценка множества всех допустимых маршрутов также равна: = r=45. Обратите внимание из нулевых элементов матрицы затрат невозможно составить полный замкнутый цикл, следовательно оптимальный маршрут будет иметь большую стоимость.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7