Problem marszrutyzacji

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

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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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

Klasyczne ujęcie problemuEdytuj

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

 

gdzie:

  – pojazd należący do zbioru jednorodnych (identycznych) pojazdów  
    – wierzchołki pomiędzy, którymi odbywa się przewóz,
  – koszt przewozu pomiędzy wierzchołkami   i  
  – zmienna binarna określająca, czy pomiędzy wierzchołkami   i   pojazd   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   W przypadku wierzchołków pośrednich liczba pojazdów wjeżdżających jest równa liczbie pojazdów wyjeżdżających:
      – dla bazy początkowej,
      – dla bazy końcowej,
      – dla wierzchołków pośrednich.
    W przypadku, gdy istnieje połączenie pomiędzy punktami   oraz   to dopuszczalne są puste drogi.
  • Przypisanie każdemu klientowi dokładnie jednego pojazdu, który zaspokaja jego zapotrzebowanie (dostawy są niedzielone):
      – warunek przypisania dokładnie jednego pojazdu,
      – warunek niedzielonych dostaw.

Przykładowe rozwinięcia problemuEdytuj

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

  • Warunek nieprzekroczenia pojemności poszczególnych środków transportu (problem CVRP).
     
    gdzie:
      – popyt przypisany do danego klienta,
      – 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)
     
    gdzie:
      – czas rozpoczęcia obsługi klienta  
      – czas przejazdu pomiędzy   a  
      – czas rozpoczęcia obsługi klienta  

Rozwinięcia problemuEdytuj

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

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

PrzypisyEdytuj

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

BibliografiaEdytuj

  • Jacek Żak, Wielokryterialne wspomaganie decyzji w transporcie drogowym, Poznań: Wydawnictwo Politechniki Poznańskiej, 2005, ISBN 83-7143-591-6, OCLC 69491746.

Linki zewnętrzneEdytuj