Pomóż wybrać odpowiedni silnik routingu

16

Buduję system planowania trasy, ale wciąż muszę zdecydować, z którego silnika routingu będę korzystać. Do tej pory znalazłem pgrouting i neo4j.

Mam sieć tras w bazie danych postgresql / postgis (importowanej z pliku shapefile). Zrobiłem zapytania, aby wyodrębnić węzły (punkty końcowe sposobów, w których musisz podjąć decyzję, w którym kierunku pójść lub ślepe zaułki) i wyodrębnić krawędzie (często złożone z kilku kolejnych sposobów). Wszystkie moje krawędzie są dwukierunkowe.

Moim głównym celem jest obliczenie tras w tej sieci przy użyciu algorytmu gwiazdy A, w którym odległość = koszt.

Moje odczucie mówi mi, że baza danych z grafami, taka jak neo4j, jest właściwą drogą (jak się wydaje, jest stworzona tylko do tego celu), ale domyślnie nie obsługują one gwiazdy A, a także nie ma prawdziwego poczucia geometrii . Wydaje się, że lepiej nadaje się do sieci społecznościowych zamiast map.

  • Czy rozwiązywanie problemów spełni moje potrzeby?
  • Czy jest wystarczająco szybki dla zapytań w locie (+ -2000 węzłów, + -4000 krawędzi)? Normalnie byłoby to kilka ms dla A-star, ale nie jestem pewien co do tej implementacji w sql.
  • Czy rozkładanie gwiazdy A daje mi listę węzłów i krawędzi?
  • W większości przykładów, które widzę na temat planowania, zauważam, że po obliczeniu trasy zwykle jest lista poleceń (np. „Na X skręć w lewo itp.”). Czy rozwiązywanie tego powoduje, czy jest to z innego systemu?

Mam nadzieję, że ktoś może podać mi informacje o tym, jaki system wybrać. Neo4j, pgrouting lub jakiś inny system.

mrg
źródło
3
Myślę, że większość algorytmów routingu nie działa z „wyczuciem geometrii”, zamiast tego obliczany jest atrybut geometryczny i stosowany jako koszt (tj. Miara odległości polilinii). Nigdy nie korzystałem z Neo4j, ale wygląda naprawdę dobrze i być może wkrótce go użyję. Właśnie spojrzałem na dokumentację i wygląda na to, że można użyć A-Star: docs.neo4j.org/chunked/stable/graph-algo.html docs.neo4j.org/chunked/stable/... pgRouting jest również zdolny i Jestem wielkim fanem tego. Interesujące byłoby porównanie wydajności tych dwóch rozwiązań.
Allan Adair
Po pierwsze, proponuję spojrzeć na urbansim model użytkowania gruntów typu open source. Jeśli chodzi o twoje pytanie dotyczące routingu, jeśli jest to aplikacja planująca, sugerowałbym najpierw przejrzenie oprogramowania takiego jak TransCAD, CUBE, PLANAR lub EMME / 2 pod kątem funkcjonalności i interfejsu użytkownika. Zazwyczaj rozdają 1-godzinne lub 2-godzinne wersje demonstracyjne swojego oprogramowania (oprogramowanie, które można uruchomić na godzinę lub dwie, aby się zorientować). Jeśli chcesz zbudować coś do użytku online lub stacjonarnego, spójrz na pgRouting; jednak z doświadczenia czasami nie jest to tak łatwe, jak to przedstawia warsztat / samouczek.
dassouki
Mam pgrouting z gwiazdą i to jest niesamowite! Odpowiada tak na moje pierwsze 3 pytania. Nadal zastanawiam się, czy ktoś tutaj wie coś o generowaniu pełnych wskazówek nawigacyjnych. Czy jest jakieś narzędzie współpracujące z pgroutingiem, które generuje pełne kierunki („Po 200 m skręć w lewo itp.”) Z wyniku obliczonej trasy?
mrg

Odpowiedzi:

8

Obecnie badam ten sam problem, co ty, do celów pracy badawczej. Zanim zacząłem testować te dwie bazy danych, miałem takie samo domniemanie jak ty. Ta baza danych graficznych Neo4j byłaby idealnym rozwiązaniem dla tego rodzaju problemów. I częściowo tak jest, ale z wieloma problemami.

