Assignment-Routing Optimization with Cutting-Plane Subtour Elimination: Solver and Benchmark Dataset
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917047469867008 |
|---|---|
| author | Yuan, Qilong |
| author_facet | Yuan, Qilong |
| contents | We study a joint routing-assignment optimization problem in which a set of items must be paired one-to-one with a set of placeholders while simultaneously determining a Hamiltonian cycle that visits every node exactly once. Both the assignment and routing decisions are optimized jointly to minimize the total travel cost. In this work, we propose a method to solve this problem using an exact MIP formulation with Gurobi, including cutting-plane subtour elimination. With analysis of the computational complexity and through extensive experiments, we analyze the computational limitations of this approach as the problem size grows and reveal the challenges associated with the need for more efficient algorithms for larger instances. The dataset, formulations, and experimental results provided here can serve as benchmarks for future studies in this research area. GitHub repository: https://github.com/QL-YUAN/Joint-Assignment-Routing-Optimization |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17888 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Assignment-Routing Optimization with Cutting-Plane Subtour Elimination: Solver and Benchmark Dataset Yuan, Qilong Data Structures and Algorithms Optimization and Control Primary 90C10, Secondary 90C27, 90B06, 90C57 We study a joint routing-assignment optimization problem in which a set of items must be paired one-to-one with a set of placeholders while simultaneously determining a Hamiltonian cycle that visits every node exactly once. Both the assignment and routing decisions are optimized jointly to minimize the total travel cost. In this work, we propose a method to solve this problem using an exact MIP formulation with Gurobi, including cutting-plane subtour elimination. With analysis of the computational complexity and through extensive experiments, we analyze the computational limitations of this approach as the problem size grows and reveal the challenges associated with the need for more efficient algorithms for larger instances. The dataset, formulations, and experimental results provided here can serve as benchmarks for future studies in this research area. GitHub repository: https://github.com/QL-YUAN/Joint-Assignment-Routing-Optimization |
| title | Assignment-Routing Optimization with Cutting-Plane Subtour Elimination: Solver and Benchmark Dataset |
| topic | Data Structures and Algorithms Optimization and Control Primary 90C10, Secondary 90C27, 90B06, 90C57 |
| url | https://arxiv.org/abs/2510.17888 |