Jak skrócić proces kompletacji zamówień przy zastosowaniu SI?

22.06.2021 - Zarządzanie magazynem

Proces kompletacji jest procesem bardzo kosztownym szczególnie w obsłudze magazynu e-commerce, przyjmuje się, że stanowi nawet 35% ogółu kosztów logistyki magazynowej. Szukając możliwości na optymalizację kosztów opracowaliśmy algorytmy pozwalające skrócić czas kompletacji.

W poszukiwaniu optymalnej trasy kompletacji zamówień punktem wyjścia jest tzw. problem komiwojażera, (ang. travelling salesman problem, TSP). Jak podaje wikipedia problem komiwojażera to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Chociaż brzmi to dość skomplikowanie możemy to porównać do listy punktów, które należy odwiedzić na pewnej topologii lub w ramach określonej przestrzeni, aby zrealizować dane zadanie. Wyobraźmy sobie sprzedawcę, który ma do pokonania trasę po całej Polsce - możemy zamienić te lokalizacje na listę punktów, które musi odwiedzić. Przekładając to porównanie na obszar magazynu dostrzegamy tutaj analogię do listy kompletacji w manualnym magazynie półkowym, gdzie operator musi odwiedzić poszczególne punkty, aby skompletować zamówienie. Możliwych ścieżek przejścia jest bardzo dużo, dlatego kluczowym wyzwaniem jest ustalenie optymalnej ścieżki kompletacji.

Cel: skrócenie ścieżki kompletacji

Z takim wyzwaniem zwrócił się do nas klient, który szukał rozwiązania na skrócenie ścieżki kompletacji. Głównym zadaniem jakie nam postawiono było skrócenie czasu przejścia pickerów, czyli minimalizacja sumarycznego kosztu zbiórki. Zadanie podzieliliśmy na dwie fazy.

W pierwszej kolejności skupiliśmy się na wyznaczeniu optymalnej ścieżki kompletacji dla danej picklisty. Picklista jest gotowa, a zadaniem systemu WMS jest posortowanie tej listy i zmiana kolejności odwiedzanych punktów. W przypadku drugiej fazy idziemy dalej: mamy pulę uruchomionych zleceń (rezerwacji) i z tych zleceń tworzymy optymalne picklisty.

Standardowo systemy klasy WMS wyznaczają sekwencje przejścia pickera, według pewnych schematów, takie podejście sprawdza się dobrze w prostych magazynach o stosunkowo prostej topologii.

W przykładowej sekwencji TYX operator zbiera towar najpierw wzdłuż alejki, dochodząc do końca regału cofa się do końca alejki i zbiera towar z drugiej strony regału. W przypadku magazynu obsługującego e-commerce mamy dużo bardziej skomplikowaną topologię, musimy brać pod uwagę różnego rodzaju promocje. Często spotykane w magazynach e-commerce są regały kartonowe, które pozwalają na szybkie przemodelowanie magazynu w zależności od potrzeb. Dlatego tak bardzo ważne jest elastyczne narzędzie, które pozwoli na optymalizację ścieżki kompletacji.

Wyznaczenie optymalnej ścieżki kompletacji

Przystępując do wyznaczenia optymalnej ścieżki kompletacji w pierwszej kolejności zmieniliśmy topologię magazynu półkowego (widzianą z góry) na graf nieskierowany. Na grafie niebieskie punkty oznaczają punkty, w których może być dokonana kompletacja. Linie pionowe i poziome wyznaczają odpowiednio przejścia wzdłuż regałów oraz przejść pomiędzy regałami. Punkty czerwone oznaczają miejsca, które należy odwiedzić podczas kompletacji. Sumaryczny czas przejścia jest sumą odległości, którą musi „pokonać” algorytm na takim grafie. W ten sposób uzyskujemy wartość, która mówi nam czy dane przejście jest lepsze czy gorsze.

Po lewej stronie przedstawiony jest wynik standardowego wyznaczania trasy przez WMS - 344 jednostki (możemy je porównać do metrów, które musi pokonać operator podczas kompletacji danej picklisty). Po prawej stronie przedstawione jest rozwiązanie optymalizacyjne TSP. Długość ścieżki jest o 30% krótsza przy zastosowaniu optymalizatora. W przypadku braku towaru w danej lokacji, operator zgłasza taki błąd w systemie WMS, a optymalizator ponownie przesortowuje listę.

