Логистическое планирование доставки товаров

Стоимость пути рассчитывается, как и в случае стандартной  ЗМТ.

4. Маршрутизация с возвратом товаров (VRP with Pick-Ups and Deliveries, VRPPD)

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

Для простоты обычно рассматриваются  задачи с дополнительными ограничениями, например, когда все запросы на доставку товаров начинаются в депо и все запросы на возврат товаров  оканчиваются в депо, то есть, не происходит обмен товарами между потребителями. Другой способ состоит в отмене ограничения, что все клиенты должны посещаться только один раз. Существует еще одно обычное упрощение – принять, что каждый автомобиль сначала развозит все товары, прежде чем начать принимать товар от клиентов (VRp with Backhauls, VRPB).

Цель: минимизировать парк транспорта и общее время движения.

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

5. Маршрутизация с возвратом товаров (VRP with Backhauls, VRPB)

Задачи маршрутизации  с возвратом товаров (VRPB) являются расширением ЗМТ, в котором потребители могут как запросить, так и вернуть некоторые товары. В задаче с доставкой и возвратом (VRPPD) необходимо принять во внимание, что товары, которые вернут потребители, должны уместиться в машине. Отличие от VRPPD состоит в том, что все товары должны быть доставлены, прежде чем произойдет любой возврат. Это требование происходит из того факта, что все машины загружаются сзади и перестановка грузов не является экономически выгодной и приемлемой. Количество товара, который необходимо доставить и принять, фиксировано и известно заранее.

Цель: найти такой набор  маршрутов, чтобы минимизировать общее  пройденное расстояние.

Ограничения: возврат товаров  происходит только после того, как  завершена доставка. Объем товаров  при доставке и при возврате не должен превышать грузоподъемности.

6. Маршрутизация с различным транспортом (Split Delivery VRP, SDVRP)

Данная задача расширяет ЗМТ, позволяя обслуживать одного клиента различными видами транспорта, если это уменьшает общую стоимость задачи. Этот случай типичен для ситуации, когда объем заказа сравним по величине с вместимостью машины. Как правило, для задачи маршрутизации с различными видами транспорта получить оптимальное решение сложнее, чем для классической задачи ЗМТ.

Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.

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

7. Периодическая маршрутизация (Periodic VRP, PVRP)

В классической задаче ЗМТ обычный период планирования – один день. В задачах с периодической маршрутизацией ЗМТ обобщается расширением периода планирования до нескольких дней.

Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.

Ограничения: те же, как и  в классической ЗМТ. Кроме того, машина может вернуться в депо не в тот же день. По истечении M-дневного периода каждый клиент должен быть посещен как минимум один раз.

8. Маршрутизация со случайными данными (Stochastic VRP, SVRP)

В данном варианте ЗМТ один или несколько компонентов задачи могут иметь случайное поведение.

Случайные клиенты: каждый клиент существует с вероятностью p и отсутствует  с вероятностью p-1.

Случайные запросы: запрос каждого  клиента – случайная величина.

Случайные времена: времена  поездок (расстояния между потребителями) – случайные величины.

Решение SVRP происходит в два подхода. Первый этап дает решение без учета случайных переменных. На втором этапе, когда становятся известными случайные значения, происходит коррекция ранее полученного решения.

Цель: минимизировать парк транспорта и общее время обслуживания всех клиентов.

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

9. Маршрутизация с возможностью дозагрузки (VRP with Satellite Facilities, VRPSF)

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

Цель: минимизировать расходы  на доставку товаров за определенный срок (возможно, что, учитывая расходы  на вспомогательные машины, общая  стоимость решения задачи в краткосрочной  перспективе будет выше, чем, например, при решении классической задачи ЗМТ).

Ограничения: товар на складе клиента не должен заканчиваться.

6. Существующий инструментарий для решения ЗМТ

На сегодняшний день, существует два крупнейших поставщика программного обеспечения, реализующего решение задач маршрутизации транспорта, хорошо известный ArcGIS, а так же PVT Vision, в добавок к ним, в сети можно найти множество различных мелких утлит от разных производителей. ArcGIS и PTV Vision не являются программами транспортной логистики в чистом виде, но содержат необходимые функции для этого. Так как разбор продукта PTV Vision в сети довольно скуден, я рассмотрю геоинформационную систему ArcGIS, а в частности ее дополнительный модуль Расширение ArcGIS Network Analyst, именно этот продукт является самым популярным и используемым среди крупных транспортно-экспедиторских организаций.

 Расширение ArcGIS Network Analyst может с успехом применяться предприятиями, общественными службами и другими организациями, которые смогут вести свою деятельность более эффективно и принимать более выгодные стратегические решения. Данные о том, кто нуждается в их товарах или услугах помогут таким организациям лучше понимать текущую и потенциальную динамику рынка. Можно сократить транспортные расходы, оптимально распределив остановки и определив кратчайшие пути между этими остановками с учетом ограничивающих факторов, таких как временные интервалы/окна, вместимость машин и максимальное время в пути. Уровень обслуживания клиентов можно повысить за счет сокращения быстроты реагирования или более удачного расположения пункта обслуживания. Расширение ArcGIS Network Analyst помогает лучше понимать задачи такого характера и решать их.

