In Endlish

Перевозка грузов с подхватом и доставкой

Главные достоинства программы VrpPd

VrpPd может находить близкие к оптимальному решения различных задач планирования маршрутов транспортных средств - CVRP,VRP,VRPPD с временными окнами или без, с разнородным парком транспорта, с одним или несколькими депо. Программа планирует маршруты таким образом, что она минимизирует число посещений клиентов , если это возможно (или может не делать этого) , планирует маршруты с возвратом для повторной погрузки/разгрузки если это необходимо, может планировать маршруты в режимах ограничений на порядок загрузки - "последний загружен - первый выгружен" - (LIFO) или (FIFO), учитывает транспортную работу тр.средства при оптимизации - это дополнительная экономия.

VrpPd очень простая в установке и использовании - просто скопировать два файла в любую папку на компьютер под управлением Ms Windows где установлен Ms.Net фреймворк версии не ниже 4.0 - практически любой компьютер под управлением OS Windows. Все данные программа хранит в файле Ms Access - у вас нет нужды поддерживать большие и сложные базы данных и её легко интегрировать с другими программами. Программа так же имеет встроенную поддержку импорта данных из простых текстовых файлов и может получать информацию из Google Maps.

Очень хорошо распараллеливает работу - чем больше доступно процессорных ядер - тем быстрее работает.Это важно если решаются большие задачи.

(Описание программы VrpPd)

Задачу перевозки грузов с подхватом и доставкой (английская аббревиатура VRPPD - Vehicle routing problem with pickup and delivery) можно описать следующим образом.Есть список пунктов между которыми нужно перевезти грузы с учётом грузоподъёмности транспортного средства и при этом оптимизировать маршрут используя те или иные критерии.

Это одна из наиболее общих постановок задач для маршрутизации транспорта.Например если необходимо доставлять грузы из депо к клиентам - то эта классическая задача развозки грузов, причём при необходимости автоматически будут планироваться повторные посещения депо. Если необходимо доставлять грузы от клиентов в депо - то эта задача сборки грузов.Могут быть описаны просто перевозки грузов между клиентами, между несколькими складами и клиентами и т.д.

Может быть вариант с ограничениями по разгрузке транспортного средства - например разгрузка по принципу - груз, который загружен последним - выгружается первым ( так называемый LIFO - last in first out принцип) или FIFO - первый загружен, первый выгружен.Это нужно,например,в тех случаях, когда загрузка осуществляется через заднюю дверь транспортного средства.Если планировать маршрут по принципу LIFO - то не нужно будет перегружать грузы, которые нужно доставить позже - при этом экономится время на разгрузку, хотя длина маршрута может быть немного больше.

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

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

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

Это, так называемая, NP - полная задача, т.е. она не решается простым перебором вариантов уже при достаточно небольшом количестве заказов на перевозку грузов. В моей программе используется один из лучших методов поиска решения - так называемая LNS (large neighborhood search) эвристика вместе с "имитациией отжига".

В программе также предусмотрена интеграция с - Google Maps - геокодирование и получение матрицы расстояний и времени между пунктами.Либо матрица расстояний и времени может быть введена вручную.

Несколько скриншотов :

Расстояния и время между пунктами задаюся таким же образом как в "Задаче коммивояжера в городе",затем задаётся список разнородных машин :

Транспортные средства

Для каждого транспортного средства грузоподъёмность,максимальный объём, максимальный пробег и ограничение на количество заказов по маршруту. Определяется так же пункт начала маршрута и устанавливается признак , является ли маршрут кольцевым. Возможное ограничение на погрузку - без ограничений,LIFO или FIFO. Время начала - конца работы. Набор свойств,если нужно чтобы конкретные заказы выполнялись определёнными тр. средствами.(Свойства для заказа, которые требуются для его выполнения - могут быть заданы для каждого конкретного заказа.)

Далее описывается список заказов на перевозку.

Заказы на перевозку

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

Поиск оптимального маршрута

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

Примеры найденных маршрутов (маршруты для каждого транспортного средства) - в нормальном and LIFO режимах оптимизации.


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


Одной из уникальных особенностей VrpPd является то, что она оптимизирует не только расстояние, но и объём транспортной работы. Посмотрите на картинку справа.Я попробую привести очень простой пример. У нас есть депо D и два клиента "A" и "B".Мы должны доставить им 30 и 100 единиц груза соответственно, одним транспортным средством и вернуться в депо.Расстояния показаны на картинке. Если мы спланируем маршрут "D->A->B->D" или "D->B->A->D" расстояние, пройденное транспортным средством будет одним и тем же - 110. Но, если маршрут будет "D->A->B->D" , мы будем везти 100 единиц груза для "B" на расстояние 80, и 30 единиц груза для "A" на расстояние 50 ,а если мы спланируем маршрут "D->B->A->D" мы перевезём 100 единиц груза для "B" только на расстояние 30, а для "A" - всего 60. Таким образом, нет разницы в расстоянии, но значительно больше работа транспортного средства - оно везёт тяжелый груз на большее расстояние. Большинство программ это не учитывают.VrpPd всегда это учитывает.Это может дать значительую экономию топлива.


Чтобы протестировать программу, были решёны A-n65-k9 и G-n262-k25 известные примеры CVRP задачи. CVRP - частный случай VRPPD когда все заказы на перевозку грузов - из депо к клиентам. Для тестирования временных окон, я решил несколько известных CVRPTW примеров - например , пожете посмотреть здесь

Тестовую версию программы вы можете загрузить с английской странички.


© 2016 Если у вас есть вопросы,предложения или вы заинтересованы в решении таких задач - Пишите на shobb@narod.ru