18 ноя 2013153.2K2

Задача коммивояжера - метод ветвей и границ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о странствующем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Содержание:

История появления и исследования задачи коммивояжера

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

Одним из первых, кто сформулировал ранний вариант этой задачи, был выдающийся ирландский математик, физик и механик XIX в. – Уильям Роуэн Гамильтон. Ученый изучал симметрии икосаэдра (двадцатигранника) и в 1857 году предложил игру «Икосиан» (англ. «Icosian Game»), цель которой заключалась в прохождении всех вершин додекаэдра (двенадцатигранника) ровно по одному разу и только по его ребрам, с последующим возвращением в отправную точку. Иными словами нужно было найти так называемый гамильтонов цикл на графе с 20 узлами, в данном случае являющийся решением задачи и содержащий 20 ребер («двадцать» на древнегреческом «icosa», отсюда и название игры). Придуманную математиком головоломку выпускали в виде доски с изображением додекаэдра и выемками на месте его вершин, и продавали в Европе.

В 1930 году австрийско-американский математик Карл Менгер сформулировал задачу коммивояжера как «задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно».

Современное название «задача коммивояжера» или «задача странствующего торговца» (англ. «Traveling Salesman Problem») было предложено американским математиком Хасслером Уитни.

Важный этап в развитии задачи коммивояжера наступил в 1950-1960 гг., когда ее исследованием занялись американские и европейские ученые. И здесь в первую очередь стоит отметить математиков Джорджа Данцига, Делберта Рея Фалкерсона и Селмера Джонсона. Именно они в 1954 году в институте RAND Corporation сформулировали проблему в качестве задачи дискретной оптимизации. Ученые применили метод отсечений для решения частной задачи коммивояжера с 49 городами и обосновали оптимальность найденного маршрута.

В 1960-1970 гг. исследование задачи коммивояжера было продолжено, причем в 2-х направлениях: теоретическом и практическом (изучались возможности ее приложения в экономике, биологии, химии, информатике).

В 1972 году американский ученый в информатики Ричард Мэннинг Карп доказал NP-полноту задачи поиска гамильтоновых путей, из чего следовала NP-трудность задачи коммивояжера.

Плодотворными были 1970-1980 гг. когда Мартин Гретчел, Манфред Падберг, Джованни Ринальди и ряд других ученых применяя новые разработки, такие как метод деления плоскостью и метод ветвей и границ, смогли найти решение для задачи коммивояжера с 2392 городами.

Рекорд по решению задачи коммивояжера установили в апреле 2006 года, когда было найдено решение для задачи с 85900 городами. Но это не предел, используя определенные методы можно найти решение и для случая с миллионами городов.

Определение и постановка условий задачи коммивояжера

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

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

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

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

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

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

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

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

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

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

  1. Построение матрицы с исходными данными.
  2. Нахождение минимума по строкам.
  3. Редукция строк.
  4. Нахождение минимума по столбцам.
  5. Редукция столбцов.
  6. Нахождение нижней границы.
  7. Вычисление оценок нулевых клеток.
  8. Редукция матрицы.
  9. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 10.
  10. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т. д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

В статье представлена авторская интерпретация метода ветвей и границ, не гарантирующая получение оптимального результата.

Итак, методика решения задачи коммивояжера методом ветвей и границ, с использованием алгоритма Литтла:

1. Построение матрицы с исходными данными

Сначала необходимо длины путей, соединяющих города между собой, представить в виде следующей матрицы (таблицы):

Город A B C D E
A M 20 18 12 8
B 5 M 14 7 11
C 12 18 M 6 11
D 11 17 11 M 12
E 5 5 5 5 M

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

Обратите внимание, что в зависимости от направления движения расстояние между городами различается (конечно в реальности расстояние при движении от пункта A к пункту B будет скорее всего одинаковым, но не обязательно: к примеру, пункты могут соединять дороги с односторонним движением различной длины; или, если мы говорим о стоимости, билеты на прямой и обратный рейс могут иметь разную цену).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности (∞) или сокращение «Inf» (от англ. «Infinity» - бесконечность). Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

Город A B C D E di
A M 20 18 12 8 8
B 5 M 14 7 11 5
C 12 18 M 6 11 6
D 11 17 11 M 12 11
E 5 5 5 5 M 5

Найденные значение di называются константами приведения для строк.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Например, в ячейке A-B (ячейку A-A и другие клетки с M не трогаем) у нас было число 20. После редукции (20 - 8) получаем новое значение 12. Затем для остальных ячеек первой строки: 18 - 8 = 10, 12 - 8 = 4, 8 - 8 = 0, и в том же духе для ячеек других строк.

