Problem marszrutyzacji

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

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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 .

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