Partial Column Generation with Graph Neural Networks for Team Formation and Routing
This work addresses optimization challenges in real-world applications like airport and healthcare operations, but it is incremental as it builds on existing column generation methods.
The paper tackles the team formation and routing problem by proposing a partial column generation strategy that uses graph neural networks to predict which pricing problems yield negative reduced cost columns, enhancing solution methods and outperforming traditional approaches, especially on hard instances under tight time limits.
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.