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: planer Transportial, PTV OptiFlow, PTV xTour, OSRM do ustalania kolejności dla jednego pojazdu lub CloverOpt. Planer Transportial to przeszukiwanie dużego sąsiedztwa (large neighbourhood search): zaczyna od zbudowanego planu, a potem wielokrotnie rozbiera jego części i odbudowuje je wstawianiem zachłannym i wstawianiem z żalem (regret); alternatywą jest przeszukiwanie atomowe z ruchami przeniesienia, zamiany, łączenia, podziału i 2-opt. Jedno przeszukiwanie decyduje dla każdej trasy o pojeździe, kierowcy i naczepie albo o kontrakcie na zdolność przewozową przewoźnika, w transporcie drogowym, kolejowym, śródlądowym, morskim i lotniczym, łącznie z łańcuchami door-to-door na usługach rozkładowych. Każde wstawienie jest sprawdzane pod kątem licznika czasu jazdy każdego kierowcy według UE 561/2006, naczep, ADR, komór, przepustowości doków i wspólnego zapasu sprzętu. Celem jest gotowy wariant (odległość, czas, CO₂e, koszt lub jak najmniej zasobów) albo własny cel ważony z poziomami priorytetów, a planista sprawdza podgląd 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.