Problem marszrutyzacji

Problem marszrutyzacji – problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej liczby ś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. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

Graficzna prezentacja rozwiązania problemu marszrutyzacji (nieoptymalnego!). Zostały wyznaczone trzy marszruty (zobrazowane liniami: ciągłą, przerywaną i kropkowaną), takie że każda swój punkt początkowy i końcowy ma w bazie (żółty prostokąt „D”) oraz każda przebiega przez wszystkie punkty pośrednie (klientów – czerwone, zielone i niebieskie punkty).

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

• problem komiwojażera (ang. traveling salesman problem),
• problem chińskiego listonosza (ang. 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 liczbie klientów (do 135).

Problem został po raz pierwszy zaprezentowany przez G.B. Dantziga oraz R.H. Ramsera w 1959 roku w pracy The Truck Dispatching Problem opublikowanej na łamach czasopisma Management Science.

Klasyczne ujęcie problemu

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

Minimalizowana jest funkcja

$\min C=\sum _{r\in R}\sum _{f\in \Psi }\sum _{g\in \Psi }c_{fg}x_{fgr},$

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 liczba pojazdów wjeżdżających jest równa liczbie pojazdów wyjeżdżających:

  $\forall _{r\in R}\sum _{g\in \epsilon }x_{0,g,r}=1$ – dla bazy początkowej,

  $\forall _{r\in R}\sum _{f\in \epsilon }x_{f,n+1,r}=1$ – dla bazy końcowej,

  $\forall _{r\in R}\land \forall _{f\in \Psi }\sum _{f\in \epsilon }x_{f,z,r}-\sum _{g\in \epsilon }x_{z,g,r}=0$ – 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):

  $\forall _{f\in \Psi }\sum _{g\in \epsilon }\sum _{r\in R}x_{fgr}=1$ – warunek przypisania dokładnie jednego pojazdu,

  $\forall _{f\in \epsilon }\land \forall _{g\in \epsilon }\land \forall _{r\in R}~x_{fgr}\in \{0,1\}$ – 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).

  $\forall _{r\in R}\sum _{f\in \Psi }d_{f}\sum _{g\in \Psi }x_{fgr}\leqslant m_{r},$

  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)

  $\forall _{r\in R}\land \forall _{f\in \Psi }\land \forall _{g\in \Psi }~x_{fgr}(t_{fr}+t_{fg}-t_{gr})\leqslant 0,$

  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 Delivery – 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.

Bibliografia

• JacekJ. Żak JacekJ., Wielokryterialne wspomaganie decyzji w transporcie drogowym, Poznań: Wydawnictwo Politechniki Poznańskiej, 2005, ISBN 83-7143-591-6, OCLC 69491746 .brak strony (książka)

Linki zewnętrzne

• Serwis poświęcony problemowi marszrutyzacji. osiris.tuwien.ac.at. [zarchiwizowane z tego adresu (2007-03-22)]. (ang.)
• Serwis poświęcony problemowi marszrutyzacji (ang.)
• Witryna VRP w BranchAndCut.org (ang.)