Современное производственное или торговое предприятие, доставляющее покупателю продукцию собственным автотранспортом, сталкивается с так называемой транспортной задачей. Проблема заключается в оптимальном формировании комплекта заказов в каждую машину таким образом, чтобы:
- Построить оптимальный маршрут доставки. Зачастую отдельные адреса доставки находятся в значительном удалении от общей массы адресов, что приводит к сложностям в правильном формировании маршрутов и доставке в срок товара покупателю
- Оптимизировать загрузку транспорта. Маршруты должны быть сформированы так, чтобы исключить значительный недогруз или перегруз по весу автомобиля или сделать это явление контролируемым оператором. Плотная загрузка транспорта вкупе с оптимальным маршрутом позволяет справиться с нехваткой транспорта, уменьшить количество необходимого парка машие на линии и уменьшить затраты на зарплату водителей и ГСМ (прямые расходы на доставку).
- Решить проблему доставки товара в срок. Многие клиенты требуют доставить товар к определенному времени. Чаще всего это раннее утро или время, указанное в графике приема товара розничных сетей. Это так называемая «вилка доставки». В некоторые точки товар должен быть доставлен в первую очередь. Построение маршрутов должно учитывать эти ограничения.
- Учитывать длительность рабочей смены водителя
- Контролировать пробег автомобилей и расход топлива. Отслеживать движение автотранспорта, который должен следовать строго по маршруту .
В разработанной нашей компанией подсистеме реализовано решение транспортной задачи, а именно: распределение всех имеющихся заказов таким образом, чтобы максимально загрузить весь имеющийся парк автотранспорта, маршрутизация всех заказов с учетом сроков доставки, и построение для каждой машины оптимального маршрута проезда с минимизацией пробега или времени развоза; диспетчеризация водителей.
Данная подсистема реализована на платформе 1С:Предприятие 8.3 и является полноценной системой автоматизации транспортной задачи.
Подсистема предназначена для торговых, логистических и производственных предприятий, осуществляющих доставку товаров покупателям. Программа может быть интегрирована в учетную систему предприятия, либо приобретена в составе нашего головного продукта - учетной системы ТОД:Предприятие 2011 УНФ
Работу программы рассмотрим на примере работы в составе ТОД:Предприятие 2011 УНФ. Если у вас другая система, то входные и выходные данные для программы будут получены с помощью специальных интеграционных обработок.
Алгоритм построения маршрутов может быть реализован полностью автоматически, либо в интерактивном режиме. В последнем случае, оператору, при построении очередного маршрута предлагается следующий адрес доставки с расчетом времени доставки и общим весом заказов. Оператор может добавить предложенный заказ в текущий маршрут или пропустить адрес (см. рис.1). Также оператор может закончить построение текущего маршрута и перейти к построению нового. При желании можно продолжить построение маршрута в автоматическом режиме, а также вернуться в интерактивный режим. Так же возможен и полностью ручной режим, который может быть задействован в любой момент, в том числе и в процессе использования автоматического и полуавтоматического режима.
Для удобства автоматического формирования маршрутов существует возможность исключить из построения некоторые зоны доставки (например, центр). Полученное решение можно временно «заморозить», затем снять ограничения на зоны доставки и продолжить строить маршруты (например, для заказов в зоне центра). При таком подходе для особых зон при построении можно учесть определенные особенности и ограничения, которые не включены в автоматический алгоритм поиска. После окончания расчёта можно откорректировать вручную результат расчёта с помощью элементов управления в интерфейсе, при этом результаты динамически пересчитаются на форме и на карте.
При построении маршрутов можно учесть ограничения на время доставки (ночную или дневную доставку). В случае выбора такого фильтра в построении маршрутов будут участвовать заказы, удовлетворяющие условию отбора по времени доставки. Однако учет времени, к которому нужно доставить заказ покупателю, при автоматическом построении маршрута не производится, а строится оптимальный порядок объезда без учета ограничений по времени доставки.
Рис 1. Интерактивное построение маршрута.
Для учета ограничений по времени доставки используется следующий подход. Для найденных рейсов рассчитывается оптимальный порядок объезда и прогнозируемое время прибытия в каждый адрес доставки. Если доставка не вовремя, то она выделяется цветом (ранняя синим, поздняя красным – Рис.2). По желанию, оператора можно назначить начальный и конечный порядок объезда для некоторых заказов. Остальные заказы по-прежнему будут выстроены оптимально. Для учета начального и конечного порядка объезда следует использовать метод Литтла (метод ветвей и границ. Описание можно найти http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004. Протестировать работу алгоритма можно http://uchimatchast.ru/aplication/litl0.php). Мы несколько модифицировали описанный алгоритм. Результат учета порядка объезда показа на рис 3.
При анализе текущего маршрута, оператор имеет возможность посмотреть – можно ли его догрузить. Пример визуального добавление заказа к текущему маршруту показан на рис. 4. При этом предполагаемая длина маршрута и время доставки будут пересчитаны автоматически. Если оператора все устраивает, то он может добавить заказ в выбранный маршрут.
Анализ работы алгоритмов поиска маршрутов и оптимизации пути движения показал высокую их эффективность. Ожидаемый эффект от внедрения может составить от 5 до 20% снижения издержек на доставку товаров.
Рис. 2 Расчет оптимального порядка объезда для текущего маршрута.
Рис. 3 Построение оптимального маршрута с учетом порядка объезда.
Рис. 4 Визуальное добавление адреса к текущему маршруту.
