Маршрутизация дуги

маршрутизации дуг Проблемы (ARP) — это категория общих проблем маршрутизации (GRP), которая также включает проблемы маршрутизации узлов (NRP). Целью ARP и NRP является перемещение по ребрам и узлам графа соответственно. Цель задач дуговой маршрутизации заключается в минимизации общего расстояния и времени, что часто предполагает минимизацию времени тупика , времени, необходимого для достижения пункта назначения. Проблемы с прокладкой дуги могут применяться при сборе мусора , школьного автобуса планировании маршрута , доставке посылок и газет, борьбе с обледенением и уборке снега с помощью транспортных средств зимнего обслуживания , которые посыпают солью , дорогу доставка почты , обслуживание сети, подметание улиц , патрулирование полицией и охраной, и уборка снега . Задачи трассировки дуг являются NP-сложными , в отличие от задач проверки трассы , которые можно решить за полиномиальное время .

В качестве реального примера решения проблемы маршрутизации дуг Кристина Р. Дельгадо Серна и Хоакин Пачеко Бонростро применили аппроксимационные алгоритмы, чтобы найти лучшие маршруты школьных автобусов в системе средних школ испанской провинции Бургос . Исследователи свели к минимуму количество маршрутов, первое прохождение которых занимало более 60 минут. Они также минимизировали продолжительность самого длинного маршрута с фиксированным максимальным количеством транспортных средств.

Существуют обобщения задач дуговой маршрутизации, в которых участвуют несколько почтальонов, например, задача k китайского почтальона (KCPP).

Предыстория

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

Основа

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

Проблема с китайским почтальоном

Задача китайского почтальона (CPP) направлена ​​на поиск минимальной длины цикла для одного почтальона. CPP требует, чтобы все ребра были пройдены один раз, задача сельского почтальона (RPP) требует прохождения подмножества ребер с циклом минимальной длины.

Проблемы с маршрутом транспортного средства/VRP

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

сельского

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

Алгоритмы

Поиск эффективного решения с большими объемами данных проблемы китайского почтальона (CPP), проблемы ветреного почтальона (WPP), проблемы сельского почтальона (RPP), проблемы k -китайского почтальона (KCPP), смешанной задачи китайского почтальона (MCPP) ), Задача направленного китайского почтальона (DCPP), Задача вспашки под гору (DPP), Задача вспашки с приоритетом (PPP), Задача ветреного сельского почтальона (WRPP) и Ветреная общая задача маршрутизации (WGRP) требуют использования продуманных математических концепций, включая эвристические методы оптимизации , методы ветвей и границ. методы , целочисленное линейное программирование и приложения алгоритмов задачи коммивояжера, такие как алгоритм Хелда-Карпа, улучшают $O(n!)$ к $O(2^{n}n^{2})$. В дополнение к этим алгоритмам, эти классы задач также могут быть решены с помощью алгоритма секущей плоскости , выпуклой оптимизации , выпуклых оболочек , множителей Лагранжа и других методов динамического программирования . В случаях, когда запустить алгоритм Хелда – Карпа невозможно из-за его высокой вычислительной сложности, подобные алгоритмы можно использовать для аппроксимации решения за разумное время.

Эйлеровы схемы

Самым ранним документально подтвержденным упоминанием проблемы маршрутизации дуг является классическая задача Кенигсберга по мостам , которую Эйлер доказал невозможным. Житель Кенигсберга , ныне являющегося частью Калининграда , хотел найти способ пересечь все семь мостов через реку Прегель , не возвращаясь и не возвращаясь по своим следам, то есть пересекая каждый мост один и только один раз. В 1736 году Эйлер свел проблему к вопросу об узлах и ребрах и показал, что проблема невозможна. В 1873 году Гирхольцер проделал дополнительную работу по вопросу о замкнутых цепях.

Работа над эйлеровыми схемами была популяризирована журналом Scientific American 1 июля 1953 года. Эту работу продолжил Мейгу Гуан, также известный как Кван Мей-Ко, из Шантунского педагогического колледжа. Мэйгу Гуань интересовал другой вопрос, а не определение замкнутой цепи. Гуань пытался найти путь минимальной длины, который пересекал бы каждое ребро графа хотя бы один раз. Гуань описал свою цель в 1962 году: «Почтальон должен пройти назначенный ему отрезок пути, прежде чем вернуться на почту. Проблема в том, чтобы найти для почтальона кратчайшее расстояние ходьбы».

