Маршрутизация по дугам: Задача китайского почтальона (CPP) и снегоуборочная логистика

Математическая основа Задачи китайского почтальона (Chinese Postman Problem, CPP) уходит корнями в историческую задачу Леонарда Эйлера о семи кенигсбергских мостах. В неориентированном графе требуется найти замкнутый маршрут минимальной длины, проходящий через каждое ребро ровно один раз. Такой идеальный маршрут называется эйлеровым циклом. Теорема Эйлера гласит, что эйлеров цикл существует тогда и только тогда, когда граф является связным и степень каждой его вершины (количество выходящих из нее дорог) является четным числом. Если почтальону повезло работать в городе с идеальной эйлеровой топологией, задача решается тривиальным алгоритмом Флери за линейное время $O(E)$.

К сожалению, реальные города полны перекрестков, в которые сходятся три или пять дорог (нечетные вершины). Если в графе есть вершины с нечетной степенью, пройти по каждой улице ровно один раз физически невозможно — почтальону придется повторять свой путь по некоторым улицам дважды (мертвый пробег). Цель оптимизации в CPP — найти такой набор ребер для повторного прохождения, чтобы их суммарная длина была минимальной. Гениальность математического решения заключается в теореме о том, что количество нечетных вершин в любом графе всегда четно. Следовательно, их можно разбить на идеальные пары.

Для решения задачи китайского почтальона алгоритм сначала находит абсолютно все кратчайшие пути между всеми нечетными вершинами (используя алгоритм Флойда-Уоршелла). Затем строится полный граф, где узлами выступают только нечетные вершины, а весами ребер — кратчайшие расстояния между ними. В этом новом графе алгоритм Джека Эдмондса находит минимальное совершенное паросочетание (Minimum Weight Perfect Matching). Найденные пары указывают, какие именно улицы (или их цепочки) почтальон должен пройти дважды. После виртуального дублирования этих улиц в исходной карте, граф становится эйлеровым, и задача успешно завершается.

Промышленная сложность возникает при переходе к Задаче маршрутизации транспорта по дугам с ограниченной вместимостью (Capacitated Arc Routing Problem, CARP). Снегоуборочная машина не может убирать снег бесконечно — у нее заканчивается пескосоляная смесь, и она обязана возвращаться в депо. CARP комбинирует сложность эйлеровых графов с NP-трудностью задачи упаковки в контейнеры (разбиения маршрутов). Для решения CARP в современных GIS-системах применяются эвристики (Path-Scanning) и метаэвристики на основе муравьиных алгоритмов, которые позволяют городским службам минимизировать холостой пробег тяжелой техники и оперативно ликвидировать последствия снежных бурь с миллионной экономией бюджета.