6570141614

3.4. Odległościowy problem marszrutyzacji

Wariant PPM, w którym zamiast maksymalnej pojemności pojazdu używa się maksymalnej długości trasy lub maksymalnego możliwego czasu transportu. W praktyce każda krawędź e E E ma przypisaną nieujemną długość (czas lub odległość) a suma długości krawędzi w jednym cyklu nie może przekraczać zadanej wartości T. Jeśli długość krawędzi reprezentuje czas, można dodatkowo rozpatrywać czas obsługi s-, powiązany z klientem i, odzwierciedlający na przykład skomplikowany rozładunek. Uwzględnienie czasu obsługi polega na dodaniu do czasu krawędzi połowy czasu obsługi klientów reprezentowanych przez wierzchołki każdej krawędzi, tj. dla każdej krawędzi e(i,j)EE, t'y = ty + j + ■£, gdzie fy jest czasem krawędzi uwzględniającym czas obsługi, natomiast ty oznacza bazowy czas krawędzi.

3.5. Marszrutyzacja z oknem czasowym

Przypadek rozszerzający PPM, dodatkowo każdemu z klientów przypisany jest przedział czasowy, w którym klient ten może zostać obsłużony. Z formalnego punktu widzenia, istnieją dwie funkcje operujące na wierzchołkach: ssj oraz se_i( zwracające dla każdego wierzchołka i należącego do V odpowiednio czas początku i końca okna czasowego, w którym może nastąpić obsługa. Pojazd musi rozpocząć i zakończyć obsługę wewnątrz okna czasowego. Jeśli istnieje dodatni czas obsługi klienta i równy s-, musi zostać uwzględniony - czas startu obsługi musi zawierać się w [ssj, se-Sj]. Jeśli pojazd dojedzie do klienta i wcześniej niż ssi, możliwe jest czekanie na start obsługi.

Rozwiązanie PMOC 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 klienta i obsługa jest wykonywana w oknie czasowym [ssj, sej], pojazd zatrzymuje się na określony czas s-,

16