RichVRPSolver для задач логистики представителей

В докладе мы представим обзор фреймворка RichVRPSolver, разработанного для задачи логистики представителей Т-Банк.

Фреймворк основан на SOTA-алгоритме для задач типа Vehicle Routing Problem (VRP) — гибридном генетическом поиске (HGS-CVRP), разработанном Тибо Видалем.

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

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