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

К задачам, решаемым транспортной логистикой, специалисты относят [4]:

• создание транспортных систем, в том числе создание транспортных коридоров и транспортных цепей;
• обеспечение технологического единства транспортно-складского процесса;
• определение рационального маршрута доставки груза;
• выбор типа и вида транспортного средства и др.

 В настоящее время, задачи транспортной логистики ежедневно решаются транспортно-экспедиторскими организациями.  

2. Транспортная экспедиция

Транспортная экспедиция – это оказание услуг грузоотправителям и грузополучателям (клиентам), и организация доставки грузов  каким-либо видом транспорта. 

Первые экспедиторские организации  были созданы для завоза и вывоза грузов с железнодорожных станций. До 1979 года все грузоотправители и  грузополучатели сами  договаривались с автотранспортными предприятиями для доставки грузов на железнодорожную станцию или со станции. В 1979 году Совет Министров СССР  установил, что только предприятия грузового автотранспорта могут предоставлять транспортно-экспедиторские услуги. Позже был разработан  типовой договор на централизованную перевозку грузов автомобильным транспортом с железнодорожных станций, из морских и речных портов, аэропортов и обратно.  На протяжении многих лет транспортные компании пользовались этим договором.  Но услуги, оказываемые автомобильными предприятиями центровывоза, не были комплексными.

В идеале, транспортная экспедиция подразумевает организацию перевозки  грузов от двери склада грузоотправителя до двери склада грузополучателя, сокращенно «от двери – до двери». При  этом экспедиторское предприятие оказывает  полный комплекс услуг по доставке груза: доставку от склада грузоотправителя на грузовую железнодорожную станцию, погрузку в вагон, оплату железнодорожного тарифа, выгрузку из вагона на станции  назначения и доставку  груза автомобильным транспортом до склада грузополучателя. Руководство грузовыми перевозками и грузовыми станциями на железных дорогах  осуществляют грузовые службы. Первые экспедиторские компании были организованы  именно при грузовых службах, а затем они были преобразованы в государственные унитарные предприятия (ГУП).                       

Краткий перечень транспортно-экспедиционных услуг:

• составление маршрута перевозки груза по поручению клиента при смешанных перевозках (т.е.  при перевозках несколькими видами транспорта, эти перевозки также называются интермодальными). 
• заключение договоров с другими экспедиторами и участниками перевозочного процесса для фрахтования морских и речных судов, самолетов, вагонов и автомобилей;
• оформление транспортных накладных коносаментов и других документов, необходимых для доставки грузов по назначению;
• оплата транспортных тарифов и других платежей и сборов;
• взаимодействие со страховыми компаниями по страхованию грузов, участие в оформлении документов при несохранных перевозках ( т.е. при прибытия грузов с повреждениями, порчей или недостачей);
• выполнение обязанностей таможенного брокера  при перевозках экспортно-импортных  грузов;
• передача грузовладельцам информации о продвижении грузов, розыск грузов;
• организация переадресовки грузов в пути следования;
• получение разрешений и оформление документов на перевозку опасных, крупногабаритных и тяжеловесных грузов.

Это далеко не полный перечень услуг, которые могут быть обусловлены  договором транспортной экспедиции.

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

3.  Основные принципы маршрутизации

Маршруты в транспортной логистике делятся на 4 типа [5]:

1. Городское  –  в данном случае, транспортное средство перевозит груз только по городу, не выезжая за его пределы (Например, перевозка груза по Харькову);
2. Пригородные – движение транспортного средства, перевозящего груз в точку разгрузки, производится по маршруту в радиусе до 50 километров от точки его загрузки. (К примеру, доставка грузов по Харьковскому району);
3. Междугородние  – это маршрут перевозки груза, пролегающий от одного города к другому, на расстоянии более 50 километров, к данному пункту относятся грузоперевозки по Украине;
4. К международным  – относятся маршруты перевозки груза пересекающие границы соседних государств.

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

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

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

Регулярные маршруты грузоперевозок делятся на три типа: 
Маятниковые маршруты перевозки груза  – когда транспортировки груза производится между определенными пунктами, туда и обратно. [6] Варианты маятникового движения представлены на рисунке 1.1.

Рисунок 1.1  – Варианты маятникового движения

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

Кольцевые маршруты перевозки  груза – данные маршруты имеют вид замкнутого круга, с разгрузками и загрузками на всем протяжении пути (рисунок 1.2).

Рисунок 1.2 – Кольцевые маршруты перевозки груза

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

4. Задачи маршрутизации транспорта

Задачи маршрутизации  транспорта (ЗМТ) – задачи комбинаторной оптимизации, в которых для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких отдаленных точек – потребителей [7]. Интерес к ЗМТ вызван ее практической значимостью при значительной сложности. Наглядный пример ЗМТ показан на рисунке 1.3.

 

Рисунок 1.3 – Пример ЗМТ

