发帖
雷达卡
摘要翻译：
本文在一个大邻域搜索方案中研究了约束规划和局部搜索技术的混合，以解决高度约束的护士排班问题。研究发现，大邻域搜索的一个关键部分是选择片段（邻域，即变量集），以迭代的方式放松和重新优化。大邻域搜索的成功与否取决于所识别的邻域对于解分配中有问题部分的充分性以及邻域大小的选择。我们研究了在大邻域搜索方案中选择不同大小片段的三种策略。前两种策略是根据问题的性质定制的。第三种策略更为通用，以软约束违反行为的代价信息及其传播为指标，选择添加到片段中的变量。以一个基准护士名册问题为例，对这三种策略进行了分析和比较。有希望的结果证明了未来在混合方法中工作的可能性。
---
英文标题：
《A Constraint-directed Local Search Approach to Nurse Rostering Problems》
---
作者：
Fang He, Rong Qu
---
最新提交年份：
2009
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
In this paper, we investigate the hybridization of constraint programming and local search techniques within a large neighbourhood search scheme for solving highly constrained nurse rostering problems. As identified by the research, a crucial part of the large neighbourhood search is the selection of the fragment (neighbourhood, i.e. the set of variables), to be relaxed and re-optimized iteratively. The success of the large neighbourhood search depends on the adequacy of this identified neighbourhood with regard to the problematic part of the solution assignment and the choice of the neighbourhood size. We investigate three strategies to choose the fragment of different sizes within the large neighbourhood search scheme. The first two strategies are tailored concerning the problem properties. The third strategy is more general, using the information of the cost from the soft constraint violations and their propagation as the indicator to choose the variables added into the fragment. The three strategies are analyzed and compared upon a benchmark nurse rostering problem. Promising results demonstrate the possibility of future work in the hybrid approach.
---
PDF链接：
https://arxiv.org/pdf/0910.1253
京公网安备 11010802022788号
