酒店房间优化/排序算法

Question

酒店有没有众所周知的房间优化/排序算法？

问题是重新分配房间以最大化占用率.假设我有10个房间,每个预订的开始日期和结束日期.有些房间不能被调整,而有些房间可以(标记).

任何正确方向的提示都会很棒.谢谢.

Answer 1

如果您有一组预订和固定数量的房间,那么问题不是如何最大限度地利用,而是验证预订是否可以实际实现.如果实现所有预订,利用率显然保持不变.

另一个可能的用例是,您有一组您知道可以实现的预订,然后您尝试适应新的预订,即新客户想要进行新预订,并且您想检查是否可以重新定位一些保留为新的空间创造空间.

在这两种情况下,实际问题是如何检查是否可以实现一组给定的预订.

对于不可重定位的预留,这是微不足道的,因此假设它们可以实现并且您想要检查是否也可以实现可重定位的预留.

第一项检查是每晚计算当晚的预订数量; 如果在任何一个晚上预订的数量超过可用房间的数量,一旦固定预订被计算在内,您无法通过任何技巧实现预订; 那天晚上你的酒店超额预订.

否则,您可以使用贪婪算法尝试解决方案:按照开始日期的顺序处理预订,并将每个预订预订到可用的第一个房间(例如,以数字房间顺序).如果这给你一个解决方案,那么你已经意识到预订已经完成了.

如果这不起作用,那么您可以使用GRAPH COLORING来解决问题,这就是通用解决方案.构建一个图表,其中每个预留都是一个节点,当且仅当它们按时间重叠时,才连接两个节点(预留).在图表中包含固定(不可重定位)预留.然后,一旦您使用他们所属的房间号预先固定了固定预订,尝试使用N种颜色(N =您酒店的房间总数)对图表进行完全着色.

您也可以通过这种方式处理部分灵活的预订,当且仅当预订无法在房间n(例如,较低的房间等级)中实现时,才能添加从预订r到房间n的特殊n预先着色节点的链接.

这种相同的图着色算法成功地用于例如编译器中用于寄存器分配.

当然,问题是如何有效地实现图着色; 为此,有现成的实现.

祝好运!

Answer 2

您想要搜索 Drools-Planer：http://www.jboss.org/drools。