论文标题
神经网络辅助树搜索人员名册问题
Neural Networked Assisted Tree Search for the Personnel Rostering Problem
论文作者
论文摘要
人员名册问题是找到一种最佳方法来将员工分配到轮班的问题，但要遵守所有有效解决方案必须遵循的硬性约束，以及一组定义有效解决方案相对质量的软约束。该问题在文献中受到了极大的关注，并通过大量精确和元启发式方法来解决。为了为人事训练问题自动制作复杂且昂贵的启发式方法，我们提出了一种新方法，将深层神经网络和树木搜索结合在一起。通过将计划视为矩阵，神经网络可以预测当前解决方案与最佳解决方案之间的距离。它可以通过分析对人员名册问题实例的现有（接近）最佳解决方案来选择解决方案策略。结合分支和绑定，该网络可以为每个节点提供一个概率，以指示其与最佳距离之间的距离，从而可以在下一步选择哪个分支上做出明智的选择并修剪搜索树。
The personnel rostering problem is the problem of finding an optimal way to assign employees to shifts, subject to a set of hard constraints which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions. The problem has received significant attention in the literature and is addressed by a large number of exact and metaheuristic methods. In order to make the complex and costly design of heuristics for the personnel rostering problem automatic, we propose a new method combined Deep Neural Network and Tree Search. By treating schedules as matrices, the neural network can predict the distance between the current solution and the optimal solution. It can select solution strategies by analyzing existing (near-)optimal solutions to personnel rostering problem instances. Combined with branch and bound, the network can give every node a probability which indicates the distance between it and the optimal one, so that a well-informed choice can be made on which branch to choose next and to prune the search tree.
