Czy w bazach danych GIS są nowsze algorytmy routingu (niż Dijkstra, A *)?

Istnieją prace takie jak Reach for A * od naukowców Microsoft i Highway Hierarchies Sandersa i Schtolza (jeśli poprawnie przeliteruję nazwę) z Karlsruhe Uni . Oba z nich znacznie zmniejszają kolejność obliczeń i przyspieszają tysiące razy na dużych wykresach (zobacz wyniki w połączonych dokumentach). Ta ostatnia praca doprowadziła do stworzenia Open Source Routing Machine , która niestety nie jest wystarczająco popularna i nie jest przystosowana (nie mogłem jej skompilować, chociaż bardzo się starałem).

W tym samym czasie dbs, których próbowałem, Spatialite i PgRouting, zgodnie z ich dokumentami, oferują tylko algorytmy Dijkstra i A * . Nie widziałem nawet wspomnianego wyszukiwania dwukierunkowego, co dwukrotnie oszczędza czas obliczeń.

Czy istnieją lepsze algorytmy dla baz danych lub innych aplikacji?

Prawda jest taka, że ​​większość ludzi używa niestandardowej odmiany algorytmu A * . Zobaczysz to u większości „dużych facetów” (nie mogę powiedzieć, kim oni są na forum publicznym, ale mogę powiedzieć, że prawdopodobnie używasz jednego z nich - gwarantowane), gdzie modyfikacja heurystyki jest bardzo zależy od używanych przez nich zestawów danych.

Wspomniałeś już o pgroutowaniu , które uważam za opcję „tradycyjną”. Jest dobry do wykonywania prostych algorytmów routingu i do większości problemów. Jest również łatwy w użyciu i wykorzystuje tradycyjną bazę danych na swoim backendie.

Niemniej jednak tak naprawdę zależy to od skali i rodzaju problemu, który próbujesz rozwiązać, a routing jest problemem graficznym .

Po raz kolejny „duzi faceci” zwykle mają dużo danych związanych z ich wykresem (na przykład dane o ruchu, trasy autobusów, ścieżki spacerowe), które wpływają na algorytm routingu. Są one znane jako multimodalne planery podróży (w których można również wybrać „tryby” planowania - bez ścieżek rowerowych - tylko transport publiczny - tego rodzaju rzeczy). Można pomyśleć, jak planowanie podróż staje się również wrażliwą kwestią czasu (czyli jeśli idziesz z powrotem kilka brzegi z powrotem, będzie można złapać metro, która przeniesie Cię do miejsca docelowego do przodu o wiele szybciej, niż gdyby po prostu starał się poruszać krawędzie przodu przy użyciu najniższego kosztu).

„Duzi faceci” nie przechowują swoich danych w tradycyjnej bazie danych jako takiej, używają wcześniej obliczonych wykresów (mile widziane klastry hadoop / mapreduce!). Jak możesz sobie wyobrazić, te wykresy stają się naprawdę duże, więc znajomość sposobu łączenia krawędzi sąsiednich wykresów może być wyzwaniem.

Tak czy inaczej, polecam spojrzeć na kilka projektów multimodalnego grafu routingu:

Przychodzi mi na myśl Graphserver . Nie dużo dokumentacji, ale dużo czystej kodowania (AFAIK, uważam, że MapQuest używa odmiany tego projektu dla niektórych swoich produktów routingu).

Inną opcją byłby OpenTripPlanner, który ma za sobą wielu inteligentnych ludzi (w tym ludzi z serwera grafów).

Nie jestem pewien, czy jest nowszy, ale pgRouting ma algorytm Shooting-Star :

Algorytm Shooting-Star to najnowszy algorytm pgRouting najkrótszej ścieżki. Jego specjalnością jest to, że trasuje od łącza do łącza, a nie od wierzchołka do wierzchołka, jak robią to algorytmy Dijkstra i A-Star. Umożliwia to na przykład zdefiniowanie relacji między łączami i rozwiązuje niektóre inne problemy związane z algorytmem opartym na wierzchołkach, takie jak „łącza równoległe”, które mają to samo źródło i cel, ale różne koszty.

W rozszerzeniu ESRI Network Analyst zastosowano hierarchiczne podejście , o którym wspomniałeś, aby ograniczyć czas rozwiązywania:

Znalezienie dokładnie najkrótszej ścieżki w ogólnopolskim zestawie danych sieci jest czasochłonne ze względu na dużą liczbę krawędzi, które należy przeszukać. Aby poprawić wydajność, zestawy danych sieciowych mogą modelować naturalną hierarchię w systemie transportowym, w którym jazda na autostradzie międzystanowej jest lepsza niż jazda po drogach lokalnych. Po utworzeniu sieci hierarchicznej modyfikacja dwukierunkowej Dijkstra służy do obliczania trasy między punktem początkowym a docelowym.

Na stronie ESRI znajduje się bardzo szczegółowa biała księga z przykładami tego podejścia - wymaga to jednak zalogowania się w celu pobrania (biała księga w sprawie hierarchicznych tras w ArcGIS Network Analyst).

Skurcz Hierarchia jest bardzo szybki algorytm:

• http://algo2.iti.kit.edu/1087.php

Ten algorytm jest przyjazny dla pamięci RAM podczas wykonywania zapytania (aby utrzymać zwężony wykres, potrzebna jest więcej pamięci RAM, a także ogromne przetwarzanie wstępne)

Istnieją inne algorytmy - w tym te, które rozwiązują routing transportu publicznego:

• http://i11www.iti.uni-karlsruhe.de/members/thomas_pajor/publications

Microsoft prowadzi również badania:

• http://research.microsoft.com/en-us/people/dadellin/

(cóż, Daniel Delling też pochodzi z Karlsruhe)

Możesz uzyskać miłe wprowadzenie i przegląd dostępnych algorytmów:

• http://i11www.iti.uni-karlsruhe.de/teaching/sommer2012/routenplanung/index

Ostrzeżenie: niemieckie (!) Wykłady. ale przynajmniej nagłówki mogą pomóc ci uzyskać więcej informacji (ALT, flagi łukowe, CHASE, ...) lub dołączoną literaturę!

aktualizacja

GraphHopper implementuje teraz hierarchie skurczów, a także inne algorytmy, możesz również wypróbować wersję demonstracyjną .