Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

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

29 апреля 2011 года в 08:57   Просмотров: 11575

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

 

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

 


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


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

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

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


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

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


Решение является приемлемым (feasible), если все маршруты удовлетворяют дополнительным ограничениям задачи.


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

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


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


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


Разновидности VRP


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

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)


Данная задача подобна VRP с основным дополнительным условием: для выполнения запроса каждого клиента vi существует известный промежуток времени, определенный как интервал [ei,li] — намеченный горизонт (scheduling horizon).

 


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

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

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

 1) решение неприемлемо, если клиент обслуживается после верхней временной границы;

 2) машина, прибывшая ранее нижней временной границы, ожидает ее наступления;

 3) как вариант, опоздание не влияет на пригодность решения, но добавляет некоторое штрафное значение к целевой функции.


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


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


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


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

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

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

Стоимость пути рассчитывается, как и в случае стандартной VRP.


4. Маршрутизация с возвратом товаров (VRP with Pick-Ups and Deliveries, VRPPD)


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


Для простоты обычно рассматриваются задачи с дополнительными ограничениями, например, когда все запросы на доставку товаров начинаются в депо и все запросы на возврат товаров оканчиваются в депо, то есть, не происходит обмен товарами между потребителями. Другой способ состоит в отмене ограничения, что все клиенты должны посещаться только один раз. Существует еще одно обычное упрощение — принять, что каждый автомобиль сначала развозит все товары, прежде чем начать принимать товар от клиентов (VRP with Backhauls, VRPB).

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

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


5. Маршрутизация с возвратом товаров (VRP with Backhauls, VRPB)


Задачи маршрутизации с возвратом товаров (VRPB) являются расширением VRP, в котором потребители могут как запросить, так и вернуть некоторые товары. В задаче с доставкой и возвратом (VRPPD) необходимо принять во внимание, что товары, которые вернут потребители, должны уместиться в машине. Отличие от VRPPD состоит в том, что все товары должны быть доставлены, прежде чем произойдет любой возврат. Это требование происходит из того факта, что все машины загружаются сзади и перестановка грузов не является экономически выгодной и приемлемой. Количество товара, который необходимо доставить и принять, фиксировано и известно заранее.

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

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

Постановка задачи: Задача формулируется аналогично задаче с доставкой и возвратом товаров (VRPPD).


6. Маршрутизация с различным транспортом (Split Delivery VRP, SDVRP)


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

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

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

Задача SDVRP сводится к VRP разбиением каждого заказа на несколько неделимых заказов.


7. Периодическая маршрутизация (Periodic VRP, PVRP)


В классической задаче VRP обычный период планирования — один день. В задачах с периодической маршрутизацией VRP обобщается расширением периода планирования до нескольких дней.


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

Ограничения: те же, как и в классической VRP. Кроме того, машина может вернуться в депо не в тот же день. По истечении M-дневного периода каждый клиент должен быть посещен как минимум один раз.

Постановка задачи: запросы каждого клиента должны быть выполнены за один визит одним автомобилем. Если период планирования M=1, задача сводится к классической VRP. Каждый клиент в задаче с периодической маршрутизацией должен быть посещен k раз, причем 1 ≤ k ≤ M. В классическом варианте PVRP, ежедневный заказ клиента всегда фиксированный. PVRP можно рассматривать, как задачу компоновки группы маршрутов на каждый день, причем, маршруты должны удовлетворять наложенным ограничениям и общая стоимость задачи должна быть минимальна.


8. Маршрутизация со случайными данными (Stochastic VRP, SVRP)


В данном варианте VRP один или несколько компонентов задачи могут иметь случайное поведение.
Случайные клиенты: каждый клиент существует с вероятностью p и отсутствует с вероятностью p-1.
Случайные запросы: запрос каждого клиента — случайная величина.
Случайные времена: времена поездок (расстояния между потребителями) — случайные величины.

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

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

 



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

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

 1) вернуться в депо, когда машина заполнится, с целью разгрузиться, затем продолжить путь по маршруту;

 2) вернуться в депо, когда машина заполнится, и заново оптимизировать оставшуюся часть пути;

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


