What is the assignment problem?

The assignment problem asks: given N agents and N tasks and a cost c(i,j) for assigning agent i to task j, find the one-to-one assignment that minimises total cost. Here the agents are products and the tasks are storage slots, with cost equal to a product's order frequency multiplied by that slot's distance from the dock. Brute force checking all N! possible assignments is only feasible for tiny N -- 10 products already means 3,628,800 permutations. The Hungarian algorithm solves the exact optimum in polynomial time, O(N^3), regardless of N.

How does the Hungarian algorithm actually work?

The classic Kuhn-Munkres formulation maintains a row potential u(i) and column potential v(j) for every agent and task such that c(i,j) - u(i) - v(j) is always non-negative, and is zero exactly on edges used by the current partial matching. Starting from an empty matching, it repeatedly grows an alternating tree from an unmatched row, tracking the minimum slack to any unreached column. When that slack is nonzero, potentials are adjusted uniformly across the tree so a new zero-cost edge appears, extending the tree without ever revisiting work. When an unmatched column is reached, the algorithm augments -- flips matched/unmatched status along the path -- growing the matching by one. After N augmentations every agent is matched, and the potentials certify optimality by LP duality.

Why is a greedy assignment usually worse?

A greedy heuristic assigns products to slots one at a time -- e.g. busiest product first, cheapest still-free slot -- and never revisits earlier choices. This is fast (O(N^2 log N)) but short-sighted: an early greedy pick can lock in a cheap slot for a product that didn't really need it, forcing a much later product into an expensive leftover slot. The Hungarian algorithm considers the whole matrix simultaneously via its potentials, so it can never be beaten by a greedy strategy on total cost -- it is provably optimal. This simulation's stats panel shows the percentage gap between the two live.

What do the dual potentials u and v represent?

u(i) and v(j) come from the linear-programming dual of the assignment problem. Intuitively, u(i) is a lower bound on how much agent i must cost no matter which task it gets, and v(j) is a similar bound for task j. The algorithm increases these potentials as it explores, always preserving c(i,j) >= u(i) + v(j). When a complete matching is found where every matched edge satisfies equality, the sum of potentials equals the total matching cost -- proving no cheaper matching can exist, by weak LP duality.

Why does warehouse slotting matter in real logistics?

In a real distribution centre, a picker's travel time to and from storage locations is one of the largest components of order-fulfilment cost -- often over half of total labour time. Placing high-frequency, fast-moving SKUs close to the dock or pack station, and slow movers further away, can cut total travel distance substantially without changing the building or the pick process at all. This is exactly the assignment problem this simulation solves: minimise sum of (order frequency x travel distance) over a one-to-one product-to-slot mapping.

Does the algorithm scale to thousands of SKUs?

The classic O(N^3) Hungarian algorithm handles a few hundred to low thousands of items comfortably in milliseconds to seconds. Real warehouse-management systems with tens of thousands of SKUs typically use the equivalent Jonker-Volgenant variant (faster constants, same complexity class) or decompose the problem into zones/aisles solved independently, since slotting decisions are usually re-optimised periodically (weekly/monthly) rather than in real time.

Is this the same algorithm used for other matching problems?

Yes -- the Hungarian algorithm solves any balanced bipartite minimum-cost perfect matching, so the identical machinery applies to task scheduling (workers to shifts), sports/exam pairing, and multi-object tracking (matching detections to tracked identities frame-to-frame, e.g. in the Kalman-filter-based trackers common in computer vision). Only the cost matrix definition changes; the row/column reduction and augmenting-path logic is unchanged.

Strona główna▸AI i ML▸Optymalizator rozmieszczenia w magazynie

📦 Optymalizator rozmieszczenia w magazynie — algorytm węgierski na żywo

Obserwuj, jak prawdziwy algorytm węgierski rozwiązuje optymalne przypisanie produktów do slotów magazynowych, minimalizując całkowity dystans przemieszczania się przy kompletacji, i przelicza się na żywo przy zmianie danych o częstości zamówień.

AI i ML3DZaawansowany60 FPS

O optymalizatorze rozmieszczenia w magazynie

Rozmieszczenie (slotting) to logistyczny problem decydowania, które miejsce magazynowe powinien zajmować każdy produkt (SKU) wewnątrz magazynu. Zrób to dobrze, a kompletujący spędzają mniej czasu na chodzeniu; zrób to źle, a czas przemieszczania się — często pojedynczy największy koszt realizacji zamówień — gwałtownie rośnie. Ta symulacja ujmuje rozmieszczenie jako klasyczny problem przypisania: N produktów, N slotów magazynowych i macierz kosztów, gdzie koszt(i,j) = częstość-zamówień(produkt i) × odległość-od-doku(slot j). Celem jest znalezienie jednoznacznego przypisania produktów do slotów, które minimalizuje całkowity koszt.

Zamiast przybliżać, ta symulacja uruchamia prawdziwy algorytm węgierski (Kuhna–Munkresa) po stronie klienta w JavaScript: dualne potencjały wierszy/kolumn, konstrukcję drzewa naprzemiennego oraz ścieżki powiększające, dokładnie tak, jak opisano w literaturze badań operacyjnych — rozwiązując przypisanie do prawdziwej globalnej optymalności w czasie O(N³). Obok działa zachłanna baza odniesienia (najbardziej zajęty produkt zajmuje swój najtańszy wciąż wolny slot, powtórz), dzięki czemu można ilościowo zobaczyć, ile kosztu oszczędza dokładny algorytm w porównaniu z naiwną heurystyką. Losuj dane o częstości zamówień lub zmień rozmiar problemu i obserwuj, jak oba rozwiązania — i różnica między nimi — aktualizują się na żywo.

Najczęściej zadawane pytania

Czym jest problem przypisania?

Problem przypisania pyta: mając N agentów i N zadań oraz koszt c(i,j) przypisania agenta i do zadania j, znajdź jednoznaczne przypisanie minimalizujące całkowity koszt. Tutaj agentami są produkty, a zadaniami sloty magazynowe, przy czym koszt to częstość zamówień produktu pomnożona przez odległość tego slotu od doku. Sprawdzenie brute force wszystkich N! możliwych przypisań jest wykonalne tylko dla bardzo małego N — 10 produktów to już 3 628 800 permutacji. Algorytm węgierski rozwiązuje dokładne optimum w czasie wielomianowym, O(N³), niezależnie od N.

Jak dokładnie działa algorytm węgierski?

Klasyczne sformułowanie Kuhna–Munkresa utrzymuje potencjał wierszowy u(i) i kolumnowy v(j) dla każdego agenta i zadania takie, że c(i,j) − u(i) − v(j) jest zawsze nieujemne i wynosi zero dokładnie na krawędziach używanych przez bieżące częściowe skojarzenie. Zaczynając od pustego skojarzenia, algorytm wielokrotnie rozbudowuje drzewo naprzemienne od niedopasowanego wiersza, śledząc minimalny luz do dowolnej nieosiągniętej kolumny. Gdy ten luz jest niezerowy, potencjały są dostosowywane jednolicie w całym drzewie, tak by pojawiła się nowa krawędź o zerowym koszcie, rozszerzając drzewo bez ponownego przetwarzania pracy. Gdy osiągnięta zostanie niedopasowana kolumna, algorytm wykonuje powiększenie — odwraca status dopasowany/niedopasowany wzdłuż ścieżki — powiększając skojarzenie o jeden. Po N powiększeniach każdy agent jest dopasowany, a potencjały potwierdzają optymalność poprzez dualność programowania liniowego.

Czemu przypisanie zachłanne jest zwykle gorsze?

Heurystyka zachłanna przypisuje produkty do slotów po jednym naraz — np. najbardziej zajęty produkt pierwszy, najtańszy wciąż wolny slot — i nigdy nie wraca do wcześniejszych wyborów. To szybkie (O(N² log N)), ale krótkowzroczne: wczesny zachłanny wybór może zablokować tani slot dla produktu, który go tak naprawdę nie potrzebował, zmuszając znacznie późniejszy produkt do drogiego pozostałego slotu. Algorytm węgierski rozważa całą macierz jednocześnie poprzez swoje potencjały, więc strategia zachłanna nigdy nie może go pobić pod względem kosztu całkowitego — jest on dowiedlnie optymalny. Panel statystyk tej symulacji pokazuje procentową różnicę między nimi na żywo.

Co reprezentują dualne potencjały u i v?

u(i) i v(j) pochodzą z dualnego programu liniowego problemu przypisania. Intuicyjnie u(i) to dolna granica tego, ile musi kosztować agent i, niezależnie od tego, jakie zadanie otrzyma, a v(j) to podobna granica dla zadania j. Algorytm zwiększa te potencjały w miarę eksploracji, zawsze zachowując c(i,j) ≥ u(i) + v(j). Gdy znalezione zostanie pełne skojarzenie, w którym każda dopasowana krawędź spełnia równość, suma potencjałów równa się całkowitemu kosztowi skojarzenia — dowodząc, że nie może istnieć tańsze skojarzenie, poprzez słabą dualność programowania liniowego.

Czemu rozmieszczenie w magazynie ma znaczenie w prawdziwej logistyce?

W prawdziwym centrum dystrybucji czas przemieszczania się kompletującego do i z miejsc magazynowych jest jednym z największych składników kosztu realizacji zamówień — często ponad połową całkowitego czasu pracy. Umieszczenie szybko rotujących SKU o wysokiej częstości blisko doku lub stacji pakowania, a wolno rotujących dalej, może znacząco skrócić całkowity dystans przemieszczania się bez żadnej zmiany budynku czy procesu kompletacji. To dokładnie ten problem przypisania, który rozwiązuje ta symulacja: minimalizacja sumy (częstość zamówień × dystans przemieszczania się) dla jednoznacznego mapowania produktów na sloty.

Czy algorytm skaluje się do tysięcy SKU?

Klasyczny algorytm węgierski O(N³) wygodnie obsługuje od kilkuset do niewielu tysięcy pozycji w czasie od milisekund do sekund. Prawdziwe systemy zarządzania magazynem z dziesiątkami tysięcy SKU zwykle używają równoważnego wariantu Jonkera–Volgenanta (szybsze stałe, ta sama klasa złożoności) lub dekomponują problem na strefy/alejki rozwiązywane niezależnie, ponieważ decyzje o rozmieszczeniu są zwykle reoptymalizowane okresowo (tygodniowo/miesięcznie), a nie w czasie rzeczywistym.

Czy to ten sam algorytm używany do innych problemów dopasowania?

Tak — algorytm węgierski rozwiązuje dowolne zbalansowane dwudzielne skojarzenie doskonałe o minimalnym koszcie, więc identyczny mechanizm ma zastosowanie do planowania zadań (pracownicy do zmian), parowania sportowego/egzaminacyjnego oraz śledzenia wielu obiektów (dopasowywanie detekcji do śledzonych tożsamości klatka po klatce, np. w trackerach opartych na filtrze Kalmana powszechnych w widzeniu komputerowym). Zmienia się tylko definicja macierzy kosztów; logika redukcji wierszy/kolumn i ścieżek powiększających pozostaje bez zmian.

⚙ Co pod maską

Prawdziwa macierz kosztów (częstość zamówień × dystans slotu) jest rozwiązywana przez rzeczywisty algorytm Kuhna–Munkresa — dualne potencjały, drzewa naprzemienne, ścieżki powiększające — i porównywana na żywo z zachłanną bazą odniesienia na podłodze magazynu i mapie cieplnej macierzy kosztów.

Canvas 2DHungarian AlgorithmKuhn-MunkresAssignment ProblemCombinatorial Optimization

3D · renderer Three.js / WebGL · cel 60 FPS · działa w całości w przeglądarce, bez instalacji