Типы проблем

Задачи маршрутизации дуг (ARP) различаются по своей цели и эвристике. Однако все они, как известно, NP-трудны .

сельского

Эта задача названа в честь почтальона и его задачи доставить почту в любом порядке, который он выберет, но при этом минимизируя его затраты, такие как время или расстояние в пути. Ее также иногда называют проблемой ненаправленного китайского почтальона . Задача ненаправленного сельского почтальона (URPP) направлена ​​на минимизацию общей стоимости маршрута, отображающего всю сеть, или, в более конкретных случаях, маршрута, отображающего каждое ребро, требующее услуги. Если необходимо нанести на карту всю сеть, маршрут, картирующий всю сеть, называется покрывающим туром . В случае, когда необходимо отобразить только определенные ребра, задача состоит в том, чтобы решить маршрут, оптимизирующий требования, переходя на необязательные маршруты минимальное количество раз.

Проблема с ненаправленной прокладкой емкостной дуги

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

История

доказали, что она является NP-сложной задачей URPP была впервые представлена ​​в 1974 году и Ленстра и Кан . UCARP может быть получен из URPP и, следовательно, также является NP-сложным. В 1981 году другой паре ученых-компьютерщиков, Голдену и Вонгу, удалось доказать, что даже получение приближения 0,5 к URPP было NP-трудным. В 2000 году Дрор опубликовал книгу, описывающую различные проблемы трассировки дуг.

Проблема с ветреным почтальоном и варианты

Задача ветреного почтальона, предложенная Миниекой, представляет собой вариант задачи проверки маршрута, в которой входными данными является неориентированный граф, но где каждое ребро может иметь разную стоимость прохождения его в одном направлении и стоимость прохождения в другом направлении. В отличие от решений для ориентированных и неориентированных графов оно NP-полное . Стоимость поездки в одном направлении выше, когда ветер дует вам в лицо, чем когда ветер дует вам в спину, и отсюда и возникла проблема с названием «Ветреный почтальон». Работа, необходимая для пересечения улицы в одном направлении, отличается от работы, необходимой для пересечения улицы в другом направлении в ветреный день.

Задача ветреного почтальона — это задача дуговой маршрутизации (ARP), которая в качестве частного случая содержит смешанную китайскую задачу почтальона MCPP.

Задачу можно сформулировать следующим образом: «Дана неориентированный и связный граф G=(V,E) с двумя неотрицательными стоимостями $c_{i,j}$ и $c_{j,i}$ связанный с каждым ребром $\{i,j\}\in E$ соответствующий стоимости прохождения от i до j и от j до i соответственно, WPP должен найти обход с минимальной стоимостью на G, пересекающий каждое ребро хотя бы один раз». Эту проблему предложил Миниека. WPP в целом является NP-полной и может быть решена за полиномиальное время, если G эйлеров, если стоимость двух противоположных ориентаций каждого цикла в G одинакова или если G является последовательно-параллельным графом. Задача ветреного сельского почтальона (WRPP) — это обобщение WPP, в котором необходимо пройти не все ребра графа, а только те, которые входят в заданное подмножество требуемых ребер. Например, почтальону не обязательно пересекать некоторые сельские дороги, а подъем по некоторым дорогам на крутых холмах занимает больше времени, чем спуск.

Задача ветреного сельского почтальона (WRPP) — это обобщение WPP, в котором необходимо пройти не все ребра графа, а только те, которые входят в заданное подмножество требуемых ребер. Например, почтальону не обязательно пересекать некоторые сельские дороги, а подъем по некоторым дорогам на крутых холмах занимает больше времени, чем спуск. Рассмотрим неориентированный граф $G=\{E,V\}$ с двумя затратами $c_{ij}$ и $c_{ji}$ связанный со стоимостью пересечения края $(i,j)$ начиная с i и j соответственно. G — ветреный граф, и нас интересует подмножество ребер или математические символы, $E_{R}\subseteq E$.

Если WRPP включает дополнительное ограничение, согласно которому необходимо посетить определенный набор вершин: $V_{R}\subseteq V$, проблема превращается в проблему общей маршрутизации Windy (WGRP). Бенавент предложил формулировку целочисленного линейного программирования, а также различные эвристики и нижние оценки для WRPP.

