Problem marszrutyzacji


Problem marszrutyzacji w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania 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 marszrutyzacjiproblem 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:

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

Spis treści

Klasyczne ujęcie problemu | edytuj kod

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

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

gdzie:

r {\displaystyle r} – pojazd należący do zbioru jednorodnych (identycznych) pojazdów R , {\displaystyle R,} f , {\displaystyle f,} g {\displaystyle g} – wierzchołki pomiędzy, którymi odbywa się przewóz, c f g {\displaystyle c_{fg}} – koszt przewozu pomiędzy wierzchołkami f {\displaystyle f} i g , {\displaystyle g,} x f g r {\displaystyle x_{fgr}} – zmienna binarna określająca, czy pomiędzy wierzchołkami f {\displaystyle f} i g {\displaystyle g} pojazd r {\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 r . {\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: r R g ϵ x 0 , g , r = 1 {\displaystyle \forall _{r\in R}\sum _{g\in \epsilon }x_{0,g,r}=1} – dla bazy początkowej, r R f ϵ x f , n + 1 , r = 1 {\displaystyle \forall _{r\in R}\sum _{f\in \epsilon }x_{f,n+1,r}=1} – dla bazy końcowej, r R f Ψ f ϵ x f , z , r g ϵ x z , g , r = 0 {\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 0 {\displaystyle 0} oraz n + 1 , {\displaystyle n+1,} to dopuszczalne są puste drogi.
  • Przypisanie każdemu klientowi dokładnie jednego pojazdu, który zaspokaja jego zapotrzebowanie (dostawy są niedzielone): f Ψ g ϵ r R x f g r = 1 {\displaystyle \forall _{f\in \Psi }\sum _{g\in \epsilon }\sum _{r\in R}x_{fgr}=1} – warunek przypisania dokładnie jednego pojazdu, f ϵ g ϵ r R   x f g r { 0 , 1 } {\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 | edytuj kod

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

  • Warunek nieprzekroczenia pojemności poszczególnych środków transportu (problem CVRP). r R f Ψ d f g Ψ x f g r m r , {\displaystyle \forall _{r\in R}\sum _{f\in \Psi }d_{f}\sum _{g\in \Psi }x_{fgr}\leqslant m_{r},} gdzie: d f {\displaystyle d_{f}} – popyt przypisany do danego klienta, m r {\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) r R f Ψ g Ψ   x f g r ( t f r + t f g t g r ) 0 , {\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: t f r {\displaystyle t_{fr}} – czas rozpoczęcia obsługi klienta f , {\displaystyle f,} t f g {\displaystyle t_{fg}} – czas przejazdu pomiędzy f {\displaystyle f} a g , {\displaystyle g,} t g r {\displaystyle t_{gr}} – czas rozpoczęcia obsługi klienta g . {\displaystyle g.}

Rozwinięcia problemu | edytuj kod

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” | edytuj kod

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 | edytuj kod

  1. Jozefowiez Nicolas, Semet Frédéric, Talbi El-Ghazali. Multi-objective vehicle routing problems. „European Journal of Operational Research”. 2 (189), s. 293–309, 2008. Elseiver. DOI: 10.1016/j.ejor.2007.05.055. ISSN 0377-2217 (ang.). 
  2. Gilbert Laporte: Fifty Years of Vehicle Routing (ang.). W: Prezentacja wygłoszona podczas Międzynarodowego Seminarium Transportowego [on-line]. transportation.put.poznan.pl, 2009-04-23. [dostęp 2009-05-10].
  3. (ang.)(PDF)Biografia G.B. Dantziga autorstwa Richarda Cottle, Ellisa Johnsona, and Rogera Wetsa.
  4. Luc Muyldermans. Routing, districting and location for arc traversal problems. „4OR: A Quarterly Journal of Operations Research”. 2, s. 169–172, czerwiec 2003. Springer-Verlag. DOI: 10.1007/s10288-003-0015-5 (ang.). 

Bibliografia | edytuj kod

  • 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 | edytuj kod

Na podstawie artykułu: "Problem marszrutyzacji" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy