Рассмотрены методы решения задачи маршрутизации транспортных средств в условиях мелкопартионных перевозок грузов автомобильным транспортом и предлагается использование двухэтапного алгоритма
транспортная логистика, мелкопартионные перевозки, эвристические методы решения, метод Кларка-Райта, задача маршрутизации
Развитие e-commerce и логистики «последней мили» привело к экспоненциальному росту объема мелкопартионных (сборных) грузовых перевозок. Этот сегмент характеризуется высокой операционной сложностью: большим количеством точек сбора/доставки N, малым объемом отдельных партий, жесткими временными окнами клиентов и необходимостью консолидации грузов для эффективного использования транспорта. Традиционные подходы к планированию становятся неэффективными, что требует разработки специализированных алгоритмов маршрутизации, способных работать в режиме, близком к реальному времени [1]. Одним из вариантов решения является задача маршрутизации транспорта ограниченной вместимости с временными окнами (CVRPTW), которая относится к классу NP-трудных комбинаторных задач, что определяет ее высокую теоретическую значимость для развития методов дискретной оптимизации. Для решения этой задачи применяются:
1.Точные методы (метод ветвей и границ, динамическое программирование) применимы лишь для малых N из-за стремительного роста числа возможных вариантов маршрутов при увеличении количества обслуживаемых точек.
2. Классические эвристики (метод Кларка-Райта, алгоритмы вставки, локальный) используются для получения начального решения, которое затем улучшается более сложными методами [1].
3.Метаэвристики («имитация отжига», генетические алгоритмы, «муравьиные колонии», поиск с запретами). Основное преимущество метаэвристик перед классическими эвристиками – наличие механизмов, позволяющих избегать локальных оптимумов и продолжать поиск глобально оптимальных решений.
4.Методы на основе машинного обучения (RL). RL методы позволяют системе принятия решений самостоятельно обучаться оптимальному поведению на основе взаимодействия со средой.
Для решения задачи маршрутизации транспортных средств (CVRPTW) в условиях мелкопартионных перевозок предлагается использование двухэтапного алгоритма:
1. Метод Кларка-Райта (clark-wright savings algorithm) – классический эвристический инструмент быстрого получения опорных решений и наглядной демонстрации принципов оптимизации маршрутов [2].
2. Метод «суммирования по столбцам» (Column Generation) – продвинутый метод декомпозиции для решения задач линейного программирования с огромным числом переменных (потенциальных маршрутов). Он применяется для оптимизации сформированного множества маршрутов [3].
На первом этапе метод Кларка-Райта обеспечивает быстрое получение начального решения, приемлемого для оперативной работы диспетчера. На втором этапе метод «суммирования по столбцам», используя это решение как отправную точку, позволяет провести углубленную оптимизацию, находя глобально или близкие к ним оптимальные комбинации маршрутов. Это особенно важно при ежедневном изменяющемся портфеле заказов.
1. Никоноров, В.М. Усовершенствование метода Кларка-Райта для решения задачи маршрутизации автомобильных мелкопартионных перевозок/ Никоноров В.М. - Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Экономические науки. 2012. № 1 (139). С. 295-298. – Текст: непосредственный.
2. Clark, G. Sheduling of vehicles from a central depot to a number of de-livery points [Text] / G. Clark, J. Wright // Operational Research Quarterly. – 1964. – Vol. 12, no. 4. – P. 568–581. – Текст : непосредственный.
3. Desaulniers, G. Column Generation [Text] / Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), 2005. Springer Books, Springer, number 978-0-387-25486-9, January.
