В статье хотим поделиться своим опытом реализации алгоритма решения задачи маршрутизации на основе метода имитации отжига в Norbit CDS – умной системе управления доставкой. 

Проанализировав материалы, можно обнаружить различные предлагаемые способы решения VRP-задач (Vehicle Routing Problem). Главная их цель – планирование маршрутов для транспортных средств оптимальным способом. Основными критериями, как всегда, остаются наикратчайший путь для транспортного средства и доставка услуг во все заданные точки. В рабочем месте логиста Norbit CDS задача не отличается. 

Создавая свой алгоритм оптимизации построения маршрутов доставки, мы исходили из следующих входных данных: количество транспортных средств, число заявок для распределения с учетом их габаритов и окон желаемого времени доставки. Для реализации был выбран метод отжига.

Метод имитации отжига

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

,где – множество всех состояний, а – начальное состояние;

–  температура системы на -ом шаге, соответственно – температура при начальном состоянии ;

– функция изменения температуры;

– функция, вызывающая новое состояние;

– функция вероятности принятия нового состояния ;

– состояние, при котором достигнуто лучшее решение.

Алгоритм метода заключается в следующем.

1. Формируется начальное состояние ,,.

2. -я итерация алгоритма:

• ;

• ;

• если , , то ,.

Реализация метода имитации отжига в Norbit CDS

Обозначения

Рассмотрев основные понятия метода, перейдем к реализации метода имитации отжига в системе Norbit CDS.

Для более комфортного обсуждения введем некоторые понятия.

– список транспортных средств для формирования маршрутов, где – количество транспортных средств для решения задачи. 

– список сформированных маршрутов, .

  – список заявок на доставку, где– количество заявок на доставку, которые необходимо распределить по маршрутам. У каждой   имеются такие атрибуты, как вес, ожидаемое время доставки (рассчитывается в зависимости от других заявок в маршруте), окно доставки, указанное клиентом.

– значение температуры, при котором завершается алгоритм поиска лучшего решения.

– максимальное количество доставок в одном маршруте.

DeliveryInfoMatrix – матрица M×M, содержащая информацию о дальности расположения точек заявок на доставку друг от друга. 

Для формирования матрицы используется проект OSRM API, написанный на C++ c открытым исходным кодом и позволяющий строить наикратчайшие пути между точками на карте. Для наших нужд был использован Route Service, предоставляющий ответ в виде объекта Route, который содержит в себе расстояние пути в метрах и время в секундах для данного пути. 

Стоит обратить внимание, что время указывается среднее, так как в OSRM API отсутствуют данные о прогнозах пробок. На рисунке 1 представлен наглядный вид формируемой матрицы. Для каждого пересечения указаны два значения – расстояние в метрах и необходимое время в секундах, чтобы добраться из одной точки доставки в другую.

 – критерий оптимизации, отвечающий за величину опозданий при доставках заявок по всем сформированным маршрутам в состоянии . 

 – критерий оптимизации, отвечающий за общее значение метража всех маршрутов в состоянии .

– основное решение для оптимизации, то есть лучшее решение.

– функция, для которой требуется найти состояние , при котором она будет принимать наименьшее значение.

– вероятность принятия нового состояния .

Алгоритм

Входными параметрами реализованного алгоритма являются: список транспортных средств, список заявок, начальная температура, конечная температура и максимальное количество заявок в одном маршруте . Перед запуском алгоритма рассчитывается матрица DeliveryInfoMatrix.

Следующим шагом идет формирование начального состояния. Транспортные средства получают заявки в порядке очередности. В цикле происходит заполнение маршрута заявками путем обнаружения самой ближней заявки по матрице DeliveryInfoMatrix к крайней добавленной точке заявки в маршрут. Для каждого маршрута отправной точкой является точка склада .

При добавлении заявка проверяется – может ли она быть размещена в транспортном средстве. Учитываются следующие пункты: проходит ли по весу, превышает ли маршрут максимальное количество заявок , а также фиксируется, что заявка не была добавлена в другие маршруты ранее. Как только первый маршрут укомплектован, начинает заполняться следующий.

При формированииесть вероятность, что часть заявок не поместилась в транспортные средства и осталась незагруженной. Незагруженные заявки отправляются в список.

Для каждого маршрута происходит подсчет параметра BeginDateTime – время, к которому водитель доставит первую заявку. Следом происходит подсчет приблизительного времени доставки для всех заявок в маршруте. После этого мы можем рассчитать критерии и и записать начальное состояние как временное решение и лучшее решение .

Теперь рассмотрим алгоритм на -ой итерации. Первым делом генерируется новое состояние решения c помощью функции .

В состоянии x из каждого маршрута в случайном порядке выбирается и удаляется по одной заявке. Данная выборка перемешивается с ранее нераспределенными по маршрутам заявкам . Таким образом получаем список заявок, с которыми будем работать в текущей итерации. 

