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).