酒店房间优化/排序算法
有没有众所周知的酒店房间优化/排序算法？
问题是重新分配房间以最大限度地提高入住率。假设我有 10 个房间，每个预订都有开始日期和结束日期。有些房间无法重新分配，而其他房间则可以（标记）。
任何关于正确方向的暗示都会很棒。谢谢。
Is there any well known room optimization/sorting algorithm for hotels ?
Problem is to redistribute rooms to maximize occupancy. Let's say I have 10 rooms, start date and end date for every reservation. Some rooms cannot be realocated while others can (flag).
Any hint on the right direction would be great. Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您有一组预订和固定数量的房间，那么问题不是如何最大化利用率，而是验证预订是否可以真正实现。如果实现所有预订，利用率显然保持不变。
另一个可能的用例是，您有一组您知道可以实现的预订，然后您尝试适应新的预订，即新客户想要进行新的预订，并且您想检查是否可以重新定位一些保留是为了给新的腾出空间。
在这两种情况下，实际的问题是如何检查是否可以实现给定的一组保留。
对于不可重新定位的预订，这是微不足道的，因此假设它们可以实现，并且您想检查可重新定位的预订是否也可以实现。
第一个检查是计算每晚的预订数量；如果任何一个晚上的预订数量超过了固定预订计算后的可用房间数量，您将无法通过任何手段实现预订；您当晚的酒店已超额预订。
否则，您可以使用贪心算法尝试解决方案：按照开始日期的顺序处理预订，并将每个预订预订到第一个可用的房间（例如，按照数字房间顺序）。如果这给了你一个解决方案，那么你就已经意识到了保留，你就完成了。
如果这不起作用，那么您可以使用图形着色来解决问题，这就是通用解决方案。构造一个图，其中每个预订都是一个节点，并且两个节点（预订）当且仅当它们在时间上重叠时才连接。 在图表中包含固定（不可重新定位）的预留。然后，在使用固定预订所属的房间号对固定预订进行预着色后，尝试使用 N 种颜色（N = 酒店房间总数）对图表进行完整着色。
您还可以通过这种方式处理部分灵活的预订，当且仅当预订无法在房间 n 中实现时（例如较低的房间等级），添加从预订 r 到房间 n 的特殊 n 预着色节点的链接。
该相同的图形着色算法已成功用于例如寄存器分配的编译器中。
当然接下来的问题是如何高效地实现图形着色；为此，有现成的实现。
祝你好运！
If you have a set of reservations and a fixed number of rooms then the question is not how to maximize utilization but to verify if the reservations can be actually realized at all or not. The utilization obviously remains the same if all reservations are realized.
Another possible use case is that you have a set of reservations which you know can be realized, and then you try to fit a new reservation in, i.e. a new customer wants to make a new reservation and you want to check if you can possible relocate some of the reservations to create room for the new one.
In both cases the actual question is how to check if a given set of reservations can be realized.
For the non-relocatable reservations this is trivial, so assume they can be realized and you want to check if the relocatable reservations can be realized also.
The first check is to calculate for every night the number of reservations per that night; if at any night the number of reservations exceeds the number of available rooms once the fixed reservations are accounted for you can't realize the reservations by any tricks; your hotel is overbooked for that night.
Otherwise you can then use a greedy algorithm to attempt a solution: process the reservations in the order of their starting dates and book every reservation to a first room (e.g. in numerical room order) that's available. If this gives you a solution, then you have realized the reservations and you are done.
If that doesn't work, then you can use GRAPH COLORING to solve the problem, and this is then the universal solution. Construct a graph where every reservation is a node and two nodes (reservations) are connected if and only if they overlap time-wise. Include the fixed (not relocatable) reservations in the graph. Then attempt to do complete coloring of the graph with N colors (N = total number of rooms in your hotel) once you have precolored the fixed reservations with the room numbers they pertain to.
You can handle also only partially flexible reservations in this manner, adding a link from reservation r to a special n-precolored node for room n if and only if the reservation can NOT be realized in room n (e.g. lower room class).
This same graph coloring algorithm is used successfully e.g. in compilers for register allocation.
Of course then the question is how to implement graph coloring efficiently; for that there are ready-made implementations.
Good luck!
可以使用数学编程或约束编程来建模您的问题，使用许多现成的工具（尝试cplex或用于 MP 的 >gurobi 和用于 CP 的 gecode 或 cp 优化器（仅举几例）用于建模和解决此类问题。它们通常具有可以从大多数编程语言调用的 API。
我想这个答案是在很长一段时间后才出现的，但我希望它仍然可以帮助其他人:-)
It is possible to model your problem using mathematical programming or constraint programming, using on of the many ready-available tools (try cplex or gurobi for MP and gecode or cp optimizer for CP, just to name a few) for modelling and solving these classes of problems. They usually have APIs which can be called from most programming languages.
I guess this answer arrives after a very long time, but I hope it can still help somebody else :-)
您想要搜索 Drools-Planer：http://www.jboss.org/drools。
You want to search for Drools-Planer: http://www.jboss.org/drools.
根据我的经验，回溯对于此类问题非常有效。首先将第一个预订分配给房间类型。继续分配保留，直到有一个保留未分配为止。然后回溯你出错的地方，并相应地改变之前的决定。
这样，您要么找到一个/所有可行的解决方案，要么证明不存在。
优点是可以证明不可行性。而且，回溯可以让你找到不可行的“原因”。
参见例如 http://en.wikipedia.org/wiki/Backtracking
Backtracking works pretty well for such problems, in my experience. Just start by assigning the first reservation to a room type. Continue assigning reservations until one remains unassigned. Then backtrack where you went wrong, and change earlier decisions accordingly.
This way, you will either find a/all feasible solution(s), or you will prove that none exists.
Advantage is that you can prove non-feasibility. Moreover, backtracking allows you to find the "cause" of non-feasibility.
See e.g. http://en.wikipedia.org/wiki/Backtracking