🏆 Хакатон "Весна", г. Ростов-на-Дону

❓ Задача

Нам предстояло разработать веб-сервис для мониторинга поставок пищевой продукции. Конкретно я решал задачу поиска оптимального маршрута между несколькими точками и работал с временными рядами.

🎉 Результат

🏆 Место: 1 место🥇

📄 Данные

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

📝 Решение: Генетические алгоритмы

Для решения задачи поиска оптимального маршрута мне приглянулись генетические алгоритмы. Можно было использовать, конечено, алгоритм Дейкстры, но мне захотелось попробовать что-то новое, да и кажется, в итоге у меня получилось решить задачу оптимальнее. Решение получилось на голом numpy) Что я делал: инициализировал какую-то популяцию из маршрутов точек, итеративно происходила эволюция, в конце брал лучший маршрут. В целом, более менее оптимальный маршрут появлялся быстро, а чтобы получить самый оптимальный маршрут, нужно было подождать) Вот небольшой пример работы, это изначальный рандомный маршрут между точками:



Это маршрут в конце, оптимальный



Вот график сходимости алгоритма:



В качестве distance я брал общее время в пути или общее расстояние. По сути, мы можем по-разному инициализировать distance, если хотим смотреть еще и на другие параметры оптимизации, грузоподъемность и т.п. Также кейсодержатели попросили решить задачу и для нескольких фургонов, т.е. если мы имеем несколько грузовиков для развозки товара по точкам. Я реализовал кластеризацию K-Means точек на карте и просто раскинул грузовики по разным кластерам точек. В целом, идея довольно неплохая, хоть и простая, по сути, грузовики поедут в разные районы города)

📝 Решение: Анализ временных рядов

Также получилось поработать с библиотекой ETNA, удобно построил графики трендов, сезонности на разных типах продуктов. Получилось реализовать модель предсказания объема продаж на несколько месяцев вперед.



В итоге получилось все интегрировать на платформу, веб-сервис целиком можно посмотреть вот здесь) https://github.com/NikitaKrylov/HackatonSpring