Куда послать коммивояжера?

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

Задача коммивояжера (Travelling Salesman Problem) — одна из наиболее изучаемых в комбинаторной оптимизации. Ее суть состоит в нахождении кратчайшего расстояния между N городами, при условии, что каждый город необходимо посетить единожды, а потом вернуться в исходный. В классической формулировке она носит название задачи китайского почтальона (Chinese Postman Problem, CPP), которому необходимо по кратчайшему маршруту разнести почту по всем улицам назначенного ему участка города и вернуться в исходную точку. Первоначально эту задачу изучал китайский математик Мэй Ку-Куан, отсюда и ее название. Задачи маршрутизации могут быть преобразованы друг в друга, что открывает широкие возможности для исследований.

Существуют различные вариации классической задачи коммивояжера, основанные на типе расстояний между вершинами:

симметричная задача коммивояжера (Symmetric TSP): расстояния между вершинами удовлетворяют аксиомам симметричности (одинаковы для одних и тех же вершин независимо от направления).
асимметричная задача коммивояжера (Asymmetric TSP): маршрут представлен ориентированным графом, причем расстояние между одними и теми же вершинами в одном направлении может отличаться от противоположного;
обобщенная задача коммивояжера (Generalized TSP): нахождение кратчайшего замкнутого пути, проходящего через одну вершину в каждом из кластеров вершин.

Несмотря на простоту формулировок задач коммивояжера и многолетние усилия по созданию методов их решения, воз и ныне там: точности наивного метода перебора всех возможных вариантов не достигает ни один из предложенных на сегодняшний день алгоритмов. Однако перебор имеет экспоненциальную вычислительную сложность, и уже при N = 15 (N — число вершин) необходимо перебрать более 87 млрд различных маршрутов, что потребует более 12 часов работы при условии, что один маршрут вычисляется за одну микросекунду. Вместе с тем накоплено множество алгоритмов, призванных с помощью эвристик оптимизировать решение.

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

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

— Методы наращивания пути. В качестве отправного элемента выбирается одна вершина или ребро, на каждой итерации одно ребро выбирается согласно определенному критерию и добавляется в конец текущего пути. Недостаток — вероятность возникновения ситуации, когда после добавления всех ребер конечные точки маршрута окажутся очень далеко друг от друга и для превращения маршрута в цикл придется добавлять очень «тяжелое» (с большим весом) ребро, что может значительно повлиять на итоговый результат. К методам данной группы относятся: алгоритм «ближайшего соседа» (Nearest Neighbour) — поиск очередной вершины ведется относительно последней добавленной в путь вершины; модифицированный алгоритм «ближайшего соседа» (Double Ended Nearest Neighbour) — поиск ближайшей вершины ведется относительно крайних вершин в текущем пути; алгоритмы из группы заполняющих пространство кривых (Space-filling Curve Heuristic) — рекурсивные кривые (кривая Мура, кривая Серпинского) определяют порядок обхода, на основе которого соединяются вершины для решения задачи коммивояжера.

— Методы вставки в подцикл. В качестве первоначального подцикла выбирается одно ребро, а на каждой итерации по определенному правилу выбирается ранее не использованная вершина и «вклинивается» в подцикл. Среди методов данной группы: алгоритм добавления «ближайшего» (Nearest Addition), алгоритм вставки «ближайшего» (Nearest Insertion), алгоритм вставки «дальнейшего» (Farthest Insertion), алгоритм «выгодной» вставки (Cheapest Insertion), алгоритм случайной вставки (Arbitrary Insertion).

— Комбинированные методы построения маршрута. Алгоритмы, основанные на построении кратчайшего связывающего дерева: алгоритм Double MST — удвоение кратчайшего связывающего дерева, составление эйлерова цикла и его сведение к гамильтонову циклу путем удаления повторяющихся вершин; алгоритм Christofides — поиск минимальных паросочетаний вершин нечетной степени минимального остовного дерева.

— Методы улучшения маршрута. На вход алгоритмов этой группы подается цикл, построенный с помощью одного из перечисленных методов построения маршрутов. А затем происходит его улучшение за счет уменьшения веса. К методам этой группы относятся как простые локально оптимальные эвристики, основанные на взаимном обмене нескольких ребер, так и сложные метаэвристики. Среди локально оптимальных методов можно отметить простой алгоритм 2-Opt, суть которого заключается в удалении пересекающихся ребер, и перспективный алгоритм Lin and Kernighan Heuristic (LKH) [1], подразумевающий взаимный обмен k ребер. К метаэвристикам относятся: алгоритмы имитации отжига, предполагающие периодическое увеличение стоимости маршрута, что способствует снижению вероятности получения решения, «застрявшего» в локальном минимуме; эволюционные алгоритмы, инспирированные природой биологической эволюции; алгоритмы роевого интеллекта, основанные на моделировании интеллектуального поведения колоний агентов.

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

