Задача о составлении маршрута коммивояжера. Метод ветвей и границ

Введение

Актуальность данной темы заключается в следующем, Для решения оптимизационных и других задач строительства нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ, симплексный метод,метод Фогеля (приближенного решения), метод дефектов и другие методы.

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

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

Целью данной работы будет:

1. Познакомить читателя с основными понятиями теории графов.

2. Дать представление о задаче коммивояжера.

3. Описать метод ветвей и границ.

4. Привести пример использования метода ветвей и границ для решения задачи коммивояжера.

1. Постановка задачи

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

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

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

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. В качестве примера конкретного применения метода может быть предложена прикладная задача, связанная с проблемой размещения и обслуживания оборудования, в которой требуется определить оптимальную траекторию циклического маршрута движения робота-транспортера по траектории цеха с целью периодического обслуживания оборудования.

2. Обзор других методов решения задачи коммивояжера

Другие методы, предложенные для поиска кратчайших гамильтоновых циклов – алгебраический метод, основанный на работе Йоу, Даниэльсона и Дхавана (включает в себя построение всех простых цепей с помощью последовательного перемножения матриц), метод перебора Робертса и Флореса (метод перебора имеет дело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется некоторым систематическим способом, после чего продолжается поиск гамильтонова цикла. Другой подход – мультицепной метод, предложенный Селби.

3. Теория графов

3.1 Основные понятия теории графов. Определения

Граф G задается множеством точек или вершин x₁, x₂, …x_n(которое обозначается через X) и множеством линий или ребер a₁, a₂, …a_m(которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X, A).

Если ребра из множества А ориентированны, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называют ориентированным графом. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Граф в этом случае обозначается парой G=(X, Г).

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

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

Иногда дугам графа G сопоставляются (приписываются) числа – дуге (x_i, x_j) ставится в соответствие некоторое число c_i_j, называемое весом, или длинной. Тогда граф G называется графом со взвешенными дугами. Иногда веса приписываются вершинам x_i графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. При рассмотрении пути

, представленного последовательностью дуг, за его вес (или длину) принимается число

, равное сумме весов всех дуг, входящих в

, т.е.

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

коммивояжер граф задача метод

Если G = (X, A) – неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в котором каждая пара вершин соединена одной и только одной простой цепью). Например, если G – граф, показанный на рис. 1а, то графы на рис. 1.б, в являются остовом этого графа.

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

Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

Решение обобщенной задачи коммивояжера

Пусть каждой дуге (i, j) графа (I, U) поставлено в соответствие число

называемое длиной дуги.

Рассмотрим задачу: определить кратчайший путь из множества А в множество В, пересекающий каждое множество разбиения один и только один раз. Очевидно, что если каждое множество разбиения состоит из одного элемента и

, то имеем обычную задачу коммивояжера.

Определим функцию

: положим для произвольного пути

. Итак, значениями функции

будут множества номеров подмножеств разбиения, которые пересекает путь

. Пусть каждое множество Ф_i,

, состоит из всевозможных подмножеств множества {1, 2,…, p}, a

. Применим для решения этой задачи следующий алгоритм.

Достаточной системой функций в данном случае будут функции

Обозначим через

число элементов произвольного конечного множества А.

Шаг 0. Положим

. Пометим вершины

признаками

. Для помеченных вершин увеличим

на 1. Рассмотрим одну из пометок и перейдем к шагу 1.

Задача о составлении маршрута коммивояжера. Метод ветвей и границ (стр. 1 из 3)

Задача о составлении маршрута коммивояжера. Метод ветвей и границ

Решение обобщенной задачи коммивояжера