Prowadzenie łuku

Problemy z trasowaniem łuku (ARP) to kategoria ogólnych problemów z trasowaniem (GRP), która obejmuje również problemy z trasowaniem węzłów (NRP). Celem ARP i NRP jest przechodzenie odpowiednio przez krawędzie i węzły grafu. Celem problemów związanych z trasowaniem łuku jest minimalizacja całkowitej odległości i czasu, co często wiąże się z minimalizacją martwego punktu , czyli czasu potrzebnego na dotarcie do miejsca docelowego. Problemy z trasowaniem łuków można zastosować do zbierania śmieci , planowania tras autobusów szkolnych , dostarczania paczek i gazet, odladzania i usuwania śniegu za pomocą pojazdów służb zimowych , które posypują drogę solą , dostarczania poczty , konserwacji sieci, zamiatania ulic , patrolowania policji i ochroniarzy, i odśnieżanie . Problemy trasowania łuków są NP-trudne , w przeciwieństwie do problemów kontroli tras , które można rozwiązać w czasie wielomianowym .

Aby uzyskać rzeczywisty przykład rozwiązywania problemów związanych z wyznaczaniem trasy łuku, Cristina R. Delgado Serna i Joaquín Pacheco Bonrostro zastosowali algorytmy aproksymacji, aby znaleźć najlepsze trasy autobusów szkolnych w hiszpańskim systemie szkół średnich w prowincji Burgos . Naukowcy zminimalizowali liczbę tras, których pokonanie zajęło im więcej niż 60 minut. Zminimalizowali także czas trwania najdłuższej trasy przy ustalonej maksymalnej liczbie pojazdów.

Istnieją uogólnienia problemów związanych z trasowaniem łuków, które wprowadzają wielu listonoszy, na przykład problem chińskiego listonosza k (KCPP).

Tło

Efektywne planowanie i wyznaczanie tras pojazdów może zaoszczędzić przemysłowi i rządowi miliony dolarów każdego roku. Problemy z trasowaniem łuków mają zastosowanie w planowaniu autobusów szkolnych, wywozie śmieci i odpadów oraz śmieci w miastach, dostarczaniu poczty i paczek przez listonoszy i usługi pocztowe, zimowym piaskowaniu i układaniu soli w celu zapewnienia bezpieczeństwa dróg w zimie, odśnieżaniu i usuwaniu śniegu, odczytach liczników w tym technologia zdalnego odczytu liczników identyfikacji radiowej, konserwacja i zamiatanie ulic, planowanie tras policyjnych radiowozów patrolowych i nie tylko.

Podstawa

Podstawowy problem wyznaczania tras to: biorąc pod uwagę zestaw węzłów i/lub łuków, które mają być obsługiwane przez flotę pojazdów, znajdź trasy dla każdego pojazdu rozpoczynającego się i kończącego w zajezdni. Trasa pojazdu to ciąg punktów lub węzłów, przez które pojazd musi po kolei przejechać, zaczynając i kończąc w zajezdni.

Problem z chińskim listonoszem

Problem chińskiego listonosza (CPP) ma na celu znalezienie minimalnej długości cyklu dla pojedynczego listonosza. CPP wymaga, aby wszystkie krawędzie zostały pokonane raz, problem wiejskiego listonosza (RPP) wymaga, aby podzbiór krawędzi został pokonany w cyklu o minimalnej długości.

Problemy z wyznaczaniem tras pojazdów/VRP

Problemy z prowadzeniem łuku wpływają na decyzje dotyczące planowania strategicznego, taktycznego i operacyjnego. Strategiczna rola miejsca umieszczenia magazynu zależy od najbardziej wydajnej dostępnej trasy łuku. Decyzja o wielkości floty pojazdów i typach pojazdów o różnych specyfikacjach dotyczy taktycznego aspektu problemów związanych z trasowaniem łuków w badaniach operacyjnych. Decyzje dotyczące wyznaczania tras i planowania są decyzjami dotyczącymi planowania operacyjnego w przypadku problemów związanych z trasowaniem łuków. Decyzje dotyczące planowania operacyjnego obejmują również czas, w którym pojazdy są używane przez pracowników wraz z decyzjami personelu. Decyzje dotyczące tras pojazdów dla lokalizacji składu zależą od kosztów transportu materiałów w regionie geograficznym. Bodin i in. al zastosował wyznaczanie tras pojazdu do tarczy problem z jazdą.

