TMS Dynamic Empty Mileage Minimization: Hungarian Matching Algorithm & Automated Backhaul Pairing
Enterprise transportation management systems can dramatically reduce uncompensated deadhead miles by treating the daily dispatch problem as a classic assignment task. This technical deep-dive explains how Strong Tower Consulting implements the Kuhn-Munkres (Hungarian) algorithm inside production TMS platforms to optimally pair terminating power units with outbound freight orders in real time.
By Scott Elliott, Principal Transportation Systems Architect at Strong Tower Consulting. Strong Tower Consulting, LLC was founded in Minnesota in 2008 and has served motor carriers and freight brokerages for more than 18 years. Strong Tower Consulting, LLC and Exspeedite LLC are separately organized sister companies under common ownership (separate EINs; liability firewall). Scott Elliott is founder and transportation systems architect of both.
The Daily Combinatorial Challenge for Motor Carriers
Every evening, dispatch teams at truckload and refrigerated carriers face the same optimization problem: dozens of power units are terminating their current runs across a geographic region while an overlapping set of new outbound loads must be covered the following day. The objective is to assign each available tractor to an outbound order such that total empty (deadhead) mileage is minimized.
When the number of terminating tractors (N) and available outbound loads (M) are unequal, or when some tractors cannot physically reach certain loads within driver hours-of-service limits, the problem becomes a rectangular bipartite matching task with constraints. Manual dispatchers typically achieve 15-20% empty miles on dry van and reefer fleets. Production-grade algorithmic pairing routinely lowers this figure to under 7.5% across large networks.
Problem Formulation as Bipartite Minimum-Cost Assignment
Let T = {t₁, t₂, …, tₙ} be the set of terminating power units with known location, available driver, and hours-of-service remaining.
Let L = {l₁, l₂, …, lₘ} be the set of outbound freight orders with pickup location, earliest pickup time, and revenue characteristics.
We construct an n × m cost matrix C where c_{i,j} equals the highway routing distance (or estimated driving time) from the termination point of tractor tᵢ to the pickup point of load lⱼ. If the assignment is infeasible due to HOS, equipment type, or service-time violation, we set c_{i,j} = ∞ (represented in code as a large sentinel value).
The goal is to find a matching that minimizes the sum of selected costs while assigning at most one load per tractor and at most one tractor per load. When n ≠ m, the Hungarian algorithm is applied to the larger dimension after padding the matrix with dummy rows or columns having zero cost (for maximization of covered loads) or appropriately penalized costs.
Highway Distance Matrix Construction in the TMS
Enterprise TMS platforms maintained by Strong Tower integrate with commercial routing engines (PC*Miler, ALK, Google Routes API, or proprietary graph engines). For each candidate pair (tᵢ, lⱼ), the system executes a point-to-point routing request that respects:
- Legal truck routes and bridge restrictions
- Live or predicted traffic patterns for the departure window
- Driver HOS remaining hours and 14-day reset status
- Equipment compatibility (dry van, reefer, flatbed, etc.)
The resulting matrix is stored in a temporary PostgreSQL table with JSONB metadata for auditability. Typical matrix sizes in mid-sized fleets range from 25×40 to 120×180; larger matrices are partitioned by geographic cluster (e.g., Midwest, Southeast, California) to keep polynomial runtime manageable.
The Kuhn-Munkres (Hungarian) Algorithm in Production
The Hungarian algorithm solves the assignment problem in O(n³) time. Strong Tower implements a JavaScript/TypeScript version based on the Munkres extension for rectangular matrices, compiled to WebAssembly for execution inside the TMS application server. The core steps executed by the TMS are:
- Row reduction: subtract the smallest value in each row from all elements in that row.
- Column reduction: subtract the smallest value in each column from all elements in that column.
- Cover all zeros with the minimum number of lines (rows and columns).
- If the number of covering lines equals the dimension of the square matrix, an optimal assignment exists in the zero positions. Otherwise, adjust the matrix by finding the smallest uncovered value and updating rows and columns accordingly.
- Repeat until an optimal covering is found.
Once the zero-cost positions are identified, the algorithm returns the column index (load) assigned to each row (tractor). The TMS then converts these assignments into ranked dispatch recommendations ordered by projected deadhead savings.
HOS Validation and Business Rule Layer
Before any assignment is locked, the TMS performs a secondary validation pass against the driver’s ELD data. This integration, detailed in our ELD & EDI Integration practice, confirms:
- Sufficient on-duty and driving hours remain within the 11-hour and 14-hour rules
- The driver has not exceeded weekly limits
- The projected arrival time at the new pickup falls inside the load’s appointment window
Assignments that fail HOS validation are removed from the feasible set and the cost matrix is recomputed with updated availability. This feedback loop typically runs every 15 minutes during peak dispatch windows.
Automated Backhaul Pairing Workflow
The complete production workflow inside a modern TMS includes the following steps:
- Termination events are detected via telematics or driver check-call (GPS stop + duty status change).
- Available outbound loads are queried from the order management module with pickup windows overlapping the next 48 hours.
- Geographic clustering groups tractors and loads within 250-mile radius to reduce matrix size.
- Cost matrix is built using highway routing distances.
- Hungarian solver returns optimal assignment.
- Each recommended pairing is scored by deadhead savings versus the historical average for that lane.
- Dispatchers receive a ranked list with one-click acceptance that writes the new load to the tractor’s itinerary and transmits EDI 204 to the carrier or driver mobile application.
- Post-assignment, actual deadhead miles are captured and used to refine future routing engine parameters.
This closed-loop system has been observed to reduce system-wide empty miles from an 18% baseline to under 7.5% in dry van and refrigerated fleets when combined with disciplined load acceptance standards.
Database Schema Considerations for Scalability
Strong Tower recommends the following core tables for supporting dynamic matching:
CREATE TABLE tms_assignment_matrix (
matrix_id UUID PRIMARY KEY,
run_date TIMESTAMPTZ NOT NULL,
cluster_id TEXT,
matrix JSONB NOT NULL, -- sparse representation
solution JSONB,
created_at TIMESTAMPTZ DEFAULT NOW()
);
CREATE TABLE tms_power_unit_availability (
tractor_id TEXT,
snapshot_time TIMESTAMPTZ,
lat NUMERIC,
lon NUMERIC,
hos_driving_remaining INTEGER,
hos_on_duty_remaining INTEGER,
next_available_time TIMESTAMPTZ,
PRIMARY KEY (tractor_id, snapshot_time)
);These structures integrate with existing transportation accounting systems to ensure deadhead costs are properly allocated to the correct profit center.
Integration with Broader TMS Capabilities
Dynamic empty-mileage minimization does not operate in isolation. It must be tightly coupled with:
- TMS Implementation that maintains clean master data for lanes, equipment, and facilities
- Carrier Rate Matrix Optimization to ensure backhaul rates are competitive
- Business Process Optimization that aligns dispatchers with algorithmic recommendations
- Advanced Reporting that tracks before-and-after deadhead percentages by region, fleet type, and dispatcher
Carriers operating in the truckload, intermodal drayage, and brokerage / 3PL segments each require slight variations of the core algorithm to accommodate different network densities and service expectations.
Practical Results and Maintenance
When properly integrated, the Hungarian-based backhaul pairing module typically pays for itself within the first quarter through reduced fuel, driver overtime, and equipment wear. Ongoing maintenance involves quarterly recalibration of the routing engine against actual telematics data and periodic review of constraint weights (HOS, appointment windows, equipment compatibility).
Strong Tower Consulting continues to enhance these optimization engines for clients running both on-premise and cloud-native TMS platforms. The same mathematical foundation can be extended to multi-objective optimization that balances empty miles, driver dwell time, and on-time performance.
Ready to reduce your fleet's empty mileage?
Our team will evaluate your current TMS dispatch workflow and quantify the potential savings from automated Hungarian matching.
Frequently Asked Questions
How long does the Hungarian algorithm take to run on a 100×100 cost matrix?
On modern server hardware the WebAssembly implementation completes in under 400 milliseconds for a 100×100 matrix, making it suitable for real-time dispatch recommendations every 10-15 minutes.
Can the algorithm handle more loads than available tractors?
Yes. The rectangular variant of the Munkres algorithm automatically selects the highest-value assignments up to the number of available tractors while leaving excess loads unassigned for manual or secondary optimization passes.
Does this replace human dispatchers?
No. The system produces ranked recommendations that experienced dispatchers review and accept. Human expertise is still required for exceptions, customer-specific requirements, and strategic decisions that fall outside the mathematical model.