Problem trasowania pojazdów (VRP): definicja, warianty i przykłady z praktyki

Czym jest Problem trasowania pojazdów (VRP)?#

VRP to ogólny problem fleet routing stojący za planowaniem dostaw, harmonogramowaniem field service i planowaniem tras dla wielu kierowców. Pytanie brzmi: jak zbudować jedną lub wiele tras, które efektywnie odwiedzą wszystkie wymagane przystanki?

W praktyce VRP oznacza podjęcie decyzji:

• Który pojazd powinien obsłużyć dany przystanek
• W jakiej kolejności każdy pojazd powinien odwiedzić przypisane przystanki
• Kiedy każdy przystanek powinien zostać odwiedzony (ETA), przy zachowaniu ograniczeń

To właśnie robi oprogramowanie do optymalizacji tras. Jeśli chcesz praktycznego przeglądu, zacznij od głównego artykułu: Optymalizacja tras: kompletny przewodnik .

VRP vs TSP: jaka jest różnica?#

Częstym nieporozumieniem jest mylenie VRP z problemem komiwojażera (TSP).

• TSP: jeden pojazd musi odwiedzić wszystkie przystanki raz i wrócić (lub zakończyć trasę) — najlepsza pojedyncza trasa.
• VRP: może istnieć wiele pojazdów, przystanki trzeba przypisać do pojazdów, a ograniczenia takie jak okna czasowe, pojemność i godziny pracy są powszechne.

Innymi słowy: VRP to TSP dla świata rzeczywistego.

Dlaczego VRP jest trudne#

VRP szybko staje się trudne, ponieważ liczba możliwych rozwiązań rośnie wykładniczo: nie wybierasz tylko kolejności przystanków, ale również tego, który pojazd obsłuży które przystanki.

Dodaj ograniczenia takie jak okna czasowe i pojemność, a wiele kandydackich tras staje się nieważnych. Dlatego produkcyjne optymalizatory tras koncentrują się na szybkim uzyskiwaniu rozwiązań wysokiej jakości, a nie na idealnej optymalności.

Popularne warianty VRP (typy spotykane w praktyce)#

Większość problemów związanych z optymalizacją tras to jeden z tych wariantów VRP albo ich kombinacja.

Jeśli Twoja firma działa na oknach czasowych, zobacz: Optymalizacja tras z oknami czasowymi . Jeśli korzystasz z wielu kierowców, zobacz: Optymalizacja tras z wieloma pojazdami .

Ograniczenia ze świata rzeczywistego obsługiwane przez modele VRP#

W realnych operacjach najkrótsza trasa często nie jest wykonalna. Ograniczenia definiują, co jest dozwolone.

• Okna czasowe: przyjazd tylko w czasie dostępności klienta
• Czas obsługi: czas spędzony na każdym przystanku (dostawa, inspekcja, dokumenty)
• Pojemność pojazdu: limity wagi/objętości i zapotrzebowanie na każdym przystanku
• Godziny pracy: początek/koniec zmiany dla każdego pojazdu/kierowcy
• Lokalizacje startu/końca: magazyn, hub lub baza kierowcy
• Priorytety: pilne przystanki najpierw lub gwarantowane zasady dostawy

Dlatego samo przestawianie kolejności przystanków nie jest tym samym co optymalizacja dla flot. Aby zobaczyć praktyczny workflow, przeczytaj: Jak działa optymalizacja tras .

Jak VRP rozwiązuje się w praktyce (bez ciężkiej matematyki)#

Duże instancje VRP rzadko rozwiązuje się metodą brute force. Zamiast tego silniki optymalizacji tras zazwyczaj:

• Szybko budują rozwiązanie początkowe (wykonalny plan tras)
• Ulepszają je iteracyjnie poprzez zamianę przystanków, przesuwanie przystanków między trasami i zmianę kolejności sekwencji
• Równoważą szybkość i jakość, aby dostarczyć wyniki wystarczająco szybko do codziennego planowania

Praktyczny wniosek: najlepsze narzędzia routingowe koncentrują się na wykonalnych trasach, które kierowcy mogą faktycznie zrealizować, a nie tylko na najkrótszym dystansie.

Jeśli chcesz zobaczyć stronę biznesowych efektów, zobacz: Korzyści z optymalizacji tras .

Jakie dane są potrzebne do rozwiązania VRP#

Aby uzyskać dokładne trasy i ETA, potrzebujesz dobrych danych wejściowych. Oto minimalna lista kontrolna:

Przystanki

• Adres lub szerokość/długość geograficzna
• Opcjonalnie: czas obsługi (minuty na przystanku)
• Opcjonalnie: okna czasowe (najwcześniej/najpóźniej)
• Opcjonalnie: zapotrzebowanie (waga/objętość)

Pojazdy / kierowcy

• Lokalizacja startu (i opcjonalnie końca)
• Godziny pracy (Time In / Time Out)
• Opcjonalnie: limity pojemności

TrackRoad obsługuje takie dane wejściowe (w tym import z Excela) tutaj: Route Optimizer .

Prosty przykład VRP#

Wyobraź sobie 30 przystanków dostawczych i 3 pojazdy. Optymalizator musi zdecydować, które przystanki przypisać do którego pojazdu, a następnie ustalić kolejność przystanków na każdej trasie tak, aby zminimalizować czas przejazdu, przy jednoczesnym zapewnieniu, że każdy kierowca skończy pracę w swoich godzinach oraz że okna czasowe zostaną dotrzymane.

Ta kombinacja przypisania + kolejności + ograniczeń to właśnie VRP — i dlatego optymalizacja tras to coś więcej niż zwykła nawigacja.