Comments 9
А какой результат был у занявших первое место? :)
Если на руках уже есть готовое решение его всегда можно попытаться оптимизировать убрав так называемые «пересечения». Посмотрите работу алгоритма Bitonic tour. Этот алгоритм итерационный и с каждой перестановкой он приближается к максимально эффективному решению. Конечно он тоже неимоверно медленный, но как минимум до какого-то шага его можно прогнать.
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
Спасибо за наводку про Bitonic tour. Изучим
Реализация — алгоритм на python, закодили «Алгоритм набора расписания» по картинке в статье. Алгоритм выполняется циклично для всех тороговых агентов и всех дневных расписаний каждого агента. Заполняем расписание агента, корректируем доступные для заполнения следующего расписания точки (убираем точки первого агента), заполняем расписание следующего агента и т.д. пока доступные точки есть.
Как использовали данные — положили их в несколько pandas DataFrame, их не много — БД не стали использовать. Промежуточные данные складывали в списки и DataFrame.
Как использовали данные — положили их в несколько pandas DataFrame, их не много — БД не стали использовать. Промежуточные данные складывали в списки и DataFrame.
Обожаю такие задачи, а самое главное они дают гигантский value компании, которые заказали и используют такие. я попробую описать проблемы, с которыми я сталкивался решаю такие задачи:
1) иллюзия что программа должна работать быстро — на самом деле если время расчета программы будет несколько дней, но это поможет рассчитать более оптимальные маршруты то смело используйте это время
2) четко сформулируйте в математических терминах что дано на входе, и что вы хотите получить. для каждой NP задачи существуют свои пути оптимизации и приемы, как нужно думать для решения. Вы же пошли стандартным путем, который дал неплохие результаты, но, готов поспорить, не идеальные результаты. для меня меня задача звучит следующим образом: Разбиение графа на подграффы с ограниченной суммой ребер. и это уже не коммивояжер. Или зайти в геометрию и искать начало фигур, чтобы их длина соответствовала условиям задачи, что тоже нас приводит к другой задаче
3) Метрики — на первый взгляд у вас все хорошо, а на второй — думать надо))
4) не стесняйтесь применить методы со случайностями — вероятностные методы, метод монте-карло
5) проделайте составление рассписания руками — это помогает зачастую нащупать правильную идею для успешного решения.
p.s. я бы для решения такой задачи брал бы около 4-5 месяцев на небольшую команду, но мог бы гарантировать дотаточно хорошее приближение к идеальному решению.
1) иллюзия что программа должна работать быстро — на самом деле если время расчета программы будет несколько дней, но это поможет рассчитать более оптимальные маршруты то смело используйте это время
2) четко сформулируйте в математических терминах что дано на входе, и что вы хотите получить. для каждой NP задачи существуют свои пути оптимизации и приемы, как нужно думать для решения. Вы же пошли стандартным путем, который дал неплохие результаты, но, готов поспорить, не идеальные результаты. для меня меня задача звучит следующим образом: Разбиение графа на подграффы с ограниченной суммой ребер. и это уже не коммивояжер. Или зайти в геометрию и искать начало фигур, чтобы их длина соответствовала условиям задачи, что тоже нас приводит к другой задаче
3) Метрики — на первый взгляд у вас все хорошо, а на второй — думать надо))
4) не стесняйтесь применить методы со случайностями — вероятностные методы, метод монте-карло
5) проделайте составление рассписания руками — это помогает зачастую нащупать правильную идею для успешного решения.
p.s. я бы для решения такой задачи брал бы около 4-5 месяцев на небольшую команду, но мог бы гарантировать дотаточно хорошее приближение к идеальному решению.
Спасибо за развернутый комментарий. А что думаете про применение систем типа solver?
Спасибо.
Метрики дали на хакатоне, главная — количество торговых агентов. Про геометрию — в задании даны адреса торговых точек, по ним можно самостоятельно получить координаты, а уже по ним работать с фигурами (но мы пока не пробовали). Мы использовали только матрицу расстояний от точки до точки.
Попробовали применять случайности — рандомно выбирать первую точку маршрута, плохо помогло.
Попробовали изменять лимит дневного времени ( от 8 часов до 9 часов 40 минут) — это помогло равномерно «утрясти» точки в расписаниях, чтобы не получилось, что все агенты загружены, а последние два съездять всего в пару точек.
Помогло управление критерием «частая точка с большим временем работы» — меняли показатель на сколько она частая (2 — 4 раза в неделю посещение) и как долго в ней нужно работать, т.е. управляли отбором таких точек.
Уменьшить расписание 13 до 12 торговых агентов помогло добавление условия: при заполнении первого рабочего дня очередного торгового агента (ТА) мы смотрим на точки в расписании предыдущего ТА и ищем точки как можно дальше от них. С этих дальних точек начинаем набор нового расписания. Таким образом расставляем расписания ТА по разным концам города. До 11 ТА расписание уменьшить нельзя — в один из дней будет превышено рабочее время сотрудников (даже без учета времени на передвижения между точками), остается только оптимизировать длину маршрутов для 12 ТА.
Метрики дали на хакатоне, главная — количество торговых агентов. Про геометрию — в задании даны адреса торговых точек, по ним можно самостоятельно получить координаты, а уже по ним работать с фигурами (но мы пока не пробовали). Мы использовали только матрицу расстояний от точки до точки.
Попробовали применять случайности — рандомно выбирать первую точку маршрута, плохо помогло.
Попробовали изменять лимит дневного времени ( от 8 часов до 9 часов 40 минут) — это помогло равномерно «утрясти» точки в расписаниях, чтобы не получилось, что все агенты загружены, а последние два съездять всего в пару точек.
Помогло управление критерием «частая точка с большим временем работы» — меняли показатель на сколько она частая (2 — 4 раза в неделю посещение) и как долго в ней нужно работать, т.е. управляли отбором таких точек.
Уменьшить расписание 13 до 12 торговых агентов помогло добавление условия: при заполнении первого рабочего дня очередного торгового агента (ТА) мы смотрим на точки в расписании предыдущего ТА и ищем точки как можно дальше от них. С этих дальних точек начинаем набор нового расписания. Таким образом расставляем расписания ТА по разным концам города. До 11 ТА расписание уменьшить нельзя — в один из дней будет превышено рабочее время сотрудников (даже без учета времени на передвижения между точками), остается только оптимизировать длину маршрутов для 12 ТА.
UPD: после написания статьи мы оптимизировали до -2 агентов. Помогло то, что для каждого агента мы берем первую точку, максимально удаленную от точек предыдущих агентов
Sign up to leave a comment.
Жадный алгоритм, ветви и границы для расписания мерчендайзеров (кейс Хакатона на оптимизацию)