相关疑难解决方法(0)

我每年都会帮助一个青年营.将参加者分配到卧室是一项艰巨的任务 - 有92间卧室,活动持续一周,与会者可以待上不同的时间,床需要重复使用.

目前需要一名志愿者〜一周时间将人员分配到房间.有很多规则可供遵循,因为并非所有与会者都会在整个一周内完成任务,而是在夜间进行.

我想自动完成任务.编程语言和计算成本是实现细节,我可以根据需要格式化输入数据/规则(包括代码生成).任何可以节省繁琐时间的东西......

可用的技术

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

约束编程似乎是明显的方法,因为有规则要遵循.但是规则不是二进制的,前一个线程向我介绍了软约束和成本函数.

当我阅读成本函数时,它指出了机器学习和神经网络.这些都很受欢迎,但我相信需要一组数据来训练它们,这是我没有的东西 - 我可以创建,但这需要花费更多的时间而不是手动分配.我已经知道了这些限制因素:我不必从数据中推断它们.

我找不到在网上,期刊等讨论的房间分配问题; 它必须是常见的,因此我缺少一些特定于域的术语.对于需要它的医院和酒店,我确信它已经得到很好的研究.

我也有一个概念性的问题.我可以看到我如何解决一个晚上,但我怎么想多个夜晚建模？

约束求解器(或其他技术)不知道时间(并且2016-09-05之前不会知道2016-09-06),但我需要输入人们住的夜晚并且每晚看到作业.

第二个是:系统如何输出分配给哪些卧室的人？在Prolog数独求解器(例如)中,可以有多个解决方案,但这有很多约束.对于模糊约束,我最终会得到人X在房间Y中的概率,以及他们也在房间Z中的概率(如果你愿意的话,量子叠加)？

必须手动调整的首次通过分配将节省时间.就像手动分配"复杂"的参与者(如夜间安全,谁在特定房间睡觉)并让计算机完成其余工作一样.

最初我想过从13年前复活我一个学期的Prolog知识,并为所有标准设置约束.这适用于一个非常简单的案例,但是一旦我超越了"必须"标准,我就失败了灰色规则和妥协.

所有规则都有不同的优先级为了简化我的分组must,should和nice.

must 同房性别
- 除非被"必须与之分享"选项(如夫妻)所覆盖
must 需要残障人士客房的人可以获得
must 如果与会者需要一个带婴儿床的房间,他们必须得到它
must 指定"必须与X共享"或"必须与Y&Z共享"的与会者必须被分配到同一个会议室
- 他们可能不会在相同的夜晚停留(例如,A-Thu停留,周二至周五为B).在整个期间阻止床是好的)
- "必须共享"关系可以是单向的或双向的 - 我也可以实现
must/should 如果与会者需要一个房间,他们必须得到它,除非没有可能的解决方案
should按角色分组参加会议的与会者,例如"青年","青年领袖","厨师","领导者".有些角色比其他角色更适合混合.
should尽量减少跳房:一旦你有一张床,整晚都待在这里.除非没有可能的解决方案
should 情侣优先客房配有双人床
- (我还没有弄清楚如何为此制定规则,这并不是假设所有"必须与之分享"的关系都是夫妻关系.目前它是用人类知识完成的)
nice 他们参加的大学会议室的参加者(如适用)
nice 优先考虑带有卫浴设施的房间,以及非青年角色