Problem marszrutyzacji

Tagi: Zarządzanie logistyką, Zarządzanie transportem
Problem marszrutyzacji - problem decyzyjny, związany z wyznaczeniem optymalnych tras przewozowych dla określonej liczby środków transportu, mających obsłużyć klientów, znajdujących się w różnych punktach.

Problem marszrutyzacji 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)

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

gdzie:
r – pojazd należący do zbioru jednorodnych (identycznych) pojazdów R
f, g – wierzchołki pomiędzy, którymi odbywa się przewóz
‎– koszt przewozu pomiędzy wierzchołkami f i g
‎ – 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 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 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).
  • :
    ‎– warunek przypisania dokładnie jednego pojazdu
  • :
    ‎ – warunek niedzielonych dostaw

Przykładowe rozwinięcia problemu

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
  • ::[[ Plik:Problem marszrutyzacji 9.1.png]] ‎ – czas rozpoczęcia obsługi klienta f
  • ::
    ‎ – czas przejazdu pomiędzy f, a g
  • ::
    ‎ – czas rozpoczęcia obsługi klienta g


Bibliografia

ostatnia modyfikacja 30 listopada 2017 r.