Problem marszrutyzacji

Skocz do: nawigacji, szukaj
Graficzne przedstawienie rozwiązania problemu marszrutyzacji: zostały wyznaczone trzy marszruty (czarne, zielone i niebieskie kreski), które swój punkt początkowy i końcowy mają w bazie (czarny punkt) oraz przebiegają przez wszystkie punkty pośrednie (klientów - niebieskie punkty).

Problem marszrutyzacji (MAR) (ang. Vehicle Routing Problem (VRP)) – problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej ilości środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Problematyka ta należy do podstawowej problematyki zarządzania operacyjnego floty ś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.

Problem został po raz pierwszy zaprezentowany przez G.B. Dantziga oraz R.H. Ramser'a w 1959 roku w pracy The Truck Dispatching Problem opublikowanej na łamach Management Science[1].

Spis treści

[edytuj] Klasyczne ujęcie problemu

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

Minimalizowana jest funkcja

minC = \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
cfg – koszt przewozu pomiędzy wierzchołkami f i g
xfgr – 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 ilość pojazdów wjeżdżających jest równa ilości 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} \and \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} \and \forall_{g \in \epsilon} \and \forall_{r \in R} ~ x_{fgr} \in \{ 0,1 \} – warunek niedzielonych dostaw
  • Warunek nieprzekroczenia pojemności poszczególnych środków transportu.
    \forall_{r \in R} \sum_{f \in \Psi} d_f \sum_{g \in \epsilon} x_{fgr} \le m_r
    gdzie
    df – popyt przypisany do danego klienta
    mr – pojemność pojazdów
  • Ograniczenia czasowe (pojazd nie przybędzie do określonego wierzchołka przed wykonaniem poprzednich zadań w węzłach poprzedzających)
    \forall_{r \in R} \and \forall_{f \in \epsilon} \and \forall_{g \in \epsilon} ~ x_{fgr} (t_{fr} + t_{fg} - t_{gr}) \le 0
    gdzie
    tfr – czas rozpoczęcia obsługi klienta f
    tfg – czas przejazdu pomiędzy f, a g
    tgr – czas rozpoczęcia obsługi klienta g

[edytuj] 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 Delivering – problem rozwózkowo-zwózkowy)
  • Problemy, w których problem został ujęty stochastyczne (Stochastic VRP)

[edytuj] Bibliografia

  • Jacek Żak, Wielokryterialne Wspomaganie Decyzji w Transporcie Drogowym, Wydawnictwo Politechniki Poznańskiej, Poznań, 2005, ISBN 83-7143-591-6

[edytuj] Linki zewnętrzne

[edytuj] Przypisy

  1. ↑ (en)(PDF)Biografia G.B. Dantziga autorstwa Richarda Cottle'a, Ellisa Johnson'a, and Rogera Wets'a
Źródło: „http://pl.wikipedia.org/wiki/Problem_marszrutyzacji”