Простейшая постановка задачи маршрутизации, когда все сводится только к минимизации пробега, встречается крайне редко. Чаще ситуация осложняется необходимостью учесть окна приемки в точках доставки. А иногда этот фактор просто до неузнаваемости может изменить казалось бы совершенно очевидный кратчайший маршрут объезда точек.
В основе поиска оптимального маршрута в ОТМ и многих других TMS лежит метод Кларка-Райта известный как алгоритм сбережений (Savings algorithm, 1964). В оригинале алгоритм нацелен на поиск решения с минимальным пробегом и на каждой итерации он оценивает выгоду от прибавления точки в общий маршрут в сравнении с перевозкой отдельной машиной. На следующую итерацию переходит тот вариант присоединения точки, который дал наибольший выигрыш. Очень подробный разбор работы этого алгоритма в изолированном виде я уже делала в статье про «анализатор и думатель».
Вот так этот принцип выглядит на схеме:
Берем сумму расстояний до двух точек с возвратом при доставке двумя машинами и сравниваем с вариантом доставки путем объезда обеих точек одной машиной также с возвратом в начало.
Это самый базовый алгоритм, на который затем накладываются все прочие факторы, которые нужно учитывать, в том числе и окна доставки, по причине нарушения которых точка может быть отброшена при переборе вариантов. Можно сказать, что это один из примеров «несовместимости» заказов. И проявляется эта несовместимость точно также, как и любая другая, а именно в виде дополнительной машины для заказов, которые не удалось объединить с другими. То есть в общем виде наличие строгих окон доставки приводит к увеличению количества задействованных машин и зачастую к их недогрузу.
Разберем непосредственно в ОТМ ситуацию, когда совершенно идеальный маршрут превращается в хаотичные метания или вовсе распадается на две машины.
Возьмем 9 адресов в Томске, на которые нужно выполнить доставку со склада.
Заказы в эти адреса изначально не имеют строгих ограничений по временным окнам. Окно во всех заказах задано пределами рабочего дня (9:00 — 18:00), которого с избытком будет достаточно, чтобы выполнить доставку одной машиной. И действительно в результате планирования мы получаем один рейс с аккуратным объездом точек по порядку. Общий пробег получился 29 км.
Теперь возьмем самую дальнюю от склада точку и ограничим для нее окно доставки 9:00 — 11:00. В исходном рейсе машина прибывает на эту точку гораздо позже. Чтобы успеть до 11:00 нужно поменять последовательность или пропустить какие-то точки.
Первый вариант, который предлагает ОТМ с учетом приоритета минимизации пробега — это пропустить две точки в начале рейса, выполнив туда доставку отдельной машиной. Пробег в этом случае на два рейса в сумме получится 32 км. Учитывая свободные окна этот рейс сможет выполнить та же самая машина, после завершения основного рейса.
Но нас на самом деле гораздо больше интересует выполнение всех заказов одной машиной за один раз. Поэтому меняем приоритеты и получаем решение с одним рейсом, который позволит учесть новое окно доставки. Оказывается такой рейс возможен, но пробег по нему будет немного больше — 35 км. Здесь ОТМ пропустил две точки, которые были на 3 и 4 месте в исходном рейсе, чтобы успеть в дальнюю точку до 11:00, а затем вернулся к ним и завершил объезд.
Фактор строгих окон доставки часто усугубляется непрогнозируемыми задержками на некоторых точках. То есть обязательно нужно приехать к определенному часу, чтобы вообще встать в очередь на разгрузку, но вот собственно разгрузки приходится ждать очень долго. Чтобы не ставить другие точки в зависимость от таких проблемных заказов их стараются отправлять отдельными машинами или догружать такими грузами, у которых вообще нет ограничений по окну доставки, то есть можно доставить совершенно в любое время. С точки зрения автоматизации подобная житейская мудрость кажется довольно сложной в реализации, но на самом деле если разложить все на простые слагаемые можно получить очень даже неплохой результат. Главное все правильно формализовать: задать окна доставки на заказах или сразу на точках, зафиксировать максимальное время нахождения на точке для подстраховки, задать приоритет по проблемным заказам или вообще признак, который исключает объединение с другими. Одним словом если не мудрость, то здравый смысл ОТМ точно сможет применить в конкретном случае.
Кстати, мой самый частый ответ на самый частый вопрос пользователей ОТМ «Почему он так странно поехал?!» обычно звучит так — «Наверное, потому что такие окна в заказах!» Как правило, так и есть. А в случае со сложными окнами, когда время оказывается важнее расстояний, даже опытному логисту простого взгляда на карту для составления согласованного маршрута будет недостаточно.