Оптимизационные задачи в транспортной логистике
Проведен обзор задач транспортной маршрутизации Vehicle Routing Problem (VRP). Рассмотрены наиболее исследованные варианты постановки задач VRP. Приведены методы их решения. Проведено огляд задач транспортної маршрутизації Vehicle Routing Problem (VRP). Розглянуті найбільш досліджені варіанти постан...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/112406 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оптимизационные задачи в транспортной логистике / А.Е. Скукис // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 106-113. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860242997138948096 |
|---|---|
| author | Скукис, А.Е. |
| author_facet | Скукис, А.Е. |
| citation_txt | Оптимизационные задачи в транспортной логистике / А.Е. Скукис // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 106-113. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Проведен обзор задач транспортной маршрутизации Vehicle Routing Problem (VRP). Рассмотрены наиболее исследованные варианты постановки задач VRP. Приведены методы их решения.
Проведено огляд задач транспортної маршрутизації Vehicle Routing Problem (VRP). Розглянуті найбільш досліджені варіанти постановки задач VRP. Приведено методи їх розв’язання.
It was made an overview of routing traffic namely Vehicle Routing Problem (VRP). The most researched options that define the stated tasks of VRP were considered in the article. The methods for their solution were given.
|
| first_indexed | 2025-12-07T18:32:42Z |
| format | Article |
| fulltext |
106 Теорія оптимальних рішень. 2015
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Проведен обзор задач транс-
портной маршрутизации Vehicle
Routing Problem (VRP). Рассмо-
трены наиболее исследованные
варианты постановки задач VRP.
Приведены методы их решения.
А.Е. Скукис, 2015
УДК 519.21
А.Е. СКУКИС
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ
В ТРАНСПОРТНОЙ ЛОГИСТИКЕ
Введение. Транспортная логистика – это пе-
ремещение требуемого количества товара в
нужную точку, оптимальным маршрутом за
требуемое время и с наименьшими затрата-
ми. Затраты на создание любого товара скла-
дываются из себестоимости его изготовления
и издержек на выполнение всех работ от мо-
мента закупки материалов до момента по-
купки товара конечным потребителем. Дви-
жение готового товара от первичного источ-
ника сырья, необходимого для его изготов-
ления до конечного потребления также тре-
бует затрат, которые могут доходить до 50 %
от общей суммы затрат на логистику. Таким
образом, транспортировка товара (груза) вы-
ступает одной из ключевых функций логи-
стики, связанная с перемещением продукции
транспортными средствами по определенной
методике в цепи поставок.
Задачи маршрутизации являются одним из
наиболее важных классов задач транспорт-
ной логистики. Цель данных задач – это ми-
нимизация стоимости, расстояния или вре-
мени транспортировки грузов.
Задачам в области формирования опти-
мальных транспортных маршрутов посвяще-
ны многочисленные исследования в разных
странах мира. Особую актуальность приоб-
ретают работы, позволяющие точно вычис-
лять объемы грузоперевозок, рассчитывать
количество единиц транспорта, необходимых
для обеспечения грузопотоков, определять
рациональные маршруты движения, а также
сократить суммарные затраты на транспор-
тировку. История задач маршрутизации
насчитывает более полувека. Первая работа,
посвященная данному типу задач, появилась
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В ТРАНСПОРТНОЙ ЛОГИСТИКЕ
Теорія оптимальних рішень. 2015 107
в 1959 году [1]. В ней сформулирована группа задач, впоследствии названная
Vehicle Routing Problem (VRP).
VRP – хорошо известная задача целочисленного программирования, явля-
ется практически важной и NP-сложной задачей комбинаторной оптимизации
[2]. На текущий момент существует большое множество вариантов задач
маршрутизации, которые можно классифицировать по некоторым признакам.
Среди основных, следует выделить такие:
- пункты производства (склад, база, депо);
- пункты потребления;
- базы (депо) транспортных средств (ТС);
- виды ТС;
- типы ТС;
- количество перевозимого груза;
- качество перевозимого груза;
- временные ограничения (получение/доставка груза в указанные
временные окна);
- другие признаки.
Классический вариант задачи маршрутизации можно представить комби-
наторной задачей в виде графа 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) – стоимость маршрута ;iR
- qi – объем груза, поставляемый i-му потребителю.
С каждой вершиной Vi ассоциировано некоторое количество товаров, ко-
торые должны быть доставлены соответствующему потребителю. Задача
маршрутизации состоит в определении такого множества маршрутов m с ми-
нимальной общей стоимостью, чтобы каждая вершина множества V была по-
сещена только одним автомобилем только один раз. Кроме того, все маршру-
ты должны начинаться и заканчиваться в депо (v0).
Решением задачи является:
- разбиение множества V на подмножества (маршруты);
- задание порядка обхода на каждом подмножестве (перестановка
вершин маршрута).
Решение является приемлемым (feasible), если все маршруты удовлетво-
ряют дополнительным ограничениям задачи.
Целевая функция – это стоимость решения задачи:
FVRP = ∑C(Ri), i = 1..m,
где C(Ri) – сумма длин ребер маршрута Ri.
А.Е. СКУКИС
Теорія оптимальних рішень. 2015
108
В классическом варианте требуется найти приемлемое решение с мини-
мальной стоимостью.
Варианты постановки задач маршрутизации. Наиболее исследованны-
ми вариантами задач маршрутизации являются [3, 4]:
- 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): существует возможность доза-
грузки автомобиля на маршруте.
Маршрутизация с ограничением по грузоподъемности (Capacitated
VRP, CVRP). В задачах данного типа вводится дополнительное ограничение:
объем грузов на каждом маршруте Ri не должен превышать заданной величи-
ны Q (одинаковый для всех машин).
Цель: минимизировать парк машин, необходимых для выполнения зада-
ния, а также общее время выполнения задачи.
Маршрутизация с ограничением по времени (VRP with Time Windows,
VRPTW). Данная задача подобна VRP с основным дополнительным услови-
ем: для выполнения запроса каждого клиента vi существует известный про-
межуток времени, определенный как интервал [ei, li] – намеченный горизонт
(scheduling horizon).
Цель: минимизировать количество машин, общие времена пути и ожида-
ния, необходимые для обработки запросов клиентов в назначенные интервалы
времени.
Ограничения: по сравнению с VRP, в задачах данного типа добавляются
следующие условия:
- решение неприемлемо, если клиент обслуживается после верхней
временной границы;
- машина, прибывшая ранее нижней временной границы, ожидает ее
наступления;
- как вариант, опоздание не влияет на пригодность решения, но добав-
ляет некоторое штрафное значение к целевой функции.
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В ТРАНСПОРТНОЙ ЛОГИСТИКЕ
Теорія оптимальних рішень. 2015 109
Получив решение VRPTW, кроме всего остального, имеется возможность
точнее подобрать время выезда транспорта из депо и тем самым избежать
бесполезных простоев.
Маршрутизация с несколькими депо (Multiple Depot VRP, MDVRP). В
наличии может быть несколько депо, которыми обслуживаются потребители.
В случае, если потребители сгруппированы вокруг каждого депо, задача
может быть разбита на несколько независимых. Однако, если потребители
и депо расположены в беспорядке, нужно искать решение для задачи маршру-
тизации с множественным депо (MDVRP).
Данная задача требует распределения потребителей по разным депо.
В каждом депо располагается парк транспорта. Каждая машина выезжает
из своего депо, обслуживает потребителей, прикрепленных к данному депо,
и затем возвращается обратно.
Цель: минимизировать парк транспорта и общее время пути.
Ограничения: каждый маршрут должен удовлетворять стандартным огра-
ничениям VRP, а также начинаться и заканчиваться в одном и том же депо.
Стоимость пути рассчитывается, как и в случае стандартной VRP.
Маршрутизация с возвратом товаров (VRP with Pick-Ups and Delive-
ries, VRPPD). Задача маршрутизации с возможностью возврата и доставки
товаров расширяет стандартную VRP тем, что требуется доставка некоторого
количества товаров назад от потребителей в депо. Таким образом, нужно быть
уверенным в том, что товары, которые вернет потребитель, не превысят вме-
стимость машины. Это ограничение делает планирование задачи более слож-
ным и может привести к непроизводительному использованию вместимости
транспорта, увеличению общего пути и количества единиц транспорта в депо.
Для простоты обычно рассматриваются задачи с дополнительными огра-
ничениями, например, когда все запросы на доставку товаров начинаются в
депо и все запросы на возврат товаров оканчиваются в депо, то есть, не про-
исходит обмен товарами между потребителями. Другой способ состоит в от-
мене ограничения, что все клиенты должны посещаться только один раз. Су-
ществует еще одно обычное упрощение – принять, что каждый автомобиль
сначала развозит все товары, прежде чем начать принимать товар от клиентов
(VRP with Backhauls, VRPB).
Цель: минимизировать парк транспорта и общее время движения.
Ограничения: количество товара, который нужно доставить потребителей
и товара, которые нужно забрать от потребителей в депо, не должно превы-
шать вместимость машины ни в одной точке маршрута.
Маршрутизация с возвратом товаров (VRP with Backhauls, VRPB).
Задачи маршрутизации с возвратом товаров (VRPB) – это расширение VRP,
в котором потребители могут как запросить, так и вернуть некоторые товары.
В задаче с доставкой и возвратом (VRPPD) необходимо принять во внимание,
что товары, которые вернут потребители, должны уместиться
в машине. Отличие от VRPPD состоит в том, что все товары должны быть до-
А.Е. СКУКИС
Теорія оптимальних рішень. 2015
110
ставлены, прежде чем произойдет любой возврат. Это требование происходит
из того факта, что все машины загружаются сзади и перестановка грузов не
является экономически выгодной и приемлемой. Количество товара, который
необходимо доставить и принять, фиксировано и известно заранее.
Цель: найти такой набор маршрутов, чтобы минимизировать общее прой-
денное расстояние.
Ограничения: возврат товаров происходит только после того, как завер-
шена доставка. Объем товаров при доставке и при возврате не должен превы-
шать грузоподъемности.
Постановка задачи. Задача формулируется аналогично задаче с достав-
кой и возвратом товаров (VRPPD).
Маршрутизация с различным транспортом (Split Delivery VRP,
SDVRP). Данная задача расширяет VRP, позволяя обслуживать одного клиен-
та различными видами транспорта, если это уменьшает общую стоимость за-
дачи. Этот случай типичен для ситуации, когда объем заказа сравним по ве-
личине с вместимостью машины. Как правило, для задачи маршрутизации
с различными видами транспорта получить оптимальное решение сложнее,
чем для классической задачи VRP.
Цель: минимизировать парк транспорта и общее время обслуживания всех
клиентов.
Ограничения: в отличие от классической VRP, в задачах SDVRP снимает-
ся ограничение на то, что клиент должен быть обслужен только одной маши-
ной. Кроме того, парк транспорта включает машины различной вместимости.
Задача SDVRP сводится к VRP разбиением каждого заказа на несколько
неделимых заказов.
Периодическая маршрутизация (Periodic VRP, PVRP). В классической
задаче VRP обычный период планирования – один день. В задачах с периоди-
ческой маршрутизацией VRP обобщается расширением периода планирования
до нескольких дней.
Цель: минимизировать парк транспорта и общее время обслуживания всех
клиентов.
Ограничения: те же, как и в классической VRP. Кроме того, машина
может вернуться в депо не в тот же день. По истечении M-дневного периода
каждый клиент должен быть посещен как минимум один раз.
Постановка задачи. Запросы каждого клиента должны быть выполнены
за один визит одним автомобилем. Если период планирования M = 1, задача
сводится к классической VRP. Каждый клиент в задаче с периодической
маршрутизацией должен быть посещен k раз, причем 1 ≤ k ≤ M. В классиче-
ском варианте PVRP, ежедневный заказ клиента всегда фиксированный. PVRP
можно рассматривать, как задачу компоновки группы маршрутов на каждый
день, причем, маршруты должны удовлетворять наложенным ограничениям и
общая стоимость задачи должна быть минимальна.
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В ТРАНСПОРТНОЙ ЛОГИСТИКЕ
Теорія оптимальних рішень. 2015 111
Маршрутизация со случайными данными (Stochastic VRP, SVRP).
В данном варианте VRP один или несколько компонентов задачи могут иметь
случайное поведение.
Случайные клиенты: каждый клиент существует с вероятностью p
и отсутствует с вероятностью p – 1.
Случайные запросы: запрос каждого клиента – случайная величина.
Случайные времена: времена поездок (расстояния между потребителями)
– случайные величины.
Решение SVRP происходит в два подхода. Первый этап дает решение без
учета случайных переменных. На втором этапе, когда становятся известными
случайные значения, происходит коррекция ранее полученного решения.
Цель: минимизировать парк транспорта и общее время обслуживания всех
клиентов.
Ограничения: когда некоторые данные неизвестны, становится невозмож-
ным выполнение всех ограничений для всех случайных переменных. Таким
образом, может требоваться выполнение некоторых условий с заданной веро-
ятностью, либо построение корректирующей модели, выполняющейся при
нарушении каких-либо ограничений.
Например, в задаче SVRP с возвратом товаров и ограничением по вме-
стимости, возможными способами коррекции будут следующие:
- вернуться в депо, когда машина заполнится, для разгрузки, затем про-
должить путь по маршруту;
- вернуться в депо, когда машина заполнится, и заново оптимизировать
оставшуюся часть пути;
- запланировать досрочный возврат в депо, даже если машина заполнена
не до конца. В данном случае, решение может зависеть от количества собран-
ного груза, и расстояния до депо. Машина может вернуться в депо, если из-
вестно, что груз следующего потребителя превысит вместимость автомобиля.
Маршрутизация с возможностью дозагрузки (VRP with Satellite
Facilities, VRPSF). Классическая задача VRP предполагает, что каждый
маршрут начинается и заканчивается в депо. Одной из причин возврата в депо
является ограниченная грузоподъемность. Когда машина развозит все товары,
она должна вернуться в депо за новой порцией товаров. Однако, в некоторых
случаях выгоднее произвести дозагрузку на маршруте, без возврата в депо, с
помощью дополнительных транспортных средств. Типичный случай, когда
множество потребителей ожидают регулярных поставок от одного централь-
ного поставщика.
Цель: минимизировать расходы на доставку товаров за определенный
срок (возможно, что учитывая расходы на вспомогательные машины, общая
стоимость решения задачи в краткосрочной перспективе будет выше, чем,
например, при решении классической задачи VRP).
Ограничения: товар на складе клиента не должен заканчиваться.
А.Е. СКУКИС
Теорія оптимальних рішень. 2015
112
Методы решения задач маршрутизации. Учитывая высокую вычисли-
тельную сложность задач маршрутизации точные алгоритмы не всегда дают
решение за приемлемое время при большом размере задачи. Поэтому для ре-
шения задачи разрабатывались эвристические и мета-эвристические методы.
На текущий момент предлагается следующая классификация методов реше-
ния задач маршрутизации [5 – 8].
Точные алгоритмы. Такой подход перебирает все возможные решения,
пока не будет найдено оптимальное. Наиболее известные алгоритмы этого
класса:
- метод ветвей и границ;
- метод ветвей и отсечений.
Эвристические методы. Производится относительно ограниченный поиск
по пространству решений, и обычно находятся хорошие решения за приемле-
мое время. В этом классе выделяют:
- конструктивные методы. Постепенно строят подходящее решение,
принимая во внимание получающуюся общую стоимость (механизм сбереже-
ний (Savings), метод, основанный на совпадениях (Matching Based), эвристики
улучшения многих маршрутов (Multi-route Improvement Heuristics));
- двухфазные алгоритмы. Задача разделяется на две части: организация
вершин в группы, и построение маршрута по каждой группе. алгоритм заме-
тания (sweep algorithm), алгоритм Фишера-Джекумера (Fisher and Jaikumar).
Мета-эвристические методы. Мета-эвристику создает вычислительная
схема, объединяющая два алгоритма. Один алгоритм главный, другой подчи-
ненный. В мета-эвристических методах упор делается на тщательном изуче-
нии наиболее перспективных частей пространства решений. Качество получа-
емых решений получается выше, чем у полученных классическими эвристи-
ками. Среди известных и наиболее применяемых мета-эвристик можно выде-
лить: генетические алгоритмы (Genetic Algorithms), алгоритмы муравьиной
колонии (Ant Algorithms), имитации отжига (Simulated Annealing), поиск с за-
претами (Tabu Search), программирование в ограничениях (Constraint
Programming).
Заключение. Проведенный обзор задач транспортной маршрутизации по-
казал существование множества вариантов их постановок. Эти задачи харак-
теризуются высокой вычислительной сложностью, так как относятся к классу
NP-сложных задач комбинаторной оптимизации. Следовательно, существует
необходимость в разработке и применении эвристических и мета-
эвристических алгоритмов решения задач транспортной оптимизации.
О.Є. Скукіс
ОПТИМІЗАЦІЙНІ ЗАДАЧІ В ТРАНСПОРТНІЙ ЛОГІСТИЦІ
Проведено огляд задач транспортної маршрутизації Vehicle Routing Problem (VRP). Розгля-
нуті найбільш досліджені варіанти постановки задач VRP. Приведено методи їх розв’язання.
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ В ТРАНСПОРТНОЙ ЛОГИСТИКЕ
Теорія оптимальних рішень. 2015 113
O.E. Skukis
OPTIMIZATION TASKS OF VEHICLE LOGISTICS
It was made an overview of routing traffic namely Vehicle Routing Problem (VRP). The most re-
searched options that define the stated tasks of VRP were considered in the article. The methods for
their solution were given.
1. Dantzig G. and Ramser J. The Truck Dispatching Problem. Management Science. – 1959. –
N 1(6). – P. 80 – 90.
2. Archetti C., Mansini R., Speranza M.G. Complexity and reducibility of the skip delivery prob-
lem. Transportation Science. – 2005. – N 39. – P. 182 – 187.
3. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part I: Transpor-
tations between customers and depot // Journal fur Betriebswirtschaft. – 2008. – N 58. –
P. 21 – 51.
4. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transpor-
tations between customers and depot // Journal fur Betriebswirtschaft. – 2008. – N 58. –
P. 81 – 117.
5. Toth P., Vigo D. Branch-and-bound algorithms for the capacitated VRP.
/ Toth P., Vigo, D. (Eds.) The Vehicle Routing Problem. SIAM Monographs on Discrete Math-
ematics and Applications // SIAM: Philadelphia. – 2002. – P. 29 – 51.
6. Lysgaard J., Letchford A.N., Eglese R.W. A New Branch-and-cut Algorithm for Capacitated
Vehicle Routing Problems // Math. Program., Springer Berlin/Heidelberg. – 2004. –
N 2(100). – P. 423 – 445.
7. Гуляницкий Л.Ф., Самусь А.В. Решение Н-методом задачи оптимизации маршрутов
транспортных средств с временными окнами // Компьютерная математика. – 2012. –
№ 2. – С. 147 – 155.
8. Cordeau J.-F., Laporte G., Mercier A. A unified tabu search heuristic for vehicle routing
problems with time windows // Journal of the Operational Research Society. – 2001. – N 8(52).
– P. 928 – 936.
Получено 09.03.2015
|
| id | nasplib_isofts_kiev_ua-123456789-112406 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:32:42Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скукис, А.Е. 2017-01-20T21:44:59Z 2017-01-20T21:44:59Z 2015 Оптимизационные задачи в транспортной логистике / А.Е. Скукис // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 106-113. — Бібліогр.: 8 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112406 519.21 Проведен обзор задач транспортной маршрутизации Vehicle Routing Problem (VRP). Рассмотрены наиболее исследованные варианты постановки задач VRP. Приведены методы их решения. Проведено огляд задач транспортної маршрутизації Vehicle Routing Problem (VRP). Розглянуті найбільш досліджені варіанти постановки задач VRP. Приведено методи їх розв’язання. It was made an overview of routing traffic namely Vehicle Routing Problem (VRP). The most researched options that define the stated tasks of VRP were considered in the article. The methods for their solution were given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Оптимизационные задачи в транспортной логистике Оптимізаційні задачі в транспортній логістиці Optimization tasks of vehicle logistics Article published earlier |
| spellingShingle | Оптимизационные задачи в транспортной логистике Скукис, А.Е. |
| title | Оптимизационные задачи в транспортной логистике |
| title_alt | Оптимізаційні задачі в транспортній логістиці Optimization tasks of vehicle logistics |
| title_full | Оптимизационные задачи в транспортной логистике |
| title_fullStr | Оптимизационные задачи в транспортной логистике |
| title_full_unstemmed | Оптимизационные задачи в транспортной логистике |
| title_short | Оптимизационные задачи в транспортной логистике |
| title_sort | оптимизационные задачи в транспортной логистике |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112406 |
| work_keys_str_mv | AT skukisae optimizacionnyezadačivtransportnoilogistike AT skukisae optimízacíinízadačívtransportníilogísticí AT skukisae optimizationtasksofvehiclelogistics |