ЗМТ – хорошо известная задача целочисленного программирования, относящаяся к классу NP-трудных задач, что означает, что вычислительная сложность задачи зависит от размера входных данных экспоненциально.

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

Задачи ЗМТ лежат на пересечении двух хорошо изученных задач. 

Задача коммивояжера (Traveling Salesman Problem, TSP): если грузоподъемность с  каждого транспортного средства принимается бесконечной (точнее, достаточной), то задача ЗМТ сводится к множественной задаче коммивояжера (Multiple Traveling Salesman Problem, MTSP) путем добавления к исходному графу k-1 (где k – количество маршрутов) копий нулевой вершины и ее ребер (между этими копиями ребра отсутствуют). 

Задача об упаковке рюкзака (Bin Packing Problem, BPP): решение данной задачи, по сути, эквивалентно решению задачи ЗМТ при условии, что все расстояния принимаются равными нулю (таким образом, эффективность всех подходящих решений будет одинакова).

Задачи маршрутизации  являются ключевыми в областях транспортных перевозок, перемещения и логистики. Во многих областях рынка доставка товара добавляет к его стоимости  сумму, сравнимую со стоимостью самого товара. Тем не менее, использование  компьютерных методов оптимизации  доставки товара часто выражается в экономии порядка 5–20% от общей его стоимости.

Классический вариант задачи маршрутизации:

Маршрутизация транспорта относится  к комбинаторным задачам, которые  можно представить в виде графа G(V, E):

V = {v0, v1, ..., vn} – множество вершин (v0 – депо, v1..n – потребители); 
E – множество ребер {(vi, vj) | i ≠ j};

C – матрица неотрицательных расстояний (стоимости пути) cij между потребителями;

m – количество машин;

Ri – маршрут i-й машины (i=1..m);

C(Ri) – стоимость маршрута Ri;

qi – объем груза, поставляемый i-му потребителю.

С каждой вершиной Vi ассоциировано  некоторое количество товаров, которые  должны быть доставлены соответствующему потребителю. Задача маршрутизации  состоит в определении такого множества маршрутов m с минимальной  общей стоимостью, чтобы каждая вершина  множества V была посещена только одним  автомобилем только один раз. Кроме  того, все маршруты должны начинаться и заканчиваться в депо (v0).

Решением задачи является:

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

Целевой функцией является стоимость  решения задачи:

FЗМТ = ∑C(Ri), i = 1..m, где C(Ri) – сумма длин ребер маршрута Ri.

В классическом варианте требуется  найти приемлемое решение с минимальной стоимостью.

5.  Разновидности ЗМТ

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

• Capacitated VRP (CVRP): каждое транспортное средство имеет ограниченную и грузоподъемность.
• VRP with Time Windows (VRPTW): каждый заказчик должен быть обслужен в определенное «временное окно».
• Multiple Depot VRP (MDVRP): используются несколько депо для обслуживания клиентов.
• VRP with Pick-Ups and Delivering (VRPPD): клиенты могут возвращать некоторые товары в депо.
• VRP with Backhauls (VRPB): аналогично предыдущей, но возврат начинается только после доставки всех товаров из депо.
• Split Delivery VRP (SDVRP): каждый клиент может обслуживаться одновременно несколькими машинами.
• Periodic VRP (PVRP): доставка может осуществляться в течение нескольких дней.
• Stochastic VRP (SVRP): некоторые компоненты задачи (количество и запросы клиентов, длина пути) могут иметь случайное поведение.
• VRP with Satellite Facilities (VRPSF): существует возможность дозагрузки автомобиля на маршруте. 

1. Маршрутизация с ограничением по грузоподъемности (Capacitated VRP, CVRP).

В задачах  этого типа вводится дополнительное ограничение: объем грузов на каждом маршруте Ri не должен превышать заданной величины Q (одинаковый для всех машин).

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

2. Маршрутизация с ограничением по времени (VRP with Time Windows, VRPTW).

Данная задача подобна ЗМТ с основным дополнительным условием: для выполнения запроса каждого клиента vi существует известный промежуток времени, определенный как интервал [ei,li] – намеченный горизонт.

Рисунок 1.4 – Маршрутизация с ограничением по времени

На рисунке (Рисунок 1.4) представлен типичный вариант решения задачи с ограничением по времени. Для выполнения заказа каждого клиента существует допустимый интервал времени (показан белым цветом), реальный момент выполнения заказа в соответствии с полученным решением отмечен чертой.

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

Ограничения: по сравнению  с ЗМТ, в задачах данного типа добавляются следующие условия:

1. решение неприемлемо, если клиент обслуживается после верхней временной границы;
2. машина, прибывшая ранее нижней временной границы, ожидает ее наступления;
3. как вариант, опоздание не влияет на пригодность решения, но добавляет некоторое штрафное значение к целевой функции.

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

3. Маршрутизация с несколькими депо (Multiple Depot VRP, MDVRP).

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

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

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

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