Assignment-Routing Optimization : Efficient Heuristic Solver with Shaking Algorithm

Qilong Yuan, Michal PavelkaarXiv 2025 · DOI · arXiv

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.

Flowchart of the proposed joint assignment and routing optimization pipeline.

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:

  1. Step A: Fix the visit sequence and re-optimize item-to-target assignments using the Hungarian algorithm.
  2. 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.

Final optimized path solution for a joint assignment-routing problem.

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

Abstract

This paper works on heuristic solver for joint assignment and routing optimization problem. Study on previous works shows that MIP based exact solvers can only provide efficient solutions for small to moderate size problems, due to exponentially growing computational complexity. This paper proposes to start with high quality initial guess through Hungarian algorithm based assignment and heuristic cycle merging algorithm. Subsequently, the solution is improved based on a proposed shaking algorithm to improve the assignment and routing sequence. In addition, the shaking approach also enables the Simulated Annealing algorithm to further improve the solution, which is very difficult if it is purely based on random sampling updates of item and placeholder sequences. Extensive experimental validation comparing with ground truth from the previously shared database shows that the introduced solver is much more efficient than the Gurobi solver especially for large size problems, with a 1000 node pair problem being solved within 1 min in Python implementation. The solution accuracy is within a percent in general as compared with ground truth in database. Although there are spaces for the proposed solver to be further improved with better accuracy, it works for practical applications with acceptable path quality and sufficient solver efficiency. Such shaking algorithms based solvers can also be applied to more general joint assignment and routing optimization problem with multiple type of items and corresponding placeholders. GitHub repository: https://github.com/QL-YUAN/Joint-Assignment-Routing-Optimization-Heuristic.git
BibTeX
@misc{yuan2025assignment,
  author = {Qilong Yuan and Michal Pavelka},
  title = {{Assignment-Routing Optimization : Efficient Heuristic Solver with Shaking Algorithm}},
  year = {2025},
  eprint = {2510.21488},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.21488},
  howpublished = {arXiv},
}
Figure