Jakie algorytmy obliczają kierunki z punktu A do punktu B na mapie?

[[0]} to pytanie było aktywnym obszarem badań w ostatnich latach. Główną ideą jest wykonanie wstępnego przetwarzania na wykresie raz, Aby przyspieszyć Wszystkie następujące zapytania. Dzięki tym dodatkowym informacjom trasy mogą być obliczane bardzo szybko. Mimo to, algorytm Dijkstry jest podstawą wszystkich optymalizacji.

Arachnid opisał użycie dwukierunkowego wyszukiwania i przycinania krawędzi w oparciu o informacje hierarchiczne. Te speedup techniki działają całkiem dobrze, ale najnowsze algorytmy przewyższają te techniki wszelkimi sposobami. Dzięki obecnym algorytmom najkrótsze ścieżki mogą być obliczane w znacznie krótszym czasie niż Jedna milisekunda na kontynentalnej sieci drogowej. Szybka implementacja niezmodyfikowanego algorytmu Dijkstry wymaga około 10 sekund .

Artykuł inżynierskie algorytmy szybkiego planowania trasy zawiera przegląd postępów badań w tej dziedzinie. Zobacz też więcej informacji na ten temat można znaleźć w tym dokumencie.

Najszybsze znane algorytmy nie wykorzystują informacji o hierarchicznym stanie drogi w danych, tzn. czy jest to autostrada czy droga lokalna. Zamiast tego obliczają na etapie wstępnego przetwarzania własną hierarchię, która zoptymalizowała się w celu przyspieszenia planowania trasy. Ta wstępna kalkulacja może być następnie wykorzystana do przycinania wyszukiwania: daleko od początku i celu powolne drogi nie muszą być brane pod uwagę podczas algorytmu Dijkstry. Korzyści są bardzo Dobra Wydajność i poprawność Gwarancja na wynik.

Pierwsze zoptymalizowane algorytmy planowania trasy dotyczyły tylko statycznych sieci drogowych, co oznacza, że krawędź na wykresie ma stałą wartość kosztów. Nie jest to prawdą w praktyce, ponieważ chcemy wziąć pod uwagę dynamiczne informacje, takie jak korki lub ograniczenia zależne od pojazdu. Najnowsze algorytmy mogą również radzić sobie z takimi problemami, ale nadal są problemy do rozwiązania i badania idą on

Jeśli potrzebujesz najkrótszych odległości ścieżek, aby obliczyć rozwiązanie dla TSP, prawdopodobnie interesują Cię macierze, które zawierają wszystkie odległości między twoimi źródłami i miejscami docelowymi. W tym celu można rozważyć obliczenie wielu do wielu najkrótszych ścieżek przy użyciu hierarchii autostrad. Zauważ, że zostało to poprawione przez nowsze podejścia w ciągu ostatnich 2 lat.

Po prostu rozwiązując łamanie nierówności trójkąta, miejmy nadzieję, że dodatkowym czynnikiem, dla którego optymalizują, jest zdrowy rozsądek. Nie koniecznie chcesz najkrótszej lub najszybszej trasy, ponieważ może ona doprowadzić do chaosu oraz zniszczenie . Jeśli chcesz, aby Twoje Kierunki preferowały główne trasy, które są przyjazne dla ciężarówek i mogą poradzić sobie z wysłaniem każdego kierowcy śledzącego nawigację satelitarną, szybko odrzucisz nierówność trójkąta[1].

Jeśli Y jest wąskim mieszkaniem ulica między X i Z, prawdopodobnie chcesz używać skrótu via y tylko wtedy, gdy użytkownik wyraźnie prosi o X-Y-Z. Jeśli pyta o X-Z, powinien trzymać się głównych dróg, nawet jeśli jest trochę dalej i trwa nieco dłużej. Jest to podobne do paradoksu Braessa - jeśli każdy próbuje pokonać najkrótszą i najszybszą trasę, wynikające z tego zatory oznaczają, że nie jest to już najszybsza trasa dla nikogo. Stąd przechodzimy od teorii grafów do teorii gier.

[1] w rzeczywistości każda nadzieja, że wytworzone odległości będą funkcją odległości w sensie matematycznym, gdy dopuszczamy drogi jednokierunkowe i tracimy wymóg symetrii. Utrata nierówności trójkąta to po prostu pocieranie solą w ranie.

Oto najszybsze algorytmy routingu na świecie porównane i sprawdzone pod względem poprawności:

Http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Oto Google Tech talk na ten temat:

Http://www.youtube.com/watch?v=-0ErpE8tQbw

Oto implementacja algorytmu highway-hierarchies omówiona przez schultesa (obecnie tylko w Berlinie piszę interfejs, a wersja mobilna jest rozwijana jako dobrze):

Http://tom.mapsforge.org/

Algorytmy grafowe, takie jak algorytm Dijkstry, nie będą działać, ponieważ Graf jest ogromny.

Ten argument nie musi się utrzymywać, ponieważ Dijkstra zwykle nie patrzy na kompletny Wykres, ale raczej na bardzo mały podzbiór (im lepiej Graf jest połączony, tym mniejszy ten podzbiór).

Dijkstra może rzeczywiście działać dość dobrze dla dobrze zachowanych Wykresów. Z drugiej strony, przy starannej parametryzacji A* zawsze będzie działać tak samo dobrze lub lepiej. Mieć próbowałeś już, jak to będzie działać na Twoich danych?

Nie pracowałem wcześniej na Google, Microsoft lub Yahoo Maps, więc nie mogę powiedzieć, jak one działają.

Jednak zaprojektowałem niestandardowy system optymalizacji łańcucha dostaw dla firmy energetycznej, który zawierał aplikację do planowania i wyznaczania tras dla ich floty samochodów ciężarowych. Jednak nasze kryteria dotyczące wyznaczania tras były o wiele bardziej specyficzne dla biznesu niż gdzie jest budowa, spowolnienie ruchu lub zamknięcie pasa ruchu.

Zastosowaliśmy technikę zwaną Aco (Ant colony optimization), aby zaplanować i trasy ciężarówek. Technika ta jest techniką AI, która została zastosowana do problemu komiwojażera w celu rozwiązania problemów z routingiem. Sztuczka z ACO polega na zbudowaniu obliczenia błędu na podstawie znanych faktów routingu, aby Model rozwiązywania Wykresów wiedział, kiedy zakończyć (kiedy błąd jest wystarczająco mały).

Możesz google ACO lub TSP, aby znaleźć więcej na temat tej techniki. Nie używałem do tego żadnego z narzędzi AI open-source, więc nie mogę go zasugerować (choć słyszałem, że Rój był ładny kompleksowe).

Obecny stan techniki pod względem czasów zapytań dla statycznych sieci drogowych jest algorytm znakowania węzła zaproponowany przez Abrahama et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Bardzo dobrze napisana ankieta została niedawno opublikowana jako Microsoft technical report http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

Krótka wersja jest...

Algorytm znakowania piasty zapewnia najszybsze zapytania dla statycznych sieci drogowych, ale wymaga dużej ilości pamięci ram do uruchomienia (18 GiB).

Transit node routing jest nieco wolniejszy, chociaż wymaga tylko około 2 GiB pamięci i ma szybszy czas wstępnego przetwarzania.

Hierarchie skurczowe zapewniają dobry kompromis między szybkim czasem wstępnego przetwarzania, niskim zapotrzebowaniem na miejsce (0,4 GiB) i szybkim czasem zapytań.

Żaden algorytm nie jest całkowicie dominujący...

Ta rozmowa Google tech przez Petera Sandersa może być interesująca

Https://www.youtube.com/watch?v=-0ErpE8tQbw

Również ta rozmowa Andrew Goldberga

Https://www.youtube.com/watch?v=WPrkc78XLhw

Implementacja open source hierarchii skurczowych jest dostępna na stronie internetowej Peter Sanders research group pod adresem KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Również łatwo dostępny wpis na blogu napisany przez Microsoft na temat użycia algorytmu CRP... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Jestem trochę zaskoczony, że nie widzę algorytmu Floyda Warshalla wymienionego tutaj. Ten algorytm działa bardzo podobnie do Dijkstry. ma również jedną bardzo ładną funkcję, która pozwala na obliczanie tak długo, jak chcesz kontynuować pozwalając więcej pośrednich wierzchołków. Tak więc naturalnie znajdzie trasy, które korzystają z międzystanowych lub autostrad dość szybko.

Robiłem to wiele razy, właściwie, próbując kilku różnych metod. W zależności od rozmiaru (geograficznego) mapy, warto rozważyć użycie funkcji haversine jako heurystyki.

Najlepszym rozwiązaniem, jakie zrobiłem, było użycie a* z odległością w linii prostej jako funkcji heurystycznej. Ale potem trzeba jakieś Współrzędne dla każdego punktu (przecięcia lub wierzchołka) na mapie. Można również wypróbować różne wagi dla funkcji heurystycznej, tj.