9. Маршрутизация с возможностью дозагрузки (VRP with Satellite Facilities, VRPSF)


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

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

Ограничения: товар на складе клиента не должен заканчиваться.

Постановка задачи: задача маршрутизации с возможностью дозагрузки является составной частью задачи распределения товара (IRP, Inventory Routing Problem), в связи с чем полное описание задачи выходит за рамки данной статьи.


Способы решения задач маршрутизации


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


Предлагается следующая классификация методов решения.

Точные подходы

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

Метод ветвей и границ (Branch and bound, Fisher, 1994)

Метод ветвей с отсечением (Branch and cut)

Эвристические методы

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

Конструктивные методы

Постепенно строят подходящее решение, принимая во внимание получающуюся общую стоимость.

Механизм сбережений (Savings, Clark and Wright, 1964)

Метод, основанный на совпадениях (Matching Based)

Эвристики улучшения многих маршрутов (Multi-route Improvement Heuristics)

Двухфазный алгоритм

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

Fisher and Jaikumar (1981)

The Petal Algorithm

The Sweep Algorithm

Taillard (1993)

Мета-эвристики

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

Ant Algorithms

Constraint Programming

Deterministic Annealing

Genetic Algorithms

Simulated Annealing

Tabu Search

Granular Tabu

The adaptative memory procedure

Kelly and Xu (1999)

Источники

