Problem komiwojażera w procesie kompletacji towaru

Czy jest problem komiwojażera

Matematyczny model problemu komiwojażera (TSP) został  zdefiniowany w XIX w. niezależnie przez Wiliama Hamilltona i Thomasa Kirkmana. Pierwotnie problem miał polegać na znalezieniu cyklu Hamilotana w grafie czyli ścieżki która przechodzi przez wszystkie wierzchołki grafu dokładnie raz. Znalezienie cyklu Hamiltona o najmniejszej sumie wag krawędzi zwane jest dziś rozwiązaniem problemu komiwojażera.

Odchodząc od teorii matematycznej, problem można przedstawić jako problem handlowca, który musi odwiedzić kilka miast pokonując przy tym najkrótszą drogę i odwiedzając każde miasto tylko raz. Sama definicja problemu jak widać jest prosta, jednak stojące za nim obliczenia są  czasochłonne i skomplikowane.

W XIX wieku sama trudność obliczeniowa była ambitnym wyzwaniem dla matematyków i do tego głownie sprowadzał się ówczesny problem komiwojażera. Od końca XX wieku dzięki znacznemu wzrostowi mocy obliczeniowej komputerów rozwiązania te zaczęły być wykorzystywane w biznesie.

Wykorzystanie problemu komiwojażera w procesach logistycznych

W 2020 roku nad wykorzystaniem problemu komiwojażera w procesach logistycznych pochylił się również zespół badawczo-rozwojowy Arvato Supply Chain Solutions. W pierwszej kolejności optymalizowaliśmy proces kompletacji zamówień. Żeby określić ścieżki pobierania produktów konieczne było zaimplementowanie rozwiązań TSP w algorytmie budowania serii produktów.  Dotyczy to również algorytmu określającego najkrótszą ścieżkę pomiędzy odwiedzanymi punktami.

Rysunek – Proces optymalizacji punktów pobrań w procesie kompletacji zamówień w Arvato Supply Chain Solutions

Algorytm budowania serii odpowiada za taki dobór zamówień do kompletacji, aby ich ilość była możliwa do skompletowania przez pojedynczego pracownika oraz żeby czas ich realizacji odpowiadał wskaźnikom KPI ustalonymi z klientem. Algorytm TSP natomiast pozwala na wyznaczenia optymalnej ścieżki kompletacji takiej serii.

O ile samo zastosowanie powyższych algorytmów nie stanowiło większego problemu dla zespołu, o tyle samo wykonanie tak znacznej ilości obliczeń w akceptowalnym czasie było już dużym wyzwaniem. Prace nad optymalizacją rozwiązania trwały kilka miesięcy. W lipcu 2020 uruchomiliśmy produkcyjnie pierwszą wersję rozwiązania Problemu komiwojażera.

W efekcie osiągnęliśmy o 13 proc. krótszy dystans jaki pokonywał pracownik kompletacji, przy jednoczesnym wzroście wydajności procesu o 8 proc. Wciąż widzimy potencjał dalszych prac nad TSP w przyszłości.

Udoskonalenia problemu komiwojażera

Większość rozwiązań udoskonalających problem komiwojażera w logistyce bazuje na podstawowej wielkości jaką jest dystans i głównie on jest optymalizowany. Nasz zespół R&D idzie o krok dalej i obecnie pracuje nad optymalizacją TSP bazującą na „koszcie pobrania” (wysiłku jaki jest wkładany w pojedyncze pobranie produktu).

Uwzględnianie takich czynników jak szerokość alejek w magazynie, masa wózka czy choćby preferencje pracownika jest sporym wyzwaniem zarówno pod kątem zbierania takich danych, jak i ich wykorzystania w algorytmie.

Zarządzamy zarówno magazynami z szerszymi alejkami, w których to można poruszać się z dużo sprawniej z wózkiem, jak i takimi, z alejkami węższymi gdzie wózki muszą być mniejsze, a samo poruszanie w nich jest mniej wygodne.

Pytania związane z problemem komiwojażera

• czy warto wyznaczyć trochę dłuższą drogę, lecz alejką szerszą (w tym przypadku taką, gdzie pracownik może poruszać się szybciej)
• czy może jednak pozostać przy krótszej drodze, lecz alejką węższą?

Tu pojawia się punkt decyzyjny w algorytmie. Matematycznie odpowiedź jest prosta – tą która zajmie mniej czasu.  Procesowo jednak należy tu jeszcze wziąć pod uwagę preferencje pracownika i jego naturalne zmęczenie i predyspozycje. Są one jednak kwestią indywidualną. Dodatkowym wyzwaniem jest konieczność takiego zoptymalizowania obliczeń by nie spowolniały one komunikacji pomiędzy naszymi systemami. Ostatecznie takie podejście pozwoli nam zoptymalizować algorytm pobrań pod procesy logistyczne uwzględniając jednocześnie indywidualne różnice w poszczególnych magazynach.

Na tym nie kończą się możliwości optymalizacji Problemu komiwojażera. Zapewne można tutaj zrobić jeszcze więcej, choćby uwzględniać zmiany w czasie czynników, które wpływają na sprawność procesu.  Przykładem jest zmiana ciężaru wózka podczas dokładania pracowników, co ponownie wpływa na zmęczenie pracownika.

Pytanie jakie należy postawić –  to jak daleko w optymalizacji TSP warto iść? Ten bieg ku doskonałości przypomina trochę ciągłą walkę o zmniejszenie masy sprzętu w niektórych dyscyplinach sportowych (kolarstwo, wyścigi motocykli czy wyścigi Formuły 1).

Należy jednak wszystko wyważyć i zastanowić się, ile pieniędzy możemy wydać za kolejny procent optymalizacji.