Problem wiejskiego listonosza

W niektórych sytuacjach wymagany zestaw krawędzi różni się od krawędzi na wykresie. Jest to modelowane przez wiejski problem listonosza (RPP), w którym wymagane krawędzie są podzbiorem systemu krawędzi.

Algorytmy

Znalezienie wydajnego rozwiązania z dużą ilością danych dla problemu chińskiego listonosza (CPP), problemu wietrznego listonosza (WPP), problemu listonosza wiejskiego (RPP), problemu k-chińskiego listonosza (KCPP), mieszanego problemu listonosza chińskiego ( MCPP ), Directed Chinese Postman Problem (DCPP), Downhill Plough Problem (DPP), Orka z pierwszeństwem (PPP), Windy Rural Postman Problem (WRPP) i Windy General Routing Problem (WGRP) wymaga użycia przemyślanych koncepcji matematycznych , w tym heurystyczne metody optymalizacji , metody rozgałęzień i ograniczeń , programowanie liniowe liczb całkowitych i zastosowania algorytmów problemu komiwojażera, takich jak algorytm Helda – Karpa, wprowadza ulepszenia z ${\ Displaystyle O (n!)}$ ${\ Displaystyle O (2 ^ {n} n ^ {2})}$ . Oprócz tych algorytmów, te klasy problemów można również rozwiązać za pomocą algorytmu płaszczyzny cięcia , optymalizacji wypukłej , wypukłych kadłubów , mnożników Lagrange'a i innych metod programowania dynamicznego . W przypadkach, gdy nie jest możliwe uruchomienie algorytmu Helda-Karpa ze względu na jego dużą złożoność obliczeniową, algorytmy takie jak ten mogą być użyte do przybliżenia rozwiązania w rozsądnym czasie.

Obwody Eulera

Najwcześniejszym udokumentowanym odniesieniem do obszaru problemów związanych z prowadzeniem łuku są klasyczne mosty wyzwania Königsberg , które Euler okazał się niewykonalne. Mieszkaniec Królewca , obecnie części Kaliningradu , chciał znaleźć sposób na przejście przez wszystkie siedem mostów na rzece Pregole bez cofania się lub cofania, czyli przechodzenia przez każdy most tylko raz. W 1736 roku Euler sprowadził problem do kwestii węzłów i krawędzi i wykazał, że problem jest niemożliwy. W 1873 Hierholzer zrobił więcej pracy w kwestii obiegów zamkniętych.

Prace nad obwodami Eulera zostały spopularyzowane przez Scientific American 1 lipca 1953 r. Prace te zostały rozszerzone przez Meigu Guana, znanego również jako Kwan Mei-Ko z Shangtun Normal College. Meigu Guan była zainteresowana inną kwestią niż określeniem obwodu zamkniętego. Guan pracował nad znalezieniem minimalnej długości spaceru, który przeszedł przez każdą krawędź grafu przynajmniej raz. Guan opisał swój cel w 1962 roku: „Listonosz musi pokonać przydzielony mu odcinek przed powrotem na pocztę. Problem polega na znalezieniu najkrótszej odległości dla listonosza”.

Typy problemów

Problemy z trasowaniem łuku (ARP) różnią się celem i heurystyką. Jednak wszystkie z nich są znane jako NP-trudne .

Nieukierunkowany problem listonosza wiejskiego

Problem ten został nazwany na cześć listonosza i jego wyzwania polegającego na dostarczeniu poczty w dowolnej kolejności, którą wybierze, ale minimalizując koszty, takie jak czas lub odległość dojazdu. Czasami nazywa się to również problemem nieukierunkowanego chińskiego listonosza . Problem nieukierunkowanego wiejskiego listonosza (URPP) ma na celu zminimalizowanie całkowitego kosztu trasy, która odwzorowuje całą sieć lub, w bardziej konkretnych przypadkach, trasy, która odwzorowuje każdą krawędź wymagającą usługi. Jeśli cała sieć musi zostać zmapowana, trasa, która odwzorowuje całą sieć, nazywana jest trasą obejmującą . W przypadku, gdy trzeba odwzorować tylko niektóre krawędzie, problem ma na celu rozwiązanie trasy, która optymalizuje wymagania, przecinając niepotrzebne trasy minimalną liczbę razy.