The VRP Web (http://neo.lcc.uma.es/radi-aeb/WebVRP/)

Vehicle Routing Problems (http://www.idsia.ch/~monaldo/vrp.html)

Vehicle Routing Tutor (http://www2.isye.gatech.edu/logisticstutorial/vehicle/vrtutor.htm)

Vehicle Routing and Travelling Salesperson Problems (http://www.sintef.no/static/am/opti/projects/top/vrp/index.html)


Дмитрий Трофимов, Анатолий Федуков

http://rain.ifmo.ru/cat/view.php/theory/unsorted/vrp-2006
По материалам http://www.lobanov-logist.ru

См. также: 

http://lmatrix.ru/post/18/99/Vehicle-routing-problem.html 

8 комментариев

#4149
Мебель каталог (гость) пишет:
19:17 6 июля 2017 года
Детская комната - самая светлая и добрая комната в квартире. В ней проводят много времени наши любимые малыши, поэтому от того, какой она будет, зависит их настроение, здоровье и правильное развитие.
Мебель для детской комнаты выбирают тщательно и продуманно. Сначала нужно определиться, какие элементы интерьера будут находиться в комнате. Конечно, первое, что нужно приобрести - это кровать. Она должна быть рассчитана на то, что малыш будет расти, поэтому ее выбирают с запасом по росту. Для самых маленьких кровать должна иметь ограничители, чтобы во сне малыши не упали на пол. Впоследствии их можно будет убрать. Если комната предназначена для двоих детей, можно поставить двухъярусную кровать: это сэкономит место. Дети с удовольствием спят на двухэтажных кроватях, устраивают на них игры и придумывают новые развлечения. Очень хорошо, если под кроватью будут расположены ящики, в них можно складывать игрушки, одежду или другие вещи. Важно, чтобы на кровати и другой мебели не было острых углов, производители заботятся об этом, выпуская детскую мебель с закругленными углами.
При покупке мебели в детскую комнату у продавца нужно требовать сертификат качества, чтобы быть уверенным в экологической безопасности мебели.


http://pronews24.ru/


<a href=http://lnkgo.com/5tl8>Click Here</a>
#3921
Rogerner (гость) пишет:
09:44 22 июня 2017 года
https://www.adworkmedia.com/go.php?camp=18223&pub=55498&id=38074&sid=
YouWin - MACHINE A PETS - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18224&pub=55498&id=38076&sid=
YouWin - LAMPE TORCHE - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18225&pub=55498&id=38078&sid=
YouWin - Game of Thrones - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18226&pub=55498&id=38080&sid=
YouWin - Doodle Jump - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18227&pub=55498&id=38082&sid=
YouWin - Don't Touch the White Tile - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18228&pub=55498&id=38084&sid=
YouWin - Bruno Mars - 24K Magic - PIN (FR)

https://www.adworkmedia.com/go.php?camp=18338&pub=55498&id=38304&sid=
Mobbyo - FlappyBird - PIN (CH)

https://www.adworkmedia.com/go.php?camp=18345&pub=55498&id=38318&sid=
Yurmobile - Cut the Rope - PIN (LU)

https://www.adworkmedia.com/go.php?camp=18543&pub=55498&id=38714&sid=
Movingos - Download Best Content V2 - PIN (LU)

https://www.adworkmedia.com/go.php?camp=18564&pub=55498&id=38756&sid=
Smsquest - Mario Game - PIN (AU)
#3728
DerekNeusa (гость) пишет:
12:03 11 июня 2017 года
Отзывы специалистов. Антонов К. Т. уролог, . Отзывы покупателей. Операции, таблетки . Biomanix капсулы для потенции. Большинство женщин . biomanix29.moykrest.ru
#3710
DerekNeusa (гость) пишет:
16:42 10 июня 2017 года
Трендтовар обзоры и отзывы. Обзоры трендовых товаров. Главная О нас Как заказать? Условия доставки и оплаты Возврат и обмен Адалт Для . biomanix5.moykrest.ru
#3691
Thomasfek (гость) пишет:
19:23 9 июня 2017 года
Tinedol – эффективное средство от грибка стопы, неприятного запаха и зуда.
Перейти на сайт: http://tinedol.1stbest.info/
#3689
ClintonRoone (гость) пишет:
16:20 9 июня 2017 года
Спосіб застосування та дози.
Грибок стопы очень неприятное заболевание Мало того, что стопа неприятно пахнет и зудит, так еще ногу приходилось прятать под носками, чтобы никто не видел этого кошмара Но я приобрел крем Tinedol и буквально после третьего использования заметил, что грибок стал меньше, а со времени и вовсе пропал Теперь вот всем его рекомендую, у кого похожая проблема.
Мужики Я пробовал много чего, но м16 реально помог Все.
Эмульсионный воск Используется в косметологии, уменьшает жирность мази.
В Киргизии 1410 сом.
Сахарный диабет Diatrivitin для понижения сахара в крови.
Сегодня все современные люди привыкли заботиться о здоровье своих ног, и для этих целей существует огромное количество разнообразных кремов, масел и других косметических средств Однако правильный уход не всегда может гарантировать абсолютную защиту от появления грибка стопы Инновационный крем-мазь Тинедол создан не только для эффективного профилактического ухода за кожей стоп, но и способен в кратчайшее время избавить от такого неприятного заболевания, как грибок.
Сомнения были Во-первых, я боялась, что в состав будут входить элементы, вызывающие аллергию Во-вторых, сейчас очень много подделок разных товаров и эта мазь не исключение Однако по мере того, как я собирала информацию, укреплялось мнение о том, что эту мазь нужно купить.
Комплекс полезных компонентов, входящих в состав этого лекарственного средства, не вызывают побочных эффектов Крем Tinedol от грибка восстановит кожу ног, вернет им прежнюю прелесть и избавит от неприятных ощущений Этот необыкновенный препарат можно приобрести в любое время дня и ночи на официальном сайте.
Почему лекарство Tinedol лучше стандартных противогрибковых кремов.


Официальный сайт: http://tinedol.hceap.info/tinedol-ot-gribka-nogtei-otzyvy.html - тинедол от грибка ногтей отзывы
#3019
Emiliohax (гость) пишет:
02:37 30 апреля 2017 года
Вкуснейший экзотический плод - мангустин, стал настоящим открытием в диетологии!
Он содержит РЕКОРДНОЕ количество полезных веществ, стимулирующих активное жиросжигание и снижающих вес!
Сироп мангустина растопит до 10 кг жира за 2 недели!
Спаситесь от ожирения и сократите риск инфаркта, диабета и гипертонии на 89%.
Перейти на сайт: http://mangystin.bxox.info/
#56
Caroline (гость) пишет:
07:33 10 марта 2014 года
So sorry you can pass up the workshop!
Caroline http://ultimateheightincrease1.beeplog.com/

Оставить комментарий

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

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта