Przejdź do treści
Technologia i rozwój

Planowanie tras na otwartych silnikach: VROOM i Valhalla

Co potrafią otwarte silniki planowania tras, na jakich licencjach są wydane i czego potrzeba, żeby działały na Twoim serwerze.

AutorArtem ShevchenkoZałożyciel i architekt systemów
  • 8 min czytania
  • 1 wyświetlenie
Planowanie tras na otwartych silnikach: VROOM i Valhalla

Kolejność dostaw dla kilku aut, z oknami czasowymi klientów, ładownością i przerwami kierowców, to zadanie, które ma w informatyce swoją nazwę: problem marszrutyzacji pojazdów (VRP). Nie trzeba go rozwiązywać od zera ani kupować abonamentu. Istnieją otwarte silniki, które robią to od lat, a ich kod i dokumentacja są publiczne.

Dwa elementy: optymalizator i silnik tras

Planowanie trasy składa się z dwóch kroków. Najpierw trzeba wiedzieć, ile trwa przejazd z każdego punktu do każdego innego po prawdziwych drogach: to robi silnik tras, np. OSRM albo Valhalla, na danych OpenStreetMap. Potem optymalizator, np. VROOM, układa z tego kolejność punktów dla każdego auta.

VROOM obsługuje według dokumentacji: wiele aut i kilka baz, okna czasowe, ładowność w kilku wymiarach (np. waga i palety), przerwy kierowców, odbiory i dostawy w jednym kursie oraz wymagane uprawnienia, np. tylko auto z windą do danego klienta. Odległości bierze z OSRM, Valhalli albo openrouteservice bez dodatkowej pracy, przyjmuje też własną macierz.

Do danych dla VROOM można też dopisać priorytet zlecenia oraz limity liczby zadań, czasu przejazdu i dystansu. Trzeba przy tym pamiętać, że VROOM sam nie zna dróg. Każde ograniczenie zależne od mapy, na przykład zakaz wjazdu, musi już być zawarte w macierzy przejazdów, którą dostaje od silnika tras.

Silniki tras różnią się tym, co potrafią poza wyznaczeniem jednej trasy. OSRM liczy macierz czasów i odległości między wieloma punktami naraz, czyli dokładnie to, czego potrzebuje optymalizator. Valhalla też liczy macierz, a do tego izochrony, czyli obszar, do którego auto dojedzie w zadanym czasie, i dopasowuje zapisany ślad przejazdu do dróg na mapie. Izochron nie ma OSRM; mają je Valhalla, GraphHopper i openrouteservice.

Ciężarówka to nie osobówka

Tu zaczyna się różnica, która dla przewoźnika ma znaczenie. Otwarty OSRM ma profile dla samochodu, roweru i pieszego, ale nie ma profilu ciężarówki. Valhalla ma: uwzględnia wysokość, szerokość, długość i masę pojazdu, nacisk na oś i ładunek niebezpieczny. Dlatego dla floty ciężarowej proponujemy parę VROOM i Valhalla, a dla busów i aut dostawczych, gdzie gabaryty rzadko ograniczają trasę, często wystarczy OSRM. Jak dokładnie mapa opisuje ograniczenia na Twoich trasach, warto sprawdzić na własnych danych, zanim obieca się wynik.

W Valhalli parametry auta podaje się w modelu kosztów dla ciężarówki: wysokość, szerokość i długość w metrach, masę w tonach, nacisk na oś, liczbę osi i informację o ładunku niebezpiecznym. Jeśli ich nie podasz, silnik przyjmie wartości domyślne, na przykład 4,11 m wysokości i 21,77 t masy. Dlatego parametry każdego auta we flocie warto wpisać osobno.

