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

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

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

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

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

Также предоставлена матрица 204х204 с расстояниями между точками (см. Табл.1 ниже ). Матрица не симметричная, т.к. при составлении учитывались знаки ПДД (одностороннее движение и пр.). Видимо она была получена через API Яндекс.Карт по адресам ТТ. Требовалось найти оптимальное расписание для торговых агентов (мерчендайзеров), улучшив показатели текущего AS IS (оно тоже предоставлено). Важные ограничения: каждая ТТ должна быть закреплена за определенным мерчендайзером (торговым агентом). Другими словами, если торговый агент (далее агент) посещает Магнит на улице Ленина в понедельник, то этот же Магнит в другие дни недели должен посещать именно он. Время работы каждого агента не должно превышать 9,5 часов в день с учетом работы в ТТ и перемещению между ними.

0

1

2

...

203

0

0

4031

4152

....

8853

1

4021

0

817

....

10196

2

4239

926

0

....

10306

....

....

....

....

0

10345

203

10071

10610

10289

10886

0

Таблица 1. Матрица расстояний между точками

Предоставленное  расписании AS IS распределено на 14 агентов. И как вы уже догадались, решение должно было предложить альтернативное расписание, сократив по возможности количество агентов и их время в пути.

Спустя какое-то время после хакатона наш back(python) призвал на помощь коллегу с курсов по deep learning. Парни погуглили, поискали готовый алгоритм, почитали про метод отжига, муравьев, генетику и пришли еще раз к выводу, что подходящего метода и примеров кода именно для этой задачи, куда можно было бы взять и вставить матрицу расстояний, как входной параметр на просторах интернета - нет. Если кто знает где есть – поделитесь, будем благодарны.

Позднее, и даже в параллель я сам начал изучать тему Задачи коммивояжера и эвристические методы, зарекомендовавшие себя для ее решения. Но ни хабр, ни youtube, ни Википедия не давали готового ответа именно для этого частного случая. Останавливаться все равно не хотелось. Наоборот, по мере продвижения вперед интерес подогревался. Мотивации добавило то, что классическая задача коммивояжера относится к NP полным задачам. Если решать задачу полным перебором (brutal force), то уже при 66 торговых точках нужно несколько миллиардов лет и компьютер размером с Землю. Согласитесь, мощь трансвычислительных задач завораживает! И действительно, для решения классической задачи TSP (Travelling salesman problem ) существуют различные эвристические методы, такие как Метод Имитации Отжига, Муравьиный алгоритм, Генетический метод и др. Оставалось решить один вопрос: как применить что-то из этой эвристики к сквозному недельному расписанию нескольких торговых агентов с ограничением по времени. Возможно толковый математик, который кожей чувствует физический смысл дифференцирования, логарифмов, пределов, силу числа e и т.д., справился бы с этой задачей. Но я не такой математик. Формулы счастья по-прежнему в интернете не находилось. Я даже изучил основы нейросетей, но когда я начинал проектировать свою нейросеть для решения - вырастала непреодолимая стена.

И все-таки решение родилось! Ну во-первых я обратился за помощью к своему коллеге, Черкасову Евгению @eny01. Он как раз недавно прошел курсы по data science и python, и рвался в бой, чтобы применить все приобретённые навыки. К слову сказать, бОльшую часть алгоритма именно он и разработал. Себе я взял часть, отвечающую за рекурсивный метод ветвей и границ. Но об этом позже. Вдвоем мы разработали следующий план.

  1. Мы декомпозировали задачу до каждого агента. Набираем ТТ сначала для одного агента до предела по очереди для всех дней недели, затем для второго и т.д.;

  2. Процесс набора ТТ происходит с помощью жадного алгоритма (метод ближайшего соседа);

  3. В случае, когда набор подходит к пределу (9,5 часов) - применяем оптимизацию и считаем, что для данного агента в этот день недели оптимальное расписание составлено. Переходим к следующему дню;

 Алгоритм набора расписания для каждого агента более подробно можно увидеть на блок-схеме ниже:

Теперь чуть подробнее про основные моменты:

  1. Ближайшие сосед:

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

Важно следить за переполнением не только в том дне, в котором идет набор, но и параллельно приглядывать за остальными днями торгового представителя- последующими и предыдущими. Так как выбирая точку, скажем для четверга, мы можем переполнить ею пятницу или понедельник.

Когда в одном из дней достигается предел рабочего времени (>=9,5 ч.), система сбрасывает точку приведшую к переполнению и пробует добрать следующую ближайшую. Кстати, мы пробовали вставлять сюда вместо оптимизации "первой точки" и ближайшего соседа полный перебор с ветвями и границами. И результат, !внимание!, получался в итоге тот же. Но времени на перебор с ветвями и границами потребовалось гораздо больше. Около 3,5 часов против 5 минут для всех 204 точек. Таким образом полный перебор был абсолютно избыточен и неэффективен при частом применении. Вследствие чего в этом месте было решено от перебора с ветвями и границами отказаться, но добавить его в финальную оптимизацию составленного расписания.

2. Метод ветвей и границ:

Ну тут все относительно просто. Утвержденное недельное расписание мы прогоняем через полный перебор, используя метод ветвей и границ. Реализация этой функции потребовала применения рекурсии. Причем если сравнивать работу полного перебора через библиотеку itertools (python), то время на перебор 8 точек составило 21 сек, в то время как наша рекурсия с ветвями и границами отрабатывала за 0.4 с. Что не может не радовать! Цель применения ветвей и границ - оптимизация уже готовых расписаний. Привязка ТТ и агентов уже не меняется, но оптимизируется время в пути (решаем классическую задачу коммивояжера).

Результаты:

