How to use it
- 1. Edit the matrixCost (hours, $, km) of sending each driver to each route. Every cell is editable.
- 2. Step the algorithmRow reduce → column reduce → cover the zeros → adjust. Watch zeros appear where the answer lives.
- 3. Read the coverWhen the minimum number of covering lines equals n, an optimal assignment exists among the zeros.
- 4. Check itThe tool brute-forces all n! assignments and confirms the Hungarian answer is genuinely optimal.
Drivers → routes
Problem
Algorithm
Assignment
-
–
Total cost
–
Covering lines vs n
–
vs greedy
–
vs all n! options
Working matrix. Green = the chosen assignment. Pale cells are zeros the algorithm created; red bars are the covering lines.
The same answer as a bipartite matching - each driver to exactly one route, each route to exactly one driver.
Try these experiments
- Compare with greedy (always take the cheapest remaining cell): greedy is frequently worse, because a cheap first pick can strand an expensive last one.
- Add a constant to an entire row: the optimal assignment does not change. That invariance is exactly why row reduction is legal.
- Switch to Maximise (think profit, not cost) - same algorithm, costs negated. n! grows brutally: n=7 is 5,040 options; n=15 would be a trillion.
About this tool
The concept
The assignment problem: pair n agents with n tasks, one each, at least total cost. It is the purest matching problem in operations research.
How it works
Kuhn’s Hungarian method (1955), O(n³): subtracting a constant from any row or column leaves the optimal assignment unchanged, so you can manufacture zeros until n independent ones exist.
Winning strategy
Never assign greedily. And note the transportation tool solves this too - assignment is just transportation with all supplies and demands equal to 1.
Background: Hungarian algorithm · Assignment problem · Kuhn (1955)