6570141616

i). Zakłada się, że dla każdego klienta, dostawa odbywa się przed odbiorem. Aktualny stan załadowania pojazdu określa się jako ładunek przed obsługą klienta minus ładunek dostarczany do klienta plus ładunek odbierany od klienta. Rozwiązanie PMOD 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

•    Dla każdego wierzchołka i, wierzchołek Oi, jeśli różny od HUB-a, musi zostać odwiedzony w tym samym cyklu przed wierzchołkiem i

•    Dla każdego wierzchołka i, wierzchołek Di, jeśli różny od HUB-a, musi zostać odwiedzony w tym samym cyklu po wierzchołku i

PMOD jest problemem NP-zupełnym, generalizującym PPM. PMOD jest tożsame z PPM dla 0|=Di=0 oraz pj=0 Vi G V. Dodatkowo, problem komiwojażera z dostawą/odbiorem stanowi szczególny przypadek PMOD, w którym K=l.

18