6570141613

pojemność, wspólna dla wszystkich pojazdów. Celem jest minimalizacja sumarycznego kosztu obsługi wszystkich klientów, gdzie koszt to funkcja operująca na drodze (krawędzi) przypisująca jej długość bądź czas potrzebny na jej przebycie.

3.3.1. Formalny zapis problemu

Graf G=(V,E) jest grafem z klasy grafów zupełnych. Wierzchołki i=l, ..., n odpowiadają klientom, natomiast wierzchołek i=0 odpowiada HUB-owi. Dana jest funkcja kosztu c(i,j) przypisująca krawędzi e(i,j) G E nieujemne wartości, reprezentujące koszt przejścia od wierzchołka i do wierzchołka j. Niedopuszczalne jest występowanie pętli własnych, co zostaje wymuszone przez wartość funkcji kosztu dla tego samego wierzchołka: Ca = co. Każdemu klientowi i E V jest przypisane określone zapotrzebowanie d_it które należy dostarczyć klientowi. Do HUB-a przypisane jest fikcyjne zapotrzebowanie równe 0. Dla danego zbioru S zawierającego się w V, niech d(s) =    oznacza całkowite zapotrzebowanie zbioru.

Zbiór identycznych pojazdów K o danej pojemności C jest dostępny w HUB-ie. Aby zapewnić rozwiązywalność problemu, zakładamy, że d_t < C. Jeden pojazd może przejechać tylko raz wyznaczoną trasą (początek w HUB-ie, obsługa klientów, powrót do HUB-a). Ilość pojazdów w zbiorze K jest nie mniejsza, niż K_min oznaczająca minimalną ilość pojazdów potrzebnych do obsłużenia wszystkich klientów. Wartość K_min może być wyznaczona poprzez rozwiązanie problemu plecakowego. Często jest stosowane trywialne dolne ograniczenie:

[<fO)\cl

Rozwiązanie PPM polega na znalezieniu dokładnie K prostych cykli (każdy cykl odpowiada trasie danego pojazdu) z minimalnym kosztem, zdefiniowanym jako suma kosztów krawędzi należących do cykli, 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

PPM jest problemem NP-zupełnym, generalizującym problem komiwojażera. PPM jest tożsame z problemem komiwojażera dla C > d(v) oraz K=l.

15