Wyznaczanie tras w ułamek sekundy

1 Maj

Niedawno pojawiła się wersja 0.3 silnika do wyznaczania tras Open-source Routing Machine (OSRM) autorstwa Dennisa Luxena.  W przeciwieństwie do większości programów do nawigacji, używa on nowego algorytmu wyznaczania najkrótszych ścieżek w grafie, rozwijanego na Uniwersytecie Karlsruhe i nazwanego contraction hierarchies.  Odznacza się on ogromną wydajnością działania, kosztem elastyczności wyboru parametrów routingu, przez co dla każdego środka transportu wymagany jest oddzielny indeks.

Powyżej widzimy porównanie czasów oczekiwania na wyznaczenie trasy w różnych serwisach, stworzone przez Pascala Neisa, autora wielu ciekawych statystyk i prac na temat OpenStreetMap.  Jak widać, OSRM zostawia pozostałe serwisy daleko w tyle.  Jest na tyle szybki, że na stronie projektu możemy wypróbować wyznaczania trasy z możliwością dodawania kolejnych punktów pośrednich na trasie i aktualizacją trasy na żywo w czasie przesuwania punktu.  W momencie publikacji wersja 0.3 miała jeszcze kilka znaczących błędów, ale są one szybko poprawiane i na dzisiaj powinna wyznaczać zupełnie praktyczne trasy.  Silnik obsługuje zakazy skrętu i inne ograniczenia.

Długości tras porównywanych na powyższym wykresie to kolejno: 40km, 545km, 1055km, 2320km i 2980km.  Każdy z serwisów wyznaczył trasę o nieco innej długości, jednak różnice są bardzo niewielkie.  Poza Google Maps i Bing, korzystającymi z zamkniętych danych, wszystkie pięć serwisów korzysta wyłącznie z danych drogowych OpenStreetMap.  Czasy zostały wyznaczone przez uśrednienie czasu oczekiwania z kilku kolejnych zapytań i po odjęciu opóźnień w połączeniach ze stronami serwisów.  Za OSRM plasuje się Google Maps z ponad dwukrotnie gorszym wynikiem, a za nimi dosyć podobne wyniki mają Bing, Cloudmade i MapQuest.  Jak widać wybór jest duży i może zostać dostosowany do własnych wymagań.  Projekty OSRM i YOURS są udostępniane jako otwarte programy na wolnej licencji i pozwalają na stworzenie własnej instalacji z własnymi danymi, również na prywatnym serwerze.