Empty miles, commonly called deadhead, remain one of the largest controllable costs in motor carrier operations. Manual load-to-tractor matching and simple rule-based dispatch make locally reasonable choices one truck at a time, which leaves network-wide repositioning cost on the table. The Hungarian assignment algorithm (Kuhn-Munkres) evaluates every tractor against every load at once and returns the assignment with the lowest total cost. This article covers how to formulate that problem, what belongs in the cost matrix, and how a carrier should measure the effect on its own deadhead share against its own baseline.
- Tractor-to-load dispatch is a bipartite matching problem with costs, and the Hungarian algorithm solves it optimally.
- The cost matrix is rarely pure distance. Fuel, settlement, HOS, equipment, and network balance all belong in each cell.
- Rebuild the matrix every dispatch cycle from TMS, GPS, and ELD data.
- Dispatchers review exceptions before the plan is written back to the TMS.
- Very large or stochastic networks pair the method with LP relaxations or column generation.
The Assignment Problem in Truckload Dispatch
At the start of each dispatch cycle a carrier typically has a set of available tractors (some at terminals, some en-route after unloading) and a set of known or forecasted loads. The goal is to assign each tractor to at most one load such that the total deadhead miles (and associated operating cost) is minimized. This is a classic bipartite matching problem with costs.
The Hungarian algorithm solves this optimally in O(n³) time, which is fast enough for fleets up to several hundred tractors and loads. When the number of tractors and loads are unequal, dummy rows or columns with high penalty costs are added to square the matrix.
C[i][j] is the effective cost of assigning tractor i to load j. x[i][j] is 1 when the assignment is made, otherwise 0.
minimize Σi Σj C[i][j] · x[i][j]
subject to Σj x[i][j] <= 1 for every tractor i
Σi x[i][j] <= 1 for every load j
x[i][j] in {0, 1}
Unequal counts are squared with dummy rows or columns at a high penalty cost. Solve time is O(n³).
Formulating the Cost Matrix
The heart of the solution is the cost matrix C where C[i][j] represents the effective cost of assigning tractor i to load j. In practice this cost is rarely pure distance. A typical formulation used by Strong Tower Consulting includes:
- Deadhead miles from tractor current position to load origin
- Expected fuel cost using current fuel surcharge tables and route-specific MPG
- Driver settlement impact (per-mile rate, accessorials, detention history)
- Hours-of-service remaining from ELD data
- Equipment compatibility and customer equipment requirements
- Network balance penalties for moving tractors away from high-volume origin lanes
This matrix is rebuilt each dispatch cycle using real-time data from the TMS (Truckmate, McLeod, or TMW), GPS/ELD feeds, and SQL-based business rules.
| Tractor \ Load | LAX-01 | PHX-03 | ONT-07 | LAS-02 | SLC-04 |
|---|---|---|---|---|---|
| T123 (Ontario, CA) | 42 | 187 | 18 | 231 | 412 |
| T145 (Fontana, CA) | 67 | 204 | 31 | 218 | 389 |
| T167 (Phoenix, AZ) | 372 | 12 | 341 | 289 | 521 |
| T189 (Las Vegas, NV) | 265 | 298 | 251 | 0 | 398 |
| T204 (Salt Lake City, UT) | 689 | 612 | 671 | 405 | 27 |
After the Hungarian solver returns the optimal assignment, dispatchers review exceptions and can adjust the matrix weights or add manual constraints before finalizing the plan. The resulting assignments are written back to the TMS as pre-planned moves or EDI 204 updates.
Do
- Rebuild the cost matrix every dispatch cycle from live TMS and GPS/ELD data
- Price fuel, settlement, HOS, equipment, and network balance into each cell
- Let dispatchers review exceptions before the plan is final
Avoid
- Manual load-to-tractor matching or simple rule-based dispatch
- A cost matrix built on pure distance
- Pure Hungarian on very large or stochastic networks without LP relaxation or column generation
Integration with Existing TMS Platforms
Strong Tower Consulting builds these optimization services as independent microservices that read from SQL Server or Oracle schemas common in Truckmate, McLeod, and TMW installations. Typical data sources include:
- Order header and stop tables (EDI 204 inbound)
- Asset and driver availability views
- EDI 214 status updates for real-time position
- ELD/HOS compliance tables
- Driver settlement and fuel surcharge tables
- Historical lane performance for balance scoring
The service returns recommended assignments via a web service or directly updates dispatch board priority fields. Because Strong Tower Consulting and Exspeedite LLC are separately organized sister companies under common ownership, carriers are never required to purchase software. Our only product is better decisions.
Metrics to Measure in a Pilot
The effect of assignment optimization depends on lane balance, forecast accuracy, position data quality, and how well the cost matrix reflects real cost. The only reliable way to size it for a given fleet is to measure against that fleet's own baseline. Capture a baseline period first, replay historical dispatch days through the solver, then run a live pilot and track:
- Network deadhead share: empty miles divided by total miles, from TMS mileage tables and ELD odometer data
- Driver paid miles per week, from driver settlement records
- Dispatcher planning time per cycle, from time studies or dispatch board activity logs
- On-time pickup and delivery, from EDI 214 status messages against appointment times
- Dispatcher override rate: how often the recommended assignment is changed, and why
When the Hungarian Algorithm Is Not Enough
For very large networks or when stochastic future loads must be considered, the pure Hungarian approach is often combined with linear programming relaxations or column generation. However, for regional motor carriers moving 50-300 loads per day, the Hungarian method provides a practical balance of optimality, speed, and explainability to dispatch teams.
Implementation Roadmap
Strong Tower Consulting typically follows a four-week proof-of-concept process:
- Extract current dispatch data and build initial cost matrix logic
- Implement the Kuhn-Munkres solver in Python or .NET and validate against historical assignments
- Integrate with the carrier's TMS via SQL views or API
- Train dispatchers and monitor key performance indicators for 30 days
Frequently Asked Questions
What is the Hungarian algorithm in the context of motor carrier dispatch?
The Hungarian algorithm (also known as the Kuhn-Munkres algorithm) is an optimal assignment method that solves the assignment problem in polynomial time. In motor carrier operations it is used to match available tractors to pending loads in a way that minimizes total deadhead miles while respecting business constraints such as hours-of-service, equipment type, and driver domicile.
How much deadhead reduction can the Hungarian method realistically achieve?
There is no reliable general figure, because the result depends on lane balance, customer detention patterns, forecast accuracy, position data quality, and how well the cost matrix reflects real cost. A carrier should measure it directly: record network deadhead share (empty miles divided by total miles) for a baseline period, replay historical dispatch days through the solver to compare its plan with what was actually run, then run a live pilot and compare against the same baseline.
Can this algorithm be implemented inside Truckmate, McLeod, or TMW Systems?
Yes. The algorithm is usually implemented as a supplemental optimization service that reads current order and asset data via SQL views or EDI 204/214 extracts, solves the assignment problem, and writes recommended moves back into the dispatch board or as pre-planned moves. The same pattern applies to Truckmate, McLeod, and TMW environments, which all store orders and assets in queryable SQL schemas.
What data elements are required to build an effective cost matrix?
Key inputs include: current tractor GPS location or last reported position, load origin and destination from the 204, equipment requirements, driver available hours from ELD/HOS feeds, fuel surcharge tables, driver settlement rules, and any detention or accessorial history. These are combined into a per-tractor/per-load deadhead-plus-operating-cost matrix that the Hungarian solver minimizes.
Move beyond rule-based dispatching.
Strong Tower Consulting provides independent systems architecture, feasibility audits, and engineering roadmaps for motor carriers and freight brokers. Contact our advisory team or call 763-244-1373 to discuss your operational data and evaluate practical implementation paths for your fleet.
Strong Tower Consulting, LLC was founded in Minnesota in 2008 by Scott Elliott. In business for more than 18 years.