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.

Головна▸ШІ та Машинне навчання▸Оптимізатор Розміщення на Складі

📦 Оптимізатор Розміщення на Складі — Угорський Алгоритм Наживо

Спостерігайте, як справжній угорський алгоритм розв'язує оптимальне призначення між товарами й місцями зберігання, щоб мінімізувати загальну відстань відбору, повторно розв'язуючи задачу наживо при зміні даних про частоту замовлень.

AI & Machine Learning3DПросунутий60 FPS

Про Оптимізатор Розміщення на Складі

Розміщення (слотування) — це логістична задача визначення того, яке місце зберігання має займати кожен товар (SKU) усередині складу. Якщо зробити правильно, комплектувальники витрачають менше часу на ходьбу; якщо неправильно, час переміщення — часто найбільша окрема стаття витрат у виконанні замовлень — роздувається. Ця симуляція формулює слотування як класичну задачу призначення: N товарів, N місць зберігання та матриця вартості, де cost(i,j) = частота_замовлень(товар i) × відстань_від_доку(слот j). Мета — знайти взаємно однозначне призначення товарів слотам, що мінімізує загальну вартість.

Замість наближення ця симуляція запускає справжній угорський алгоритм (Кун–Манкрес) на стороні клієнта в JavaScript: подвійні потенціали рядків/стовпців, побудова чергуючогося дерева та доповнювальні шляхи, точно як описано в літературі з дослідження операцій — розв'язуючи призначення до справжнього глобального оптимуму за час O(N³). Поряд працює жадібний базовий варіант (найзавантаженіший товар забирає свій найдешевший ще вільний слот, повторити), тож ви можете кількісно побачити, скільки вартості точний алгоритм заощаджує порівняно з наївною евристикою. Рандомізуйте дані про частоту замовлень або змініть розмір задачі й спостерігайте, як обидва розв'язки — і розрив між ними — оновлюються наживо.

Часті питання

Що таке задача призначення?

Задача призначення запитує: маючи N агентів і N завдань та вартість c(i,j) призначення агента i завданню j, знайти взаємно однозначне призначення, що мінімізує загальну вартість. Тут агенти — це товари, а завдання — місця зберігання, з вартістю, що дорівнює частоті замовлень товару, помноженій на відстань цього слота від доку. Повний перебір усіх N! можливих призначень можливий лише для крихітних N — уже 10 товарів означають 3 628 800 перестановок. Угорський алгоритм розв'язує точний оптимум за поліноміальний час, O(N³), незалежно від N.

Як насправді працює угорський алгоритм?

Класична формула Куна–Манкреса підтримує потенціал рядка u(i) і потенціал стовпця v(j) для кожного агента й завдання, такий що c(i,j) − u(i) − v(j) завжди невід'ємний і дорівнює нулю саме на ребрах, використаних поточним частковим паруванням. Починаючи з порожнього парування, вона повторно вирощує чергуюче дерево з непарованого рядка, відстежуючи мінімальний зазор до будь-якого недосяжного стовпця. Коли цей зазор ненульовий, потенціали коригуються рівномірно по всьому дереву, тож з'являється нове ребро з нульовою вартістю, розширюючи дерево без повторення роботи. Коли досягається непарований стовпець, алгоритм доповнює — перемикає статус паровано/непаровано вздовж шляху — збільшуючи парування на одиницю. Після N доповнень кожен агент паровано, і потенціали засвідчують оптимальність за LP-двоїстістю.

Чому жадібне призначення зазвичай гірше?

Жадібна евристика призначає товари слотам по одному — наприклад, найзавантаженіший товар першим, найдешевший ще вільний слот — і ніколи не переглядає ранні вибори. Це швидко (O(N² log N)), але недалекоглядно: раннє жадібне рішення може закріпити дешевий слот за товаром, який насправді його не потребував, змушуючи набагато пізніший товар зайняти дорогий залишковий слот. Угорський алгоритм розглядає всю матрицю одночасно через свої потенціали, тож жадібна стратегія ніколи не може перевершити його за загальною вартістю — він доказово оптимальний. Панель статистики цієї симуляції показує відсотковий розрив між ними наживо.

Що представляють подвійні потенціали u і v?

u(i) і v(j) походять із двоїстої задачі лінійного програмування задачі призначення. Інтуїтивно, u(i) — це нижня межа того, скільки має коштувати агент i незалежно від того, яке завдання він отримає, а v(j) — подібна межа для завдання j. Алгоритм збільшує ці потенціали в міру дослідження, завжди зберігаючи c(i,j) ≥ u(i) + v(j). Коли знайдено повне парування, де кожне паровано ребро задовольняє рівність, сума потенціалів дорівнює загальній вартості парування — доводячи, що дешевшого парування не може існувати, за слабкою LP-двоїстістю.

Чому розміщення на складі важливе в реальній логістиці?

У реальному розподільчому центрі час переміщення комплектувальника до й від місць зберігання є одним із найбільших компонентів вартості виконання замовлень — часто понад половина загального часу праці. Розміщення високочастотних, швидкорухомих SKU близько до доку чи станції пакування, а повільних — далі, може суттєво скоротити загальну відстань переміщення без будь-яких змін у будівлі чи процесі відбору. Це саме та задача призначення, яку розв'язує ця симуляція: мінімізувати суму (частота замовлень × відстань переміщення) для взаємно однозначного відображення товарів на слоти.

Чи масштабується алгоритм до тисяч SKU?

Класичний угорський алгоритм O(N³) комфортно обробляє від кількох сотень до кількох тисяч позицій за мілісекунди-секунди. Реальні системи управління складом із десятками тисяч SKU зазвичай використовують еквівалентний варіант Йонкера–Волгенанта (швидші константи, той самий клас складності) або розкладають задачу на зони/проходи, розв'язувані незалежно, оскільки рішення про розміщення зазвичай переоптимізуються періодично (щотижня/щомісяця), а не в реальному часі.

Це той самий алгоритм, що використовується для інших задач парування?

Так — угорський алгоритм розв'язує будь-яке збалансоване дводольне досконале парування мінімальної вартості, тож ідентична машинерія застосовується до планування завдань (робітники до змін), спортивного/екзаменаційного парування та багатооб'єктного трекінгу (зіставлення виявлень із відстежуваними ідентичностями кадр за кадром, наприклад, у трекерах на основі фільтра Калмана, поширених у комп'ютерному зорі). Змінюється лише визначення матриці вартості; логіка редукції рядків/стовпців та доповнювальних шляхів залишається незмінною.

⚙ Під капотом

Справжня матриця вартості (частота замовлень × відстань слота) розв'язується справжнім алгоритмом Куна–Манкреса — подвійні потенціали, чергуючі дерева, доповнювальні шляхи — і порівнюється наживо з жадібним базовим варіантом на плані складу й тепловій карті матриці вартості.

Canvas 2DУгорський алгоритмКун-МанкресЗадача призначенняКомбінаторна оптимізація

3D · рушій Three.js / WebGL · ціль 60 кадрів/с · працює повністю на клієнті, без встановлення