Каждую из заявок пытаемся распределить по маршрутам. Заявка помещается в первый попавшийся маршрут, подходящий под условия – проходит по весу и количеству заявок в маршруте. Заявка помещается в маршрут исходя из расчетов из какой точки уже существующих заявок быстрее будет до нее добраться. Так продолжается до момента пока все заявки не будут разгружены. По данному алгоритму первый подходящий маршрут не заполняется полностью заявками. Наполнение происходит постепенно в каждый из них. Пример наполнения представлен на рисунке 2.

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

Следующим этапом решим, подходит ли в качестве . Первым делом проверяем по критериям , затем уже , чтобы определить является ли текущее состояние лучше наших и состояний решений. Если или и , то . Если или и, то . Также есть вероятность, что состояние решения , которое хуже по критериям и , чем и может всё равно стать следующим состоянием решения  для продолжения поиска оптимального варианта. 

Функция применяется для принятия решения перехода . Случайным образом определяется значение . Если , то в случае, если таких состояний решений на -тых итерациях было подряд меньше 50 раз, то так и быть . В случае, если давно не находилось состояния решения лучше (а именно 50 итераций подряд), то . Тем самым, мы повышаем шансы получить более выгодное состояние решения при следующей итерации, так как меняем , от которого ищутся видоизменённые варианты новых состояний решений.

После определения состояния решения по алгоритму метода отжига требуется перерасчет температуры . Для пересчета температуры используется формула как в Больцмановском отжиге:

Так итерации будут выполняться до того момента, пока . В конце получаем лучшее состояние решения.

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

После метод отжига применяется еще раз, но относительно маршрутов , составленных в лучшем состоянии решения. В ходе самого маршрута , будут применяться перестановки точек заявок на доставку маршрута и, соответственно, лучшее решение посещения точек закрепится за маршрутом . На этом шаге мы получаем наше финальное для поставленной задачи состояние решения.

Результаты работы метода

Рассмотрим результаты работы алгоритма. Подадим на вход следующие данные: 18 заявок, расположенных следующим образом на рисунках 3, 4 транспортных средства,

Алгоритм справился за 4 минуты 15 секунд, было сформировано 2 маршрута. На рисунках 4 и 5 представлены сформированные маршруты. Несмотря на то, что было задано большее число транспортных средств на входе, происходит проверка на их необходимое количество от объема и веса заявок на доставку. Так как по нашему алгоритму максимальное количество заявок на доставку в транспортном средстве 11, то машины рассчитываются исходя из формулы , где – количество возможных машин. Следом, если есть еще свободные транспортные средства, идет расчет по весу заявок, чтобы добавить дополнительно машину. Такой подход помогает избежать полупустых маршрутов. 

В маршрут №1 попали заявки, которые находятся почти по одному адресу и где алгоритм отрабатывает корректно, выстраивая посещение этих точек друг за другом (рисунок 6). Однако также присутствует пара заявок, которые не вошли ни в один сформированный маршрут.

Рассмотрим маршруты, сформированные на рисунке 7. Можно заметить, что точка под номером 1 (рисунок 7a) и точка под номером 2 (рисунок 7б) находятся в одной и той же области доставки. Следовательно, было бы логично послать в дальнюю область доставки не два транспортных средства, а одно. Данная ситуация появляется за счет того, что написанный алгоритм распределения заявок по маршрутам не учитывает глобальное состояние всех маршрутов, а рассматривает и улучшает только уже сформированный, внося в него с каждой итерацией минимальное случайное изменение. 

Также наполнение маршрута сильно зависит от начального состояния, которое состоит из полностью заполненных сформированных маршрутов и части маршрутов с парой заявок, не поместившихся в другие. Итого мы получаем следующую картину: на рисунке 8 представлено отображение созданных алгоритмом маршрутов, отсортированных по заполненности. Красный означает полную загрузку, а зеленый, что транспортное средство почти не загружено. Это обращает наше внимание на то, что распределение заявок по маршрутам неравномерно. Где-то очень много доставок, а где-то почти нет. 

Данная проблема также оказывает влияние на большой разброс заявок по карте, что видно на двух примерах формирования маршрутов. В алгоритме отсутствует возможность рассмотрения заявок по области их месторасположения. А начальное состояние и последующие изменения в виде перестановки по одной заявке из маршрута в другие не приводит к желаемому результату.

Заключение

Таким образом, на основе метода имитации отжига был сформирован один из алгоритмов автоматического планирования маршрутов, который является частью программного решения Norbit CDS, разработанного компанией НОРБИТ. В ходе анализа его работы можно заключить, что требуется доработка алгоритма в будущем для лучшего распределения заявок. Также стоит отметить, что система Norbit CDS поддерживает множественность алгоритмов и даже алгоритмы заказчиков. В частности, присутствуют комбинаторные и генетические алгоритмы, которые дают не только лучшую сходимость, но и время выполнения, однако при этом хуже горизонтально параллелятся.