задача в ориентированном графе/мультиграфе (Directed Chinese Postman Problem, DCPP) — здесь все дороги имеют только одностороннее движение;
задача в неориентированном графе/мультиграфе (Undirected Chinese Postman Problem, UCPP) — все с двусторонним движением;
задача в смешанном графе/мультиграфе (Mixed Chinese Postman Problem, MCPP) — дороги могут быть двух типов.

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

В зависимости от получаемого маршрута выделяется закрытая задача китайского почтальона (Closed CPP), решением которой является замкнутый цикл (начальная и конечная вершины совпадают), и открытая задача (Open CPP), результирующий маршрут которой должен содержать все ребра/дуги графа, причем стартовая и конечная вершины не обязательно совпадают. Имеется множество модификаций задачи CPP, основанных на варьировании параметров дуг и ребер: задача ветреного китайского почтальона (Windy Chinese Postman Problem, WCPP) — стоимость прохода в прямом и обратном направлении по дороге с двусторонним движением зависит от направления прохождения; задача сельского китайского почтальона (Rural Chinese Postman Problem, RCPP) — имеются две группы дорог, причем дороги первой группы должны обязательно появиться в решении, а дороги второй группы могут отсутствовать; кластеризованная задача китайского почтальона (The Hierarchical Postman Problem, HPP) — дороги разделены на кластеры, где каждый кластер имеет приоритет прохождения, причем сначала должны быть пройдены дороги с более высоким приоритетом.

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

Алгоритмы решения задачи MCPP можно разделить на две группы: решение непосредственно задачи китайского почтальона; преобразование задачи в эквивалентную. Для решения непосредственно задачи китайского почтальона в графе были разработаны эвристические и приближенные алгоритмы, в частности жадные, генетические эвристики, дающие приемлемые результаты. Задача китайского почтальона может быть преобразована в асимметричную обобщенную задачу коммивояжера, которую можно затем преобразовать в асимметричную задачу коммивояжера, которая, в свою очередь, может быть преобразована в классическую симметричную задачу коммивояжера.

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

— Преобразование обобщенной задачи коммивояжера в асимметричную задачу (ATSP). Здесь необходимо внутри каждого кластера установить нулевую стоимость прохода между каждой парой вершин в кластере. Если две вершины находятся в разных кластерах, то стоимость прохода между ними остается прежней. Основная идея трансформации состоит в том, что сначала коммивояжер посетит все вершины из одного кластера, а затем перейдет в другой. Поэтому из решения ATSP легко может быть получено решение A-GTSP путем извлечения из получившегося тура только одной первой вершины, принадлежащей каждому кластеру [2].

— Преобразование асимметричной задачи коммивояжера в симметричную (STSP). Существуют алгоритмы преобразования ATSP в STSP, правда, некоторые втрое увеличивают размерность задачи (количество вершин больше в три раза). Для каждой вершины создается фиктивная вершина (клон). Стоимость прохождения между вершиной и вершиной-клоном устанавливается очень маленькой, это гарантирует, что в решении вершина и ее клон всегда будут появляться совместно, следуя друг за другом. Исходные расстояния для ATSP используются между вершинами и фиктивными вершинами. Каждая вершина отвечает за расстояние, ведущее к вершине, а каждая фиктивная вершина отвечает за расстояние, ведущее от вершины. Расстояния между всеми парами вершин и всеми парами фиктивных вершин устанавливаются очень большими, что исключает их появление в решении [3].

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

Рис. 1. Точность решения задачи MCPP алгоритмом LKH при 500 вершинах

Рис. 2. Время работы алгоритма LKH на задаче MCPP при 500 вершинах

Именно алгоритмы преобразования задачи китайского почтальона в эквивалентную задачу коммивояжера дают неплохие результаты (высокая точность решения, погрешность для 500 вершин не более 0,25%), что и следует использовать сегодня на практике.

***

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

Литература

T. Bagchi, J. Gupta, C. Sriskandarajah. A review of TSP based approaches for flowshop scheduling // European Journal Operations Research. — 2006. Vol. 169, N. 3. — P. 816–854.
D. Ben-Arieh, G. Gutin, M. Penn, A. Zverovitch. Transformations of generalized ATSP into ATSP // Operations Research. — 2003. Vol. 31, N. 5. — P. 357–365.
R. Kumar, H. Li. On Asymmetric TSP: Transformation to Symmetric TSP and Performance Bound // Journal of Operations Research. — 1996.

Екатерина Береснева (eberesneva@hse.ru), Мария Горденко (mgordenko@hse.ru) — преподаватели НИУ ВШЭ (Москва).