f(n) = k*h(n) + g(n)

Gdzie k jest pewną stałą większą niż 0.

Prawdopodobnie podobne do odpowiedzi na wstępnie obliczonych tras między głównymi lokalizacjami i map warstwowych, ale rozumiem, że w grach, aby przyspieszyć a*, masz mapę, która jest bardzo gruba do nawigacji makro, i drobnoziarnistą mapę do nawigacji do granicy kierunków makro. Więc masz 2 małe ścieżki do obliczenia, a zatem przestrzeń wyszukiwania jest znacznie znacznie mniejsza niż po prostu robi jedną ścieżkę do miejsca docelowego. A jeśli zajmujesz się tym często, będziesz miał wiele z tych danych jest wstępnie obliczonych, więc przynajmniej część wyszukiwania polega na wyszukiwaniu wstępnie obliczonych danych, a nie na wyszukiwaniu ścieżki.

Mam jeszcze kilka przemyśleń na ten temat:

1) pamiętaj, że mapy reprezentują fizyczną organizację. Zapisz szerokość / długość geograficzną każdego skrzyżowania. Nie musisz sprawdzać znacznie poza punktami leżącymi w kierunku celu. Tylko jeśli znajdziesz się zablokowany, musisz wyjść poza to. Jeśli przechowujesz nakładkę z doskonałymi połączeniami, możesz ją ograniczyć jeszcze bardziej-Zwykle nigdy nie przejdziesz przez jedno z nich w sposób, który odejdzie od Twojego końcowego miejsce.

2) podziel świat na całą masę stref zdefiniowanych przez ograniczoną łączność, zdefiniuj wszystkie punkty łączności między strefami. Znajdź strefy, w których znajduje się Twoje źródło i cel, dla trasy strefy początkowej i końcowej z Twojej lokalizacji do każdego punktu połączenia, dla stref między po prostu Mapuj między punktami połączenia. (Podejrzewam, że wiele z tych ostatnich jest już wstępnie obliczonych.)

Zauważ, że strefy mogą być mniejsze niż obszar Metropolitalny. Każde miasto z terenem cechy, które dzielą go (powiedzmy, rzeka) będzie wiele stref.

Byłem bardzo ciekawy heurystyki użytej, kiedy jakiś czas temu dostaliśmy trasy z tego samego miejsca startu w pobliżu Santa Rosa, do dwóch różnych kempingów w Parku Narodowym Yosemite. Te różne kierunki produkowały zupełnie różne trasy (via I-580 lub CA-12), pomimo faktu, że obie trasy zbiegały się przez ostatnie 100 mil (wzdłuż CA-120), a następnie ponownie rozeszły się o kilka mil na końcu. To było dość powtarzalne. Dwie trasy oddalone były od siebie o ok., ale odległości/czasy były dość blisko siebie, jak można się było spodziewać.

Niestety nie mogę tego odtworzyć-algorytmy musiały się zmienić. Ale zaciekawił mnie algorytm. Wszystko, co mogę spekulować, to to, że było jakieś kierunkowe przycinanie, które stało się wyjątkowo wrażliwe na niewielką różnicę kątową między celami, widzianymi z daleka, lub były różne wstępnie obliczone segmenty wybrane przez wybór ostatecznego miejsca przeznaczenia.

A propos GraphHopper , szybki Open Source route planner oparty na OpenStreetMap, przeczytałem trochę literatury i zaimplementowałem kilka metod. Najprostszym rozwiązaniem jest Dijkstra, a prostym ulepszeniem jest dwukierunkowa Dijkstra, która bada mniej więcej tylko połowę węzłów. Z dwirctional Dijkstra trasa przez całe Niemcy trwa już 1sec( w trybie samochodowym), w C to pewnie tylko 0,5 S lub tak ;)

Stworzyłem animowany gif z prawdziwego wyszukiwania ścieżek z dwukierunkową Dijkstrą tutaj . Istnieją również inne pomysły, aby sprawić, by Dijkstra była szybsza , Jak Robienie*, która jest "zorientowaną na cel Dijkstrą". Ponadto stworzyłem do tego GIF-animację.

Ale jak to zrobić (dużo) szybciej?

Problem polega na tym, że dla przeszukiwania ścieżki wszystkie węzły między lokalizacjami muszą być zbadane i jest to naprawdę kosztowne, ponieważ już w Niemczech jest ich kilka milionów. Ale dodatkowy punkt bólu Dijkstry itp czy takie wyszukiwania używają dużo pamięci RAM.

