用图神经网络预测最优解方向，加速团队组建与路径规划求解。
Partial Column Generation with Graph Neural Networks for Team Formation and Routing
- 基于图神经网络预测哪些子问题能生成负成本列
- 在严苛时限下求解硬实例时速度显著优于传统方法
- 适合需要快速求解复杂团队调度问题的工业场景
团队组建与路由问题是具有多个现实应用场景（如机场、医疗和维护运营）的复杂优化问题。现有文献提出基于列生成的精确求解方法。本文针对存在多个定价子问题的场景，提出一种新型部分列生成策略，通过机器学习模型预测哪些子问题可能产生负减少成本的列。我们设计了专用于该问题的图神经网络模型实现此预测。计算实验表明，该策略显著提升求解效率，在严苛时间限制下对困难实例的表现优于已有部分列生成方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。