Применение технологий обучения с подкреплением для решения задачи назначения курьеров на заказы в алгоритмах логистических компаний

Доставка последней мили - область, бурно развивающаяся последнее время. Каждая компания на этом специализирующаяся, решает задачу назначения курьеров на заказы клиентов. Основной вопрос - как делать эти назначения наиболее эффективно? В этой работе я поставил данную задачу формально, и на примере симуляций реального мира исследую возможности решения задачи с помощью нейросетей с применением обучения с подкреплением. Полученный алгоритм я сравниваю с рядом эвристических алгоритмов, чтобы оценить качество относительно базового уровня. Эта работа имеет несколько результатов. Во-первых, я реализую инфраструктуру, позволяющуя симулировать курьеров и заказы; выстраиваю архитектуру нейронной сети; а также имплементирую алгоритм, позволяющий в режиме обучения с подкреплением тренировать модели. Во-вторых, я анализирую качество модели в зависимости от ряда параметров. Я протестировал различные функции наград, подходы для работы с геокоординатами, размеры моделей. В-третьих, я доказываю несколько теоретических утверждений, которые применимы для большого количества схожих задач. В частности, я доказал оптимальность одного из алгоритмов при некоторых условиях и предложил метод работы с некоторыми видами разреженных наград. Текущий вывод работы заключается в том, что в базовой постановке задачи назначений эвристические алгоритмы, опирающиеся на расстояния между курьерами и заказами, достаточно эффективны. Нейросети могут научиться решать эти задачи на том же уровне, но улучшить результат пока не удалось. Таким образом, эта работа делает дает лишь начальное понимание задачи и возможных ее решений, оставляя ряд вопросов для будущих исследований. Например, возможность добавления нового заказа в уже существующий остались за рамками представленной модели, хотя необходимый функционал в коде реализован. Это может быть одним из направлений, где обучение с подкреплением может продемонстрировать более высокий результат по сравнению с эвристиками.