Город A B C D E di
A M 12 10 4 0 8
B 0 M 9 2 6 5
C 6 12 M 0 5 6
D 0 6 0 M 1 11
E 0 0 0 0 M 5

В итоге получаем таблицу с новыми данными, в каждой строке которой будет хотя бы одна нулевая клетка.

4. Нахождение минимума по столбцам

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы (включая нули) выписываем в отдельную строку.

Город A B C D E
A M 12 10 4 0
B 0 M 9 2 6
C 6 12 M 0 5
D 0 6 0 M 1
E 0 0 0 0 M
dj 0 0 0 0 0

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

5. Редукция столбцов

Производим редукцию столбцов - вычитаем из каждого элемента матрицы соответствующее ему dj.

Например, ячейка B-A после редукции (0 - 0) будет равна 0. Далее для остальных ячеек первого столбца: 6 - 0 = 6, 0 - 0 = 0, 0 - 0 = 0 и т. д.

Город A B C D E
A M 12 10 4 0
B 0 M 9 2 6
C 6 12 M 0 5
D 0 6 0 M 1
E 0 0 0 0 M
dj 0 0 0 0 0

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6. Нахождение нижней границы

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

Обратите внимание, что мы не вычисляем заново константы приведения для строк, а берем предыдущие (уже найденные) значения.

Город A B C D E di
A M 12 10 4 0 8
B 0 M 9 2 6 5
C 6 12 M 0 5 6
D 0 6 0 M 1 11
E 0 0 0 0 M 5
dj 0 0 0 0 0

Итак, H = ∑di + ∑dj = (8 + 5 + 6 + 11 + 5) + (0 + 0 + 0 + 0 + 0) = 35 + 0 = 35.

В первый раз найденное значение H = 35, одновременно является и локальной (текущей) величиной минимальной нижней границы (Hmin). При последующих вычислениях Hmin = Hmin + H, т. е. к текущему значению минимальной нижней границы прибавляется новое значение локальной нижней границы.

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

Корень дерева решения35

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

7. Вычисление оценок нулевых клеток

Для каждой нулевой клетки преобразованной матрицы находим «оценку». Ею будет сумма минимума по строке и минимума по столбцу, в которых размещена данная нулевая клетка. При этом сама нулевая клетка для которой вычисляется оценка, найденные ранее di и dj, а также клетки с M, НЕ учитываются (но другие нулевые клетки, если они есть в рассматриваемых строке и столбце, учитывать нужно). Полученную оценку записываем рядом с нулем, в скобках.

Например, первая строка в нашем примере содержит одну нулевую клетку A-E. Вычислим для нее оценку: 4 (минимальное значение среди ячеек данной строки) + 1 (минимальное значение среди ячеек столбца) = 5.

Город A B C D E
A M 12 10 4 0 (5)
B 0 M 9 2 6
C 6 12 M 0 5
D 0 6 0 M 1
E 0 0 0 0 M

Повторяем вычисления оценок для всех остальных нулевых клеток:

Город A B C D E
A M 12 10 4 0 (5)
B 0 (2) M 9 2 6
C 6 12 M 0 (5) 5
D 0 (0) 6 0 (0) M 1
E 0 (0) 0 (6) 0 (0) 0 (0) M

Вычисленные нами оценки также называются штрафами за НЕиспользование тех отрезков маршрута, которым соответсвуют клетки с нулями (напоминаю, что каждая клетка «указывает» на два города: по своей строке - на город из которого выезжаем, и по своему столбцу - на город в который прибываем). Штрафы указывают на возможные затраты пути, времени, стоимости или иного параметра, в целях оптимизации которого мы решаем задачу коммивояжера, которые появятся если НЕ выбрать данные клетки (но подробнее об этом в следующем пункте).

8. Выбор нулевой клетки с максимальной оценкой

Следующий важный шаг - выбор среди нулевых клеток матрицы ту, что имеет наибольшую оценку.

Город A B C D E
A M 12 10 4 0 (5)
B 0 (2) M 9 2 6
C 6 12 M 0 (5) 5
D 0 (0) 6 0 (0) M 1
E 0 (0) 0 (6) 0 (0) 0 (0) M

В нашем случае максимальную оценку имеет клетку E-B. Этой ячейке соответствует отрезок пути от города E к городу B.

Стоит отметить, что если бы не одна, а несколько ячеек имели одинаковую максимальную оценку, то можно было бы выбрать любую из них.

9. Проверка ветвей решения

На этом этапе решение задачи начинает ветвиться. Возникает развилка с двумя вариантами: ветвь решения, где мы включаем в итоговый маршрут отрезок E-B, и ветвь, где мы его в маршрут не включаем.

