Hotel room optimization/sorting algorithm

Is there any well know开发者_StackOverflown 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.

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!

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 :-)

You want to search for Drools-Planer: http://www.jboss.org/drools.

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