Istnieją rozwiązania heurystyczne, ale także dokładne rozwiązania, które organzują Wykres (sieć drogowa) w warstwach hierarchicznych, oba mają zalety i wady i głównie rozwiązują problem prędkości i pamięci RAM. Niektóre z nich wymieniłem w tej odpowiedzi .

Dla Graphhoppera zdecydowałem się użyć hierarchii skurczowej , ponieważ jest to stosunkowo "łatwe" do wdrożenia i nie zajmuje wiele czasu na przygotowanie wykresu. To nadal skutkuje bardzo szybko Czas odpowiedzi, jak można przetestować na naszej instancji online GraphHopper Mapy . Np. Z RPA do wschodnich Chin co daje 23000km dystansu i prawie 14 dni jazdy samochodem i zajęło tylko ~0.1 s na serwerze.

To czysta spekulacja z mojej strony, ale przypuszczam, że mogą użyć struktury danych mapy wpływu nakładającej się na kierowaną mapę w celu zawężenia domeny wyszukiwania. Pozwoli to algorytmowi wyszukiwania skierować ścieżkę do głównych tras, gdy pożądana podróż jest długa.

Biorąc pod uwagę, że jest to aplikacja Google, można również przypuszczać, że wiele magii odbywa się za pomocą rozległego buforowania. :) Nie zdziwiłbym się, gdyby buforowanie top 5% najczęstszych zapytań o trasę Mapy Google dozwolone dla dużego kawałka (20%? 50%?) wniosków, na które należy odpowiedzieć prostym przeglądem.

Pracowałem nad routingiem od kilku lat, z ostatnim impulsem aktywności spowodowanym potrzebami moich klientów i odkryłem, że A* jest wystarczająco szybki; naprawdę nie ma potrzeby szukać optymalizacji lub bardziej złożonych algorytmów. Routing na ogromnym wykresie nie stanowi problemu.

Ale prędkość zależy od posiadania całej sieci routingu, przez co mam na myśli skierowany Wykres łuków i węzłów reprezentujących odpowiednio segmenty trasy i węzły, w pamięci. Główny czas napowietrzność to czas potrzebny na stworzenie tej sieci. Niektóre przybliżone dane oparte na zwykłym laptopie z systemem Windows i trasy w całej Hiszpanii: czas potrzebny na stworzenie sieci: 10-15 sekund; czas potrzebny na obliczenie trasy: zbyt krótki, aby zmierzyć.

Inną ważną rzeczą jest możliwość ponownego wykorzystania sieci do tak wielu obliczeń routingu, jak chcesz. Jeśli twój algorytm oznaczał węzły w jakiś sposób, aby nagrać najlepszą trasę (całkowity koszt do bieżącego węzła, a najlepszy łuk do it) - Jak to trzeba W* - trzeba zresetować lub wyczyścić te stare informacje. Zamiast przechodzić przez setki tysięcy węzłów, łatwiej jest korzystać z systemu numerów generacji. Zaznacz każdy węzeł numerem generacji jego danych; zwiększ numer generacji przy obliczaniu nowej trasy; każdy węzeł ze starszym numerem generacji jest przestarzały, a jego Informacje mogą być ignorowane.

Widzę o co chodzi z mapami w OP:

Spójrz na trasę z określonym punktem pośrednim: Trasa biegnie lekko do tyłu z powodu tej drogi, która nie jest prosta.

Jeśli ich algorytm nie cofnie się, nie zobaczy krótszej trasy.

Algorytm najkrótszej ścieżki dla wszystkich par wyliczy najkrótsze ścieżki między wszystkimi wierzchołkami grafu. Pozwoli to na wstępne obliczanie ścieżek zamiast wymagać, aby ścieżka była obliczana za każdym razem, gdy ktoś chce znaleźć najkrótszą ścieżkę między źródłem a miejscem docelowym. Algorytm Floyda-Warshalla jest algorytmem najkrótszej ścieżki dla wszystkich par.

Mapy Nigdy nie biorą pod uwagę całej mapy. Zgaduję, że:- 1. Zgodnie z Twoją lokalizacją, ładują miejsce i punkty orientacyjne na tym miejscu. 2. Podczas wyszukiwania miejsca docelowego, to jest, gdy załadować drugą część mapy i zrobić Wykres z dwóch miejsc, a następnie zastosować algorytmy najkrótszej ścieżki.

Istnieje również ważna technika programowania dynamicznego, która, jak podejrzewam, jest używana do obliczania najkrótszych ścieżek. Do tego też możesz się odnieść.