Problem marszrutyzacji (VRP)
Problem marszrutyzacji (Vehicle Routing Problem, VRP) to problem optymalizacyjny polegający na przydzieleniu zbioru dostaw do floty pojazdów i ustaleniu kolejności przystanków tak, aby zminimalizować koszt przy zachowaniu ograniczeń, takich jak ładowność i okna czasowe.
Czym jest Problem marszrutyzacji (VRP)?
VRP to skrót od Vehicle Routing Problem. Uogólnia on problem komiwojażera (TSP), który szuka najkrótszej trasy okrężnej dla jednego pojazdu, na całą flotę z rzeczywistymi ograniczeniami: ładownością pojazdów, oknami czasowymi dostaw, czasem pracy kierowców, typami pojazdów i innymi. Dantzig i Ramser opisali go po raz pierwszy w 1959 roku jako „truck dispatching problem” i do dziś jest jednym z najlepiej zbadanych problemów badań operacyjnych.
Większość praktycznych problemów to jego warianty. VRP z ograniczoną ładownością (CVRP) ogranicza to, co może przewieźć każdy pojazd; VRP z oknami czasowymi (VRPTW) dodaje okno odbioru lub dostawy dla każdego przystanku; problem odbioru i dostawy (PDP) łączy każdy odbiór z jego dostawą w tym samym pojeździe; a wersje z wieloma bazami lub mieszaną flotą pozwalają pojazdom startować z różnych miejsc lub różnić się wielkością i wyposażeniem.
VRP jest problemem NP-trudnym: liczba możliwych rozwiązań rośnie lawinowo z każdym przystankiem. Już jeden pojazd z dziesięcioma przystankami może je odwiedzić w 3 628 800 różnych kolejnościach. Metody dokładne sprawdzają się tylko dla małych instancji, dlatego solvery produkcyjne korzystają z heurystyk. Metoda konstrukcyjna, taka jak najbliższy sąsiad czy algorytm oszczędności Clarke’a–Wrighta, buduje pierwszy dopuszczalny plan, a przeszukiwanie lokalne ulepsza go ruchami takimi jak 2-opt, przeniesienie i zamiana, często pod kierunkiem metaheurystyki, np. symulowanego wyżarzania.
Przykład: dystrybutor ma 3 busy o ładowności 1000 kg i 45 dostaw, każdą z oknem czasowym. Planista może ręcznie ułożyć wykonalny plan; solver uwzględnia każde okno i każdą ładowność, minimalizując łączny dystans, i zwraca plan w kilka sekund. Dostawy, które się nie mieszczą, są zgłaszane jako niezaplanowane, więc planista może dodać przestrzeń lub poluzować okno.
Optymalizacja tripów w Transportial czyni solver ustawieniem platformy: PTV OptiFlow, PTV xTour, OSRM do ustalania kolejności dla jednego pojazdu, CloverOpt lub własny solver Transportial, który buduje tripy metodą najbliższego sąsiada, ulepsza je ruchami przeniesienia, zamiany, łączenia i dzielenia, a każdą trasę dopracowuje metodą 2-opt. Optymalizator uwzględnia okna czasowe, wagę, typ pojazdu i ograniczenia wyposażenia, potrafi wstawiać do tras i ETA przerwy wymagane przepisami o czasie jazdy i zwraca podgląd, który planista koryguje przed zapisaniem.
Najczęściej zadawane pytania
Co oznacza VRP w logistyce?
VRP to skrót od Vehicle Routing Problem, czyli problemu marszrutyzacji: decyzji, który pojazd obsługuje których klientów i w jakiej kolejności, tak aby łączny dystans, czas lub koszt był jak najniższy, a każdy pojazd mieścił się w swojej ładowności i każdy przystanek w swoim oknie czasowym.
Jaka jest różnica między TSP a VRP?
Problem komiwojażera (TSP) znajduje najlepszą kolejność przystanków dla jednego pojazdu. VRP dodatkowo decyduje, jak podzielić przystanki między kilka pojazdów przy ograniczeniach ładowności i czasu; po dokonaniu tego podziału trasa każdego pojazdu jest osobnym TSP.
Jak solver VRP pomaga planistom w logistyce?
Automatycznie buduje efektywne tripy, przydzielając przesyłki do pojazdów i ustalając kolejność przystanków, więc planiści poświęcają mniej czasu na ręczne układanie harmonogramów, a flota przejeżdża mniej pustych lub zbędnych kilometrów, z zachowaniem ładowności, okien czasowych i przepisów o czasie jazdy.
Czy solver VRP gwarantuje najlepszy możliwy plan?
Nie przy realistycznej wielkości floty: udowodnienie optimum trwałoby zdecydowanie za długo. Praktyczne solvery dążą do bardzo dobrego planu w ciągu sekund lub minut i zgłaszają przystanki, których nie udało się umieścić, a właśnie tego planiści potrzebują na co dzień.
Zobacz Problem marszrutyzacji (VRP) w prawdziwym TMS
Transportial wprowadza te pojęcia w życie na jednej platformie operacyjnej: planowanie, śledzenie, dokumenty i finanse.