Nieukierunkowany problem z kierowaniem łuku pojemnościowego

Problem kierowania nieukierunkowanego łuku pojemnościowego składa się z wymagań stawianych krawędziom, a każda krawędź musi spełniać wymagania. Przykładem jest wyrzucanie elementów bezużytecznych, gdzie każda trasa może wymagać zarówno wyrzucania elementów bezużytecznych, jak i zbierania nadającego się do recyklingu. Problemy w rzeczywistych aplikacjach mogą pojawić się, jeśli występują problemy z synchronizacją, takie jak przypadek, w którym niektóre trasy nie mogą być obsługiwane z powodu konfliktów w czasie lub harmonogramie lub ograniczeń, takich jak ograniczony okres czasu. Heurystyki opisane w tym artykule ignorują wszelkie tego typu problemy wynikające z ograniczeń aplikacji.

Historia

Lenstra i Kan udowodnili, że jest to problem NP-trudny . UCARP można wyprowadzić z URPP, a zatem jest również NP-trudny. W 1981 roku inna para informatyków, Golden i Wong, zdołała udowodnić, że nawet wyprowadzenie przybliżenia 0,5 do URPP było NP-trudne. W 2000 roku Dror opublikował książkę opisującą różne problemy związane z prowadzeniem łuku.

Wietrzny problem listonosza i warianty

problem wietrznego listonosza jest wariantem problemu inspekcji trasy, w którym dane wejściowe są grafem nieskierowanym, ale gdzie każda krawędź może mieć inny koszt przejścia w jednym kierunku niż w drugim kierunku. W przeciwieństwie do rozwiązań dla grafów skierowanych i nieskierowanych jest NP-zupełny . Koszt podróży w jednym kierunku jest większy, gdy wiatr wieje w twarz niż gdy wiatr wieje w plecy, i stąd nazwa problemu Windy Postman. Praca potrzebna do przebycia ulicy w jednym kierunku różni się od pracy potrzebnej do przebycia ulicy w innym kierunku w wietrzny dzień.

Problem z wietrznym listonoszem to problem z trasowaniem łuku (ARP), który zawiera problem mieszanego chińskiego listonosza MCPP jako przypadek specjalny.

Problem można zdefiniować w następujący sposób: „Dając nieskierowany i spójny wykres G = (V, E) z dwoma nieujemnymi kosztami do ja , jot {\ $, j}}$ i ${ \ Displaystyle c_ {j, i}}$ związane z każdą krawędzią ${\ Displaystyle \ {i, j \} \ w E}$ odpowiadające kosztowi przejścia przez nią od i do j oraz od j do i , odpowiednio, WPP ma znaleźć trasę o minimalnym koszcie na G przechodzącą przez każdą krawędź co najmniej raz. Problem ten przedstawiła Minieka. WPP jest ogólnie NP-zupełny i można go rozwiązać w czasie wielomianowym, jeśli G jest eulerowskie, jeśli koszt dwóch przeciwnych orientacji każdego cyklu w G jest taki sam lub jeśli G jest grafem szeregowo-równoległym. Problem wietrznego listonosza wiejskiego (WRPP) jest uogólnieniem WPP, w którym nie wszystkie krawędzie grafu muszą zostać pokonane, ale tylko te z danego podzbioru wymaganych krawędzi. Na przykład listonosz nie musi przekraczać niektórych wiejskich dróg, a niektóre drogi na stromych wzgórzach wymagają więcej czasu na wjazd niż w dół.

Problem wietrznego listonosza wiejskiego (WRPP) jest uogólnieniem WPP, w którym nie trzeba przechodzić przez wszystkie krawędzie grafu, ale tylko te w danym podzbiorze wymaganych krawędzi. Na przykład listonosz nie musi przekraczać niektórych wiejskich dróg, a niektóre drogi na stromych wzgórzach wymagają więcej czasu na wjazd niż w dół. $Displaystyle$ wykres $nieskierowany$ $_$ dwoma do związane z kosztem przejścia przez krawędź ${\ Displaystyle (i, j)}$ zaczynając odpowiednio od i i j. G jest wietrznym wykresem i interesuje nas podzbiór krawędzi lub symbole matematyczne, ${\ Displaystyle E_ {R} \ subseteq E}$ .

