Heurystyki generowania tras kompletacji

Zagadnienia sekwencjonowania miejsc pobierania artykułów i ustalania tras pracowników analizowano w literaturze problemu dla czterech podstawowych systemów magazynowych zawierających: konwencjonalne systemy i układy komisjonowania z wieloma równoległymi korytarzami roboczymi (jedno- i wieloblokowe), automatyczne systemy składowania (AS/RS) człowiek do materiału oraz materiał do człowieka, jak również systemy komisjonowania wyposażone w automatyczne regały karuzelowe.

Konwencjonalne układy komisjonowania z wieloma równoległymi korytarzami mają w większości przypadków regularny, prostokątny (ewentualnie kwadratowy) układ. Zawierają wiele równoległych korytarzy, zlokalizowanych wzdłuż miejsc oferowania asortymentu (zestawionych w rzędy regałowe, pola odkładcze, itp.), nazywanych korytarzami roboczymi lub kompletacyjnymi oraz dwa lub więcej korytarze poprzeczne, służące do zmiany korytarzy roboczych. Liczba korytarzy poprzecznych warunkuje liczbę bloków regałowych (wydzielonych dwoma korytarzami poprzecznymi powierzchni wraz z rzędami regałowymi i korytarzami roboczymi).

Opisanym powyżej konwencjonalnym układom komisjonowania o układzie jednoblokowym poświęcono w literaturze wiele uwagi. Przedstawiono tam wiele heurystyk wskazujących sposoby sekwencjonowania miejsc oferowania i wyznaczania w ten sposób tras kompletacji. Do najbardziej znanych i najczęściej omawianych należy zaliczyć metodę każdego korytarza S-shape, która charakteryzuje się tym, iż pracownicy przemierzają każdy korytarz roboczy, w którym znajduje się co najmniej jedna lokalizacja do odwiedzenia. Przeciwieństwem tej metody jest metoda powrotna Return zakładająca, iż pracownik wchodzi tylko do tych korytarzy roboczych, w których zlokalizowany jest co najmniej jeden artykuł do pobrania, jednak nie przemierza go całego, a jedynie dociera do miejsca pobrania i wraca do tego samego korytarza poprzecznego, z którego do niego wszedł. Heurystyka kompleksowa Composite Heuristic łączy w sobie cechy dwóch poprzednich. Umożliwia ocenę tego, czy przemieszczając się pomiędzy kolejnymi parami miejsc pobrania należy przejść cały korytarz czy zawrócić. Inna metoda, zwana heurystyką punktu środkowego Midpoint dzieli jednoblokowy układ strefy kompletacji na dwie równe części (górną i dolną). Każde z miejsc pobrań znajdujących się w określonej części jest odwiedzane z korytarza poprzecznego należącego do tej części. Heurystyka największej szczeliny Largest Gap jest pewną odmianą metody punktu środkowego. W tym przypadku pojedynczy blok regałowy również dzielony jest na dwie części, ale podział jest umowny, tzn. wyznaczany jest niezależnie dla każdego każdego korytarza i zależy od ułożenia w nim miejsc pobrań. Korytarze dzielone są w miejscu, które stanowi największy odstęp pomiędzy dwoma miejscami pobrań w tym korytarzu albo pomiędzy końcem korytarza poprzecznego a najbliższym miejscem pobrań. Zastosowanie metody Largest Gap gwarantuje uzyskanie co najmniej tak krótkich tras, jak w przypadku metody Midpoint. Podobne metody heurystyczne zostały opracowane również dla wieloblokowych układów stref kompletacji, np. zmodyfikowane heurystyki S-shape i Largest Gap, jak również korytarz-po-korytarzu Aisle-by-aisle, czy kombinowana Combined. Dwie ostatnie opierają się na programowaniu dynamicznym i konstruują trasy kompletacji na podstawie odpowiedniego powiązania ze sobą najkrótszych ścieżek cząstkowych (segmentów całych tras).

W szeroko rozumianej problematyce wyznaczania tras (w dystrybucji, handlu, zaopatrzeniu, jak również transporcie wewnętrznym) bardzo często analizowane jest także zagadnienie komiwojażera. Najogólniej można je przedstawić w poniżej przytoczony sposób. Danych jest n punktów do odwiedzenia, które powiązane są ze sobą drogami o określonych długościach. W jednym z punktów (mieście początkowym) znajduje się komiwojażer, który chce odwiedzić wszystkie punkty (miejscowości) w taki sposób, aby w każdym z nich znaleźć się dokładnie jeden raz, a na koniec powrócić do miejsca startowego. Celem jest znalezienie najkrótszej możliwej trasy. Problem ten znajduje swoje zastosowanie również w procesach magazynowych. Osoba realizująca zamówienie klienta (komiwojażer) rozpoczyna proces kompletacji w punkcie, w którym pobiera listę kompletacyjną, czyli tzw. punkcie startu kompletacji. Następnie musi odwiedzić wszystkie miejsca oferowania asortymentu, by w końcu powrócić do punktu rozpoczęcia procesu wraz ze skompletowaną jednostką ładunkową.

W klasycznym podejściu do problemu komiwojażera, wszystkie miasta muszą być odwiedzone tylko raz. W przypadku procesu komisjonowania sytuacja wygląda nieco inaczej. Jedynymi miejscami, które muszą zostać odwiedzone przez kompletującego (komiwojażera) są miejsca pobrania artykułów, będących na liście kompletacyjnej. Pozostałe miejsca oferowania mogą zostać pominięte. Dodatkową różnicą jest fakt, iż dopuszczalne jest, aby te same węzły (punkty) były odwiedzone więcej niż jeden raz. Ze względu na te rozbieżności problem komiwojażera (Traveling Salesman Problem) wykorzystywany do generowania tras pracowników kompletacyjnych nazywany jest Steiner Traveling Salesman Problem, który generalnie jest nierozwiązywalny w czasie wielomianowym. Problemem tym zajmowali się Ratliff i Rosenthal, którzy w 1983 roku w pracy zwrócili uwagę na to, iż dla prostych jednoblokowych, prostokątnych układów strefy komisjonowania istnieje algorytm rozwiązujący ten problem w czasie liniowo zależnym od liczby korytarzy roboczych i liczby miejsc oferowania artykułów. W kolejnych latach algorytm ten był badany i analizowany w wielu pozycjach literatury. W roku 1998 De Koster i Van der Poort rozszerzyli Steiner Traveling Salesman Problem do postaci umożliwiającej wyznaczanie najkrótszych dróg kompletacji w magazynach o jednoblokowym układzie strefy kompletacji ze zdecentralizowanym punktem startu/końca kompletacji (osoba realizująca procesy kompletacyjne może odkładać sformowane jednostki ładunkowe w różnych, niezależnych miejscach, np. na różne segmenty przenośnika zlokalizowanego na czole strefy kompletacji). Inną analizowaną w literaturze modyfikacją rozwiązania problemu Steiner Traveling Salesman Problem był algorytm zaprezentowany przez Roodbergen’a i De Koster’a w publikacji. Umożliwiał on wyznaczanie najkrótszej drogi kompletowania zamówień klientów w magazynach z trzema korytarzami poprzecznymi: z przodu, z tyłu i w środku strefy kompletacji, czyli dla dwublokowych układów strefy komisjonowania.

Artykuł zawiera 27200 znaków.

Źródło: Czasopismo Logistyka