Assignment-Routing Optimization: Solvers for Problems Under Constraints
This provides an efficient optimization method for practical robotic packaging and logistics, though it is incremental as it extends existing MIP solvers with tailored constraints.
The paper tackles the Joint Routing-Assignment problem for robotic packaging by developing a mixed-integer programming solver that handles constraints like multiple placeholders and time frames, achieving global optima with stable low computation times and outperforming existing solvers by up to an order of magnitude.
We study the Joint Routing-Assignment (JRA) problem in which items must be assigned one-to-one to placeholders while simultaneously determining a Hamiltonian cycle visiting all nodes exactly once. Extending previous exact MIP solvers with Gurobi and cutting-plane subtour elimination, we develop a solver tailored for practical packaging-planning scenarios with richer constraints.These include multiple placeholder options, time-frame restrictions, and multi-class item packaging. Experiments on 46 mobile manipulation datasets demonstrate that the proposed MIP approach achieves global optima with stable and low computation times, significantly outperforming the shaking-based exact solver by up to an orders of magnitude. Compared to greedy baselines, the MIP solutions achieve consistent optimal distances with an average deviation of 14% for simple heuristics, confirming both efficiency and solution quality. The results highlight the practical applicability of MIP-based JRA optimization for robotic packaging, motion planning, and complex logistics .