$, że należy odwiedzić określony zestaw wierzchołków -$ problem w Windy General Routing Problem (WGRP). Benavent zaproponował formułę programowania liniowego liczb całkowitych oraz różne heurystyki i dolne granice dla WRPP.

Benavent i wsp. opublikowali ocenę kilku metod heurystycznych zastosowanych do rozwiązania WRPP w ciągu kilku sekund z odchyleniem nie większym niż 1% od dolnej granicy na wykresach średniej wielkości. Poprawili to za pomocą algorytmu wyszukiwania rozproszonego, który zmniejszył różnicę do 0,5%. Wyszukiwanie rozproszone znalazło rozwiązania, które różniły się o mniej niż 2%, gdy zostały zaimplementowane w sieciach z setkami węzłów i tysiącami krawędzi.

W rzeczywistych zastosowaniach istnieje wiele pojazdów, które mogą się poruszać, co prowadzi do uogólnienia nazwanego problemem wietrznego wiejskiego listonosza min-maks K-pojazdów (MM K-WRPP). Problem min-max K-pojazdów wietrznego wiejskiego listonosza (MM K-WRPP) jest zdefiniowany w następujący sposób: Biorąc pod uwagę wietrzny wykres, wyróżniający się wierzchołek ${\ Displaystyle G = \ {V, E \}}$ 1 ${\ Displaystyle 1 \ in V}$ , reprezentujący zajezdnię, podzbiór wymaganych krawędzi mi $\ Displaystyle E_ {R} \ subseteq E} i stałą liczbę K$ , MM K- WRPP polega na znalezieniu zestawu tras K dla pojazdów w taki sposób, aby każda trasa rozpoczynała się i kończyła w zajezdni, a każda wymagana krawędź była obsługiwana przez dokładnie jeden pojazd. Celem jest zminimalizowanie długości najdłuższej trasy w celu znalezienia zestawu zrównoważonych tras dla pojazdów. Niektóre rzeczywiste zastosowania problemów związanych z trasowaniem z celami min-max to wyznaczanie tras autobusów szkolnych (Degado i Pacheco 2001), dostawa gazet do klientów (Applegate i in. 2002) oraz zbiórka odpadów (Lacomme i in. 2004).

Najlepszy algorytm MM K_WRPP był bardzo zbliżony do rozwiązania minimalnego przy 2 i 3 pojazdach, średnio mniej niż 0,4%. Różnica wzrasta do około 1,00% i 1,60% przy 4 i 5 pojazdach.

Według Dussaulta i in. oraz Benaventa i in., metaheurystyczny, wielocelowy algorytm symulujący wyżarzanie (MOSA) może rozwiązać różne ograniczenia nałożone na WRPP. WRPP jest ważnym problemem wyznaczania trasy łuku, który uogólnia wiele problemów związanych z trasowaniem łuku dla pojedynczych pojazdów. W rzeczywistych zastosowaniach matematyki preferowane jest rozwiązanie, które minimalizuje łączne koszty trasy wszystkich pojazdów i długość najdłuższej trasy. Trudno jest być w miejscu, w którym paczka jest spóźniona o kilka godzin. Należy zacząć od założenia, że kilka pojazdów o określonej mierzalnej pojemności do obsługi klientów jest bardziej realistyczne niż jeden pojazd o niemierzalnej i nieskończonej pojemności. Rabbani i in. al zmierzył wydajność algorytmów i modeli MOSA przy użyciu wielocelowego rozwoju wyszukiwania Cuckoo - opracowanego przez Yang i in., określanego również jako Multi-objective Cuckoo Search i w skrócie MOCS. Doszli do wniosku, że metody MOSA były bardziej wydajne niż metody MOCS. W przyszłości można by zbadać porównania z innymi metodami metaheurystycznymi, w tym algorytmem genetyki sortowania niezdominowanego (NSGA-), wielocelowym algorytmem optymalizacji roju cząstek (MOPSO) i wielocelowym imperialistycznym algorytmem konkurencyjnym.

W modelu Windy Postman Problem (WPP) koszt pójścia w jednym kierunku jest inny niż koszt pójścia w drugim kierunku. Na przykład, jeśli wiatr wieje ulicą, pójście pod wiatr wymaga więcej czasu i energii niż z wiatrem. Innym przykładem WPP jest to, że koszt orki pod górę jest większy niż koszt orki w dół. Jest to modelowane przez wariant badany przez Dussaulta i wsp., Problem orki zjazdowej (DPP).

Algorytm rozgałęzienia i cięcia został opublikowany przez Angela Corberana dla problemu wietrznego listonosza. Algorytm opiera się na heurystycznych i dokładnych metodach manipulowania naruszeniami nierówności nieparzystych.

Aplikacje

Różne problemy kombinatoryczne zostały zredukowane do problemu chińskiego listonosza, w tym znalezienie maksymalnego cięcia w grafie planarnym i obwodu o minimalnej średniej długości w grafie nieskierowanym.

Pługi śnieżne

Zimą często zadawane jest pytanie, który zestaw tras ma najmniejszą (minimalną) maksymalną długość trasy? Zwykle jest to oceniane jako problem z prowadzeniem łuku z wykresem. Czas potrzebny na przejechanie ulicy, znany jako czas martwy, jest krótszy niż czas potrzebny na odśnieżanie ulic (lub dostarczanie poczty lub dostarczanie paczek). Innym aspektem, który należy wziąć pod uwagę przy stosowaniu trasowania po łuku do odśnieżania, jest fakt, że na stromych ulicach oranie pod górę jest albo trudne, albo niemożliwe. Celem jest trasa, która unika orki pod górę na stromych ulicach, która szybciej kończy pracę, maksymalizując czas martwego punktu, aby uzyskać lokalizację. Zostało to wymodelowane za pomocą algorytmu heurystycznego, który przybliża dolną granicę Dussaulta, Goldena i Wasila. To jest problem pługa zjazdowego (DPP). Zespoły śnieżne wolą orać w dół i pod górę. Ten problem zakłada, że warunki są na tyle surowe, że ulice są zamknięte i nie ma ruchu.

Problem orki zjazdowej ignoruje problem orki z pierwszeństwem (PPP), który opiera się na rozsądnym założeniu, że jeśli śnieg jest zbyt głęboki, pług śnieżny nie może zablokować nieodśnieżonej ulicy. DPP przyjmuje założenie, że poziom śniegu jest na tyle niski, że nieodśnieżone ulice mogą być zalane, ale śnieg jest na tyle głęboki, że nie ma ruchu. Jeśli na drogach panuje ruch uliczny, założenie, że nie da się orać pod górę, nie ma już racji bytu. Symulacja nieodśnieżonej ulicy DPP przez około 5% czasu, co jest tematem przyszłych badań teorii grafów i trasowania łuków.

$uwagę$ $łuków$ wykres nieskierowany $gdzie$ jest wierzchołków i węzłów . Każdy $Displaystyle c_ {ij$ reprezentowany przez ma $ja jot$ koszty: } koszt orki od ${\ Displaystyle v_ {i}}$ do ${\ Displaystyle v_ {j}}$ , ${\ Displaystyle c_ {ji} ^ {+}}$ , koszt orki od ${\ Displaystyle v_ {j}}$ do ${\ displaystyle v_ {i}}$ , ${\ Displaystyle c_ {ij} ^ {-}}$ , koszt deadheading od ${\ displaystyle v_ {i }}$ do ${\ Displaystyle v_ {j}}$ ${\ Displaystyle c_ {ji} ^ {-}}$ do , koszt deadheading od ${\ Displaystyle v_ {j}}$ do ${\ displaystyle v_ {i}}$ . Konfiguracja zakłada, że $ma$ ${\ Displaystyle c_ {ij} ^ {+} \ gg c_ {ji} ^ {+} \ gg c_ {ij} ^ {-} \ geq c_ {ji} ^ {-}}$ , stwierdzenia: $jot$ . W praktyce orka w dół zbocza jest dwa razy wydajniejsza niż orka pod górę, a orka na martwy fragment jest dwa razy wydajniejsza niż orka. Algorytm znajduje $ponieważ$ $razy,$ zajezdni , przeorać łuk dwa lewa i prawa strona ulicy zajmują dwa przejazdy do orki.

Najlepsze rozwiązanie zminimalizuje maksymalną długość trasy. Dussault, Golden i Wasil znaleźli algorytm, który nie przekroczył dolnej granicy o 5,5% w ponad 80 testach. Odchylenie wzrastało wraz ze wzrostem złożoności modelu, ponieważ w miarę wzrostu modelu jest więcej przybliżeń niezoptymalizowanych niż przybliżeń zoptymalizowanych. Ulepszenie Dussault et. Algorytm DPP może nakładać kary za zawracanie i skręcanie w lewo lub przechodzenie na wprost przez skrzyżowanie, co zajmuje odpowiednio dodatkowy czas i wpycha śnieg na środek skrzyżowania. (patrz Problem kierowanego wiejskiego listonosza z problemem kar za skręt, często określany poniżej jako DRPP-TP).

k - problem z chińskim listonoszem ( k - CPP)

K - chiński listonosz można sformułować w następujący sposób: „Dając spójny graf ważony krawędziami G i liczby całkowite p i k , zdecyduj, czy istnieje co najmniej k zamkniętych spacerów, takich że każda krawędź G jest zawarta w co najmniej jednym z nich i całkowita waga krawędzi w spacerach wynosi co najwyżej p ?” Proces otrzymywania rozwiązania k -CPP jest NP zupełny. Gutin, Muciaccia i Yeo udowodnili w 2013 r., że k -CPP jest wykonalny przy stałych parametrach. Autorzy udowadniają $-CPP$ k jądro a k to kompletny.

Problem listonosza wiejskiego (RPP) i uogólnienia

Problem wiejskiego listonosza (RPP) sprawia, że niektóre trasy są obowiązkowe i bezwzględne, ale osoba przemierzająca wykres nie musi iść w jednym określonym kierunku. RPP jest NP twarde i kompletne, w ten sam sposób, w jaki kCPP, DPP, PPP są NP twarde. Benevant zbadał uogólnienie tego problemu nazwanego Directed Rural Postman Problem with Turn Penalties (DRPP-TP). Algorytm Benevanta przybliżył rozwiązanie, przekształcając DRPP-TP w asymetryczny problem komiwojażera (ATSP).

Heurystyki i algorytmy

Większość algorytmów wymaga wstępnego przetworzenia wykresu, co upraszcza początkowy wykres poprzez usunięcie wszystkich krawędzi, które nie znajdują się na najkrótszej ścieżce między dwiema wymaganymi krawędziami. Kolejnym uproszczeniem, które dodaje przetwarzanie wstępne, jest to, że przekształca najkrótszą ścieżkę między 2 wymaganymi krawędziami w pojedynczą, niewymaganą krawędź, niezależnie od liczby krawędzi na ścieżce, pod warunkiem, że nie ma wymaganych krawędzi na ścieżce.

Po zakończeniu wstępnego przetwarzania problem można uogólnić na problem kadłuba wypukłego , w którym krawędzie są punktami kadłuba. Problem kadłuba wypukłego można rozwiązać za pomocą programowania liniowego lub algorytmów kadłuba wypukłego, ale proces znajdowania kadłuba wypukłego jest problemem wykładniczym.

Metody rozwiązywania URPP po zakończeniu wstępnego przetwarzania składają się z algorytmu płaszczyzny cięcia oraz metodologii branch & cut .

Złożoność

To jest lista złożoności obliczeniowej dla różnych problemów związanych z trasowaniem łuku.

wariant CP	Klasyczna złożoność	Przybliżenie	Sparametryzowana złożoność
Bezkierunkowy	${\ Displaystyle O (\| V \| ^ {3})}$ algorytm czasowy
Skierowany	${\ Displaystyle O (\| V \| ^ {3})}$ algorytm czasowy ${\ Displaystyle O ((\| E \| - \| V \|) \| V \| ^ {2})}$ algorytm czasowy
Mieszany	NP-zupełny ${\ Displaystyle O (\| V \| ^ {3})}$ -rozwiązywalny czas, jeśli każdy wierzchołek ma parzysty stopień	${\ Displaystyle O (\ max \ {\| V \| ^ {3}, \| A \| (\ max \{\|A\|,\|E\|\})^{2}\})}$ -czynnik czasu 3/2	${\ Displaystyle O (2 ^ {\| E \|} \ cdot \| V \| ^ {3})}$ algorytm czasowy W FPT w odniesieniu do \|A\| W XP w odniesieniu do szerokości drzewa
Wietrzny	NP-zupełny P w niektórych szczególnych przypadkach	Współczynnik 3/2
k-hierarchiczny	NP-zupełny ${\ Displaystyle O (k \| V \| ^ {4})}$ -czas rozwiązywalny, jeśli relacja pierwszeństwa liniowa
Minimalna suma k listonoszy	${\ Displaystyle O (\| V \| ^ {3})}$ -czasowy algorytm z wierzchołkiem urzędu pocztowego, w przeciwnym razie NP-zupełny		W FPT względem k bez wierzchołka urzędu pocztowego
Min-max k listonoszy	NP-zupełny	${\ Displaystyle O (\| V \| ^ {3})} -$ czynnik czasu (2-1 / k)

Lista wariantów prowadzenia łuku


Problem	Skrót	Opis	Uwagi wyjściowe	Przykłady
Problem z trasowaniem łuku	ARP	Określ najmniej kosztowny przebieg określonego podzbioru łuków wykresu, z ograniczeniami lub bez.		Siedem mostów Królewca
Problem z chińskim listonoszem	CPP	graf nieskierowany G z wierzchołkami V i ważonymi krawędziami E	Przemierz każdą krawędź przynajmniej raz minimalnym kosztem	„Listonosz musi pokonać przydzielony mu odcinek przed powrotem na pocztę. Problem polega na znalezieniu najkrótszej odległości dla listonosza”.
Wiejski problem listonosza	RPP	graf nieskierowany G z wierzchołkami V i ważonymi krawędziami E	Przemierz podzbiór krawędzi E przynajmniej raz przy minimalnych kosztach
Skierowany problem listonosza wiejskiego	DRPP
Problem wiejskiego listonosza z karami za obrót	RPP-TP, RPPTP
Wietrzny problem listonosza	WPP
Wietrzny problem listonosza wiejskiego	WRPP
Problem zamiatarki ulicznej	SPP
m-Problem z orką	m-PP
Problem pługa z pojemnością	C-PP
Problem pługa zjazdowego	DPP
Problem pługa zjazdowego z karami za zakręt	DPP-TP
Wiejski problem pługa zjazdowego z karami za zakręt	RDPP-TP
Problem z trasowaniem łuku pojemnościowego	KARP
k-Plough Wietrzny problem listonosza wiejskiego	k-WRPP
Min-Max Problem pługa zjazdowego z wieloma pługami	MM k-DPP
Min-Max Wietrzny wiejski problem listonosza	MM k-WRPP
Orka z problemem pierwszeństwa	PPP
Min-Max Rozszerzony problem pługa zjazdowego	MM k-DPPE
Problem chińskiego listonosza z pojemnością	CCPP
Skierowany problem chińskiego listonosza	DCPP
Skierowany problem listonosza wiejskiego	DRPP
Rozszerzony problem z trasowaniem łuku pojemnościowego	ECARP
Hierarchiczny problem chińskiego listonosza	HCPP
Problem z trasowaniem łuku pojemnościowego mieszanego	MCARP
Mieszany problem chińskiego listonosza	MCPP
Problem z układnicą	SCP	Niektóre łuki należy przebyć co najmniej raz w jednym kierunku, ale można je przebyć tyle razy w drugim kierunku
Problem komiwojażera	TSP
Problem z kierowaniem nieukierunkowanego łuku pojemnościowego	UCARP
Nieukierunkowany problem wiejskiego listonosza	URPP
Problem z wyznaczaniem tras pojazdów	VRP
Min-Max Problem listonosza wiejskiego z wieloma zajezdniami	MMMDRPP
Uogólniony problem wyznaczania tras pojazdów	GVRP

Linki zewnętrzne

Zobacz też