Описанным выше образом мы производим набор точек для второго агента, затем для третьего и т.д. В результате работы алгоритма нам удалось не только снизить количество агентов с 14 до 13, но и сократить суммарную траекторию перемещения между ТТ вдвое. Ниже представлены результаты, которых нам удалось добиться:

Параметр

До оптимизации

После оптимизации (с брутфорсом в наборе расписания)

Дельта

Относительное изменение, %

Число Мерчендайзеров

14

13

1

7,14%

Суммарная средняя траектория всех ТП, км

25,06

13,54

11,52

45,96%

Суммарная траектория всех маршрутов всех ТП, км

1729,342

839,69

889,65

51,44%

Средняя длительность рабочего дня для ТП

469,43

508,03

-38,6

-8,22%

Общая продолжительность работы всех ТП, час

539,85

524,97

14,88

2,76%

Время работы алгоритма для всех агентов на всех днях недели составило 8 минут на домашнем ПК.

И в качестве финального аккорда мы позволили себе выкрутить лимит с 9 часов 30 минут до 9 часов 38 минут. И получили сокращение до 12 агентов с небольшой погрешностью. Из 60 дневных  расписаний 14 уходят в переработки от 1 до 8 минут (51 минута в сумме).

Ждем ваших комментариев, замечаний и предложений! Ответим на все вопросы. Пишите, как бы вы решали эту задачу. Особенно ценны для нас будут мнения практиков. Как математиков, так и data science'ов. Возможно кто-то предложит существующие библиотеки python для решения задачи. Мы, как я уже сказал, подходящих библиотек не нашли. Всем спасибо, что дочитали до конца!

Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 9

    0

    А какой результат был у занявших первое место? :)

      0
      -1 агент, но при этом, как я понял, они вышли за пределы дневного лимита
      0
      Если на руках уже есть готовое решение его всегда можно попытаться оптимизировать убрав так называемые «пересечения». Посмотрите работу алгоритма Bitonic tour. Этот алгоритм итерационный и с каждой перестановкой он приближается к максимально эффективному решению. Конечно он тоже неимоверно медленный, но как минимум до какого-то шага его можно прогнать.
      А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
      И да хотелось бы услышать больше деталей вашей реализации, спасибо.
        0
        Спасибо за наводку про Bitonic tour. Изучим
          0
          Реализация — алгоритм на python, закодили «Алгоритм набора расписания» по картинке в статье. Алгоритм выполняется циклично для всех тороговых агентов и всех дневных расписаний каждого агента. Заполняем расписание агента, корректируем доступные для заполнения следующего расписания точки (убираем точки первого агента), заполняем расписание следующего агента и т.д. пока доступные точки есть.

          Как использовали данные — положили их в несколько pandas DataFrame, их не много — БД не стали использовать. Промежуточные данные складывали в списки и DataFrame.
          0
          Обожаю такие задачи, а самое главное они дают гигантский value компании, которые заказали и используют такие. я попробую описать проблемы, с которыми я сталкивался решаю такие задачи:
          1) иллюзия что программа должна работать быстро — на самом деле если время расчета программы будет несколько дней, но это поможет рассчитать более оптимальные маршруты то смело используйте это время
          2) четко сформулируйте в математических терминах что дано на входе, и что вы хотите получить. для каждой NP задачи существуют свои пути оптимизации и приемы, как нужно думать для решения. Вы же пошли стандартным путем, который дал неплохие результаты, но, готов поспорить, не идеальные результаты. для меня меня задача звучит следующим образом: Разбиение графа на подграффы с ограниченной суммой ребер. и это уже не коммивояжер. Или зайти в геометрию и искать начало фигур, чтобы их длина соответствовала условиям задачи, что тоже нас приводит к другой задаче
          3) Метрики — на первый взгляд у вас все хорошо, а на второй — думать надо))
          4) не стесняйтесь применить методы со случайностями — вероятностные методы, метод монте-карло
          5) проделайте составление рассписания руками — это помогает зачастую нащупать правильную идею для успешного решения.

          p.s. я бы для решения такой задачи брал бы около 4-5 месяцев на небольшую команду, но мог бы гарантировать дотаточно хорошее приближение к идеальному решению.
            0
            Спасибо за развернутый комментарий. А что думаете про применение систем типа solver?
              0
              Спасибо.
              Метрики дали на хакатоне, главная — количество торговых агентов. Про геометрию — в задании даны адреса торговых точек, по ним можно самостоятельно получить координаты, а уже по ним работать с фигурами (но мы пока не пробовали). Мы использовали только матрицу расстояний от точки до точки.

              Попробовали применять случайности — рандомно выбирать первую точку маршрута, плохо помогло.
              Попробовали изменять лимит дневного времени ( от 8 часов до 9 часов 40 минут) — это помогло равномерно «утрясти» точки в расписаниях, чтобы не получилось, что все агенты загружены, а последние два съездять всего в пару точек.
              Помогло управление критерием «частая точка с большим временем работы» — меняли показатель на сколько она частая (2 — 4 раза в неделю посещение) и как долго в ней нужно работать, т.е. управляли отбором таких точек.

              Уменьшить расписание 13 до 12 торговых агентов помогло добавление условия: при заполнении первого рабочего дня очередного торгового агента (ТА) мы смотрим на точки в расписании предыдущего ТА и ищем точки как можно дальше от них. С этих дальних точек начинаем набор нового расписания. Таким образом расставляем расписания ТА по разным концам города. До 11 ТА расписание уменьшить нельзя — в один из дней будет превышено рабочее время сотрудников (даже без учета времени на передвижения между точками), остается только оптимизировать длину маршрутов для 12 ТА.
              0
              UPD: после написания статьи мы оптимизировали до -2 агентов. Помогло то, что для каждого агента мы берем первую точку, максимально удаленную от точек предыдущих агентов

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое