Przykład algorytmu grupowania zleceń na komisjonowanie
- Michał Kacprzak
- Kategoria: Logistyka
Grupowanie zleceń jest jedną z metod stosowanych w trakcie procesu komisjonowania. Metoda polega na łączeniu pewnej liczby zleceń na komisjonowanie w grupy oraz jednoczesną kompletację wszystkich zleceń z danej grupy. Celem takiego działania jest zwiększenie efektywności procesu komisjonowania poprzez:
- skrócenie sumarycznej długości dróg kompletacyjnych, jakie należy pokonać aby pobrać wszystkie artykuły znajdujące się w analizowanej grupie zleceń - przez to komisjonowanie może być realizowane szybciej lub przy udziale mniejszej liczby pracowników i środków transportu wewnętrznego,
- pełniejsze wykorzystanie możliwości zastosowanych środków transportu wewnętrznego (zwłaszcza, kiedy komisjonowane są artykuły drobnicowe oraz na zleceniach na komisjonowanie znajduje się stosunkowo niewiele artykułów).
Na ogół, w takich przypadkach wykorzystywany środek transportu wewnętrznego ma możliwości jednoczesnego przenoszenia artykułów z więcej niż jednego bazowego zlecenia na komisjonowanie. Ogólnie, algorytmy grupowania zleceń można podzielić na trzy zasadnicze podgrupy:
1. Algorytmy bazujące na przyznawaniu pierwszeństwa dla zamówień według pewnego kryterium (ang. priority rule based algorithms). Jest to grupa najprostszych algorytmów, dwie najczęściej stosowane odmiany to:
- zasada "kto pierwszy" (first come, first served) - zamówienia po kolei (w chronologicznym porządku pojawiania się / spływania zamówień) są dodawane do grupy, dopóki kolejne zlecenie nie przekroczy możliwości transportowych przyjętego środka transportu. W takim wypadku obecna grupa zostaje zamknięta, a otworzona zostaje nowa grupa z właśnie tym zleceniem,
- zasada równoległych partii - tworzone jest kilka (kilkanaście, kilkadziesiąt) równoległych partii, a kolejne zamówienie jest dodawane do grupy o najniższym numerze, która jednocześnie posiada jeszcze odpowiedni zapas miejsca (first fit rule) lub do grupy, która posiada zapas miejsca najbardziej zbliżony do rozmiaru danego zlecenia (best fit rule).
Algorytmy takie są stosunkowo proste zarówno jeżeli chodzi o ich implementację, jak i o czas obliczeniowy potrzebny na ich wykonanie. Nie są tutaj wymagane żadne dodatkowe obliczenia, a analiza może być wykonana tylko i wyłącznie na podstawie zleceń na komisjonowanie.
2. Algorytmy "oszczędne" (savings algorithms) - działanie takich algorytmów polega na porównaniu, jak wiele drogi zostanie zaoszczędzone poprzez stworzenie danych grup zleceń oraz poszukiwaniu jak najkorzystniejszej kombinacji zleceń wchodzących w skład tych grup (oraz najbardziej korzystnej liczby grup). Zasada działania algorytmów oszczędnych została przedstawiona na rysunku 1, gdzie A, B, C to trasy kompletacyjne dla poszczególnych zleceń, natomiast D to trasa kompletacyjna dla połączonych zleceń A, B oraz C. Trasa łączona (D) jest dłuższa (lub co najwyżej równa) od każdej z tras wyznaczonych dla zleceń A, B, C, a jednocześnie długość trasy D jest wyraźnie mniejsza od długości sumy tras A, B i C. Dla powyższego przypadku "oszczędność" to różnica pomiędzy długością trasy D, a sumą długości tras A, B oraz C. Celem działania algorytmów oszczędnych jest zmaksymalizowanie sumy takich oszczędności. W celu prawidłowego działania, taki algorytm wymaga wyznaczenia tras kompletacyjnych (i ich długości) dla każdego z wariantów grupowania zleceń. Liczba możliwych wariantów jest również bardzo wysoka - na przykład dla 100 zleceń na komisjonowanie można stworzyć prawie 4 mln różnych 4-elementowych grup zleceń. Nawet przy wykorzystaniu algorytmów heurystycznych wyznaczania trasy kompletacyjnej, obliczenia niezbędne dla wszystkich możliwych rozwiązań będą bardzo czasochłonne, a ze względu na złożoność obliczeniową, staną się praktycznie niewykonalne przy wykorzystaniu algorytmu optymalnego wyznaczania trasy kompletacyjnej. Dodatkowo, poza samą liczbą wymaganych obliczeń, grupowanie zleceń wydłuża listę kompletacyjną, co może mieć znaczący negatywny wpływ na wydajność takiego algorytmu. Z tego powodu optymalne rozwiązanie problemu grupowania zleceń dla algorytmów oszczędnych jest uznawane za problem NP-trudny.
3. Algorytmy bazujące na wyborze zamówienia "pierwotnego" (seed) oraz zamówień "towarzyszących/dodatkowych" (additional orders) według pewnych kryteriów (seed algorithms) - ta grupa algorytmów stanowi ogniwo pośrednie jeżeli chodzi o wydajność oraz prędkość obliczeń pomiędzy dwoma wymienionymi powyżej typami algorytmów. Ogólną zasadę działania tej grupy algorytmów można opisać następująco:
a) wybierz początkowe zlecenie (zgodnie z przyjętym kryterium), tworząc nową grupę zleceń,
b) wybierz dodatkowe zlecenie (zgodnie z przyjętym kryterium), które może wejść w skład grupy stworzonej w punkcie 1,
c) powtarzaj punkt 2, dopóki istnieją niepogrupowane zlecenia, które mogą wejść w skład danej grupy lub dana grupa osiągnęła maksymalną liczność,
d) powtarzaj punkty 1-3 do momentu, kiedy wszystkie zlecenia zostaną zgrupowane lub nie można stworzyć więcej grup zleceń (zgodnie z przyjętym kryterium/kryteriami).
Cały artykuł jest dostępny poniżej w formacie PDF.
Źródło: Czasopismo Logistyka