Problem marszrutyzacji

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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:

problem komiwojażera (traveling salesman problem),
problem domokrążnego kupca (traveling purchaser problem),
problem chińskiego listonosza (chinese postman problem),

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

[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

c f g

– koszt przewozu pomiędzy wierzchołkami f i g

x f g r

– 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

$d f$ – popyt przypisany do danego klienta

$m r$ – 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

$t f r$ – czas rozpoczęcia obsługi klienta f

$t f g$ – czas przejazdu pomiędzy f, a g

$t g r$ – 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)