Жадный алгоритм, ветви и границы для расписания мерчендайзеров (кейс Хакатона на оптимизацию)

Это пилотная статья. Будем благодарны за обратную связь. Если тема вызовет интерес, мы возможно примем решение выложить на GitHub наши исходники(python) и входные данные.

Случилось мне поучаствовать в марте 2021 г. в хакатоне с задачей на комбинаторику и оптимизацию. Команду решил собрать свежую, из одиночек, дрейфующих в пуле самого хака. Довольно быстро нашлись front и back, и втроем мы принялись старательно размышлять, как потратим деньги, когда выиграем. Надо сказать, что в хаках я не так давно, но уже успел поучаствовать и в ЛЦТ(Лидеры Цифровой Трансформации), и в Цифровом Прорыве. В последнем даже нам удалось занять бронзу в финале. Роль всегда у меня была project+product+ppt. Так вот этот мартовский хакатон меня заинтересовал живостью и насущностью бизнес проблем, которые там решались. Так как часто в хакатонских кейсах проблемы немного надуманы, решения этих проблем немного фееричны и не несут практического смысла, а побеждает профессиональная преза и поставленный питч. Опытные хакантощики, читающие эти строки, поймут. Но полно про хакатоны и про то, какие они бывают, а то собьемся с курса.

В этам хаке преза и даже front мало интересовали кейсодержателей. Это был натуральный бизнес хакатон с абсолютно живыми дата сетами и с натуральной бизнес болью. К слову сказать, наша команда не выиграла, а заняла третье место (всего до защиты дошло 5 команд). Теперь наконец к условию:

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

Читать далее