Graficzna prezentacja rozwiązania problemu marszrutyzacji (nieoptymalnego!). Zostały wyznaczone trzy marszruty (linie: ciągła, przerywana i kropkowana), które swój punkt początkowy i końcowy mają w bazie (żółty prostokąt "D") oraz przebiegają przez wszystkie punkty pośrednie (klientów - czerwone, zielone i niebieskie punkty).

Problem marszrutyzacji - problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej ilości środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej, niż jedno kryterium optymalizacji^[1]. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

Problem ten jest rozwinięciem takich problemów jak:

• problem komiwojażera (traveling salesman problem),
• problem domokrążnego kupca (traveling purchaser problem),
• problem chińskiego listonosza (chinese postman problem),

oraz zaliczany jest do problemów NP-trudnych . Z tego względu zazwyczaj jest rozwiązywany przy pomocy metod heurystycznych . Algorytmy dokładne mogą być wykorzystywane tylko dla problemów o stosunkowo niewielkiej ilości klientów (do 135)^[2].

Problem został po raz pierwszy zaprezentowany przez G.B. Dantziga oraz R.H. Ramser'a w 1959 roku w pracy The Truck Dispatching Problem opublikowanej na łamach Management Science^[3].

Klasyczne ujęcie problemu

W klasycznym ujęciu problem sformułowany jest w postaci grafu nieskierowanego Γ = (Ψ,ε), gdzie Ψ oznacza zbiór wierzchołków, do których przypisane jest zapotrzebowanie, natomiast ε zbiór krawędzi, do których przypisane są koszty przewozu ewentualnie czas lub długość trasy.

Minimalizowana jest funkcja

gdzie:

r – pojazd należący do zbioru jednorodnych (identycznych) pojazdów R

f, g – wierzchołki pomiędzy, którymi odbywa się przewóz

c_fg – koszt przewozu pomiędzy wierzchołkami f i g

x_fgr – zmienna binarna określająca, czy pomiędzy wierzchołkami f i g pojazd r wykonuje przewóz.

Warunkami ograniczającymi są:

• Występowanie tylko jednej bazy początkowej i końcowej (miejsca, z którego pojazdy rozpoczynają/kończą przewóz), z której/do której wyjeżdża dokładnie jeden pojazd r. W przypadku wierzchołków pośrednich ilość pojazdów wjeżdżających jest równa ilości pojazdów wyjeżdżających.

  – dla bazy początkowej

  – dla bazy końcowej

  – dla wierzchołków pośrednich

  W przypadku, gdy istnieje połączenie pomiędzy punktami 0 oraz n+1 to dopuszczalne są puste drogi

• Przypisanie każdemu klientowi dokładnie jednego pojazdu, który zaspokaja jego zapotrzebowanie (dostawy są niedzielone).

  – warunek przypisania dokładnie jednego pojazdu

  – warunek niedzielonych dostaw

Przykładowe rozwinięcia problemu

W rozwinięciach klasycznego problemu marszrutyzacji występować mogą dodatkowe ograniczenia. Przykładowo:

• Warunek nieprzekroczenia pojemności poszczególnych środków transportu (problem CVRP).

  

  gdzie

  d_f – popyt przypisany do danego klienta

  m_r – pojemność pojazdów

• Ograniczenia czasowe w problemach z oknami czasowymi (pojazd nie przybędzie do określonego wierzchołka przed wykonaniem poprzednich zadań w węzłach poprzedzających)

  

  gdzie

  t_fr – czas rozpoczęcia obsługi klienta f

  t_fg – czas przejazdu pomiędzy f, a g

  t_gr – czas rozpoczęcia obsługi klienta g

Rozwinięcia problemu

W literaturze występują również rozwinięcia klasycznego problemu marszrutyzacji. Należą do nich m.in.:

• Problemy uwzględniające niesymetryczność kosztów przewozu pomiędzy wierzchołkami
• Problemy uwzględniające niehomogeniczność taboru
• Problemy uwzględniające przejazdy drobnicowe (Less Than Truckload)
• Problemy uwzględniające ograniczenie maksymalnej długości trasy
• Problemy umożliwiające ustalenie baz (jednej lub kilku), w których pojazdy zaczynają i kończą podróż (Multiple Depot VRP)
• Problemy umożliwiające dodanie baz pomocniczych (VRP with Satellite Facilities)
• Problemy umożliwiające ustalenie częstotliwości odbioru/dostawy ładunku
• Problemy umożliwiające uwzględnienie okien czasowych (VRP with Time Windows) odbioru/wysłania towaru.
• Problemy wiążące problem marszrutyzacji z problemem kontroli zapasów u klientów
• Problemy uwzględniające możliwość obsługi jednego klienta przez kilka pojazdów (Split Delivery VRP)
• Problemy w których kosztowa funkcja celu zastąpiona została innymi parametrami (np. czas wykonania zleceń, długość tras, ilość przewiezionego ładunku)
• Problemy umożliwiające zdefiniowanie kolejności odwiedzania poszczególnych miejsc oraz opcjonalnego odwiedzania niektórych punktów.
• Problemy uwzględniające możliwości zwrotów i wysyłki towarów przez klientów (VRP with Backhauls oraz VRP with Pick-Up and Delivering – problem rozwózkowo-zwózkowy)
• Problemy, w których warunki zostały ujęte stochastycznie (Stochastic VRP)

Problem marszrutyzacji a problemy "capacitated arc routing"

W problemie marszrutyzacji klienci stwarzający popyt na transport są zlokalizowani w wierzchołkach grafu. W rzeczywistości problem ten ma zastosowanie np. w tradycyjnych firmach przewozowych. Problemy, w których popyt jest zlokalizowany na krawędziach grafu należą do grupy problemów arc routing, a odpowiednikiem problemu marszrutyzacji jest problem CARP. W rzeczywistości sytuacje takie występują przykładowo podczas opracowywania marszrut dla zamiatarek drogowych , śmieciarek , czy też pługopiaskarek ^[4].

Bibliografia

• Jacek Żak, Wielokryterialne Wspomaganie Decyzji w Transporcie Drogowym, Wydawnictwo Politechniki Poznańskiej, Poznań, 2005,

Linki zewnętrzne

• Serwis poświęcony problemowi marszrutyzacji ( ang. )
• Serwis poświęcony problemowi marszrutyzacji ( ang. )
• Witryna VRP w BranchAndCut.org ( ang. )

Przypisy