Planowanie transportu oraz optymalizacja tras to jedne z największych wyzwań dla przewoźnika. To oznacza dostarczenie towaru lub usług do odbiorcy w zaplanowanym czasie i najlepszą drogą. Niestety jednak najlepszą, nie zawsze znaczy najkrótszą.
W nauce wydzielono dwie grupy zagadnień, których dotyczy optymalizacja tras:
- VRP (Vehicle Routing Problem – problem marszrutyzacji)
- TSP (Travelling Salesman Problem – problem komiwojażera)
Jak to się zaczęło?
Planowanie transportu to problem tak stary, jak branża transportowa, a pierwsze naukowe opracowania, którym bliska jest optymalizacja tras, pochodzą z początków XIX wieku. Matematycznie zostało to opisane w 1930 roku przez austriackiego naukowca Karla Mengera. Wtedy brano pod uwagę niektóre parametry podróży: miasta, adresy, odległości między nimi i szacowany czas dojazdu. Główną trudnością była bardzo duża liczba danych podlegających analizie, ponieważ wszystkie obliczenia wykonywane były ręcznie. Jedna z ciekawszych metod bazowała na wyznaczaniu tras poprzez przywiązywanie sznurka do szpilek wbitych w papierową mapę: http://www.google.com.pg/patents/US844664.
Współcześnie, wszystkie dane pochodzą z map cyfrowych i są analizowane przez zaawansowane algorytmy optymalizacyjne. Są one w stanie uwzględnić dodatkowe cechy problemu komplikujące obliczenia, np. parametry pojazdu (wysokość, szerokość, DMC, czy dopuszczalny nacisk na oś), czy punktu odbioru (np. okna czasowe).
Przede wszystkim planowanie transportu
Optymalizacja tras to główne założenie, jakie poruszają algorytmy VRP, a w związku z tym kosztów związanych z działalnością transportową. Projektowe algorytmy Emapy mogą jednak być skierowane na optymalizację innych celów lub zasobów. Przykładem niech będzie równomierne rozłożenie zleceń dla poszczególnych pojazdów (wykorzystanie całej floty lub tylko jej części).
Algorytymy VRP opierają się na poniższych danych:
- lista punków do odwiedzenia,
- dane dotyczące liczby pojazdów (liczba zdefiniowana, ograniczona, nieograniczona),
- okna czasowe i ich parametry (dla każdego z odwiedzanych punktów),
- problem pick-up delivery,
- ładowność pojazdów,
- kalkulator tras, w tym maksymalny koszt trasy.
Każdy z parametrów może dodatkowo zawierać wyjątki lub dopuszczenie do przekroczenia zdefiniowanej reguły. Często ma to znaczenie dla pojęć typu okna czasowe lub dla generowania oszczędności na transporcie. W tych przypadkach najczęściej dochodzi do zaburzenia harmonogramu dostaw wynikających zwykle z powodów niezależnych od przewoźnika.
Liczba lub waga wyjątków również może być zdefiniowana dla trasy, magazynu lub całości floty. Istnieje możliwość wyceny każdego z nich, tak aby w razie konieczności wybrać trasę o możliwie najmniejszym koszcie przekroczenia.
Wyścig w dziedzinie VRP
Algorytmy VRP od lat 50-tych XX wieku do dziś są polem konkurencji i wyścigu pod kątem skuteczności rozwiązywania problemu komiwojażera. Wiele zespołów (w tym naukowych) rywalizuje tym polu przez optymalizowanie tras pewnych znanych i ogólnie dostępnych instancji problemów. Każdy kolejny wyśrubowany wynik świadczy o efektywności zastosowanych algorytmów (lub komputerów), daje dowód umiejętności ich twórców oraz podnosi coraz wyżej poprzeczkę konkurencji.
Warto mieć na uwadze, że Emapa jest w ścisłej czołówce światowych liderów bijących rekordy VRP.
