Задача о составлении маршрута коммивояжера. Методветвей и границ
Введение
Актуальностьданной темы заключается в следующем, Для решения оптимизационных и других задачстроительства нередко прибегают к формулировке поставленной задачи в видекаких-то хорошо известных математических задач: транспортная задача, задачапоиска оптимального пути (задача коммивояжера) и другие. Сформулированную такимобразом задачу решают, используя такие математические методы, как метод ветвейи границ, симплексный метод, метод Фогеля (приближенного решения), методдефектов и другие методы.
Переборныеалгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решениикаждой конкретной задачи существенным образом зависит от способа организацииперебора.
Знаменитаязадача коммивояжера, поставленная еще в 1934 г., является одной из самыхважнейших задач в теории графов. В своей области (оптимизации дискретных задач)задача коммивояжера служит своеобразным полигоном, на котором испытываются всеновые методы.
Целью даннойработы будет:
1. Познакомитьчитателя с основными понятиями теории графов.
2. Датьпредставление о задаче коммивояжера.
3. Описатьметод ветвей и границ.
4. Привестипример использования метода ветвей и границ для решения задачи коммивояжера.
1.Постановка задачи
Коммивояжер(бродячий торговец) должен выйти из первого города, посетить по разу внеизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния междувсеми городами известны. В каком порядке следует обходить города, чтобызамкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найтигамильтонов цикл в графе минимальной длины.
Задачакоммивояжера является так называемой NP-трудной задачей, т.е. задачей, точноерешение которой в общем случае может быть получено только за экспоненциальноевремя. Следовательно, решать ее переборным алгоритмом неэффективно при большомколичестве вершин графа.
Одним из подходов к еерешению является сокращение перебора методом ветвей и границ. Этот методпозволяет опознать бесперспективные частичные решения, в результате чего отдерева поиска на одном шаге отсекается целая ветвь. Тем не менее,удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этомметоде, и родственных алгоритмов нет, хотя практика показывает, что насовременных ЭВМ они иногда позволяют решить задачу коммивояжера для графов сколичеством вершин, меньшим 100.
Впервые методветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачицелочисленного линейного программирования. Интерес к этому методу и фактическиего «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела,посвященной задаче коммивояжера. Начиная с этого момента, появилось большоечисло работ, посвященных методу ветвей и границ и различным его модификациям.Столь большой успех объясняется тем, что авторы первыми обратили внимание нашироту возможностей метода, отметили важность использования специфики задачи исами воспользовались спецификой задачи коммивояжера. В основе метода ветвей играниц лежит идея последовательного разбиения множества допустимых решений наподмножества (стратегия «разделяй и властвуй»). На каждом шаге метода элементыразбиения подвергаются проверке для выяснения, содержит данное подмножествооптимальное решение или нет. В качестве примера конкретного применения методаможет быть предложена прикладная задача, связанная с проблемой размещения иобслуживания оборудования, в которой требуется определить оптимальнуютраекторию циклического маршрута движения робота-транспортера по траекториицеха с целью периодического обслуживания оборудования.
2. Обзордругих методов решения задачи коммивояжера
Другиеметоды, предложенные для поиска кратчайших гамильтоновых циклов –алгебраический метод, основанный на работе Йоу, Даниэльсона и Дхавана (включает в себя построение всех простых цепей с помощью последовательногоперемножения матриц), метод перебора Робертса и Флореса (метод перебора имеетдело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либостановится ясно, что эта цепь не может привести к гамильтонову циклу. Тогдацепь модифицируется некоторым систематическим способом, после чего продолжаетсяпоиск гамильтонова цикла. Другой подход – мультицепной метод, предложенныйСелби.
3. Теорияграфов
3.1Основные понятия теории графов. Определения
Граф G задается множествомточек или вершин x/>1, x2, …xn(которое обозначаетсячерез X)и множеством линий или ребер a1, a2, …am(которое обозначаетсясимволом А), соединяющих между собой все или часть этих точек. Таким образом,граф Gполностью задается парой (X, A).
Если ребра измножества А ориентированны, что обычно показывается стрелкой, то они называютсядугами, и граф с такими ребрами называют ориентированным графом. Другое,употребляемое чаще описание ориентированного графа G состоит в заданиимножества вершин Х и соответствия Г, которое показывает, как между собойсвязаны вершины. Граф в этом случае обозначается парой G=(X, Г).
Путем (илиориентированным маршрутом) ориентированного графа называется последовательностьдуг, в которой конечная вершина всякой дуги, отличной от последней, являетсяначальной вершиной следующей.
Ориентированнойцепью называется такой путь, в котором каждая дуга используется не большеодного раза. Простой цепью называется такой путь, в котором каждая вершинаиспользуется не более одного раза. Очевидно, что простая орцепь является такжеорцепью, но обратное уже неверно.
Иногда дугамграфа Gсопоставляются (приписываются) числа – дуге (xi, xj) ставится в соответствиенекоторое число cij, называемое весом, илидлинной. Тогда граф G называется графом со взвешенными дугами. Иногда весаприписываются вершинам xi графа, и тогда получается граф со взвешеннымивершинами. Если в графе веса приписаны и дугам, и вершинам, то он называетсяпросто взвешенным. При рассмотрении пути />,представленного последовательностью дуг, за его вес (или длину) принимаетсячисло />, равное сумме весов всехдуг, входящих в />, т.е. />.
Гамильтоновцикл в орграфе – это ориентированный цикл (контур), проходящий ровно один разчерез каждую вершину графа (т.е. простая орцепь).
коммивояжерграф задача метод
/>
Если G = (X, A) – неориентированныйграф с nвершинами, то остовным деревом (или, короче, остовом) графа G называется всякийостовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в которомкаждая пара вершин соединена одной и только одной простой цепью). Например,если G– граф, показанный на рис. 1а, то графы на рис. 1.б, в являютсяостовом этого графа.
3.2 Задачакоммивояжера
Знаменитаязадача коммивояжера, поставленная еще в 1934 г., является одной из самыхважнейших задач в теории графов. В своей области (оптимизации дискретных задач)задача коммивояжера служит своеобразным полигоном, на котором испытываются всеновые методы.
Постановказадачи. Коммивояжер (бродячий торговец) должен выйти из первого города,посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первыйгород. Расстояния между всеми городами известны. В каком порядке следуетобходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминахтеории графов: найти гамильтонов цикл в графе минимальной длины.
Задачакоммивояжера является так называемой NP-трудной задачей, т.е. задачей, точноерешение которой в общем случае может быть получено только за экспоненциальноевремя. Следовательно, решать ее переборным алгоритмом неэффективно при большомколичестве вершин графа.Решениеобобщенной задачи коммивояжера
Пусть каждойдуге (i,j) графа (I, U) поставлено всоответствие число /> называемоедлиной дуги.
Рассмотримзадачу: определить кратчайший путь из множества А в множество В, пересекающийкаждое множество разбиения один и только один раз. Очевидно, что если каждоемножество разбиения состоит из одного элемента и />,то имеем обычную задачу коммивояжера.
Определимфункцию />: положим для произвольногопути />. Итак, значениями функции /> будут множества номеровподмножеств разбиения, которые пересекает путь />.Пусть каждое множество Фi, />,состоит из всевозможных подмножеств множества {1, 2,…, p}, a />. Применим для решения этойзадачи следующий алгоритм.
Достаточнойсистемой функций в данном случае будут функции
/>
Обозначимчерез /> число элементовпроизвольного конечного множества А.
Шаг 0.Положим />. Пометим вершины /> признаками />. Для помеченных вершинувеличим />на 1. Рассмотрим одну изпометок и перейдем к шагу 1.
Шаг 1. Пусть /> – рассматриваемая пометка.Пометим признаками /> все те вершины,для которых />. Для вновь помеченныхвершин увеличим /> на 1.
Рассмотримследующую помеченную вершину, и будем повторять помечивания до тех пор, пока непометим некоторую вершину /> так,чтобы для признака />пометки этойвершины выполнялось условие /> илипока нельзя будет сделать дальнейших пометок. В первом случае перейдем к шагу2. а во втором к шагу 3.
Шаг 2. Строимкратчайший допустимый путь от вершины />.Пусть /> – пометка вершины, длякоторой />. Перейдём к вершине /> и рассмотрим пометку /> вершины,
для которой />. Далее перейдем к вершине />, с пометкой />, для которой />. Последовательность />и является кратчайшимдопустимым путем.
Шаг 3. Пусть /> – множество помеченныхвершин. Рассмотрим все возможные числа />при/>. Определим среди этихчисел наименьшее и возьмем его за новое приближение />кдлине искомого пути. Затем перейдем к шагу 1.
Этот алгоритмможно изменить. Если для некоторой пометки />привсех j,для которых /> или />, то путь соответствующийэтой пометке, уже продленво все смежные с />вершины.Следовательно, для таких пометок признаки /> можностирать.
3.3 Методветвей и границ (МВГ)
Представим, чтонеобходимо обойти все города страны. Так как их много, то определить кратчайшийпуть затруднительно. Тогда можно выбрать некоторое разбиение множества городов,например, рассматривать республики, области или районы, и определить кратчайшийпуть, пересекающий каждое из выбранных подмножеств разбиения только один раз.Затем уже в пределах выбранных подмножеств достроить полученный путь дотребуемого. Такой подход используется в методе ветвей и границ. Этот методпозволяет опознать бесперспективные частичные решения, в результате чего отдерева поиска на одном шаге отсекается целая ветвь. Тем не менее,удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этомметоде, и родственных алгоритмов нет, хотя практика показывает, что насовременных ЭВМ они иногда позволяют решить задачу коммивояжера для графов сколичеством вершин, меньшим 100.
Впервые методветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачицелочисленного линейного программирования. Интерес к этому методу и фактическиего «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела,посвященной задаче коммивояжера. Начиная с этого момента, появилось большое числоработ, посвященных методу ветвей и границ и различным его модификациям. Стольбольшой успех объясняется тем, что авторы первыми обратили внимание на широтувозможностей метода, отметили важность использования специфики задачи и самивоспользовались спецификой задачи коммивояжера.
Описаниеметода ветвей и границ
Пусть х1– центр куба Х. Вычисляем /> иприсваиваем это значение рекорду />.Разбиваем куб Х 1i со стороной ½ и вычисляем значения целевойфункции в их центрах: />, i= 1,… 2n, обновляя по ходувычислений значение рекорда />.Проверяем выполнение условия />для i=1,…, 2n и отбрасываемсоответствующие подкубы. Каждый из оставшихся разбиваем на 2n одинаковых подкубов Х2ij со стороной ¼ ипоступаем как прежде. На любом шаге у нас формируется множество К «кубиков» состоронами 2-l, l>=2, целое. Правило выбора очередного кубика для разбиенияназывается правилом ветвления – возможные варианты приводятся ниже. Кубики состороной не больше /> исключаются измножества К – дробление кубика заканчивается. Также исключаются кубики,попавшие в множество /> (с индексом k – номером кубика) длятекущего значения рекорда, – правило отсечения ветвей. Рекорд обновляется приполучении меньшего значения целевой функции (правило получения границ, т.е.оценок). Значения целевой функции вычисляются в центре каждого новогоподкубика, включаемого в К после разбиения выбранного для этого кубика.Алгоритм останавливается, когда К пусто.
Рис. 2.Граф-дерево
/>
Указаннаятерминология и название метода определяются тем, что визуально данная схемаперебора представляется в виде графа-дерева, корневая вершина которогосоответствует кубу Х, вершины первого яруса – подкубам Xli, вершины второго яруса –кубикам X2li, подсоединенным к своим порождающим вершинам Xli-го яруса, и т.д. (см.рис. 2). Если кубик исключается из К, его вершина закрывается – из нее небудут идти ветви на следующий ярус. Порядок закрытия вершины определяется правиломотсечения (своим для каждой массовой задачи), порядок раскрытия – правиломветвления (своим для каждой индивидуальной задачи). Различают два вида правилветвления по типу построения дерева решений (выбора вершин для раскрытия): «вширину», когда сначала раскрываются все вершины одного яруса до перехода кследующему, и в «глубину» – всякий раз раскрывается лишь одна (обычно с лучшимзначением рекорда) вершина на ярусе до конца ветви. На практике реализуютнекоторую смесь, например, первое правило пока хватает машинной памяти (в К неслишком много элементов), затем переключаются на второе. Предпочтительность тойили иной стратегии ветвления оценивается каждым вычислителем по-своему, исходяиз главной задачи метода ветвей и границ – быстрее получить лучший рекорд,чтобы отсечь больше ветвей. Удачный выбор стратегии ветвления в МВГ (например,на основе имеющейся у вычислителя дополнительной информации или эвристическихсоображений об объекте) позволяет (хотя и не гарантированно) решать задачибольшой размерности.
Отметим, чтов худшем случае /> – не удаетсяотбросить ни одной точки х – и приходим к полному перебору; т.е. указанная экспоненциальнаяоценка точна на классе всех липшицевых функций.
4. Выборобъекта управления. анализ аспектов его работы
В качествепримера конкретного применения метода может быть предложена прикладная задача,связанная с проблемой размещения и обслуживания оборудования, в которойтребуется определить оптимальную траекторию циклического маршрута движенияробота-транспортера по траектории цеха с целью периодического обслуживанияоборудования.
Длярассмотрения можно представить себе, что робот развозит по цеху некоторыйматериал, требуемый для работы агрегатов. Предположим, что уже имеетсянекоторый образец робота, т.е. нет необходимости покупать новый – капитальныезатраты отсутствуют. Пусть робот имеет электрический привод и в качестве источникапитания – переносные аккумуляторы.
5.Постановка и решение оптимизационной задачи
5.1 Выборкритерия оптимальности
Основнымбудем считать экономический критерий, т.е. будем стремиться снизить все статьиденежных расходов, связанных с работой данного робота. Отметим, что схемаработы робота должна соответствовать технологической схеме работы цеха, т.е.поставка требуемого материала должна осуществляться в поставленные сроки,определяемые видом работ цеха. Условно будем считать это требование удовлетворенным.
Перечислимосновные экономические показатели, связанные с работой робота:
1. Прямыезатраты
1.1 Единовременные– по доставке машин.
1.2 Амортизационныесуммы.
2. Накладныерасходы. Заработная плата рабочих.
3. Условно-постоянныерасходы.
Содержаниеслужебных помещений.
Пожарнойи сторожевой охраны.
Бытовоеблагоустройство цеха и подсобных помещений.
Расходы,связанные с техникой безопасности.
4. Косвенныерасходы.
Расходына содержание обслуживающего персонала.
Ремонтныхмастерских. Расходы на ремонт.
Анализируяработу робота, можно сказать, что основной экономический показатель, которыйможно регулировать (и за счет этого добиться большего экономического эффекта) –это амортизационные суммы, связанные с перемещением машин по цеху, строительнойплощадке и т.п.
Такимобразом, следует по возможности сократить путь, проходимый роботом.
Итак, задачууменьшения денежных затрат мы свели к задаче поиска пути минимальной длинны.Имеем задачу коммивояжера.
5.2Выявление основных особенностей рассматриваемого объекта
Будемсчитать, что у нас имеются собранные статистические данные, показывающие времядвижения робота между агрегатами цеха (См. табл. 1). Здесь /> – номера агрегатов. /> – соответствует временидвижения выраженном в некоторых условных единицах. Таблица симметрична.Незаполненные поля говорят о невозможности данного маршрута по каким-топричинам.
Таблица 1.
/> 1 2 3 4 5 1 * 4 2 5 2 * 1 9 3 * 3 4 4 * 11 5 *
5.3 Примеррешения задачи коммивояжера
Имеем «чисто»математическую задачу, которую решим, используя метод Ветвей и Границ.
/>
В симметричном графе,изображенном на рис. 3, определить кратчайший путь из вершины 1 в вершину2, проходящим через все вершины графа только по одному разу.
Шаг 0.Значение/>. Пометим вершину 1признаком />
Шаг 1.Пометим вершину 3 признаками />
Рис. 3. ШагЗ. Имеем />.
Шаг1. Пометим следующие вершины: вершину 4 – признаками /> вершину 5 – признаками />
Шаг 3. Имеем />.
Шаг 1.Пометим вершину 5 признаками />
Шаг 3. Имеем />.
Шаг 1.Пометим вершину 3 признаками />
Шаг 3. Имеем />.
Шаг 1.Пометим вершину 4 признаками />
Шаг 1.Пометим вершину 2 – признаками /> таккак />, то искомый путь построен.
Шаг 2.Искомый путь составляет последовательность вершин 1, 5, 3, 4, 2.
Общеезатрачиваемое время в пути составит 13.
Выводы
В даннойработе мы познакомили читателя с основными понятиями теории графов, далипредставление о задаче коммивояжера, описали метод ветвей и границ. Такжепривели пример использования метода ветвей и границ для решения задачикоммивояжера.
Еще разотметим, что задача коммивояжера является одной из самых важнейших задач втеории графов. Возможность представления (записи) различных производственныхпроцессов на языке теории графов и умение решить сформулированнуюматематическую задачу позволяют найти оптимальную стратегию ведения хозяйства,сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки.Очевидно, что изучение методов теории графов, методов математического программирования,системного анализа и пр. – является важным этапом подготовки инженеров в МГСУ.
Списоклитературы
1. Н.М. Новикова«Основы оптимизации», курс лекций. М. 1998.
2. Н. Кристофидес«Теория графов. Алгоритмический подход», М., Мир, 1978.
3. С.Е. Канторер.«Методы обоснования эффективности применения машин в строительстве». М. 1969.
4. Институт математикиим. С.Л. Соболева СО РАН Лаборатория «Математические модели принятиярешений», статья «Метод ветвей и границ». Адрес в интернете:math.nsc.ru/AP/benchmarks/index.html.
5. Е.А. Тишкин«Эвристическийалгоритм решения задачи коммивояжера». Публикация на сайте nit.itsoft.ru. Самарскийгосударственныйаэрокосмическийуниверситет,Россия.