Dlaczego pgRouting nie zwraca najlepszej ścieżki?

Niech następna część wykresu:

Kiedy używam funkcji shortest_path między punktami A i B, mam niebieską ścieżkę. Dlaczego to się dzieje?

Tak zachowuje się shortest_path (algorytm Dijkstry) w pgRouting. Jeśli są dwie krawędzie z tym samym źródłem i celem, używana jest losowa (a dokładniej: pierwsza, która wychodzi z bazy danych). Nie wiem, jak to naprawić, ale jest kilka obejść.

Jeśli to możliwe, należy podzielić jedną z tych krawędzi na dwie części. Nie testowałem tego, ale powinno to naprawić to zachowanie.

Inne rozwiązanie na wypadek, gdy nie można zmodyfikować zestawu danych. Dodaj pole „shorter_alternative” do swojej tabeli. Przykładowe zapytanie, zmodyfikuj je do swoich potrzeb. Mam nadzieję, że to wyjaśnia pomysł:

UPDATE roads t1
SET shorter_alternative = t2.id
FROM roads t2
WHERE 
((t2.source = t1.source AND t2.target = t1.target) OR
(t2.source = t1.target AND t2.target = t1.source)) AND
(t2.length < t1.length)

Teraz krawędź „0.098” będzie zawierać identyfikator krawędzi „0.011”. Wszystkie pozostałe krawędzie będą miały wartość null w polu shorter_alternative. Po wykonaniu zapytania shortest_path sprawdź zwrócony zestaw danych - jeśli w dowolnym wierszu jest ustawione pole shorter_alternative, zmień je.

Problem został już opisany w poprzedniej odpowiedzi. Jest to problem algorytmów „najkrótszej ścieżki” opartych na wierzchołkach, które dbają tylko o źródło i cel.

W narzędziu do śledzenia problemów znajduje się bilet i możliwe rozwiązanie zmiany implementacji algorytmu: https://github.com/pgRouting/pgrouting/issues/34 (Byłoby miło, gdyby ktoś mógł to wypróbować i wysłać żądanie ściągnięcia; - )

Inną możliwością jest podzielenie „równoległych połączeń drogowych”, jak wspomniano wcześniej. Możesz też użyć algorytmu Shooting Star, który prowadzi od krawędzi do krawędzi, dzięki czemu „wie” o obu połączeniach drogowych.

Możesz też spróbować zamówić sieć drogową według kosztu, a następnie wybrać tylko różne kombinacje źródła i celu:

SELECT * FROM shortest_path(
  'SELECT DISTINCT ON (source, target)
      gid as id,
      source::integer,
      target::integer,
      cost::double precision
    FROM ways ORDER BY source, target, cost',
  true,false
);

Zakłada się, że szukasz najtańszej trasy. W przeciwnym razie musisz ORDER BY ... DESC.

Musisz wypróbować, jeśli wpłynie to na wydajność.

Stworzyłem łatkę do pgRouting, która rozwiązuje problem: https://github.com/pgRouting/pgrouting/issues/78