Profil ciężarówki mają też openrouteservice (profil driving-hgv: długość, szerokość, wysokość, nacisk na oś, masa i ładunek niebezpieczny) oraz otwarty rdzeń GraphHopper (profil truck, który omija drogi z zakazem wjazdu dla ciężarówek i porównuje ograniczenia szerokości, wysokości i masy na drodze z parametrami auta). Wspólna zasada: ograniczenia ciężarówki trafią do planu VROOM tylko wtedy, gdy macierz przejazdów policzy silnik z profilem ciężarówki. Z macierzą z OSRM tych ograniczeń w planie nie będzie.

Gdy reguły są nietypowe, sięga się po solver: Google OR-Tools albo Timefold Solver w wersji Community. Oba wymagają więcej pracy programistycznej, ale pozwalają opisać niemal każde ograniczenie.

OR-Tools to biblioteka, którą wbudowuje się we własną usługę. Obsługuje m.in. okna czasowe, ładowność, odbiory z dostawami, osobny start i koniec trasy dla każdego auta, przerwy oraz pominięcie punktu z karą, gdy nie da się go obsłużyć. Dróg sama nie liczy: macierz czasów trzeba jej podać, na przykład z OSRM albo z Valhalli. Timefold Solver dzieli ograniczenia na twarde, średnie i miękkie oraz pozwala przeliczyć plan w trakcie dnia, zostawiając na miejscu zadania, które ktoś przypiął. Do planowania tras nie proponujemy natomiast funkcji VRP z pgRouting: dokumentacja oznacza je jako eksperymentalne i ostrzega, że mogą doprowadzić do awarii serwera.

Jak wygląda taki projekt krok po kroku

Wdrożenie planowania tras na otwartych silnikach można opisać w pięciu krokach. Każdy z nich da się sprawdzić na Twoich danych, zanim system trafi do codziennej pracy.

  1. Zlecenia i flota. Punkt wyjścia to dane, które firma już ma: zlecenia z adresami, oknami czasowymi klientów, wagą i liczbą palet oraz auta z ładownością, bazą i godzinami pracy. Dla ciężarówek dochodzą wymiary i masa, a przy niektórych ładunkach informacja, że są niebezpieczne.
  2. Adresy na mapie. Optymalizator pracuje na punktach, nie na adresach. Zamianę adresu na punkt, czyli geokodowanie, może wykonać Nominatim na danych OpenStreetMap. Photon, drugi otwarty geokoder, podpowiada adres już przy wpisywaniu i radzi sobie z literówkami. Adres, którego geokoder nie znajdzie, trafia do pracownika do poprawki, a poprawiony punkt zostaje zapisany przy kliencie.
  3. Macierz przejazdów. Silnik tras liczy czasy i odległości między wszystkimi punktami dnia. Dla floty ciężarowej robi to silnik z profilem ciężarówki.
  4. Reguły planu. Do danych dochodzą ograniczenia: okna czasowe, ładowność, przerwy kierowców, wymagane uprawnienia aut i priorytety zleceń. Reguła, której nie da się zapisać w VROOM, jest sygnałem, żeby sięgnąć po OR-Tools albo Timefold.
  5. Decyzja dyspozytora. Optymalizator proponuje kolejność punktów dla każdego auta. Dyspozytor widzi plan na mapie, zmienia to, o czym system nie wie, i zatwierdza plan, zanim trafi on do kierowców.

Co trzeba uruchomić na serwerze

Na serwerze potrzebne są trzy usługi: optymalizator, silnik tras i geokoder. VROOM ma gotowy obraz Dockera vroom-docker, w którym jest sam optymalizator i vroom-express, czyli usługa HTTP przyjmująca zadania. Silnik tras wybiera się w nim jednym ustawieniem: OSRM, Valhalla albo openrouteservice. OSRM i Valhalla także mają gotowe obrazy, a dane mapy to wyciąg z OpenStreetMap, np. z serwisu Geofabrik.

