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.
Odpowiedzi:
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:
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. :)
źródło
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.
źródło