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

W jaki sposób dostawcy map (tacy jak Google lub Yahoo! Maps) sugerują wskazówki dojazdu?

Mam na myśli, że prawdopodobnie mają rzeczywiste dane w jakiejś formie, z pewnością obejmujące odległości, ale może także takie rzeczy, jak prędkości jazdy, obecność chodników, rozkład jazdy pociągów itp. Załóżmy jednak, że dane były w prostszym formacie, powiedzmy na bardzo dużym ukierunkowanym wykresie z obciążnikami krawędzi odzwierciedlającymi odległości. Chcę być w stanie szybko obliczyć kierunki z jednego dowolnego punktu do drugiego. Czasami punkty te będą blisko siebie (w obrębie jednego miasta), a czasem będą daleko od siebie (biegowe).

Algorytmy wykresów, takie jak algorytm Dijkstry, nie będą działać, ponieważ wykres jest ogromny. Na szczęście algorytmy heurystyczne, takie jak A *, prawdopodobnie będą działać. Jednak nasze dane są bardzo ustrukturyzowane, a może może działać jakieś podejście warstwowe? (Na przykład przechowuj wstępnie obliczone kierunki między niektórymi „kluczowymi” punktami daleko od siebie, a także niektóre lokalne kierunki. Następnie wskazówki dla dwóch odległych punktów będą obejmować lokalne kierunki do kluczowych punktów, globalne kierunki do innego kluczowego punktu, a następnie lokalne wskazówki ponownie.)

Jakie algorytmy są faktycznie stosowane w praktyce?

PS. To pytanie było motywowane znalezieniem dziwactw w internetowych mapach. W przeciwieństwie do nierówności trójkąta, czasami Google Maps uważa, że XZ trwa dłużej i jest dalej niż przy użyciu punktu pośredniego, jak w XYZ . Ale może ich kierunki piesze zoptymalizują się również pod kątem innego parametru?

PPS. Oto kolejne naruszenie nierówności trójkąta, które sugeruje (dla mnie), że używają one pewnego rodzaju podejścia wielopoziomowego: XZ kontra XYZ . Ten pierwszy wydaje się wykorzystywać wybitny Boulevard de Sebastopol, chociaż jest nieco na uboczu.

Edycja : Żaden z tych przykładów nie wydaje się już działać, ale oba działały w momencie publikacji oryginalnego postu.

Mówiąc jak ktoś, kto spędził 18 miesięcy pracując w firmie mapującej, która obejmowała pracę nad algorytmem routingu ... tak, Dijkstra działa, z kilkoma modyfikacjami:

• Zamiast robić raz Dijkstry od źródła do miejsca docelowego, zaczynasz na każdym końcu i rozwijasz obie strony, aż spotkają się na środku. To eliminuje mniej więcej połowę pracy (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
• Aby uniknąć eksploracji zaułków każdego miasta między źródłem a miejscem docelowym, możesz mieć kilka warstw danych mapy: Warstwa „autostrad”, która zawiera tylko autostrady, „wtórna” warstwa, która zawiera tylko drugorzędne ulice i tak dalej. Następnie eksplorujesz tylko mniejsze sekcje bardziej szczegółowych warstw, rozwijając w razie potrzeby. Oczywiście ten opis pomija wiele szczegółów, ale masz pomysł.

Dzięki modyfikacjom w tym zakresie możesz nawet trasować trasy w bardzo rozsądnych ramach czasowych.

To pytanie było aktywnym obszarem badań w ostatnich latach. Główną ideą jest wykonanie przetwarzania wstępnego na wykresie raz , aby przyspieszyć wszystkie kolejne zapytania . Dzięki tym dodatkowym informacjom można bardzo szybko obliczyć trasy. Mimo to algorytm Dijkstry jest podstawą wszystkich optymalizacji.

Arachnid opisał użycie wyszukiwania dwukierunkowego i przycinania krawędzi na podstawie informacji hierarchicznych. Te techniki przyspieszania działają całkiem dobrze, ale najnowsze algorytmy przewyższają te techniki pod każdym względem. Dzięki obecnym algorytmom najkrótsze ścieżki można obliczyć w znacznie krótszym czasie niż jedna milisekunda w kontynentalnej sieci drogowej. Szybka implementacja niezmodyfikowanego algorytmu Dijkstry zajmuje około 10 sekund .

Artykuł Algorytmy szybkiego planowania inżynierii zawiera przegląd postępów badań w tej dziedzinie. Więcej informacji można znaleźć w źródłach tego dokumentu.

Najszybsze znane algorytmy nie wykorzystują w danych informacji o hierarchicznym stanie drogi, tzn. Czy jest to autostrada, czy droga lokalna. Zamiast tego obliczają na etapie wstępnego przetwarzania własną hierarchię, która została zoptymalizowana w celu przyspieszenia planowania trasy. Tego wstępnego obliczenia można następnie użyć do przycięcia wyszukiwania: daleko od początku i do celu powolne drogi nie muszą być uwzględniane podczas algorytmu Dijkstry. Korzyści to bardzo dobra wydajność i gwarancja poprawności wyniku.

Pierwsze zoptymalizowane algorytmy planowania trasy dotyczyły wyłącznie statycznych sieci dróg, co oznacza, że ​​krawędź na wykresie ma stałą wartość kosztu. W praktyce nie jest to prawdą, ponieważ chcemy brać pod uwagę dynamiczne informacje, takie jak korki lub ograniczenia zależne od pojazdu. Najnowsze algorytmy mogą również poradzić sobie z takimi problemami, ale nadal istnieją problemy do rozwiązania, a badania trwają.

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

Po prostu zajęcie się przypadkami naruszenia nierówności trójkąta, mam nadzieję, że dodatkowym czynnikiem, dla którego optymalizują, jest zdrowy rozsądek. Niekoniecznie potrzebujesz najkrótszej lub najszybszej trasy, ponieważ może to prowadzić do chaosu i zniszczenia . Jeśli chcesz, aby Twoje wskazówki preferowały główne trasy, które są przyjazne dla ciężarówek i mogą poradzić sobie z wysłaniem ich przez każdego kierowcę nawigacji satelitarnej, szybko odrzucasz nierówność trójkąta [1].

Jeśli Y jest wąską ulicą mieszkalną między X i Z, prawdopodobnie chcesz skorzystać ze skrótu przez Y, jeśli użytkownik wyraźnie poprosi o XYZ. Jeśli poprosą o XZ, powinni trzymać się głównych dróg, nawet jeśli jest to nieco dalej i zajmuje trochę dłużej. Jest podobny do paradoksu Braessa - jeśli wszyscy spróbują wybrać najkrótszą i najszybszą trasę, wynikające z tego zatłoczenie oznacza, że ​​nie jest to już najszybsza trasa dla nikogo. Odtąd odchodzimy od teorii grafów do teorii gier.

[1] W rzeczywistości wszelka nadzieja, że ​​wyprodukowane odległości będą funkcją odległości w sensie matematycznym, umiera, gdy pozwolisz na drogi jednokierunkowe i utracisz wymóg symetrii. Utrata nierówności trójkąta to po prostu wcieranie soli w ranę.

Oto najszybsze na świecie algorytmy routingu porównane i sprawdzone pod kątem poprawności:

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

Oto dyskusja technologiczna Google na ten temat:

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

Oto implementacja algorytmu hierarchii autostrad omówionego przez schultes (obecnie tylko w Berlinie, piszę interfejs, a także tworzona jest wersja mobilna):

http://tom.mapsforge.org/

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

Stworzyłem jednak niestandardowy system optymalizacji łańcucha dostaw dla firmy energetycznej, który obejmował aplikację do planowania i routingu dla ich floty ciężarówek. Jednak nasze kryteria dotyczące routingu były znacznie bardziej specyficzne dla biznesu niż tam, gdzie jest budowa, spowolnienie ruchu lub zamknięcie pasów ruchu.

Zastosowaliśmy technikę zwaną ACO (optymalizacja kolonii mrówek) do planowania i trasowania ciężarówek. Ta technika jest techniką sztucznej inteligencji, która została zastosowana do problemu sprzedawcy podróżującego w celu rozwiązania problemów z routingiem. Sztuczka z ACO polega na zbudowaniu obliczenia błędu w oparciu o znane fakty dotyczące routingu, aby model rozwiązywania wykresów wiedział, kiedy wyjść (kiedy błąd jest wystarczająco mały).

Możesz google ACO lub TSP, aby znaleźć więcej na temat tej techniki. Jednak nie użyłem do tego żadnego z narzędzi AI typu open source, więc nie mogę zaproponować żadnego (choć słyszałem, że SWARM był dość obszerny).

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

Ten argument niekoniecznie się utrzymuje, ponieważ Dijkstra zwykle nie patrzy na pełny wykres, ale raczej na bardzo mały podzbiór (im lepiej wykres jest połączony, tym mniejszy jest ten podzbiór).

Dijkstra może faktycznie osiągać dobre wyniki w przypadku dobrze zachowanych wykresów. Z drugiej strony, przy starannej parametryzacji A * zawsze będzie działać tak samo dobrze lub lepiej. Czy próbowałeś już, jak będzie działać na twoich danych?

Powiedziałbym również, że bardzo chciałbym usłyszeć o doświadczeniach innych ludzi. Oczywiście szczególnie interesujące są wybitne przykłady, takie jak wyszukiwanie w Mapach Google. Mogłem sobie wyobrazić coś w rodzaju heurystyki najbliższego sąsiada.

Obecny stan techniki w zakresie czasów zapytań dla statycznych sieci drogowych to algorytm znakowania Hub zaproponowany przez Abraham i in. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Niedawno opublikowano kompleksową i doskonale napisaną ankietę w tej dziedzinie jako raport techniczny Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

Krótka wersja to ...

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

Routing węzłów tranzytowych jest nieco wolniejszy, chociaż wymaga tylko około 2 GiB pamięci i ma szybszy czas wstępnego przetwarzania.

Hierarchie skurczów zapewniają niezły kompromis między szybkim czasem wstępnego przetwarzania, niskim zapotrzebowaniem na miejsce (0,4 GiB) i szybkim czasem zapytania.

Żaden algorytm nie jest całkowicie zdominowany ...

Ta rozmowa techniczna Petera Sandersa na temat Google może być interesująca

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

Także ta rozmowa Andrew Goldberga

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

Implementacja hierarchii skurczów jest dostępna na stronie internetowej grupy badawczej Petera Sandersa w KIT. http://algo2.iti.kit.edu/english/routeplanning.php

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

Jestem trochę zaskoczony, że nie widzę wspomnianego tutaj algorytmu Floyda Warshalla . Ten algorytm działa bardzo podobnie do algorytmu Dijkstry. Ma także jedną bardzo fajną funkcję, która pozwala na obliczenie tak długo, jak chcesz kontynuować, pozwalając na więcej pośrednich wierzchołków. W ten sposób szybko odnajdzie trasy, które wykorzystują autostrady międzystanowe lub autostrady.

Robiłem to całkiem sporo razy, 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ą linii prostej jako funkcji heurystycznej. Ale wtedy potrzebujesz jakiegoś rodzaju współrzędnych dla każdego punktu (przecięcia lub wierzchołka) na mapie. Możesz także wypróbować różne wagi dla funkcji heurystycznej, tj

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

gdzie k jest jakąś stałą większą niż 0.

Prawdopodobnie podobna do odpowiedzi na wstępnie obliczonych trasach między głównymi lokalizacjami i mapami warstwowymi, ale rozumiem, że w grach, aby przyspieszyć A *, masz mapę, która jest bardzo zgrubna w zakresie nawigacji makro i dokładną mapę dla nawigacja do granicy kierunków makro. Masz więc 2 małe ścieżki do obliczenia, a zatem twoje pole wyszukiwania jest znacznie mniejsze niż zwykła ścieżka do miejsca docelowego. A jeśli zajmujesz się tym często, masz dużo tych danych wstępnie obliczonych, więc przynajmniej część wyszukiwania to wyszukiwanie wstępnie obliczonych danych, a nie szukanie ścieżki.

To z mojej strony czysta spekulacja, ale przypuszczam, że mogą użyć struktury danych mapy wpływów nakładającej się na ukierunkowaną mapę, aby zawęzić domenę wyszukiwania. Umożliwiłoby to algorytmowi wyszukiwania skierowanie ścieżki na główne trasy, gdy pożądana podróż jest długa.

Biorąc pod uwagę, że jest to aplikacja Google, uzasadnione jest również przypuszczenie, że wiele magii odbywa się poprzez intensywne buforowanie. :) Nie zdziwiłbym się, gdyby zapamiętanie w pamięci podręcznej 5% najpopularniejszych żądań trasy na Mapach Google pozwoliło na uzyskanie dużej części (20%? 50%?) Żądań w odpowiedzi na proste sprawdzenie.