Бенавент и др. опубликовали оценку нескольких эвристических методов, используемых для решения WRPP за несколько секунд с отклонением не более 1% от нижней границы на графиках среднего размера. Они улучшили эту ситуацию с помощью алгоритма Scatter Search, который уменьшил разницу до 0,5%. Scatter Search обнаружил решения, которые отклонялись менее чем на 2% при реализации в сетях с сотнями узлов и тысячами ребер.

В реальных приложениях существует несколько транспортных средств, которые могут двигаться, что приводит к обобщению, названному «Задача ветреного сельского почтальона Min-Max K-транспортных средств» (MM K-WRPP). Задача мин-максного K-транспорта о ветреном сельском почтальоне (MM K-WRPP) определяется следующим образом: Учитывая ветреный граф $G=\{V,E\}$, выделенная вершина, $1\in V$, представляющий депо, подмножество требуемых ребер $E_{R}\subseteq E$и фиксированном количестве K транспортных средств, MM K-WRPP состоит из поиска набора K рейсов для транспортных средств таким образом, чтобы каждый обход начинался и заканчивался в депо, а каждое требуемое ребро обслуживалось ровно одним транспортным средством. Цель состоит в том, чтобы минимизировать продолжительность самого длинного маршрута, чтобы найти набор сбалансированных маршрутов для транспортных средств. Некоторыми реальными применениями задач маршрутизации с целями мин-макс являются маршрутизация школьных автобусов (Дельгадо и Пачеко, 2001), доставка газет клиентам (Эпплгейт и др., 2002) и сбор мусора (Лакомм и др., 2004).

Лучший алгоритм MM K_WRPP был очень близок к минимальному решению с 2 и 3 автомобилями, в среднем менее 0,4%. Разрыв увеличивается примерно до 1,00% и 1,60% при 4 и 5 автомобилях.

По мнению Дюссо и др. и Бенавента и др., метаэвристический многокритериальный алгоритм моделирования отжига (MOSA) может решить различные ограничения, налагаемые на WRPP. WRPP — это важная задача дуговой маршрутизации, которая обобщает многие проблемы дуговой маршрутизации для одного транспортного средства. В реальных приложениях математики предпочтительнее решение, которое минимизирует общие затраты на маршрут всех транспортных средств и продолжительность самого длинного маршрута. Трудно находиться в месте, где ваша посылка всегда опаздывает на несколько часов. Нам следует начать с предположения, что несколько транспортных средств с определенной измеримой способностью обслуживать клиентов более реалистичны, чем одно транспортное средство с неизмеримой бесконечной мощностью. Раббани и др. коллеги измерили производительность алгоритмов и моделей MOSA, используя многоцелевую разработку поиска Cuckoo, разработанную Янгом и др. также называется «Многоцелевой поиск с кукушкой» и сокращенно MOCS. Они пришли к выводу, что методы MOSA более эффективны, чем методы MOCS. В будущем могут быть исследованы сравнения с другими метаэвристическими методами, включая генетический алгоритм сортировки без доминирования (NSGA-), многокритериальный алгоритм оптимизации роя частиц (MOPSO) и многокритериальный империалистический конкурентный алгоритм.

В модели «Задачи ветреного почтальона» (WPP) стоимость движения в одном направлении отличается от стоимости движения в другом направлении. Например, если на улице дует ветер, то чтобы идти против ветра, требуется больше времени и энергии, чем против ветра. Другой пример WPP: стоимость вспашки вверх по склону превышает стоимость вспашки вниз. Это моделируется вариантом, изученным Дюссо и др., «Проблема вспашки под гору» (DPP).

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

Приложения

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

Снегоочистители

Зимой часто возникает вопрос: какой набор маршрутов имеет наименьшую (минимальную) максимальную длину маршрута? Обычно это оценивается как проблема трассировки дуги с графом. Время, необходимое для проезда по улице, известное как «мертвое время», меньше, чем время, необходимое для уборки снега с улиц (или доставки почты или сдачи посылок). Еще одним аспектом, который необходимо учитывать при применении дуговой трассировки для уборки снега, является тот факт, что на крутых улицах либо трудно, либо невозможно двигаться в гору. Целью является маршрут, который позволяет избежать подъема по крутым улицам и быстрее завершить работу за счет максимального увеличения времени простоя для определения местоположения. Это было смоделировано с помощью эвристического алгоритма, который аппроксимирует нижнюю оценку Дюссо, Голдена и Василя. Это проблема спускового плуга (DPP). Снежные команды предпочитают пахать под гору и спускаться в гору. Эта проблема предполагает, что условия настолько суровы, что улицы закрыты и движение транспорта отсутствует.

