Zastosowanie algorytmów heurystycznych do rozwiązywania problemu układania tras pojazdów

Planowanie to jest szczególnie trudne w przypadku dystrybucji towarów, kiedy pojedynczy pojazd dostarcza ładunki w jednym cyklu do wielu odbiorców. W tej sytuacji planowanie to polega na określeniu kolejności obsługi odbiorców i w sposób znaczący może przyczynić się do skrócenia długości trasy pokonywanej przez pojazd. Obok długości trasy pojazdu kryterium planowania może być chociażby czas realizacji trasy. Tak więc, tego typu planowanie transportu staje się problemem natury kombinatorycznej.

W badaniach operacyjnych problem planowania trasy pojazdu dokonującego zwózki bądź rozwózki ładunków nosi miano problemu układania tras pojazdów (ang. Vehicle Routing Problem) i wywodzi się od powszechnie znanego problemu komiwojażera. W ogólnym ujęciu problem układania tras pojazdów polega na obsłużeniu przez pojazd każdego dostawcy/odbiory tylko jeden raz i powrocie do bazy skąd rozpoczęta została trasa. Kryterium optymalności jest w tym miejscu długość trasy, przy czym znane są odległości pomiędzy wszystkimi odbiorcami/dostawcami oraz odległości pomiędzy tymi dostawcami/odbiorcami a bazą.

W literaturze istnieje wiele różnych odmian problemu układania tras pojazdów, w zależności od warunków, na jakich pojazdy mogą realizować swoje trasy. Warunki te dotyczą chociażby określonej ładowności pojazdów, liczby baz, z jakich pojazdy obsługują odbiorców, okien czasowych odbiorców, możliwości jednoczesnej zwózki i rozwózki, konieczności zakończenia trasy w bazie, czy też wielkości zapotrzebowania odbiorców wyrażonego rozkładem prawdopodobieństwa. Niniejszy artykuł jest podsumowaniem badań nad algorytmami heurystycznymi stosowanymi do rozwiązywania problemu układania tras pojazdów.

Artykuł zawiera 21180 znaków.

Źródło: Czasopismo Logistyka