Miałem więcej przemyśleń na ten temat:

1) Pamiętaj, że mapy reprezentują organizację fizyczną. Przechowuj szerokość / długość geograficzną każdego skrzyżowania. Nie musisz sprawdzać znacznie poza punktami, które leżą w kierunku celu. Tylko jeśli zostaniesz zablokowany, musisz wyjść poza to. Jeśli przechowujesz nakładkę doskonałych połączeń, możesz ją jeszcze bardziej ograniczyć - normalnie nigdy nie natkniesz się na jedno z nich w sposób odbiegający od miejsca docelowego.

2) Podziel świat na całą grupę stref określonych 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 początkowej i końcowej strefy z Twojej lokalizacji do każdego punktu połączenia, dla stref pomiędzy mapą między punktami połączenia. (Podejrzewam, że wiele z tych ostatnich jest już wstępnie obliczonych).

Pamiętaj, że strefy mogą być mniejsze niż obszar metropolitalny. Każde miasto o cechach terenu, które go dzielą (powiedzmy, rzeka), będzie mieć wiele stref.

Byłem bardzo ciekawy zastosowanej heurystyki, kiedy jakiś czas temu dostaliśmy trasy z tego samego miejsca początkowego w pobliżu Santa Rosa, do dwóch różnych kempingów w Parku Narodowym Yosemite. Te różne miejsca docelowe stworzyły całkiem różne trasy (przez I-580 lub CA-12) pomimo faktu, że obie trasy zbiegły się w ciągu ostatnich 100 mil (wzdłuż CA-120), zanim ponownie rozdzieliły się o kilka mil na końcu. To było dość powtarzalne. Dwie trasy dzieliły od siebie około 50 mil na około 100 mil, ale odległości / czasy były bardzo zbliżone do siebie, jak można się spodziewać.