Задача о вспашке на спуске игнорирует задачу о вспашке с приоритетом (PPP), которая построена на разумном предположении, что если снег слишком глубокий, снегоочиститель не сможет направиться на невспаханную улицу. DPP исходит из предположения, что уровень снега достаточно низкий, поэтому нерасчищенные улицы могут быть забиты, но снег достаточно глубокий, чтобы на нем не было движения. Если на дорогах имеется движение транспорта, предположение о невозможности пахать в гору уже не может быть выполнено. Моделирование DPP застревает на невспаханной улице примерно в 5% случаев, что является темой будущих исследований теории графов и трассировки дуг.

Рассматривая неориентированный граф $G=\{V,A\}$ где $V$ представляет собой набор вершин и узлов и $A$ представляет собой набор дуг. Каждая дуга представлена $(v_{i},v_{j})$ имеет четыре стоимости: $c_{ij}^{+}$, определяемый как стоимость вспашки из $v_{i}$ к $v_{j}$, $c_{ji}^{+}$, стоимость вспашки из $v_{j}$ к $v_{i}$, $c_{ij}^{-}$, стоимость тупика от $v_{i}$ к $v_{j}$, и $c_{ji}^{-}$, стоимость тупика от $v_{j}$ к $v_{i}$. Установка предполагает, что $v_{j}$ имеет более высокую высоту $v_{i}$, что приводит к утверждению: $c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}$. На практике время вспашки на спуске в два раза эффективнее, чем на вспашке с подъема, а обработка вертикальных полос в два раза эффективнее, чем на вспашке. Алгоритм находит $k$ каждый маршрут будет начинаться и заканчиваться в депо $v_{0}$, вспахните дугу два раза, потому что для вспахивания левой и правой стороны улицы требуется два прохода.

Лучшим решением будет минимизация максимальной длины маршрута. Дюссо, Голден и Василь нашли алгоритм, который не превысил нижнюю границу на 5,5% в более чем 80 тестовых запусках. Отклонение увеличивалось по мере увеличения сложности модели, поскольку по мере роста модели появляется больше неоптимизированных приближений, чем оптимизированных. Улучшение Dussault et. Алгоритм Ала DPP может иметь штрафы за развороты и повороты налево или за движение прямо через перекресток, что требует дополнительного времени и забрасывает снег в середину перекрестка соответственно. (см. задачу «Направленная задача сельского почтальона со штрафами за поворот», часто называемую ниже DRPP-TP).

k - Проблема китайского почтальона ( k -CPP)

- китайский k почтальон можно сформулировать следующим образом: «дан связный взвешенный по ребрам граф G и целые числа p и k , решить, существует ли по крайней мере k замкнутых обходов таких, что каждое ребро G содержится хотя бы в одном из них и суммарный вес ребер в обходах не превосходит p ?" Процесс получения решения k -CPP является NP-полным. Гутин, Мучачча и Йео доказали в 2013 году, что k -CPP поддается управлению с фиксированными параметрами. Авторы доказывают, что k -CPP допускает ядро ​​с $O(k^{2}\log(k))$ вершин, а ориентированная версия k -CPP является NP-полной.

сельского почтальона (ЗПП)

Задача сельского почтальона (RPP) делает некоторые маршруты обязательными и абсолютными, но человек, пересекающий граф, не обязан идти в одном конкретном направлении. RPP является NP-трудным и полным, точно так же, как kCPP, DPP, PPP являются NP-жесткими. Беневант изучил обобщение этой задачи, названной «Направленная задача сельского почтальона со штрафами за поворот» (DRPP-TP). Алгоритм Беневанта аппроксимировал решение, превратив DRPP-TP в асимметричную задачу коммивояжера (ATSP).

Эвристика и алгоритмы

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

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

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

Сложность

Это список вычислительных сложностей для различных задач трассировки дуг.

