给人安排床位自动管理的方法

Question

我每年都帮助一个青年营。将与会者分配到卧室是一项艰巨的任务——共有92间卧室，活动将持续一周，与会者逗留的时间长短不一，床需要重新使用。在

目前需要一名志愿者~一周的时间来分配人员到房间。有很多规则要遵循，因为并不是所有的参加者都会在一周内呆在这里，任务是每晚完成的。在

我想把任务自动化。编程语言和计算成本是实现细节，我可以根据需要格式化输入数据/规则（inc代码生成）。任何能节省数小时无聊的东西。。。在

可用技术

我没有领域专业知识，所以首先我必须了解可能的方法。在

约束编程似乎是显而易见的方法，因为有规则可遵循。然而，这些规则不是二进制的，a previous thread向我介绍了软约束和成本函数。在

当我读到成本函数时，它让我想到了机器学习和神经网络。这些都很流行，但我相信需要一组数据来训练它们，这是我没有的——我可以创建的，但总的来说，这比手动完成任务要花更多的时间。我已经知道这些限制：我不必从数据中推断出来。在

• Q： Prolog中的成本函数与机器学习中的成本函数不同吗？在
• Q： 机器学习是否适合这个问题？在
• Q： 还有其他方法我忽略了吗？在

我找不到房间分配问题正在网上讨论，在杂志等；它一定是常见的，所以我错过了一些领域的具体术语。由于医院和酒店都需要它，我相信它是经过充分研究的。在

• Q： 文献中所说的床位分配问题是什么？在

基于时间的作业

我还有一个概念上的问题。我知道我怎么解决一个晚上的问题，但是我怎么考虑为多个晚上建模呢？在

约束求解器（或其他技术）不知道时间（也不知道2016-09-05在2016-09-06之前），但我需要输入人们每晚停留的晚上并查看任务。在

• Q： 我应该如何考虑时间序列？在

从概念上把握输出

第二个问题是：系统将如何输出分配给哪些人的卧室？例如，在Prolog数独解算器中，可以有多个解，但这是有硬约束的。有了模糊约束，我会得到X在Y房间的概率，他们也在Z房间的概率（如果你愿意的话，是量子叠加）？在

• Q： 输出会是什么样子？在

部分解决方案可以

必须手动调整的首次通过分配可以节省时间。就像手动分配那些“复杂”的与会者（比如晚上的保安，他们睡在一个特定的房间里），然后让电脑来完成剩下的工作。在

• Q： 这会使问题更容易解决吗？在

我的尝试

最初我想恢复我13年前一学期的Prolog知识，并设置所有标准的约束条件。这对于一个非常简单的案例是有效的，但是一旦我超越了“必须”的标准，变成了灰色规则和妥协，我就失败了。在

示例规则（约束）

所有规则都有不同的优先级。为了简化，我按must、should和{}分组。在

• must房间里的性别相同
  • 除非被“必须分享”选项（如夫妻）所取代
• must需要残疾人友好型房间的人可以得到
• must如果与会者需要一个有婴儿床的房间，他们必须得到
• must指定“必须与X共享”或“必须与Y&Z共享”的与会者必须分配到同一个房间
  • 他们可能不会为了同一个号码而留下来晚上（例如，A住周一至周四，B住周二至周五）。在整个时段安排床位是可以的）
  • “Must Share With”关系可以是单向的，也可以是双向的-我可以实现其中任何一个
• must/should如果与会者需要一间单人房，除非没有可能的解决办法，否则他们必须得到
• should将与会者按角色分组，例如“青年”、“青年领袖”、“厨师”、“领导者”。有些角色比其他角色更适合混合。在
• should尽量减少跳房：一旦你有了床，就在床上过夜。除非没有可能的解决办法
• should夫妇优先选择双人床房间
  • （我还没想好如何制定一个规则，即不能假设所有“必须分享”的关系都是夫妻关系。目前它是用人类的知识来完成的）
• nice将与会者按所就读的大学分组（如适用）
• nice将带套房设施的房间优先安排给非年轻人

有更多的规则（例如，有饮食需求的人必须呆在特定的建筑里），但这提供了足够的例子。在

场地按张床收费，而不是每间客房，因此尽量减少使用的房间数量非常重要，至少今年是这样。在

同样的任务也必须为与会者分配到餐厅和清洗轮值表，但两者都要简单得多。在

样本数据集

rooms:
    room1:
        building: Building1
        capacity: 2
        is_ensuite: yes
        has_cot: yes
    room2:
        building: Building2
        capacity: 4
        is_ensuite: no
        has_cot: yes
    room3:
        building: Building1
        capacity: 2
        is_ensuite: no
        has_cot: yes
    room4:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
    room5:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
---
people:
    albert:
        must_share_with: @brenda
        needs_cot: yes
        role: leader
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    brenda:
        role: no role
        gender: f
        arrive: 2016-09-06
        depart: 2016-09-09
    steve:
        role: student
        university: Cambridge
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    jason:
        role: student
        university: Bristol
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    brian:
        role: tech
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    clare:
        role: speaker
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09
    george:
        role: band/after hours
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-08
    sarah:
        role: band/after hours
        gender: f
        arrive: 2016-09-07
        depart: 2016-09-08
    john:
        role: band/after hours
        gender: m
        arrive: 2016-09-08
        depart: 2016-09-09
    janet:
        role: band/after hours
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09

样本结果

^{pr2}$

或者（这是否可以接受取决于哪些角色可以共用房间，例如，乐队成员凌晨3点睡觉，技术人员早上6点起床）：

| Room  | Capacity | 2016-09-05 | 2016-09-06     | 2016-09-07     | 2016-09-08     | 2016-09-09     | 2016-09-10 | 
|-------|----------|------------|----------------|----------------|----------------|----------------|------------| 
| room1 | 2        | albert     | albert, brenda | albert, brenda | albert, brenda | albert, brenda | albert     | 
| room2 | 4        |            |                | jason, steve   | jason, steve   | jason, steve   |            | 
| room3 | 2        | brian      | brian          | brian, george  | brian, john    | brian          | brian      | 
| room4 | 4        |            |                | sarah          | janet          |                |            | 
| room5 | 4        |            |                |                |                |                |            |