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^[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 (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)^[2].

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^[3].

Klasyczne ujęcie problemu

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

Minimalizowana jest funkcja

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

gdzie:

${\displaystyle r}$ – pojazd należący do zbioru jednorodnych (identycznych) pojazdów ${\displaystyle R,}$

${\displaystyle f,}$ ${\displaystyle g}$ – wierzchołki pomiędzy, którymi odbywa się przewóz,

${\displaystyle c_{fg}}$ – koszt przewozu pomiędzy wierzchołkami ${\displaystyle f}$ i ${\displaystyle g,}$

${\displaystyle x_{fgr}}$ – zmienna binarna określająca, czy pomiędzy wierzchołkami ${\displaystyle f}$ i ${\displaystyle g}$ pojazd ${\displaystyle 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 ${\displaystyle 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:

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

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

  ${\displaystyle \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 ${\displaystyle 0}$ oraz ${\displaystyle n+1,}$ to dopuszczalne są puste drogi.

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

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

  ${\displaystyle \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).

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

  gdzie:

  ${\displaystyle d_{f}}$ – popyt przypisany do danego klienta,

  ${\displaystyle 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)

  ${\displaystyle \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:

  ${\displaystyle t_{fr}}$ – czas rozpoczęcia obsługi klienta ${\displaystyle f,}$

  ${\displaystyle t_{fg}}$ – czas przejazdu pomiędzy ${\displaystyle f}$ a ${\displaystyle g,}$

  ${\displaystyle t_{gr}}$ – czas rozpoczęcia obsługi klienta ${\displaystyle 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^[4].

Przypisy

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.)