вариант CP	Классическая сложность	Приближение	Параметризованная сложность
Ненаправленный	$O(|V|^{3})$-временной алгоритм
Режиссер	$O(|V|^{3})$-временной алгоритм $O((|E|-|V|)|V|^{2})$-временной алгоритм
Смешанный	NP-полный $O(|V|^{3})$-разрешимо по времени, если каждая вершина имеет четную степень	$O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})$-временной коэффициент 3/2	$O(2^{|E|}\cdot |V|^{3})$-временной алгоритм В FPT относительно |A| В XP относительно ширины дерева
Ветрено	NP-полный P в некоторых особых случаях	Фактор 3/2
k-иерархический	NP-полный $O(k|V|^{4})$-разрешимо по времени, если отношение предшествования линейное
Минимальная сумма k почтальонов	$O(|V|^{3})$-временной алгоритм с вершиной почтового отделения, в противном случае NP-полный		В FPT относительно k без вершины почтового отделения
Мин-макс k почтальонов	NP-полный	$O(|V|^{3})$-временной коэффициент (2-1/к)

Список вариантов трассировки дуг

Проблема	Аббревиатура	Описание	Примечания к выходу	Примеры
Проблема с трассировкой дуги	АРП	Определите обход с наименьшей стоимостью заданного подмножества дуг графа с ограничениями или без них.		Семь мостов Кенигсберга
Проблема китайского почтальона	CPP	неориентированный граф G с вершинами V и взвешенными ребрами E	Пройдите каждое ребро хотя бы один раз с минимальными затратами.	«Почтальон должен пройти назначенный ему отрезок пути, прежде чем вернуться на почту. Проблема в том, чтобы найти для почтальона кратчайшее расстояние ходьбы».
Проблема сельского почтальона	план урока	неориентированный граф G с вершинами V и взвешенными ребрами E	Пройдите подмножество ребер E хотя бы один раз с минимальной стоимостью.
Задача о сельском почтальоне	ДРПП
Проблема сельского почтальона со штрафами за поворот	РПП-ТП, РППТП
Проблема ветреного почтальона	ВЭС
Проблема ветреного сельского почтальона	ВРПП
Проблема с дворником	СЭС
m-Проблема вспашки	м-ПП
Проблема с емкостным плугом	С-ПП
Проблема с плугом на спуске	ДПП
Задача с плугом на спуске со штрафами за поворот	ДПП-ТП
Проблема с сельским плугом на спуске со штрафами за поворот	РДПП-ТП
Проблема с прокладкой емкостной дуги	КАРП
k-Plow Задача ветреного сельского почтальона	к-WRPP
Задача Min-Max с плугом для спуска с несколькими плугами	ММ к-ДПП
Мин-макс. Задача про ветреного сельского почтальона	ММ к-ВРПП
Вспашка с проблемой приоритета	ГЧП
Задача с удлиненным плугом при спуске с мин-макс.	ММ к-ДППЭ
Проблема с китайским почтальоном	ПГУ
Задача о китайском почтальоне	ДЦПП
Задача о сельском почтальоне	ДРПП
Проблема прокладки расширенной емкостной дуги	РЭКАРП
Иерархическая задача китайского почтальона	HCPP
Проблема прокладки смешанной емкостной дуги	МКАРП
Смешанная задача китайского почтальона	МКПП
Проблема с краном-штабелером	SCP	Определенные дуги должны быть пройдены хотя бы один раз в одном направлении, но могут быть пройдены столько же раз в другом направлении.
Задача коммивояжера	ТСП
Проблема ненаправленной прокладки емкостной дуги	УКАРП
Ненаправленная задача сельского почтальона	УРПП
Проблема с маршрутом транспортного средства	ВРП
Задача сельского почтальона с несколькими депо (мин-макс)	МММДРПП
Обобщенная задача выбора маршрута транспортных средств	ГВРП

Внешние ссылки

• Страница поиска проблем с маршрутизацией дуги в Ланкастерском университете
• Тенденции в дуговой маршрутизации

См. также

• Проблема с китайским почтальоном
• Проблема с маршрутом автомобиля
• Задача коммивояжера
• Эйлеров путь
• Проблема с трассировкой емкостной дуги
• Список задач теории графов
• Проблема с маршрутизацией снегоочистителя
• Список сложности задач китайского почтальона