Это пилотная статья. Будем благодарны за обратную связь. Если тема вызовет интерес, мы возможно примем решение выложить на GitHub наши исходники(python) и входные данные.
Случилось мне поучаствовать в марте 2021 г. в хакатоне с задачей на комбинаторику и оптимизацию. Команду решил собрать свежую, из одиночек, дрейфующих в пуле самого хака. Довольно быстро нашлись front и back, и втроем мы принялись старательно размышлять, как потратим деньги, когда выиграем. Надо сказать, что в хаках я не так давно, но уже успел поучаствовать и в ЛЦТ(Лидеры Цифровой Трансформации), и в Цифровом Прорыве. В последнем даже нам удалось занять бронзу в финале. Роль всегда у меня была project+product+ppt. Так вот этот мартовский хакатон меня заинтересовал живостью и насущностью бизнес проблем, которые там решались. Так как часто в хакатонских кейсах проблемы немного надуманы, решения этих проблем немного фееричны и не несут практического смысла, а побеждает профессиональная преза и поставленный питч. Опытные хакантощики, читающие эти строки, поймут. Но полно про хакатоны и про то, какие они бывают, а то собьемся с курса.
В этам хаке преза и даже front мало интересовали кейсодержателей. Это был натуральный бизнес хакатон с абсолютно живыми дата сетами и с натуральной бизнес болью. К слову сказать, наша команда не выиграла, а заняла третье место (всего до защиты дошло 5 команд). Теперь наконец к условию:
Есть 204 ТТ (торговые точки). Каждую из них нужно посетить минимум раз в неделю, а некоторые больше одного раза. Длительности посещения каждой ТТ известны и не изменяются внутри недели.
В математике и программировании порой используются необычные названия явлений, объектов и алгоритмов. Но почти всегда такие названия позволяют быстро понять суть описываемых сущностей. Возьмём, к примеру, широко известную задачу о коммивояжёре — найти кратчайший путь между заданными точками. И действительно, сразу представляется себе коммивояжёр, которому нужно обойти все дома в небольшом городке, но при этом затратить минимум усилий и времени. Для решения этой задачи используются разные алгоритмы, один из них называется «муравьиным». Для того, чтобы разобраться с этим алгоритмом, нам для начала нужно присмотреться к поведению муравьёв в их необычном организованном мире.
К задачам на поиск кратчайшего пути я вернулся спустя год после первого не совсем успешного опыта. По воле случая пришлось углубиться в современные методы решения подобных задач и я обнаружил целый удивительный мир эвристических, не точных, методов решения логистических задач, о которых год назад и не подозревал. Исследуя эту тематику появились некоторые идеи по улучшению и развитию данных методов. Этим и хочу поделиться в данной статье.
Задача коммивояжёра – одна из интереснейших подзадач комбинаторной оптимизации. Впервые мне пришлось с ней столкнуться, работая над логистической системой торгового предприятия.
Решение методом грубой силы не подходило из-за вычислительной сложности. Была предпринята попытка реализовать метод ветвления и границ с отсечением в глубину. В целом, подход себя оправдывал, но иногда при некоторых специфических входных данных алгоритм выдавал решение далёкое от оптимального.
Типичный маршрут доставки товара предприятия состоял из пары десятков точек, изредка доходящий до 25-26. Матрица расстояний рассчитывалась с помощью алгоритма Дейкстры. Дальше нужно было выбрать оптимальный маршрут из возможных.
Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.
Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.
Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.
Дочитав эту статью до конца, вы сможете решать точно задачу коммивояжёра на сотню элементов за считанные секунды!
Заинтригованы? Тогда, добро пожаловать под кат.