http://www.perlmonks.org?node_id=492181

richard5mith has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to write code that assigns guests to hotel rooms. I have a certain number of adults, children and infants and an array containing a hashref of room types.

Each room type can take a maximum number of people, a max adults, a max children and a max infants. It also has a room id, a property id and a name.

@rooms = ( { roomid => 1, name => "Double", maxocc => 2, maxadults => +2, maxchildren => 0, maxinfants => 0, propertyid => 1 }, { roomid => 2, name => "Triple", maxocc => 3, maxadults => 3, maxchild +ren => 3, maxinfants => 2, propertyid => 1 }, { roomid => 3, name => "Quad", maxocc => 4, maxadults => 4, maxchildre +n => 2, maxinfants => 2, propertyid => 1 } );

This means that while a room can hold 4 people, it may only be allowed to hold 2 adults, or 2 children. Infants must be in a room with an adult, and realistically, children should be put in with adults as well when possible.

Somehow I need to work out the optimal combinations that the guests can fit into these rooms. While there are many combinations that will obviously work, I need to be able to decide on what are considered the "best" ones, which is really the ones that use the least number of rooms. All of these will then have to pass other tests (like is that combination of rooms actually available), so it doesn't have to pin it down to just one.

Each room can also be used more than once, meaning that if there are 6 adults, a valid combination is 3 double rooms that take 2 adults each, which is obviously better than 2 adults in the Double, 2 in the Triple and 2 in the Quad.

I've been going round and round in circles trying to write this, but really don't come close. Standard bin packing algorithms that I've written so far work great for bins of a set size, with no repeats, but not for bins that have more than one criteria and may be used again.

Any pointers in the right direction will be met with gracious approval.

Replies are listed 'Best First'.
Re: Assign guests to hotel rooms
by gri6507 (Deacon) on Sep 15, 2005 at 12:44 UTC
    This sounds like a very familiar problem. Before suggesting any algorithms, I will state some assumptions: At the time of this room assignment, the room statuses are staying in the constant state (i.e. all free rooms will remain free and all occupied rooms are not available for assignment and will remain that way) and the guest list is constant (we are asked to find the optimal arrangement for our guests given that no new guests will be signing up) Finally, a guest should be defined as a set of people (adults, children and infants) who make a single reservation. In other words, a family of two adults, one child and one infant is four people, but only one reservation.

    With these disclamers in mind you want to do something like

    • Take the first available room. For every reservation, find the reservation that has the correct number of people for that room.
    • If no reservation is found that fits the room type completely, try finding a reservation with one fewer adults (least restrictive)
    • If that doesn't work, then try finding a reservation with one fewer children (next most restrictive)
    • If that doesn't work, then try finding a reservation with one fewer infants (lease restrictive)
    • If that doesn't work, then try finding a reservation with one fewer adults and one fewer children then one fewer adults and one fewer infants and one fewer children and one fewer infants
    • etc ...

    This would require many passes through the guest list, but for a usual hotel, we are only talking about reservations numbering in low hundreds at most, so algorithm execution should not be that great of a concern. Hope this helps.

Re: Assign guests to hotel rooms
by blokhead (Monsignor) on Sep 15, 2005 at 12:52 UTC
    Looking for help with AI::Genetic and classroom scheduling is a previous thread about doing a similar kind of scheduling-with-constraints with a genetic algorithm. You may want to consider using this kind of approach.

    Update: You may also want to look at the Gale Shapely (proposal) stable matching algorithm. Each group of guests ranks the rooms in their order of preference (bigger is better, perhaps), and each room ranks the groups of guests in its order of preference (less wasted space is better, perhaps). Then the two sides "propose" to each other. When it's done, the pairs are made such that no two pairs can break their "engagements" to obtain a more favorable engagement. It's quite a quite and simple algorithm. I can't remember whether the correctness still holds when the number of rooms is different than the number of guests, and I'm a little short of time right now, but it's worth looking at.

    blokhead

Re: Assign guests to hotel rooms
by demerphq (Chancellor) on Sep 15, 2005 at 22:17 UTC

    For each room type you have available, allocate the most people you can to the room, repeat until you run out of rooms. Do it recursively for each legal possibility and then sort them by the amount of rooms used and the amount of wastage on the room. Somthing like below.

    By-the-way, for some reason i see this as more of a game play kind of scenario. You can kind of imagine a room allocation as a "move". Some moves prevent other moves, and ultimately a move cant be properly scored until you see its consequences. Thus for instance if you were allocating lots of people over lots of rooms types, the recursion would start getting heavy, so you could use wastage to prune moves. Ie, once the accumulated wastage went over a certain threshold it doesnt matter how you allocate the following moves, they are still in a losing "game".

    Also, i should say that I think an important simplification is that you probably aren't trying to match people to specific rooms, but rather to one of many rooms of a given type. So dont iterate over all the rooms, iterate over the roomtypes that are available, and keep track how many of each you have. Then once you have allocated recurse in and do it again, with the new people and room counts in play. By doing it this way you reduce the number of possible moves at any one time by not having to worry about "duplicate" moves where book the people into different rooms with identical characteristics. This should keep the size of the search space managable. I mean my girlfriend works in the business and she says twenty room types would be quite a lot for even a large hotel. Something like this is fairly managable IMO.

    So for instance the procedure might be something like selecting the room types and counts for all rooms available in the required time-period, then applying something like the below code on the results.

    Anyway, here is my really hacky attempt at a solution. (really hacky, im too tired now to document it or clean it up, maybe another day)

    ---
    $world=~s/war/peace/g

Re: Assign guests to hotel rooms
by QM (Parson) on Sep 15, 2005 at 15:47 UTC
    Also without getting into specific algorithms, it seems you need to do something along the following:
    1) Generate combinations of people-room tuples (perhaps using an iterator instead of all at once).
    2) Write a scoring function that returns a value showing how good the match is on each tuple.
    2a) You may also want a scoring function that looks at overall efficiency, such as wasted space and empty rooms.
    3) Iterate through the combinations, keeping track of which solutions have the highest totals.

    Depending on the size of the problem set, you may need to optimize this by pruning the search space. You need to ask yourself if you want a pretty good solution, or the optimal. Optimal may take a long time to find, while pretty good could be an order of magnitude quicker.

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

      I'm happy with good. The user can always change it afterwards to something more optimal.
Re: Assign guests to hotel rooms
by joecamel (Hermit) on Sep 15, 2005 at 18:55 UTC
    This is a problem dear to my heart, as I worked at a hotel front desk for about 3 years. The problem is even more complicated when you take into account occupancy time -- parties arriving and departing at different times.

    Inevitably, guests show up and ask for a different room than the one blocked for them and you have to swap around rooms assigned to other guests with different arrive/depart times. Throughout the day, there is a domino effect and things get really tight towards the end of the day. The more room options you have, the worse it gets (e.g. smoking/non-smoking, good view, suites).

    Sorry I can't offer any solutions, but out of curiosity, I'd love to see what you end up with.

    joecamel
Re: Assign guests to hotel rooms
by NateTut (Deacon) on Sep 15, 2005 at 13:03 UTC
      No, I really am working on a hotel booking system. Nothing theoretical here. :)
Re: Assign guests to hotel rooms
by polypompholyx (Chaplain) on Sep 15, 2005 at 18:08 UTC
    I am not a mathematician, but bin-packing problems are NP-hard, and any algorithm you choose will only approximate the optimal solution (potentially to arbitrary precision if your problem is formally identical to bin-packing). The only way to guarantee the optimal solution is to perform an exhaustive (impractical) search of every possible combination. How will you calculate when your solution is 'good enough'?