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

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

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

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

Фон

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

Основа

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

Типы проблем

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

Ненаправленная проблема сельского почтальона

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

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

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

История

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

Задача о ветреном почтальоне и ее варианты

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

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

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

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

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

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

В реальных приложениях существует несколько транспортных средств, которые могут двигаться, что приводит к обобщению, названному «Задача ветреного сельского почтальона 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). ^[10]

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

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

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

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

Приложения

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

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

Зимой часто возникает вопрос: какой набор маршрутов имеет наименьшую (минимальную) максимальную длину маршрута? Обычно это оценивается как проблема трассировки дуги с графом. Время, необходимое для проезда по улице, известное как «мертвое время», меньше, чем время, необходимое для уборки снега с улиц (или доставки почты или сдачи посылок). Еще одним аспектом, который необходимо учитывать при применении дуговой трассировки для уборки снега, является тот факт, что на крутых улицах либо трудно, либо невозможно двигаться в гору. Целью является маршрут, позволяющий избежать подъема в гору по крутым улицам и быстрее завершить работу за счет максимального увеличения времени простоя, чтобы добраться до местоположения. Это было смоделировано с помощью эвристического алгоритма, который аппроксимирует нижнюю границу Дюссо, Голдена и Василя. ^[3] Это проблема спускового плуга (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 поддается управлению с фиксированными параметрами. ^[19] Авторы доказывают, что k -CPP допускает ядро с $O(k^{2}\log(k))$ вершин, а ориентированная версия k -CPP является NP-полной.

Задача сельского почтальона (ЗПП) и обобщения

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

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

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

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

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

Сложность

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

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

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


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

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Чен, Хуанфа; Ченг, Тао; Шоу-Тейлор, Джон (2 января 2018 г.). «Сбалансированный проект маршрута для задачи сельского почтальона с несколькими депо (MMMDRPP): случай полицейского патрулирования» . Международный журнал географической информатики . 32 (1): 169–190. дои : 10.1080/13658816.2017.1380201 . ISSN 1365-8816 . S2CID 29526595 .
^ Jump up to: ^а ^б ^с ^д Омер, Масуд (2007). «Эффективная маршрутизация снегоуборочной техники» .
^ Jump up to: ^а ^б ^с ^д Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (октябрь 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 0160-5682 . S2CID 36977043 .
^ Jump up to: ^а ^б ^с ^д Эйзельт, штат Ха; Жандро, Мишель; Лапорт, Гилберт (апрель 1995 г.). «Проблемы маршрутизации дуги, часть I: проблема китайского почтальона» . Исследование операций . 43 (2): 231–242. дои : 10.1287/опре.43.2.231 . hdl : 11059/14013 . ISSN 0030-364X .
^ Дельгадо Серна, Кристина Р.; Пачеко Бонростро, Хоакин (2001), Восс, Стефан; Дадуна, Иоахим Р. (ред.), «Проблемы маршрутизации транспортных средств Minmax: применение к школьному транспорту в провинции Бургос» , Компьютерное планирование общественного транспорта , Берлин, Гейдельберг: Springer, стр. 297–317, doi : 10.1007 /978-3-642-56423-9_17 , ISBN 978-3-642-56423-9 , получено 1 мая 2022 г.
^ Бодин, Лоуренс; Голден, Брюс (1981). «Классификация в маршрутизации и планировании движения транспортных средств» . Сети . 11 (2): 97–108. дои : 10.1002/net.3230110204 .
^ Бодин, Лоуренс Д.; Секстон, Томас Р. (февраль 1983 г.). Проблема дозвона абонента с несколькими транспортными средствами (технический отчет). Военно-морская аспирантура. hdl : 10945/63226 . НПС55-83-002.
^ Jump up to: ^а ^б ^с ^д Раббани, Масуд; Аламдар, Сафура Фамиль; Фаррохи-Асл, Хамед (01 февраля 2016 г.). «Задача ветреного сельского почтальона с несколькими транспортными средствами: гибридный многокритериальный алгоритм моделирования отжига» (PDF) . Международный журнал управления поставками и операциями . 2 (4): 1003–20. дои : 10.22034/2015.4.03 . ISSN 2383-1359 .
^ Jump up to: ^а ^б ^с Бенавент, Э.; Корберан, А.; Пиньяна, Э.; Плана, И.; Санчис, Дж. М. (декабрь 2005 г.), «Новые эвристические алгоритмы для задачи ветреного сельского почтальона» , Computers and Operations Research , 32 (12): 3111–28, doi : 10.1016/j.cor.2004.04.007 , hdl : 10251/ 94488
^ Jump up to: ^а ^б ^с ^д Бенавент, Энрике; Корберан, Анхель; Санчис, Хосе М. (июль 2010 г.). «Метаэвристика для мин-максной задачи о ветреном сельском почтальоне с K транспортных средств» . Вычислительная наука управления . 7 (3): 269–287. дои : 10.1007/s10287-009-0119-2 . hdl : 10251/100790 . ISSN 1619-697X . S2CID 41426793 .
^ «Леонард Эйлер и Кенигсбергские мосты» . Научный американец . Проверено 30 апреля 2022 г.
^ Jump up to: ^а ^б ХА, Эйзельт; Мишель, Жандро (1995). «Проблемы маршрутизации дуги, часть II: проблема сельского почтальона» . Исследование операций . 43 (3): 399–414. дои : 10.1287/опре.43.3.399 .
^ Миниека, Эдвард (июль 1979 г.). «Задача китайского почтальона для смешанных сетей» . Наука управления . 25 (7): 643–648. дои : 10.1287/mnsc.25.7.643 .
^ Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR 0754427 .
^ Ленстра, Дж. К.; Риннуй Кан, AHG (1981), «Сложность задач маршрутизации и планирования транспортных средств» (PDF) , Networks , 11 (2): 221–7, doi : 10.1002/net.3230110211
^ Jump up to: ^а ^б ^с Корберан, Анхель; Освальд, Маркус; Плана, Исаак; Рейнельт, Герхард; Санчис, Хосе М. (апрель 2012 г.). «Новые результаты по проблеме ветреного почтальона» . Математическое программирование . 132 (1–2): 309–332. дои : 10.1007/s10107-010-0399-x . ISSN 0025-5610 . S2CID 12808962 .
^ Ян, Синь-Ше (2010). «Инженерная оптимизация с помощью Cuckoo Search». Международный журнал математического моделирования и численной оптимизации . 1 (4): 330–343. arXiv : 1005.2908 . дои : 10.1504/IJMMNO.2010.035430 . S2CID 34889796 .
^ А. Шрийвер, Комбинаторная оптимизация, многогранники и эффективность, том A, Springer. (2002).
^ Гутин, Григорий; Мучачча, Габриэле; Йо, Андерс (18 ноября 2013 г.). «Параметризованная сложность k -задачи китайского почтальона» . Теоретическая информатика . 513 : 124–128. arXiv : 1308.0482 . дои : 10.1016/j.tcs.2013.10.012 . ISSN 0304-3975 . S2CID 2867281 .
^ Бенавент, Энрике; Солер, Дэвид (ноябрь 1999 г.). «Задача о направленном сельском почтальоне со штрафами за поворот» . Транспортная наука . 33 (4): 408–418. дои : 10.1287/trsc.33.4.408 . ISSN 0041-1655 .
^ Герц, Ален. «Последние тенденции в дуговой маршрутизации» (PDF) . Политехническая школа — ГЕРАД.
^ Jump up to: ^а ^б ^с Эдмондс, Джек; Джонсон, Эллис Л. (1973). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .
^ Ясюн, Линь; Юнчан, Чжао (январь 1988 г.). «Новый алгоритм решения направленной задачи китайского почтальона» . Компьютеры и исследования операций . 15 (6): 577–584. дои : 10.1016/0305-0548(88)90053-6 . ISSN 0305-0548 .
^ Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .
^ Рагхавачари, Баладжи; Вирасами, Джеякесаван (январь 1999 г.). «Алгоритм приближения 3/2 для смешанной задачи почтальона» . SIAM Journal по дискретной математике . 12 (4): 425–433. дои : 10.1137/s0895480197331454 . ISSN 0895-4801 .
^ Jump up to: ^а ^б Гутин, Григорий; Джонс, Марк; Шэн, Бин (2014), «Параметризованная сложность проблемы китайского почтальона k-дуги» , Алгоритмы - ESA 2014 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 530–541, arXiv : 1403.1512 , doi : 10.1007/978-3 -662-44777-2_44 , ISBN 978-3-662-44776-5 , S2CID 3472348 , получено 9 мая 2022 г.
^ Фернандес, Кристина Г.; Ли, Орландо; Вакабаяси, Ёсико (январь 2009 г.). «Минимальное покрытие цикла и задачи китайского почтальона на смешанных графах с ограниченной шириной дерева» . Дискретная прикладная математика . 157 (2): 272–279. дои : 10.1016/j.dam.2007.10.032 . ISSN 0166-218X .
^ Jump up to: ^а ^б Гуань, Мейгу (сентябрь 1984 г.). «О проблеме ветреного почтальона» . Дискретная прикладная математика . 9 (1): 41–46. дои : 10.1016/0166-218x(84)90089-1 . ISSN 0166-218X .
^ Вин, Зау (май 1989 г.). «О проблеме ветреного почтальона на эйлеровых графах» . Математическое программирование . 44 (1–3): 97–112. дои : 10.1007/bf01587080 . ISSN 0025-5610 . S2CID 206800125 .
^ Вирасами, Джеякесаван (1999). Алгоритмы аппроксимации задач Почтальона (кандидатская диссертация). Техасский университет в Далласе.
^ Дрор, Моше; Стерн, Хелман; Трюдо, Пьер (1987). «Объезд почтальона по графу с отношением предшествования по дугам» . Сети . 17 (3): 283–294. дои : 10.1002/net.3230170304 . ISSN 0028-3045 .
^ «12-й Всемирный компьютерный конгресс — ИФИП-конгресс'92» . Компьютеры в промышленности . 20 (1): 124–126. Январь 1992 г. doi : 10.1016/0166-3615(92)90137-c . ISSN 0166-3615 .
^ Томассен, Карстен (июнь 1997 г.). «О сложности нахождения минимального циклического покрытия графа» . SIAM Journal по вычислительной технике . 26 (3): 675–677. дои : 10.1137/s0097539794267255 . ISSN 0097-5397 .
^ Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .
^ Jump up to: ^а ^б Фредериксон, Грег Н.; Хехт, Мэтью С.; Ким, Чул Э. (май 1978 г.). «Алгоритмы аппроксимации некоторых задач маршрутизации» . SIAM Journal по вычислительной технике . 7 (2): 178–193. дои : 10.1137/0207017 . ISSN 0097-5397 . S2CID 7562375 .
^ Эйзельт, Х. (май 1995 г.). «Проблемы маршрутизации дуги, часть II: Проблема сельского почтальона» . п. 399. ПроКвест 219174102 .
^ Гуань, Мэйгу (1962). «Графическое программирование с использованием нечетных и четных точек». Китайская математика .
^ Дюссо, Бенджамин; Голден, Брюс; Гроэр, Крис; Васил, Эдвард (01 апреля 2013 г.). «Вспашка с приоритетом: вариант задачи о ветреном почтальоне» . Компьютеры и исследования операций . 40 (4): 1047–1059. дои : 10.1016/j.cor.2012.10.013 . ISSN 0305-0548 .
^ Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (01 октября 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .
^ Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (01 октября 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .
^ Дюсюаль, Бенджамин (2012). «Моделирование и решение задач трассировки дуг при подметании улиц и уборке снега» . ПроКвест .
^ Чен, Хуанфа; Ченг, Тао; Шоу-Тейлор, Джон (2 января 2018 г.). «Сбалансированный проект маршрута для задачи сельского почтальона с несколькими депо (MMMDRPP): случай полицейского патрулирования» . Международный журнал географической информатики . 32 (1): 169–190. дои : 10.1080/13658816.2017.1380201 . ISSN 1365-8816 . S2CID 29526595 .
^ Гиани, Джанпаоло; Импрота, Дженнаро (01 апреля 2000 г.). «Эффективное преобразование обобщенной задачи маршрутизации транспортных средств» . Европейский журнал операционных исследований . 122 (1): 11–17. дои : 10.1016/S0377-2217(99)00073-9 . ISSN 0377-2217 .

[:3-1] Jump up to: ^а ^б ^с ^д Чен, Хуанфа; Ченг, Тао; Шоу-Тейлор, Джон (2 января 2018 г.). «Сбалансированный проект маршрута для задачи сельского почтальона с несколькими депо (MMMDRPP): случай полицейского патрулирования» . Международный журнал географической информатики . 32 (1): 169–190. дои : 10.1080/13658816.2017.1380201 . ISSN 1365-8816 . S2CID 29526595 .

[:4-2] Jump up to: ^а ^б ^с ^д Омер, Масуд (2007). «Эффективная маршрутизация снегоуборочной техники» .

[Dussault_1465–1474-3] Jump up to: ^а ^б ^с ^д Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (октябрь 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 0160-5682 . S2CID 36977043 .

[:0-4] Jump up to: ^а ^б ^с ^д Эйзельт, штат Ха; Жандро, Мишель; Лапорт, Гилберт (апрель 1995 г.). «Проблемы маршрутизации дуги, часть I: проблема китайского почтальона» . Исследование операций . 43 (2): 231–242. дои : 10.1287/опре.43.2.231 . hdl : 11059/14013 . ISSN 0030-364X .

[5] Дельгадо Серна, Кристина Р.; Пачеко Бонростро, Хоакин (2001), Восс, Стефан; Дадуна, Иоахим Р. (ред.), «Проблемы маршрутизации транспортных средств Minmax: применение к школьному транспорту в провинции Бургос» , Компьютерное планирование общественного транспорта , Берлин, Гейдельберг: Springer, стр. 297–317, doi : 10.1007 /978-3-642-56423-9_17 , ISBN 978-3-642-56423-9 , получено 1 мая 2022 г.

[6] Бодин, Лоуренс; Голден, Брюс (1981). «Классификация в маршрутизации и планировании движения транспортных средств» . Сети . 11 (2): 97–108. дои : 10.1002/net.3230110204 .

[7] Бодин, Лоуренс Д.; Секстон, Томас Р. (февраль 1983 г.). Проблема дозвона абонента с несколькими транспортными средствами (технический отчет). Военно-морская аспирантура. hdl : 10945/63226 . НПС55-83-002.

[auto-8] Jump up to: ^а ^б ^с ^д Раббани, Масуд; Аламдар, Сафура Фамиль; Фаррохи-Асл, Хамед (01 февраля 2016 г.). «Задача ветреного сельского почтальона с несколькими транспортными средствами: гибридный многокритериальный алгоритм моделирования отжига» (PDF) . Международный журнал управления поставками и операциями . 2 (4): 1003–20. дои : 10.22034/2015.4.03 . ISSN 2383-1359 .

[:1-9] Jump up to: ^а ^б ^с Бенавент, Э.; Корберан, А.; Пиньяна, Э.; Плана, И.; Санчис, Дж. М. (декабрь 2005 г.), «Новые эвристические алгоритмы для задачи ветреного сельского почтальона» , Computers and Operations Research , 32 (12): 3111–28, doi : 10.1016/j.cor.2004.04.007 , hdl : 10251/ 94488

[:2-10] Jump up to: ^а ^б ^с ^д Бенавент, Энрике; Корберан, Анхель; Санчис, Хосе М. (июль 2010 г.). «Метаэвристика для мин-максной задачи о ветреном сельском почтальоне с K транспортных средств» . Вычислительная наука управления . 7 (3): 269–287. дои : 10.1007/s10287-009-0119-2 . hdl : 10251/100790 . ISSN 1619-697X . S2CID 41426793 .

[11] «Леонард Эйлер и Кенигсбергские мосты» . Научный американец . Проверено 30 апреля 2022 г.

[auto1-12] Jump up to: ^а ^б ХА, Эйзельт; Мишель, Жандро (1995). «Проблемы маршрутизации дуги, часть II: проблема сельского почтальона» . Исследование операций . 43 (3): 399–414. дои : 10.1287/опре.43.3.399 .

[13] Миниека, Эдвард (июль 1979 г.). «Задача китайского почтальона для смешанных сетей» . Наука управления . 25 (7): 643–648. дои : 10.1287/mnsc.25.7.643 .

[14] Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR 0754427 .

[Complexity-15] Ленстра, Дж. К.; Риннуй Кан, AHG (1981), «Сложность задач маршрутизации и планирования транспортных средств» (PDF) , Networks , 11 (2): 221–7, doi : 10.1002/net.3230110211

[Corberán-16] Jump up to: ^а ^б ^с Корберан, Анхель; Освальд, Маркус; Плана, Исаак; Рейнельт, Герхард; Санчис, Хосе М. (апрель 2012 г.). «Новые результаты по проблеме ветреного почтальона» . Математическое программирование . 132 (1–2): 309–332. дои : 10.1007/s10107-010-0399-x . ISSN 0025-5610 . S2CID 12808962 .

[17] Ян, Синь-Ше (2010). «Инженерная оптимизация с помощью Cuckoo Search». Международный журнал математического моделирования и численной оптимизации . 1 (4): 330–343. arXiv : 1005.2908 . дои : 10.1504/IJMMNO.2010.035430 . S2CID 34889796 .

[18] А. Шрийвер, Комбинаторная оптимизация, многогранники и эффективность, том A, Springer. (2002).

[19] Гутин, Григорий; Мучачча, Габриэле; Йо, Андерс (18 ноября 2013 г.). «Параметризованная сложность k -задачи китайского почтальона» . Теоретическая информатика . 513 : 124–128. arXiv : 1308.0482 . дои : 10.1016/j.tcs.2013.10.012 . ISSN 0304-3975 . S2CID 2867281 .

[20] Бенавент, Энрике; Солер, Дэвид (ноябрь 1999 г.). «Задача о направленном сельском почтальоне со штрафами за поворот» . Транспортная наука . 33 (4): 408–418. дои : 10.1287/trsc.33.4.408 . ISSN 0041-1655 .

[21] Герц, Ален. «Последние тенденции в дуговой маршрутизации» (PDF) . Политехническая школа — ГЕРАД.

[:0c-22] Jump up to: ^а ^б ^с Эдмондс, Джек; Джонсон, Эллис Л. (1973). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .

[23] Ясюн, Линь; Юнчан, Чжао (январь 1988 г.). «Новый алгоритм решения направленной задачи китайского почтальона» . Компьютеры и исследования операций . 15 (6): 577–584. дои : 10.1016/0305-0548(88)90053-6 . ISSN 0305-0548 .

[24] Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .

[25] Рагхавачари, Баладжи; Вирасами, Джеякесаван (январь 1999 г.). «Алгоритм приближения 3/2 для смешанной задачи почтальона» . SIAM Journal по дискретной математике . 12 (4): 425–433. дои : 10.1137/s0895480197331454 . ISSN 0895-4801 .

[:2c-26] Jump up to: ^а ^б Гутин, Григорий; Джонс, Марк; Шэн, Бин (2014), «Параметризованная сложность проблемы китайского почтальона k-дуги» , Алгоритмы - ESA 2014 , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 530–541, arXiv : 1403.1512 , doi : 10.1007/978-3 -662-44777-2_44 , ISBN 978-3-662-44776-5 , S2CID 3472348 , получено 9 мая 2022 г.

[27] Фернандес, Кристина Г.; Ли, Орландо; Вакабаяси, Ёсико (январь 2009 г.). «Минимальное покрытие цикла и задачи китайского почтальона на смешанных графах с ограниченной шириной дерева» . Дискретная прикладная математика . 157 (2): 272–279. дои : 10.1016/j.dam.2007.10.032 . ISSN 0166-218X .

[:1c-28] Jump up to: ^а ^б Гуань, Мейгу (сентябрь 1984 г.). «О проблеме ветреного почтальона» . Дискретная прикладная математика . 9 (1): 41–46. дои : 10.1016/0166-218x(84)90089-1 . ISSN 0166-218X .

[29] Вин, Зау (май 1989 г.). «О проблеме ветреного почтальона на эйлеровых графах» . Математическое программирование . 44 (1–3): 97–112. дои : 10.1007/bf01587080 . ISSN 0025-5610 . S2CID 206800125 .

[30] Вирасами, Джеякесаван (1999). Алгоритмы аппроксимации задач Почтальона (кандидатская диссертация). Техасский университет в Далласе.

[31] Дрор, Моше; Стерн, Хелман; Трюдо, Пьер (1987). «Объезд почтальона по графу с отношением предшествования по дугам» . Сети . 17 (3): 283–294. дои : 10.1002/net.3230170304 . ISSN 0028-3045 .

[32] «12-й Всемирный компьютерный конгресс — ИФИП-конгресс'92» . Компьютеры в промышленности . 20 (1): 124–126. Январь 1992 г. doi : 10.1016/0166-3615(92)90137-c . ISSN 0166-3615 .

[33] Томассен, Карстен (июнь 1997 г.). «О сложности нахождения минимального циклического покрытия графа» . SIAM Journal по вычислительной технике . 26 (3): 675–677. дои : 10.1137/s0097539794267255 . ISSN 0097-5397 .

[34] Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .

[Frederickson_178–193-35] Jump up to: ^а ^б Фредериксон, Грег Н.; Хехт, Мэтью С.; Ким, Чул Э. (май 1978 г.). «Алгоритмы аппроксимации некоторых задач маршрутизации» . SIAM Journal по вычислительной технике . 7 (2): 178–193. дои : 10.1137/0207017 . ISSN 0097-5397 . S2CID 7562375 .

[36] Эйзельт, Х. (май 1995 г.). «Проблемы маршрутизации дуги, часть II: Проблема сельского почтальона» . п. 399. ПроКвест 219174102 .

[37] Гуань, Мэйгу (1962). «Графическое программирование с использованием нечетных и четных точек». Китайская математика .

[38] Дюссо, Бенджамин; Голден, Брюс; Гроэр, Крис; Васил, Эдвард (01 апреля 2013 г.). «Вспашка с приоритетом: вариант задачи о ветреном почтальоне» . Компьютеры и исследования операций . 40 (4): 1047–1059. дои : 10.1016/j.cor.2012.10.013 . ISSN 0305-0548 .

[39] Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (01 октября 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .

[40] Дюссо, Бенджамин; Голден, Брюс; Васил, Эдвард (01 октября 2014 г.). «Задача спускового плуга с несколькими плугами» . Журнал Общества операционных исследований . 65 (10): 1465–1474. дои : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .

[41] Дюсюаль, Бенджамин (2012). «Моделирование и решение задач трассировки дуг при подметании улиц и уборке снега» . ПроКвест .

[42] Чен, Хуанфа; Ченг, Тао; Шоу-Тейлор, Джон (2 января 2018 г.). «Сбалансированный проект маршрута для задачи сельского почтальона с несколькими депо (MMMDRPP): случай полицейского патрулирования» . Международный журнал географической информатики . 32 (1): 169–190. дои : 10.1080/13658816.2017.1380201 . ISSN 1365-8816 . S2CID 29526595 .

[43] Гиани, Джанпаоло; Импрота, Дженнаро (01 апреля 2000 г.). «Эффективное преобразование обобщенной задачи маршрутизации транспортных средств» . Европейский журнал операционных исследований . 122 (1): 11–17. дои : 10.1016/S0377-2217(99)00073-9 . ISSN 0377-2217 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]