Partial Column Generation with Graph Neural Networks for Team Formation and Routing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911163205287936 |
|---|---|
| author | Dall'Olio, Giacomo Kolisch, Rainer Wu, Yaoxin |
| author_facet | Dall'Olio, Giacomo Kolisch, Rainer Wu, Yaoxin |
| contents | The team formation and routing problem is a challenging optimization problem with several real-world applications in fields such as airport, healthcare, and maintenance operations. To solve this problem, exact solution methods based on column generation have been proposed in the literature. In this paper, we propose a novel partial column generation strategy for settings with multiple pricing problems, based on predicting which ones are likely to yield columns with a negative reduced cost. We develop a machine learning model tailored to the team formation and routing problem that leverages graph neural networks for these predictions. Computational experiments demonstrate that applying our strategy enhances the solution method and outperforms traditional partial column generation approaches from the literature, particularly on hard instances solved under a tight time limit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15275 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partial Column Generation with Graph Neural Networks for Team Formation and Routing Dall'Olio, Giacomo Kolisch, Rainer Wu, Yaoxin Machine Learning Artificial Intelligence The team formation and routing problem is a challenging optimization problem with several real-world applications in fields such as airport, healthcare, and maintenance operations. To solve this problem, exact solution methods based on column generation have been proposed in the literature. In this paper, we propose a novel partial column generation strategy for settings with multiple pricing problems, based on predicting which ones are likely to yield columns with a negative reduced cost. We develop a machine learning model tailored to the team formation and routing problem that leverages graph neural networks for these predictions. Computational experiments demonstrate that applying our strategy enhances the solution method and outperforms traditional partial column generation approaches from the literature, particularly on hard instances solved under a tight time limit. |
| title | Partial Column Generation with Graph Neural Networks for Team Formation and Routing |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2509.15275 |