Niestety nie mogę tego odtworzyć - algorytmy musiały się zmienić. Ale ciekawi mnie algorytm. Mogę tylko spekulować, że było pewne przycinanie kierunkowe, które okazało się wyjątkowo wrażliwe na niewielką różnicę kątową między miejscami docelowymi widzianymi z daleka, lub były różne wstępnie obliczone segmenty wybrane przez wybór ostatecznego miejsca docelowego.

Mówiąc o GraphHopper , szybkim narzędziu planowania tras Open Source opartym 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 połowę węzłów. Z dwukierunkową Dijkstra trasa przez całe Niemcy zajmuje już 1 sekundę (w trybie samochodowym), w C prawdopodobnie będzie to tylko około 0,5s;)

Utworzyłem animowany gif poszukiwania ścieżki rzeczywistym z dwukierunkowym Dijkstra tutaj . Jest też kilka pomysłów na przyspieszenie Dijkstry, takich jak robienie A *, czyli „zorientowanej na cel Dijkstry”. Mam również tworzyć GIF animacji dla niego.

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

Problem polega na tym, że podczas przeszukiwania ścieżki należy zbadać wszystkie węzły między lokalizacjami, a to jest naprawdę kosztowne, ponieważ już w Niemczech jest ich kilka milionów. Ale dodatkowym problemem Dijkstry itp. Jest to, że takie wyszukiwania wymagają dużej ilości pamięci RAM.

Istnieją rozwiązania heurystyczne, ale także dokładne rozwiązania, które organizują graf (sieć drogową) w hierarchiczne warstwy, 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 .

W przypadku GraphHopper zdecydowałem się na użycie hierarchii skurczów, ponieważ jest względnie „łatwa” do wdrożenia i nie zajmuje wieków na przygotowanie wykresu. Nadal skutkuje to bardzo krótkim czasem reakcji, który można przetestować w naszym internetowym wystąpieniu GraphHopper Maps . Np. Z południowej Afryki do wschodnich Chin, co daje dystans 23000 km i prawie 14 dni jazdy samochodem i zajmuje tylko ~ 0,1 sekundy na serwerze.

Pracowałem nad routingiem od kilku lat, a ostatnio nastąpił gwałtowny wzrost aktywności spowodowany potrzebami moich klientów i stwierdziłem, że A * jest wystarczająco szybki; naprawdę nie ma potrzeby szukania optymalizacji lub bardziej złożonych algorytmów. Rutowanie po 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 skrzyżowania, w pamięci. Głównym obciążeniem czasowym jest czas potrzebny do utworzenia tej sieci. Niektóre przybliżone liczby oparte na zwykłym laptopie z systemem Windows i routingu w całej Hiszpanii: czas potrzebny na utworzenie 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 dowolnej liczby obliczeń routingu. Jeśli twój algorytm oznaczył węzły w jakiś sposób, aby zapisać najlepszą trasę (całkowity koszt do bieżącego węzła i najlepszy łuk do niego) - jak to ma miejsce w A * - musisz zresetować lub usunąć tę starą informację. Zamiast przechodzić przez setki tysięcy węzłów, łatwiej jest użyć systemu numerów generacji. Oznacz każdy węzeł numerem generacji jego danych; zwiększ numer generacyjny podczas obliczania nowej trasy; każdy węzeł ze starszym numerem generacji jest nieaktualny i jego informacje można zignorować.

Widzę, co jest granego z mapami w PO:

Spójrz na trasę z określonym punktem pośrednim: Trasa cofa się lekko 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 obliczy najkrótsze ścieżki między wszystkimi wierzchołkami na wykresie. Umożliwi to wstępne obliczenie ścieżek zamiast konieczności obliczania ścieżki za każdym razem, gdy ktoś chce znaleźć najkrótszą ścieżkę między źródłem a miejscem docelowym. Algorytm Floyda-Warshalla to algorytm najkrótszej ścieżki składający się z wszystkich par.

Mapy nigdy nie uwzględniają całej mapy. Domyślam się: - 1. W zależności od twojej lokalizacji, ładują miejsce i punkty orientacyjne w tym miejscu. 2. Podczas wyszukiwania miejsca docelowego, to znaczy, gdy ładują one drugą część mapy i tworzą wykres z dwóch miejsc, a następnie stosują 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. Możesz się do tego również odnieść.