Задача коммивояжера: точные методы и эвристические алгоритмы маршрутизации

Математическая модель задачи коммивояжера опирается на теорию графов. Города представляются в виде вершин, а дороги между ними — в виде ребер (или дуг), каждому из которых приписан определенный вес (расстояние, время или финансовая стоимость проезда). Если вес ребра не зависит от направления движения, задача называется симметричной; в противном случае — асимметричной. Для нахождения абсолютно точного решения классический перебор всех возможных перестановок (маршрутов) применим лишь для крошечного числа городов, поскольку количество вариантов растет как факториал. Уже для 20 городов число маршрутов превышает квинтиллион, что делает прямой перебор невыполнимым даже для самых мощных суперкомпьютеров.

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

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

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