Assigning people to beds - approaches to automate

Question

I help with a youth camp every year. Assigning attendees to bedrooms is a massive task - there are 92 bedrooms and the event runs for a week, with attendees staying for varying lengths of time, and beds needing to be reused.

It currently takes a volunteer ~a week to assign people to rooms. There are lots of rules to follow, and as not all attendees stay for the full week assignment is done on a night by night basis.

I want to automate the task. The programming language and computational cost are implementation details, and I can format the input data/rules however needed (inc code generation). Anything that saves hours of tedium...

Available techniques

I have no domain expertise, so first I have to understand possible approaches.

Constraint programming seemed the obvious approach as there are rules to follow. However the rules aren't binary, and a previous thread introduced me to soft constraints and cost functions.

When I read up on cost functions it pointed me to machine learning and neural networks. These are popular but I believe need sets of data to train them, which is something I don't have - I could create, but that'd take more time overall than doing assignment manually. And I know the constraints already: I don't have to deduce them from data.

• Q: Is a cost function in Prolog different to in machine learning?
• Q: Is machine learning a 'fit' for this problem?
• Q: Are there other approaches I've overlooked?

I can't find room assignment problems being discussed on the web, in journals etc; It must be common so I am missing some domain-specific terminology. With hospitals and hotels needing it, I'm sure it is well researched.

• Q: What is a bed-assignment problem called in the literature?

Time-based assignments

I also have a conceptual problem. I can see how I solve for one night, but how do I think of modelling multiple nights?

The constraint solver (or other technique) is unaware of time (and won't know 2016-09-05 comes before 2016-09-06), but I need to input the nights people stay and see the assignments per-night.

• Q: How should I consider time series?

Conceptually grasping the output

The second is: How would the system output which bedrooms people are assigned to? In a Prolog sudoku solver (for example) there can be multiple solutions, but that's with hard constraints. With fuzzy constraints, would I end up with a probability that person X is in Room Y, and a probability they're also in Room Z (a quantum superposition if you like)?

• Q: What will the output be like?

Partial solutions are OK

A first-pass assignment which has to be manually adjusted would save time. As would manually assigning the 'complicated' attendees (like night security, who sleep in a particular room) and letting the computer do the rest.

• Q: Does this make the problem easier to solve?

My attempt

Originally I thought of resurrecting my one-semester of Prolog knowledge from 13 years ago, and setting constraints for all criteria. This worked for a very simple cases, but I failed once I moved beyond "must" criteria to grey-rules and compromises.

Sample Rules (constraints)

All rules have different priorities. To simplify I've grouped by must, should and nice.

• must Same gender in room
  • Unless over-ridden by "Must share with" option e.g. couples
• must People who need disabled-friendly rooms get them
• must If the attendee needs a room with a cot for their baby, they must get it
• must Attendees who specify "Must Share with X" or "Must Share with Y & Z" must be assigned the same room
  • They may not be staying for the same number of nights (e.g. A stays for Mon-Thu, B for Tue-Fri). Blocking out beds for the entire period is OK)
  • the "Must Share With" relationship can be unidirectional or bidirectional - I can implement either
• must/should If an attendee needs a single room, they must get it unless there's no possible solution
• should Group attendees in rooms by roles, e.g. "Youth", "Youth leaders", "Cooks", "Leaders". Some roles are more suitable to mix than others.
• should Minimise room-hopping: once you have a bed, stay in it for all nights. Unless there's no possible solution
• should Couples are prioritised rooms with double beds
  • (I haven't figured out how to make a rule for this, which doesn't assume all "Must Share With" relations are couples. At the moment it's done with human knowledge)
• nice Group attendees in rooms by university they attend (where applicable)
• nice Prioritise rooms with en-suite facilities to non-youth roles

There are more rules (e.g people with dietary requirements must stay in a particular building) but this provides enough examples.

The venue charges per-bed not per-room, so minimising the number of rooms used is NOT important - this year at least.

Similar assignment has to be done for attendees to dining rooms & washing-up rotas, but both are much simpler.

Sample data set

rooms:
    room1:
        building: Building1
        capacity: 2
        is_ensuite: yes
        has_cot: yes
    room2:
        building: Building2
        capacity: 4
        is_ensuite: no
        has_cot: yes
    room3:
        building: Building1
        capacity: 2
        is_ensuite: no
        has_cot: yes
    room4:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
    room5:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
---
people:
    albert:
        must_share_with: @brenda
        needs_cot: yes
        role: leader
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    brenda:
        role: no role
        gender: f
        arrive: 2016-09-06
        depart: 2016-09-09
    steve:
        role: student
        university: Cambridge
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    jason:
        role: student
        university: Bristol
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    brian:
        role: tech
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    clare:
        role: speaker
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09
    george:
        role: band/after hours
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-08
    sarah:
        role: band/after hours
        gender: f
        arrive: 2016-09-07
        depart: 2016-09-08
    john:
        role: band/after hours
        gender: m
        arrive: 2016-09-08
        depart: 2016-09-09
    janet:
        role: band/after hours
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09

Sample outcomes

| Room  | Capacity | 2016-09-05 | 2016-09-06     | 2016-09-07     | 2016-09-08     | 2016-09-09     | 2016-09-10 | 
|-------|----------|------------|----------------|----------------|----------------|----------------|------------| 
| room1 | 2        | albert     | albert, brenda | albert, brenda | albert, brenda | albert, brenda | albert     | 
| room2 | 4        |            |                | jason, steve   | jason, steve   | jason, steve   |            | 
| room3 | 2        | brian      | brian          | brian          | brian          | brian          | brian      | 
| room4 | 4        |            |                | george         | john           |                |            | 
| room5 | 4        |            |                | sarah          | janet          |                |            | 

Or (whether this is acceptable depends which roles can share rooms, e.g. band members go to bed at 3am, tech gets up at 6am):

| Room  | Capacity | 2016-09-05 | 2016-09-06     | 2016-09-07     | 2016-09-08     | 2016-09-09     | 2016-09-10 | 
|-------|----------|------------|----------------|----------------|----------------|----------------|------------| 
| room1 | 2        | albert     | albert, brenda | albert, brenda | albert, brenda | albert, brenda | albert     | 
| room2 | 4        |            |                | jason, steve   | jason, steve   | jason, steve   |            | 
| room3 | 2        | brian      | brian          | brian, george  | brian, john    | brian          | brian      | 
| room4 | 4        |            |                | sarah          | janet          |                |            | 
| room5 | 4        |            |                |                |                |                |            |