Для начала рассмотрим первую ветвь, предусматривающую включение отрезка в маршрут. Выбрав клетку с максимальной оценкой, вписываем в нее букву M, и затем полностью вычеркиваем соответствующие ей строку и столбец. Если мы включаем в итоговый маршрут движение из города E в город B, то естественно, что из города E в другие города мы уже двигаться не будем, а в город B по условиям задачи дважды заезжать нельзя. В результате данные строка и столбец нам более не понадобятся.

Город A B C D E
A M 12 10 4 0
B 0 M 9 2 6
C 6 12 M 0 5
D 0 6 0 M 1
E 0 M 0 0 M

Также в клетку, соответствующую обратному пути, ставим еще одну букву «М» (т. к. мы уже не будем возвращаться обратно из города B в город E).

Город A C D E
A M 10 4 0
B 0 9 2 M
C 6 M 0 5
D 0 0 M 1

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

Город A C D E di
A M 10 4 0 0
B 0 9 2 M 0
C 6 M 0 5 0
D 0 0 M 1 0
dj 0 0 0 0

H = (0 + 0 + 0 + 0) + (0 + 0 + 0 + 0) = 0. Учитывая, что предыдущее Hmin = 35, текущее значение составит: Hmin = 35 + 0 = 35. Это локальная нижняя граница.

Теперь нужно проверить и вторую ветвь. Здесь мы НЕ исключаем из таблицы отрезок E-B. Найдем константы приведения для таблицы с неисключенной ветвью.

Город A B C D E di
A M 12 10 4 0 0
B 0 M 9 2 6 0
C 6 12 M 0 5 0
D 0 6 0 M 1 0
E 0 0 (6) 0 0 M 0
dj 0 0 0 0 0

В этом случае локальная нижняя граница будет равна сумме константа приведения и максимальной оценки: H = (0 + 0 + 0 + 0 + 0) + (0 + 0 + 0 + 0 + 0) + 6 = 6. Следовательно минимальная нижняя граница для этого варианта составит Hmin = 35 + 6 = 41.

Оба рассмотренных варианта заносим в граф (звездочками помечена ветвь решения в которой рассматриваемый отрезок пути НЕ включен в итоговый маршрут).

Корень дерева решения35
E* - B*41
E - B35

Поскольку ветвь включающая в маршрут отрезок E → B имеет значение локальной нижней границы меньше, чем в случае второй ветви (35 < 41), выбираем ее.

10. Если полный путь еще не найден, переходим к пункту 2, если найден - к пункту 11

Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т. д.

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

Город A C D E di
A M 10 4 0 0
B 0 9 2 M 0
C 6 M 0 5 0
D 0 0 M 1 0
dj 0 0 0 0

Вычислим нижнюю границу H = (0 + 0 + 0 + 0) + (0 + 0 + 0 + 0) = 0.

Вновь вычисляем оценки для нулевых клеток и определяем ячейку с максимальной оценкой (D-C).

Город A C D E
A M 10 4 0 (5)
B 0 (2) 9 2 M
C 6 M 0 (7) 5
D 0 (0) 0 (9) M 1

Рассматриваем два варианта: с включением ветви D → C в маршрут и без этой ветви. В последнем случае, как мы подсчитали выше, локальная минимальная нижняя граница будет равна Hmin = 35 (предыдущая локальная нижняя граница) + 0 (текущая локальная нижняя граница) + 9 (максимальная оценка) = 44.

Рассмотрим теперь первый вариант, предусматривающий включение ветви D-C в маршрут. Для этого проводим редукцию матрицы и ставим M на обратный путь C-D.

Город A D E
A M 4 0
B 0 2 M
C 6 M 5

Вычисляем константы приведения и считаем нижнюю границу для этого варианта.

Город A D E di
A M 4 0 0
B 0 2 M 0
C 6 M 5 5
dj 0 2 0

H = (0 + 0 + 5) + (0 + 2 + 0) = 7. Тогда Hmin = 35 + 7 = 42.

Не забываем отметить оба варианта в нашем графе.

Корень дерева решения35
E* - B*41
E - B35
D* - C*44
D - C42

Если выбирать только из этих двух вариантов, то ветвь с включением в итоговый маршрут отрезка D-C предпочтительнее, поскольку 42 < 44. НО т. к. одна из предыдущих ветвей (E* - B*) имеет локальную нижнюю минимальную границу еще меньше - 41, нам необходимо вернуться и продолжить развитие этой ветви решения задачи.

