Górnośląskie Centrum Obliczeń Naukowych i Inżynierskich

Wyznaczanie tras dla pojazdów z oknami czasowymi (ang. vehicle routing problem with time windows, VRPTW) jest problemem optymalizacji dyskretnej należącym do klasy problemów NP-trudnych. Głównym celem optymalizacji jest zminimalizowanie liczby samochodów (o ograniczonej pojemności) obsługujących klientów rozmieszczonych na mapie, a drugim celem jest zminimalizowanie sumarycznej długości tras przebytej przez wszystkie samochody rozwożące towar.

Każdy z klientów definiuje ilość towaru, który powinien zostać dostarczony, oraz okno czasowe, w którym musi rozpocząć się jego obsługa. Metody rozwiązywania VRPTW można najogólniej podzielić na dwie grupy: (i) metody dokładne oraz (ii) heurystyczne, do których należą np. symulowane wyżarzanie, poszukiwanie z tabu, algorytmy mrówkowe, a także algorytmy ewolucyjne – genetyczne i memetyczne (zarówno sekwencyjne jak i równoległe). Algorytmy należące do drugiej grupy stosuje się w praktyce – pozwalają one wyznaczyć w rozsądnym czasie rozwiązania nieoptymalne o koszcie bliskim kosztowi rozwiązania optymalnego. W ostatnich latach wykazano, że zastosowanie algorytmów memetycznych – będących hybrydyzacją algorytmów ewolucyjnych wykorzystywanych do eksploracji przestrzeni rozwiązań z algorytmami lokalnych ulepszeń, służącymi do jej intensywnej eksploatacji – dla rozwiązywania problemu pozwala na uzyskanie wyników o bardzo wysokiej jakości w krótkim czasie.

W równoległym algorytmie memetycznym dla minimalizacji przebytej trasy w VRPTW, w którym zastosowano ideę zrównoleglenia obliczeń opartą na modelu wyspowym, procesy cyklicznie komunikują się ze sobą, przesyłając najlepsze rozwiązania. Model wyspowy pozwala na niezależny rozwój wielu populacji i wymianę najlepszych rozwiązań między procesami ze ściśle określoną częstotliwością. Schemat kooperacji definiuje częstotliwość kooperacji, jej topologię, sposób wyboru oraz wykorzystania rozwiązań wysłanych/odebranych. Wybór schematu znacznie wpływa na zbieżność obliczeń, jakość rozwiązań oraz czas wykonania algorytmu niezbędny do uzyskania rozwiązań o zamierzonej jakości. Niestety kooperacja procesów jest operacją stosunkowo kosztowną (zwłaszcza w wypadku dużej liczby procesów równoległych).

W ramach niniejszej pracy zbadany zostanie wpływ zastosowanych schematów kooperacji na jakość rozwiązań otrzymywanych za pomocą równoległego algorytmu memetycznego, oraz na zbieżność obliczeń. Wstępne badania, przeprowadzone dla zbioru testów wzorcowych Gehringa i Hombergera (GH) – zawierających 400 klientów – pozwoliły na znalezienie trzech najlepszych topologii kooperacji. Dalsze badania, przeprowadzone dla najtrudniejszych testów GH (zawierających 1000 klientów), pozwolą na wyłonienie najlepszych schematów i częstotliwości kooperacji w zależności od charakterystyki testów (położenia klientów, charakterystyki okien czasowych oraz pojemności dostępnych pojazdów).


Szczegóły opracowanych schematów kooperacji oraz wyniki eksperymentalnych testów porównawczych dla testów wzorcowych Gehringa i Hombergera (zawierających 1000 klientów) mają być opublikowane w czasopiśmie JCR.

FaLang translation system by Faboba