Pierwszy problem polega na tym, że A-Star jest implementowany tylko wtedy, gdy korzystasz z wbudowanej bazy danych, a nie za pośrednictwem interfejsu API REST (serwer). Jeśli chcesz używać Neo4j z REST API, obsługiwany jest tylko algorytm Dijkstra. Drugim problemem są wymagania dotyczące pamięci sprzętowej dla Neo4j. Do routingu (Dijkstra) w „większych” sieciach potrzeba dużo pamięci RAM. W przypadku dużej sieci mam na myśli wielkość niemieckiej bazy danych dróg OSM . Przeprowadziłem testy na serwerze 6 GB RAM (to wszystko, co mam obecnie) i tylko mniejsze sieci mogły być kierowane bez błędów wyjątku OutOfMemory. „Małe” sieci w moich przypadkach testowych to na przykład baza danych dróg OSM dla Austrii lub Chorwacji. Równoczesne zapytania, których wciąż nie testowałem z Neo4j.

Wszystkie te problemy nie występują w pgRouting. Pamięć nie jest takim problemem, ale współbieżne zapytania zwiększają potrzebną ilość pamięci. Na przykład, jeśli masz dwa równoczesne żądania, potrzebna jest podwójna ilość pamięci. Nie był to problem nawet dla zbioru danych OSM Niemcy, pgRouting bezproblemowo kierował wszystkie współbieżne żądania.

Wydajność: w większości przypadków Neo4j przewyższa pgRouting. Ale tylko wtedy, gdy jest wystarczająca ilość pamięci dla danego zestawu danych i jeśli wszystkie węzły i relacje są w pamięci (gorący start). Wzrost / spadek wydajności zależy od wielu czynników, ale głównie od wielkości sieci i odległości (przeskoków) między węzłem źródłowym a docelowym.

Rozmiar Twojej sieci jest dość mały, więc nie powinieneś mieć żadnych problemów z pamięcią. Prawdopodobnie Neo4j nie jest złym wyborem, ale musisz dostosować się do „małego” innego modelu danych niż w standardowych bazach relacji.

Aby odpowiedzieć na pytania:

  • W pgRouting nie musisz się martwić implementacją AStar w SQL, która już została zaimplementowana.
  • Tak, pgRouting może dać ci listę węzłów i krawędzi
  • Nie sądzę, że pgRouting może dostarczyć takich informacji bez pewnych niestandardowych obejść zapytań. Ale może się mylę, może ktoś to zrobił i może ci pomóc w tym pytaniu.

Nie wiem, czy to pomoże ci bezpośrednio, ale jednym z najszybszych serwerów routingu, jaki znalazłem, jest osm2po . Działa z zestawem danych OSM i jest dość szybki. Obecnie wdrażana jest tylko dijkstra, ale deweloper ogłosił również AStar. Mam nadzieję, że część z tego pomoże. :)

Mario Miler
źródło
Dobrze jest usłyszeć od kogoś, kto faktycznie przetestował oba systemy. Tymczasem mam dużo więcej doświadczenia z pgroutingiem. Zauważyłem, że pgrouting buduje cały wykres dla każdego zapytania i sprawia, że ​​jest on raczej powolny dla dużych sieci (rozmiar Niemiec), więc nie rozumiem, dlaczego pgrouting wymaga mniej pamięci niż Neo4j. Moja kolejna próba będzie polegała na umieszczeniu całego wykresu w ramie i kierowaniu na nim (z neo4j, nx_spatial itp.), Aby zapewnić szybszą odpowiedź dla routingu w czasie rzeczywistym.
mrg
Tak, im większy wykres, tym większa różnica między pgroutingiem a neo4j. Prawdopodobnie, jeśli umieścisz cały wykres w pamięci niż byłoby to najszybsze rozwiązanie, nie ma co do tego wątpliwości. Neo4j jest dość szybki, gdy cały wykres jest ładowany do pamięci. Nie wiem o nx_spatial, nie testowałem tego, ale może zrobię to. Wierzę, że może przewyższyć nawet Neo4j. Ale to rozwiązanie jest dobre, jeśli jest akceptowalne dla twojej aplikacji.
Mario Miler,
1
@mrg nie jest pewien, czy nadal stanowi dla ciebie problem, ale jest OSRM (C ++) i GraphHopper (Java). Zarówno w skali światowej, jak i np. GraphHopper potrzebuje mniej niż 1 GB dla Niemiec (gdzie jestem autorem)
Karussell
Karussell, dziękuję za informację! Znalazłem już OSRM, ale GraphHopper jest dla mnie nowy.
mrg
0

Możesz także zajrzeć do naszego pakietu RW Net 4 (www.routeware.dk). Może wykonywać takie najkrótsze obliczenia ścieżki przy użyciu A * prosto z pliku SHP. Pakiet podstawowy za 500 euro wydaje się wystarczający dla twoich potrzeb.

Uffe Kousgaard
źródło
Dziękuję za szybką odpowiedź, ale mój projekt jest wciąż w fazie, której nie jestem pewien, czy uzasadnia to wydawanie pieniędzy w tej chwili. Mam również pgrouting działający na moich danych, więc na razie rozwiązano nieznane.
mrg