Итак, возврашаемся по графу к ветви НЕ предусматривающей включение отрезка E-B в итоговый маршрут. Поскольку, данный отрезок пути был нами отвергнут, необходимо выбрать другой, для чего ищем среди остальных нулевых клеток обладающую максимальной оценкой.

Город A B C D E
A M 12 10 4 0 (5)
B 0 (2) M 9 2 6
C 6 12 M 0 (5) 5
D 0 (0) 6 0 (0) M 1
E 0 (0) 0 (6) 0 (0) 0 (0) M

Здесь таких клеток две: A-E и C-D. Обе ячейки имеют одинаковое значение оценки - 5, превышающее оценки остальных нулевых клеток (кроме клетки E-B, которую мы не учитываем). Остановимся на первой из клеток: A-E.

Проводим редукцию матрицы, вычеркивая соответсвующие ячейке A-E строку и столбец. Не забываем поставить на обратный путь (E-A) букву M.

Город A B C D
B 0 M 9 2
C 6 12 M 0
D 0 6 0 M
E M 0 0 0

Найдем константы приведения для новой таблицы.

Город A B C D di
B 0 M 9 2 0
C 6 12 M 0 0
D 0 6 0 M 0
E M 0 0 0 0
dj 0 0 0 0

Определим локальную нижнюю границу: H = (0 + 0 + 0 + 0) + (0 + 0 + 0 + 0) = 0, тогда Hmin = 41 + 0 = 41.

Что касается варианта не предусматривающего включение отрезка A-E в итоговый маршрут, то для него Hmin = 41 + 0 + 5 = 46. Запишем все эти данные в граф.

Корень дерева решения35
E* - B*41
E - B35
A* - E*46
A - E41
D* - C*44
D - C42

Поскольку 41 < 46, и нижние границы других ветвей больше, выбираем ветвь предусматривающую включение в итоговый маршрут отрезка A-E.

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

Город A B C D
B 0 (2) M 9 2
C 6 12 M 0 (6)
D 0 (0) 6 0 (0) M
E M 0 (6) 0 (0) 0 (0)

Вновь у нас две клекти с максимальной оценкой равной 6: C-D и D-A. Выбираем любую, например C-D.

Проверяем новые ветви: с включением в итоговый маршрут отрезка C-D и без этого отрезка пути.

Для варианта с включением отрезка в маршрут проводим редукцию матрицы, исключаем обратный путь (D-C) и считаем константы приведения.

Город A B C di
B 0 M 9 0
D 0 6 M 0
E M 0 0 0
dj 0 0 0

Считаем Hmin = (0 + 0 + 0) + (0 + 0 + 0) + 41 = 41.

Для ветви не включающей отрезок пути C-D значение Hmin = 41 + 0 + 6 = 47.

Занесем все эти данные в граф.

Корень дерева решения35
E* - B*41
E - B35
A* - E*46
A - E41
D* - C*44
D - C42
C* - D*47
C - D41

Т. к. 41 < 47, и нет других ветвей решения с меньшим значением локальной нижней границы, выбираем ветвь решения с включением отрезка пути C-D в итоговый маршрут и продолжаем ее развитие.

Минимумы по строкам и столбцам таблицы нулевые, поэтому этапы редукции строк и столбцов данные в не изменят. Потому переходим к этапу вычисления оценок нулевых клеток и определения максимальной среди них.

Город A B C
B 0 (9) M 9
D 0 (6) 6 M
E M 0 (6) 0 (9)

Две клетки (B-A и E-C) имеют максимальную оценку 9. Выбираем любую из них, например, B-A. Проводим редукцию матрицы. Исключать обратный путь (A-B) нужды нет, поскольку такая ячейка в таблице на данном этапе решения отсутствует.

Город B C
D 6 M
E 0 0

Найдем для новой таблицы константы приведения.

Город B C di
D 6 M 6
E 0 0 0
dj 0 0

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: A → E → D → B → C → A.

Общая длина пути: L = 5 + 9 + 4 + 5 + 6 = 29.

Практическая и теоретическая значимость задачи коммивояжера

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

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

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

Иногда бывает необходимо быстро просчитать какой-либо вариант для этой задачи или проверить правильность решения. На этот случай я создал сервис для решения задачи коммивояжера онлайн. Воспользоваться им можно перейдя по приведенной здесь ссылке.

Статья дополнена и доработана автором 23 сен 2020 г.

© Копирование материала допустимо только при указании гиперссылки на источник: Галяутдинов Р.Р.


Орфография

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

Цитирование

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Задача коммивояжера - метод ветвей и границ // Сайт преподавателя экономики. [2020]. URL: http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 28.09.2020).

Еще можно почитать: