Problem marszrutyzacji: Różnice pomiędzy wersjami

[[Plik:Vehicle Routing Problem Example.svg|thumb|right|300px|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 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<ref name="MoVRP">{{Cytuj pismo |autor=Jozefowiez Nicolas, Semet Frédéric, Talbi El-Ghazali |tytuł=Multi-objective vehicle routing problems| czasopismo=[[European Journal of Operational Research]]| wydawca=Elseiver| wydanie=189| wolumin=2| strony=293–309| issn=0377-2217| język=en| data=2008| doi=10.1016/j.ejor.2007.05.055}}</ref>. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

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

* 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 ''<math>r''.</math> W przypadku wierzchołków pośrednich liczba pojazdów wjeżdżających jest równa liczbie pojazdów wyjeżdżających.:

*: <math>\forall_{r \in R} \sum_{g \in \epsilon} x_{0,g,r} = 1</math> – dla bazy początkowej,

*: <math>\forall_{r \in R} \sum_{f \in \epsilon} x_{f,n+1,r} = 1</math> – dla bazy końcowej,

*: <math>\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</math> – dla wierzchołków pośrednich.

*:: W przypadku, gdy istnieje połączenie pomiędzy punktami ''<math>0''</math> oraz ''<math>n+1'',</math> to dopuszczalne są ''puste drogi''.

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

*: <math>\forall_{f \in \Psi} \sum_{g \in \epsilon} \sum_{r \in R} x_{fgr} = 1</math> – warunek przypisania dokładnie jednego pojazdu,

*: <math>\forall_{f \in \epsilon} \land \forall_{g \in \epsilon} \land \forall_{r \in R} ~ x_{fgr} \in \{ 0,1 \}</math> – warunek niedzielonych dostaw.

*: <math>\forall_{r \in R} \sum_{f \in \Psi} d_f \sum_{g \in \Psi} x_{fgr} \leleqslant m_r,</math>

*:: gdzie:

*:: <math>d_f</math> – popyt przypisany do danego klienta,

*:: <math>m_r</math> – pojemność pojazdów.

*: <math>\forall_{r \in R} \land \forall_{f \in \Psi} \land \forall_{g \in \Psi} ~ x_{fgr} (t_{fr} + t_{fg} - t_{gr}) \leleqslant 0,</math>

*:: gdzie:

*:: <math>t_{fr}</math> – czas rozpoczęcia obsługi klienta ''<math>f'',</math>

*:: <math>t_{fg}</math> – czas przejazdu pomiędzy ''<math>f''</math> a ''<math>g'',</math>

*:: <math>t_{gr}</math> – czas rozpoczęcia obsługi klienta ''<math>g''.</math>

* Problemyproblemy uwzględniające niesymetryczność kosztów przewozu pomiędzy wierzchołkami,

* Problemyproblemy uwzględniające niehomogeniczność taboru,

* Problemyproblemy uwzględniające przejazdy drobnicowe (Less Than Truckload),

* Problemyproblemy uwzględniające ograniczenie maksymalnej długości trasy,

* Problemyproblemy umożliwiające ustalenie baz (jednej lub kilku), w których pojazdy zaczynają i kończą podróż (Multiple Depot VRP),

* Problemyproblemy umożliwiające dodanie baz pomocniczych (VRP with Satellite Facilities),

* Problemyproblemy umożliwiające ustalenie częstotliwości odbioru/dostawy ładunku,

* Problemyproblemy umożliwiające uwzględnienie okien czasowych (VRP with Time Windows) odbioru/wysłania towaru.,

* Problemyproblemy wiążące problem marszrutyzacji z problemem kontroli zapasów u klientów,

* Problemyproblemy uwzględniające możliwość obsługi jednego klienta przez kilka pojazdów (Split Delivery VRP),

* Problemyproblemy w których kosztowa funkcja celu zastąpiona została innymi parametrami (np. czas wykonania zleceń, długość tras, ilość przewiezionego ładunku),

* Problemyproblemy umożliwiające zdefiniowanie kolejności odwiedzania poszczególnych miejsc oraz opcjonalnego odwiedzania niektórych punktów.,

* Problemyproblemy 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),

* Problemyproblemy, w których warunki zostały ujęte stochastycznie (Stochastic VRP).

== Problem marszrutyzacji a problemy "capacitated„capacitated arc routing"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 [[Capacitated Arc Routing Problem|CARP]]. W rzeczywistości sytuacje takie występują przykładowo podczas opracowywania marszrut dla [[zamiatarka|zamiatarek drogowych]], [[śmieciarka|śmieciarek]], czy też [[pługopiaskarka|pługopiaskarek]]<ref name="arcrouting">{{Cytuj pismo| nazwisko=Muyldermans| imię=Luc| tytuł=Routing, districting and location for arc traversal problems| czasopismo=4OR: A Quarterly Journal of Operations Research| wydawca=Springer-Verlag| wolumin=2| strony=169–172| język=en| data=czerwiec 2003| doi=10.1007/s10288-003-0015-5}}</ref>.

* {{Cytuj | autor = Jacek Żak | tytuł = Wielokryterialne wspomaganie decyzji w transporcie drogowym | data = 2005 | isbn = 83-7143-591-6 | miejsce = Poznań | wydawca = Wydawnictwo Politechniki Poznańskiej | oclc = 69491746}}