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

Задача маршрутизации транспорта (Vehicle Routing Problems, VRP) — это задача комбинаторной оптимизации. Предполагается, что имеется некоторый автопарк, который расположен в одном депо (или нескольких). Требуется определить набор маршрутов до клиентов, который находятся на определенном расстоянии. Интерес к VRP вызван ее практической значимостью.

Задача маршрутизации автотранспорта (Vehicle Routing Problem-VRP) является одной из самых актуальных проблем в логистике[21].

Фактически решить классическую задачу маршрутизации — это значит построить непересекающиеся гамильтоновы циклы в связном взвешенном графе, в вершинах которого находятся заказчики, а ребра же указывают стоимость маршрута — расстояние и/или время. Эта задача относится к NP-полным[24]. На рисунке ниже приведен пример решения классической задачи маршрутизации автотранспорта.

клиенты.

VRP — это задача целочисленного программирования. Ее вычислительная сложность зависит от размера входных данных экспоненциально.

Для таких задач (NP-полных) обычно достаточно найти приближенное решение с определенной точностью. Обычно это получается сделать, используя различные эвристические методы. Как известно, задачи VRP лежат на пересечении двух других задач:

Задача коммивояжера (TSP).

Задача об упаковке рюкзака (Bin Packing Problem, BPP).

В случае с TSP задачу VRP можно свести к MTSP. Например, если принять грузоподъемность каждого автотранспорта бесконечной (или достаточно большой). Это достигается с помощью добавления к исходному графу k-1 копий нулевой вершины и ее ребер, k — число маршрутов. Если же в случае BPP все расстояния принять равными нулю, тот ее решение будет эквивалентно решению VRP, то есть имеем одинаковую эффективность для всех решений.

Задачи маршрутизации — важные задачи в области транспортных перевозок. В некоторых областях рынка доставка товара может значительно увеличивать стоимость товара, иногда сравнимую со стоимостью самого товара. При использовании методов оптимизации возможна экономия до 10−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 на подмножества (маршруты);

задание порядка обхода на каждом подмножестве, т. е. перестановка вершин маршрута.

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

FVRP = ?C (Ri), i = 1.m.

где C (Ri) — сумма длин ребер маршрута Ri.

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

CVRP: задача с ограниченной грузоподъемностью.

VRPTW: задача с временными окнами, т. е. клиент обслуживается в удобное ему время («временное окно»).

MDVRP: задача с несколькими депо.

VRPPD: модификация VRP, в которой клиенты имеют право возвращать товары в депо.

VRPB: аналогична VRPPD с той разницей, что товар возвращается только после того, как выполнена доставка всех товаров.

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

SVRP: некоторые характеристики (длина маршрута, запросы клиентов) — случайны.

VRPSF: возможна дополнительная загрузка машины по пути Как видно из приведенной классификации, данная задача имеет весьма разнообразные ограничения, которые тем не менее применимы к реальной жизни. Этим объясняется актуальность данной проблемы. Далее рассмотрим подробнее задачи:

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

Маршрутизация с ограничением по времени.

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

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

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

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

Маршрутизация с возвратом товаров.

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

Маршрутизация с различным транспортом.

В данной модификации задачи маршрутизации допускается обслуживать одного клиента разными единицами транспорта, особенно в случае если это уменьшает стоимость. К примеру, если объем заказа достаточно большой. При этом, обычно решить такую задачу сложнее, чем стандартную. Также предполагается, что в автопарке имеются машины разной грузоподъемности. Если разбить заказ на несколько неделимых, то из SDVRP можно получить стандартную VRP.

Маршрутизация со случайными данными.

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

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

Например, в задаче SVRP с возвратом товаров и ограничением по вместимости могут использоваться такие способы коррекции:

если машина заполнена, то необходимо вернуться в депо, а затем оптимизировать оставшийся маршрут;

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

Маршрутизация с возможностью дозагрузки.

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

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