2025/09/18 by Giacomo Dall’Olio, Dall'Olio, Giacomo, Rainer Kolisch +3
Computer Science · Decision Sciences · Psychology · #Artificial Intelligence (cs.AI) #Artificial neural network #Column (typography) #Column generation #FOS: Computer and information sciences #Graph #Machine Learning (cs.LG) #Routing (electronic design automation) #Simulation Techniques and Applications #Software Engineering Techniques and Practices #Team Dynamics and Performance #Vehicle routing problem
paper · pdf · doi:10.48550/arxiv.2509.15275
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.