Исследователи и аналитики  могут использовать возможности  дополнительного модуля для определения  наименее затратных сетевых путей  между несколькими исходными  точками и пунктами назначения. Матрицы  стоимости Источник–Назначение, создаваемые с помощью дополнительного модуля Расширение ArcGIS Network Analyst, часто содержат начальные вводные данные для выполнения более масштабных расчетов. Например, при прогнозировании транспортных потоков часто учитываются данные о расстоянии до определенных узлов транспортной сети. Значения этих сетевых расстояний используются при вычислении математических выражений, помогающих прогнозировать прохождение маршрута. Пример сетевых путей в ArcGIS показан на рисунке 1.5.

Рисунок 1.5 – Сетевые пути из исходных точек до пунктов назначения в ArcGIS.

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

7.  Результаты анализа и постановка задачи

В результате исследования выяснился  интересный факт: на практике пользуются очень старыми алгоритмами. Если прикидочно, то может быть, исследованными где-нибудь в 80-х годах. То есть в статьях алгоритмов 
предложено в разы больше, чем их на деле реализовано. При этом причина 
такого положения в целом не скрывается. Самые мощные алгоритмы – 
мета эвристические, а они требуют подбора управляющих параметров, что 
может сделать только специалист. Вот и выходит, что люди предпочитают 
проверенные старые, но повсеместно применимые методы, чем новые, но 
сложные и запутанные. Пусть даже в ущерб качеству. Следовательно, существующие программы не приспособлены к условиям городской транспортной сети, а также не позволяют решать задачи маршрутизации транспорта с ограничением по грузоподъемности. Таким образом, целью настоящей работы является получение приближённых алгоритмов решения ЗМТ, способных выполнять построение маршрутов для входных данных, содержащих 100 вершин при использовании геометрической информации. В рамках указанной цели были поставлены следующие задачи:

1. Разработка и исследование эффективных приближённых алгоритмов, дающих сбалансированное по количеству вершин в отдельных маршрутах решение ЗМТ при заранее указанном количестве транспортных средств.
2. Построение планов доставки для розничной клиентской сети.
3. Разработка и исследование эффективных приближённых алгоритмов, дающих решение ЗМТ с учётом грузоподъёмности транспортных средств.

 

 

 

 

2. МАТЕМАТИЧЕСКАЯ  МОДЕЛЬ АГОРИТМА РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ  ТРАНСПОРТА В УСЛОВИЯХ ГОРОДСКОЙ  ДОРОЖНОЙ СЕТИ

1.  Классификация алгоритмов для решения ЗМТ

К настоящему моменту известно достаточно много алгоритмов для  решения ЗМТ. Большей частью это  эвристические методы, используемые при наличии матрицы расстояний или информации о расположении вершин на плоскости. Как говорилось во введении, ЗМТ является NP-трудной задачей, поэтому наиболее интенсивно поиск  ведётся в направлении приближённых алгоритмов. Предлагались точные методы решения ЗМТ, как, например, метод ветвей и границ, но время вычислений при их применении растёт слишком быстро. ЗМТ предполагает значительно большее количество вариантов решений для просмотра, чем ЗК при одинаковом количестве вершин, в то время как применение метода ветвей и границ для решения ЗК уже затруднительно для наборов данных с 30 вершинами и больше.

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

Поиск решений ЗМТ начался  в 60-е годы XX века. Эвристические методы, которые в наши дни называют классическими, разработаны в основном между 1960 и 1990 годом. В последние двадцать лет усилия направлены в основном на направление так называемых метаэвристик.

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

Классические алгоритмы  можно разбить на три группы [20]:

1. Конструктивные алгоритмы: выполняют постепенное построение решения, отслеживая рост его стоимости, но не имеют фазы дальнейшего улучшения.
2. Двухфазные (кластерные) алгоритмы: задача разбивается на две части:  группировку вершин для каждого будущего маршрута (кластеризацию) и решение ЗК для каждой полученной группы. Возможно наличие обратной связи между этапами решения. В свою очередь двухфазные методы делятся ещё на две группы:

• сначала кластеризация, затем поиск решения ЗК;

• сначала решение ЗК, а затем разделение на несколько маршрутов. ЗК решается для всех вершин исходного множества.

3. Улучшающие алгоритмы: сначала ведётся поиск некоторого решения, а затем делаются попытки обмена вершин (рёбер) внутри каждого маршрута или между маршрутами.

Следующие алгоритмы относят  к разряду метаэвристик [15]:

• Поиск с исключениями.
• Моделируемый отжиг.
• Детерминированный отжиг.
• Генетический алгоритм.
• Алгоритм на основе муравьиных колоний.
• Нейронные сети.

Все метаэвристики, кроме  поиска с исключениями, предложены на основе идей, появившихся при  наблюдении процессов живой и  неживой природы. Первые три подхода: поиск с исключениями, моделируемый отжиг и детерминированный отжиг начинают работу с некоторого начального решения x₁, на каждой итерации t выполняют переход от решения x_t к решению x_t+1, находящимся в окрестности N (x_t) решения x_t, до тех пор, пока не будет выполнено некоторое условие остановки вычислений.