Pierwsze wdrożenie algorytmu zaowocowało ciekawym zjawiskiem. Pomimo tego, iż lista powinna być zoptymalizowana to niektórzy operatorzy uzyskiwali gorsze czasy przejścia. Okazało się, że niektórzy operatorzy „wiedzą lepiej” i chodzili tak, jak sami uważali za stosowne. W celu minimalizacji tego zjawiska, powstała graficzna mapa kompletacji, która pozwoliła operatorom na wcześniejsze podejrzenie trasy zbiórki.

Na rysunku przedstawiona jest ekstremalnie długa picklista, po lewej stronie jest wykaz lokacji do odwiedzenia, a w centralnej części widzimy mapę, która ułatwia operatorowi poruszanie się po magazynie.

Wyznaczenie optymalnej listy

Druga faza jest bardziej skomplikowana, zastosowaliśmy w niej metaheurystykę genetyczną, która w praktyce działa w zbliżony sposób do natury. W przyrodzie najsilniejsze osobniki łączą się ze sobą, krzyżują, dzięki czemu powstaje kolejne pokolenie, które jest coraz lepsze. W przypadku naszego problemu jako osobnika, który podlega operacjom generycznym rozumiemy picklistę.

Na początku przetwarzania losujemy przestrzeń możliwych rozwiązań, w postaci zbioru picklist realizujących wybraną grupę zleceń. Następnie określamy czas realizacji danej picklisty, czyli rozwiązujemy dla niej problem TSP, po czym wybieramy najsilniejsze picklisty, innymi słowy takie, które mają najlepszy czas przejścia. Wybrane listy ponownie „wrzucamy” do worka możliwych rozwiązań. Zanim to zrobimy dokonujemy operacji genetycznych czyli krzyżujemy te picklisty i wprowadzamy operacje mutujące, czyli losowo zmieniamy niektóre pozycje na pickliście. Cały proces powtarzamy n- razy (np. n = 30), aby otrzymać optymalną listę, która charakteryzuje się najkrótszym sumarycznym czasem przejścia.

Najtrudniejszym z problemów jest tutaj szybkie rozwiązanie problemu TSP - musimy mieć mechanizm, który w bardzo krótkim czasie zwróci nam przybliżony czas przejścia danej picklisty. Problem jest wielomianowy, złożoność obliczeniowa jest równa O(n!), zatem dla dużych n (długi picklist) ilość możliwych rozwiązań jest bardzo duża. Na szczęście z pomocą przychodzi nam uczenie maszynowe, które pozwala na błyskawiczne wyznaczenie rozwiązania problemu TSP. W ułamku sekundy otrzymujemy przybliżone wartości TSP, które posłużą nam do walidacji picklist, czyli określenia tych najsilniejszych osobników.

Algorytmy uczenia maszynowego zastosowane w Optymalizatorze to tzw. sieci konwolucyjne (ang. CNN), możemy je spotkać np. w smartphonach do rozpoznawania obrazów. Sieć konwolucyjna na podstawie bitmapy (obrazu) dostosowuje parametry aparatu. To samo podejście zastosowaliśmy w przypadku picklist. Nasza lista widziana z góry przedstawiona jest w postaci bitmapy. Taka bitmapa trafia na wejście sieci konwolucyjnej, a na wyjściu otrzymujemy wartość, która określa wynik przejścia listy z bardzo dobrym przybliżeniem. Dzięki temu, że wynik otrzymujemy błyskawicznie możemy go wykorzystać w naszym algorytmie generycznym omówionym wyżej.

Rzeczywiste wyniki

Naukowe rozważania zaowocowały wymiernymi korzyściami. Średnie skrócenie ścieżki w rzeczywistym magazynie wyniosło około 30%, a całkowity średni wzrost wydajności dla zleceń wielosztukowych wyniósł nieco ponad 12%. Różnica między tymi dwoma parametrami wynika z faktu, że proces zbiórki składa sie z wielu etapów. W naszym algorytmie skupiamy się na pewnej części tego procesu, czyli skróceniu czasu przejścia pomiędzy poszczególnymi punktami i ten czas w zależności od topologii magazynu stanowi około 1/3 całości procesu kompletacji. Kolejne wdrożenia potwierdzają, że uzyski z wdrożenia Optymalizatora utrzymują się na stałym wysokim poziomie 30%, natomiast sam moduł trafił do nowej wersji standardu systemu PSIwms i może zostać wykorzystany w dowolnym magazynie.