6570141615

PMOC jest problemem NP-zupełnym, generalizującym problem PPM. PMOC jest tożsame z PPM dla ssj=0 oraz sei=oo dla każdego wierzchołka i należącego do V\{0}. Dodatkowo, problem komiwojażera z oknami czasowymi jest przypadkiem PMOC dla C > d(V) oraz K=l.

3.6.    Marszrutyzacja z transportem powrotnym

Rozszerzenie PPM, w którym zbiór klientów (V\{0}) dzieli się na dwa podzbiory, L oraz B⁴. Zbiór L zawiera n klientów będących odbiorcami, każdy z nich ma przypisane zapotrzebowanie na towary, natomiast B zawiera m klientów będących dostawcami, każdy z nim ma przypisaną ilość dóbr dostarczanych, które muszą zostać odebrane przez pojazd. Zachodzi równość: m+n=|V\{0}|. Występuje pierwszeństwo obsługi klientów ze zbioru L przed klientami ze zbioru B na każdej trasie. Zanim jakikolwiek wierzchołek ze zbioru B będzie zostanie odwiedzony przez pojazd, wszystkie wierzchołki ze zbioru L na tej trasie muszą zostać obsłużone. Rozwiązanie PMTP polega na znalezieniu zbioru dokładnie K cykli z minimalnym kosztem, takich, że:

•    Każdy cykl odwiedza wierzchołek reprezentujący HUB

•    Każdy wierzchołek reprezentujący klienta jest odwiedzony przez dokładnie jeden cykl

•    Suma zapotrzebowania wierzchołków w danym cyklu nie przekracza ładowności pojazdu C

•    W każdym cyklu klienci ze zbioru L (do których dobra są dostarczane) są obsługiwani przed klientami ze zbioru B (od których następuje odbiór towarów)

PMTP jest problemem NP-zupełnym, generalizującym PPM. PMTP jest tożsame z PPM dla B=[todo: zbiór pusty]. Dodatkowo, problem komiwojażera z transportem powrotnym stanowi szczególny przypadek PMTP, w którym C>=max{d(L), d(B)} oraz K=l.

3.7.    Marszrutyzacja z dostawą/odbiorem

Podstawowa wersja PMOD każdemu wierzchołkowi i należącemu do V\{0} (wierzchołek reprezentujący klienta) przypisuje dwie nieujemne wartości di oraz pi, oznaczające odpowiednio zapotrzebowanie na dostarczenie oraz odbiór jednorodnych dóbr. Wartości di oraz pi mogą być reprezentowane ogólnie jako d'j=dj-Pi oznaczające różnicę dostawy i odbioru dla danego klienta (może przyjmować wartość ujemną). Dla każdego wierzchołka i należącego do V\{0}, Oj oznacza źródło dostawy (skąd pochodzą towary, które będą dostarczone do wierzchołka i), natomiast Di oznacza cel dostawy (dokąd mają zostać dostarczone towary, które będą odebrane z wierzchołka

L od Linehaul czyli dostarczanie towarów, B od Backhaul, dosłownie wleczenie wsteczne, czyli transport powrotny

17