Abstract
This paper presents a heuristic solver for the joint assignment and routing optimization problem. While exact solvers like Gurobi provide optimal solutions for small problems, their computational complexity grows exponentially with problem size. We propose a pipeline starting with a high-quality initial guess via the Hungarian algorithm and heuristic cycle merging. The solution is iteratively improved using a novel "shaking algorithm" that alternates between optimizing assignments and routing sequences. This approach also enables Simulated Annealing to escape local minima more effectively than random sampling. Experimental results show our solver handles 1,000 node pairs in under one minute with accuracy within 1% of the ground truth, offering a practical solution for large-scale logistics and robotics applications.
Introduction
In logistics and robotics, the joint assignment-routing problem involves three interdependent decisions: which item goes to which target (Assignment), the order of visits (Sequencing), and the specific paths taken (Routing). This is a complex variation of the Traveling Salesman Problem with Pickup and Delivery (TSPPD) where pairings are flexible. While exact solvers like Gurobi are effective for small datasets, they struggle with the "curse of dimensionality" as problem size increases. This research introduces a heuristic solver designed to provide near-optimal solutions with high computational efficiency.
Methodology
The proposed solver utilizes a multi-stage pipeline to handle the complexity of joint optimization.
Initial Guess and Cycle Merging
The process begins with an initial assignment phase using the Hungarian algorithm, followed by a "Back Assignment" step to refine pairings. These assignments typically result in multiple disconnected cycles. A heuristic cycle-merging algorithm then connects these into a single continuous tour.
The Shaking Algorithm
The core innovation is the "Shaking Algorithm," which iteratively improves the solution by decoupling the assignment and sequencing steps:
- Step A: Fix the visit sequence and re-optimize item-to-target assignments using the Hungarian algorithm.
- Step B: Fix the assignments and re-optimize the visit sequence.
Simulated Annealing with Sliding Windows
To scale to massive problems (e.g., 1,000+ nodes), the solver employs Simulated Annealing (SA) with a sliding window. Instead of shaking the entire route—which would be computationally expensive ($O(n^3)$)—it applies the shaking logic to a small subset of the path at a time. This allows the solver to escape local minima while maintaining efficiency.
Experimental Results
The solver was evaluated against synthetic benchmarks and ground truth data from a Gurobi-based database.
Performance and Scalability
For a problem with 300 node pairs, the heuristic achieved a 13x speedup over Gurobi (3.9 seconds vs. 52.3 seconds). It successfully solved 1,000 node pair problems in approximately 60 seconds, a scale where exact solvers often become impractical.
Accuracy
The solution quality remains high across various problem sizes, with path lengths typically staying within 0.7% to 1.6% of the absolute mathematical optimum. This level of accuracy is sufficient for most practical applications in warehouse automation and delivery routing.
Conclusion
The introduced heuristic solver demonstrates that decoupling assignment and routing through a "shaking" metaheuristic provides a powerful balance between speed and accuracy. While the current cycle-merging step is greedy and could be further optimized, the algorithm's ability to handle large-scale joint optimization problems makes it a robust tool for real-world robotics and logistics. Future work will explore applying these principles to dynamic environments with real-time constraints.
Source: Assignment-Routing Optimization: Efficient Heuristic Solver with Shaking Algorithm (Yuan & Pavelka, 2025). Code available on GitHub.
Summary updated