Jedno zastrzeżenie dotyczy openrouteservice: jego wbudowana optymalizacja działa tylko w publicznym API, a nie na własnej instancji. Na własnym serwerze kolejność punktów układa więc osobno uruchomiony VROOM, a openrouteservice liczy przejazdy.

Licencje i koszty

VROOM i OSRM są na licencji BSD, Valhalla na MIT, OR-Tools i Timefold Community na Apache 2.0. Nie płacisz za licencję, a kod Twojego systemu pozostaje zamknięty. Płaci się za wdrożenie i serwer. Mapa wymaga jednego: podpisu „© OpenStreetMap contributors” z odnośnikiem do strony praw autorskich OSM. Uwaga na wersje płatne: optymalizacja tras GraphHopper to usługa w chmurze, a Timefold Enterprise wymaga licencji.

Licencje BSD, MIT i Apache 2.0 pozwalają wbudować silnik w zamknięty system. Trzeba tylko zachować informację o prawach autorskich i tekst licencji, a przy Apache 2.0 także plik NOTICE, jeśli projekt go ma. Na Apache 2.0 jest też otwarty rdzeń GraphHopper, który można uruchomić u siebie. Płatne są jego usługi w chmurze, a bezpłatny plan jest przeznaczony wyłącznie do użytku niekomercyjnego.

Inaczej jest z licencją GPL. Mają ją openrouteservice i geokoder Nominatim (GPL w wersji 3) oraz pgRouting (GPL w wersji 2). Obowiązek udostępnienia kodu źródłowego pojawia się przy przekazaniu programu, a tekst GPLv3 mówi wprost, że sama praca użytkownika z programem przez sieć, bez przekazania kopii, przekazaniem nie jest. Dlatego takie narzędzie proponujemy uruchomić jako osobną usługę na Twoim serwerze, a nie łączyć jego kodu z kodem Twojego systemu. Kto przekazuje komuś zmienioną wersję takiego programu, musi udostępnić źródła zmian na GPL. Licencji AGPL nie ma żadne z wymienionych tu narzędzi. Ocenę dla konkretnego projektu warto jednak zostawić prawnikowi.

Dane OpenStreetMap są udostępniane na licencji Open Database License (ODbL). Trzeba podać, że pochodzą z OpenStreetMap i są na tej licencji, z odnośnikiem do strony praw autorskich OSM. Zasady Fundacji OpenStreetMap dopuszczają podpis „© OpenStreetMap” albo „© OpenStreetMap contributors”, umieszczony na mapie w rogu albo tuż obok niej. Wskazać OpenStreetMap musi też aplikacja, która wyznacza trasy na tych danych. W systemie, który zbudujemy, podpis „© OpenStreetMap contributors” z odnośnikiem znajdzie się przy każdej mapie trasy i w portalu klienta.

Od czego zacząć

Budujemy systemy z AI, integracjami i odczytem dokumentów dla innych branż, ale systemu dla logistyki jeszcze nie budowaliśmy. Dlatego proponujemy zacząć nie od obietnic, tylko od próby. Wystarczą dane z kilku zwykłych dni: zlecenia z adresami i oknami czasowymi oraz lista aut z ładownością i bazami. Na tej podstawie możemy ułożyć plan otwartym silnikiem i położyć go obok planu, który przygotował dyspozytor. Takie porównanie pokaże, czy reguły są dobrze opisane i czy mapa zna ograniczenia na Twoich trasach.

Procentów oszczędności paliwa czy kilometrów nie podajemy z góry: bez pomiaru na Twoich danych nie ma ich z czego policzyć.

Jeśli chcesz sprawdzić, jak taki silnik ułożyłby trasy z Twoich zleceń, opisz swój proces.

Źródła

Tagi

Udostępnij ten artykuł

Wróć do bloga

Pliki cookies

Używamy niezbędnych plików cookies i jednego funkcjonalnego, tego tylko za Twoją zgodą. Statystyki odwiedzin liczymy na serwerze, bez cookies. Polityka cookies