Задача маршрутизации транспортных средств ( VRP ) - это комбинаторная задача оптимизации и целочисленного программирования, которая задает вопрос: «Каков оптимальный набор маршрутов для парка транспортных средств, который необходимо пересечь, чтобы доставить определенному набору клиентов?». Он обобщает известную задачу коммивояжера (TSP). Впервые он появился в статье Джорджа Данцига и Джона Рамсера в 1959 г. [1]в котором был написан первый алгоритмический подход и применен к поставкам бензина. Часто контекст заключается в доставке товаров, расположенных на центральном складе, клиентам, которые разместили заказы на такие товары. Цель VRP - минимизировать общую стоимость маршрута. В 1964 году Кларк и Райт усовершенствовали подход Данцига и Рамзера, используя эффективный жадный подход, названный алгоритмом экономии.
Определение оптимального решения VRP является NP-трудной , [2] , поэтому разрешение проблем , которые могут быть решены, оптимально, с использованием математического программирования или комбинаторной оптимизации может быть ограничено. Поэтому коммерческие решатели, как правило, используют эвристику из-за размера и частоты реальных VRP, которые им необходимо решать.
VRP имеет множество непосредственных применений в промышленности. Фактически, использование компьютерных программ оптимизации может дать компании 5% экономии [3], поскольку транспортировка обычно составляет значительную часть стоимости продукта (10%) [4] - действительно, транспортный сектор составляет 10%. % ВВП ЕС . Следовательно, любая экономия, созданная VRP, даже менее 5%, является значительной. [3]
Постановка проблемы
VRP касается услуг транспортной компании. Как вещи доставляются из одного или нескольких складов, которые имеют заданный набор домашних транспортных средств и управляются группой водителей, которые могут перемещаться по заданной дорожной сети к группе клиентов . Он просит определение набора маршрутов , S , (один маршрут для каждого транспортного средства , который должен начать и закончить на своем собственном складе) таким образом, чтобы требования всех клиентов и эксплуатационные ограничения удовлетворены и глобальные транспортные расходы сведены к минимуму. Эта стоимость может быть денежной, дистанционной или иной. [2]
Дорожную сеть можно описать с помощью графа, в котором дуги - это дороги, а вершины - соединения между ними. Дуги могут быть направленными или ненаправленными из-за возможного наличия улиц с односторонним движением или разной стоимости в каждом направлении. Каждая дуга имеет соответствующую стоимость, которая обычно представляет собой ее длину или время в пути, которые могут зависеть от типа транспортного средства. [2]
Чтобы узнать общую стоимость каждого маршрута, необходимо знать стоимость поездки и время в пути между каждым клиентом и станцией. Для этого наш исходный граф преобразуется в такой, в котором вершинами являются клиенты и депо, а дуги - дороги между ними. Стоимость каждой дуги - это наименьшая стоимость между двумя точками исходной дорожной сети. Это легко сделать, поскольку проблемы с кратчайшим путем относительно легко решить. Это преобразует разреженный исходный граф в полный граф . Для каждой пары вершин i и j существует дуга (i, j) полного графа, стоимость которой записывается каки определяется как стоимость кратчайшего пути от i до j . Время в пути- это сумма времени прохождения дуг кратчайшего пути от i до j на исходном графе дороги.
Иногда невозможно удовлетворить все требования клиента, и в таких случаях решатели могут уменьшить требования некоторых клиентов или оставить некоторых клиентов без обслуживания. Чтобы справиться с этими ситуациями, может быть введена приоритетная переменная для каждого клиента или связанные штрафы за частичное или отсутствие обслуживания для каждого данного клиента [2]
Целевая функция VRP может сильно различаться в зависимости от конкретного применения результата, но некоторые из наиболее общих целей: [2]
- Сведите к минимуму глобальные транспортные расходы на основе пройденного расстояния, а также фиксированных затрат, связанных с подержанными автомобилями и водителями.
- Сведите к минимуму количество транспортных средств, необходимых для обслуживания всех клиентов
- Наименьшее изменение времени в пути и загрузки автомобиля
- Минимизировать штрафы за некачественный сервис
- Максимизируйте собранную прибыль / счет.
Варианты VRP
Существует несколько разновидностей и специализаций задачи маршрутизации транспортных средств:
- Проблема маршрутизации транспортных средств с прибылью (VRPP): проблема максимизации, при которой необязательно посещать всех клиентов. Цель состоит в том, чтобы посетить один раз клиентов, максимизируя сумму собранной прибыли, соблюдая лимит времени транспортного средства. Транспортные средства должны начинать и заканчивать в депо. Среди наиболее известных и изученных VRPP мы приводим:
- Проблема с маршрутизацией транспортного средства при получении и доставке (VRPPD): необходимо переместить ряд товаров из определенных пунктов выдачи в другие места доставки. Цель состоит в том, чтобы найти оптимальные маршруты для парка транспортных средств, чтобы посетить места посадки и высадки.
- Проблема маршрутизации транспортных средств с LIFO : аналогична VRPPD, за исключением того, что на загрузку транспортных средств накладывается дополнительное ограничение: в любом месте доставки доставляемый предмет должен быть предметом, полученным последним. Эта схема сокращает время погрузки и разгрузки в местах доставки, потому что нет необходимости временно выгружать предметы, кроме тех, которые должны быть выброшены.
- Проблема маршрутизации транспортных средств с временными окнами (VRPTW): в местах доставки есть временные окна, в течение которых должны быть выполнены доставки (или посещения).
- Проблема маршрутизации емкостного транспортного средства: CVRP или CVRPTW. Транспортные средства имеют ограниченную грузоподъемность товаров, которые необходимо доставить.
- Проблема маршрута транспортного средства с несколькими поездками (VRPMT): Транспортные средства могут проехать более одного маршрута.
- Проблема с открытым транспортным средством (OVRP): Транспортные средства не обязаны возвращаться в депо.
- Проблема маршрутизации инвентаря (IRP): Транспортные средства несут ответственность за удовлетворение потребностей в каждой точке доставки [8]
- Задача маршрутизации для нескольких депо (MDVRP): существует несколько депо, с которых автомобили могут начинать и заканчивать. [9]
Некоторые поставщики программного обеспечения создали программные продукты для решения различных проблем VRP. Доступны многочисленные статьи с более подробной информацией об их исследованиях и результатах.
Хотя VRP связана с проблемой планирования работы цеха , эти две проблемы обычно решаются с использованием разных методов. [10]
Точные методы решения
Существует три основных подхода к моделированию VRP.
- Формулировки потока транспортных средств - здесь используются целочисленные переменные, связанные с каждой дугой, которые подсчитывают, сколько раз автомобиль пересекает границу. Обычно он используется для базовых VRP. Это хорошо для случаев, когда стоимость решения может быть выражена как сумма любых затрат, связанных с дугами. Однако его нельзя использовать для решения многих практических задач. [2]
- Формулировки товарных потоков - дополнительные целочисленные переменные связаны с дугами или ребрами, которые представляют поток товаров по путям, по которым проходят транспортные средства. Только недавно это было использовано для поиска точного решения. [2]
- Задайте задачу разделения - они имеют экспоненциальное количество двоичных переменных, каждая из которых связана с другой возможной схемой. Вместо этого VRP формулируется как задача разделения набора, в которой задается вопрос, какой набор каналов с минимальной стоимостью удовлетворяет ограничениям VRP. Это позволяет покрыть очень общие расходы по маршруту. [2]
Составы потока транспортных средств
Формулировка TSP, разработанная Данцигом, Фулкерсоном и Джонсоном, была расширена для создания двух формулировок индексного потока транспортных средств для VRP.
при условии
( 1 )
( 2 )
( 3 )
( 4 )
( 5 )
( 6 )
В этой формулировке представляет собой стоимость перехода от узла к узлу , это двоичная переменная, имеющая значение если дуга идет от к рассматривается как часть решения и иначе, количество доступных автомобилей и соответствует минимальному количеству автомобилей, необходимых для обслуживания комплекта . Мы также предполагаем, что - узел депо.
Ограничения 1 и 2 утверждают, что ровно одна дуга входит и ровно одна выходит из каждой вершины, связанной с заказчиком, соответственно. Ограничения 3 и 4 говорят о том, что количество автомобилей, выезжающих из депо, совпадает с количеством, которое входит в него. Ограничения 5 - это ограничения по сокращению пропускной способности, которые предполагают, что маршруты должны быть соединены и что спрос на каждом маршруте не должен превышать пропускную способность транспортного средства. Наконец, ограничения 6 являются ограничениями целостности. [2]
Одно произвольное ограничение среди ограничений фактически подразумевается оставшимися те, чтобы его можно было удалить. Каждый разрез определяется набором клиентов пересекает количество дуг не менее (минимальное количество транспортных средств, необходимое для обслуживания набора ). [2]
Альтернативная формулировка может быть получена путем преобразования ограничений сокращения пропускной способности в обобщенные ограничения исключения субтура (GSEC).
что предполагает, что по крайней мере дуги выходят из набора каждого покупателя . [2]
GCEC и CCC имеют экспоненциальное количество ограничений, поэтому решить линейную релаксацию практически невозможно. Возможный способ решить эту проблему - рассмотреть ограниченное подмножество этих ограничений и при необходимости добавить остальные.
Другой метод снова заключается в использовании семейства ограничений, которые имеют полиномиальную мощность, которые известны как ограничения MTZ, они были впервые предложены для TSP [11] и впоследствии расширены Кристофидесом, Мингоцци и Тотом. [12]
где - дополнительная непрерывная переменная, которая представляет нагрузку, оставшуюся в автомобиле после посещения клиента. а также спрос клиента . Это накладывает требования как к возможности подключения, так и к емкости. Когда ограничение тогда не является обязательным, поскольку а также тогда как они навязывают это .
Они широко использовались для моделирования базовой VRP (CVRP) и VRPB. Однако их возможности ограничиваются этими простыми задачами. Их можно использовать только тогда, когда стоимость решения может быть выражена как сумма затрат на дугу. Мы также не можем знать, какое транспортное средство движется по каждой дуге. Следовательно, мы не можем использовать это для более сложных моделей, где стоимость и / или осуществимость зависят от заказа клиентов или используемых транспортных средств. [2]
Оптимальная маршрутизация вручную или автоматически
Есть много способов решить проблемы с маршрутизацией автомобиля вручную. Например, оптимальная маршрутизация является большой проблемой для вилочных погрузчиков на больших складах. Некоторые из ручных методов выбора наиболее эффективного маршрута: наибольший зазор, S-образная форма, от прохода к проходу, комбинированный и комбинированный +. Хотя комбинированный + метод является наиболее сложным и, следовательно, трудным для использования операторами автопогрузчиков, он является наиболее эффективным методом маршрутизации. Тем не менее, процентная разница между методом оптимальной маршрутизации вручную и реальным оптимальным маршрутом составила в среднем 13%. [13] [14]
Метаэвристика
Из-за сложности решения до оптимальности крупномасштабных примеров проблем маршрутизации транспортных средств, значительные исследовательские усилия были посвящены метаэвристике, такой как генетические алгоритмы , поиск табу , имитация отжига и адаптивный поиск большого окружения (ALNS). Некоторые из самых последних и эффективных метаэвристик для проблем с маршрутизацией транспортных средств достигают решений в пределах 0,5% или 1% от оптимума для экземпляров проблем, насчитывающих сотни или тысячи точек доставки. [15] Эти методы также более надежны в том смысле, что их легче адаптировать для работы с различными побочными ограничениями. Таким образом, применение метаэвристических методов часто предпочтительнее для крупномасштабных приложений со сложными ограничениями и наборами решений.
Смотрите также
- Проблема китайского почтальона
- Проблема перепланирования автомобиля
- Маршрутизация дуги
Рекомендации
- ^ Данциг, Джордж Бернард; Рамзер, Джон Хуберт (октябрь 1959). «Проблема диспетчеризации грузовиков» (PDF) . Наука управления . 6 (1): 80–91. DOI : 10.1287 / mnsc.6.1.80 .
- ^ Б с д е е г ч я J K L Toth, P .; Виго, Д., ред. (2002). Проблема маршрутизации транспортных средств . Монографии по дискретной математике и приложениям. 9 . Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-579-2.
- ^ а б Гейр Хасле; Кнут-Андреас Ли; Эвальд Квак, ред. (2007). Геометрическое моделирование, численное моделирование и оптимизация :: Прикладная математика в SINTEF . Берлин: Springer Verlag. ISBN 978-3-540-68783-2.
- ^ Комтуа, Клод; Slack, Брайан; Родриг, Жан-Поль (2013). География транспортных систем (3-е изд.). Лондон: Routledge, Taylor & Francis Group. ISBN 978-0-415-82254-1.
- ^ Чао, И-Мин; Голден, Брюс Л; Васил, Эдвард А (1996). «Задача командного ориентирования». Европейский журнал операционных исследований . 88 (3): 464–474. DOI : 10.1016 / 0377-2217 (94) 00289-4 .
- ^ Archetti, C .; Sperenza, G .; Виго, Д. (2014). «Проблемы маршрутизации транспортных средств с прибылью»: 273–297. DOI : 10.1137 / 1.9781611973594.ch10 . Неизвестный параметр
|book-title=
игнорируется ( справка );Цитировать журнал требует|journal=
( помощь ) - ^ Хаммами, Фарук; Рекик, Моня; Коэльо, Леандро С. (2020). «Гибридная адаптивная эвристика поиска больших окрестностей для задачи командного ориентирования». Компьютеры и исследования операций . 123 : 105034. DOI : 10.1016 / j.cor.2020.105034 .
- ^ Экичи, Али; Озенер, Окан Орсан; Куйзу, Гюлтекин (ноябрь 2015 г.). «Циклические графики доставки для задачи маршрутизации инвентаря». Транспортная наука . 49 (4): 817–829. DOI : 10,1287 / trsc.2014.0538 .
- ^ Махмуд, Нафикс; Хак, штат Мэриленд, Мокаммель (февраль 2019 г.). Решение проблемы маршрутизации нескольких транспортных средств (MDVRP) с использованием генетического алгоритма . Международная конференция 2019 года по электротехнике, вычислительной технике и коммуникационной технике (ECCE). DOI : 10.1109 / ECACE.2019.8679429 .
- ^ Бек, JC; Проссер, П .; Селенский, Е. (2003). «Маршрутизация транспортных средств и планирование работы цеха: в чем разница?» (PDF) . Труды 13-й Международной конференции по планированию и календарному планированию искусственного интеллекта .
- ^ Миллер, CE; Такер, EW; Землин Р.А. (1960). "Формулировки целочисленного программирования и задачи коммивояжера". J. ACM . 7 : 326–329. DOI : 10.1145 / 321043.321046 . S2CID 2984845 .
- ^ Christofides, N .; Мингоцци, А .; Тот, П. (1979). Проблема маршрутизации транспортных средств . Чичестер, Великобритания: Wiley. С. 315–338.
- ^ «Почему так неэффективна оптимальная маршрутизация склада вручную?» . Locatible.com . 2016-09-26 . Проверено 26 сентября 2016 .
- ^ Рудберген, Кис Ян (2001). «Способы маршрутизации для складов с несколькими поперечными проходами» (PDF) . roodbergen.com . Проверено 26 сентября 2016 .
- ^ Видаль Т., Крейник Т.Г., Жендро М., Принс С. (2014). «Единая структура решения для задач маршрутизации с несколькими атрибутами». Европейский журнал операционных исследований . 234 (3): 658–673. DOI : 10.1016 / j.ejor.2013.09.045 .
дальнейшее чтение
- Oliveira, HCBde; Васконселос, GC (2008). «Гибридный метод поиска для задачи выбора маршрута транспорта с временными окнами». Анналы исследований операций . 180 : 125–144. DOI : 10.1007 / s10479-008-0487-у . S2CID 32406011 .
- Frazzoli, E .; Булло, Ф. (2004). «Децентрализованные алгоритмы маршрутизации транспортных средств в стохастической изменяющейся во времени среде». 2004 43-я конференция IEEE по принятию решений и контролю (CDC) . 43-я конференция IEEE по решениям и контролю, 14-17 декабря 2004 г., Нассау, Багамы. Труды ... IEEE Conference on Decision & Control . 4 . IEEE. DOI : 10.1109 / CDC.2004.1429220 . ISBN 0-7803-8682-5. ISSN 0191-2216 .
- Псарафтис, HN (1988). «Задачи динамического движения транспортных средств» (PDF) . Маршрутизация транспортных средств: методы и исследования . 16 : 223–248.
- Берцимас, диджей; Ван Ризин, Г. (1991). «Стохастическая и динамическая задача маршрутизации транспортных средств в евклидовой плоскости». Исследование операций . 39 (4): 601–615. DOI : 10.1287 / opre.39.4.601 . hdl : 1721,1 / 2353 . JSTOR 171167 .
- Видаль Т., Крейник Т.Г., Жендро М., Принс С. (2013). «Эвристика для задач маршрутизации с несколькими атрибутами: обзор и синтез». Европейский журнал операционных исследований . 231 (1): 1-21. DOI : 10.1016 / j.ejor.2013.02.053 .
- Хиротака, Ирие; Вонгпайсарнсин, Горагот; Терабе, Масаёши; Мики, Акира; Тагучи, Шиничиро (2019). «Квантовый отжиг задачи движения транспортных средств с учетом времени, состояния и мощности». arXiv : 1903.06322 [ квант-ф ].