Mathematically creating the 'perfect' permutation for reservations in a hostel

Question

I am working at a hostel which uses a reservation system for each room and the beds in the room (e.g. $14$ beds in one room, bed numbers $1-14$.) When we get bookings for multiple people, we assign beds as available, which can cause problems in the future. An example of our system is seen here (click to enlarge images):

As you can see, the groups 'Finan' and 'George' ($1$st of July) are nicely coordinated such that they are sequential. However, looking at the same image, the group 'Alice' is split between beds, and so is 'Aidan'.

With a bit of 'tetris', it's possible to move around all the reservations such that they are all together, however this takes time and most definitely can be automated. This can be seen much more easily in this photo:

What would be an optimal way to automate the process of repositioning these reservations such that they are all combined sequentially?

Another issue, which may, therefore, contradict the previous issue, is when reservations must be reorganized due to a required change of bed for a multi-day stay. For example, if a guest were to book for 2 nights in this situation

would be forced to change beds after their first night; perhaps (distinctive of the first issue) it is possible to algorithmically find a 'solution' such that the guest wouldn't have to change beds, and all groups are kept together.

Any support for this would be much appreciated.

Answer 1

This is eerily similar to hospital bed planning which has a number of papers under the term Patient Admission Scheduling. It is originally defined and implemented by the CoDES group here. I have an implementation in optaplanner-examples too.

Answer 2

Here are a couple of simple MIP models that (I think) accomplish the first task, of assigning everyone to a bed while minimizing splits. They are both single-day models, which means they don't address the second task, of minimizing the number of people who have to switch beds during multi-day stays.

---

First Model

Parameters:

• $N$ = number of beds (= 14 in your example)
• $G$ = number of groups to be booked
• $m_g$ = number of people in group $g$, for $g = 1,\ldots,G$

Decision variables:

• $x_{ng}$ = 1 if someone from group $g$ uses bed $n$, 0 otherwise, for $g=1,\ldots,G, n = 1,\ldots,N$
• $y^-_g$, $y^+_g$ = min, max bed number used by group $g$, for $g = 1,\ldots,G$

Formulation:

$$\begin{align} \text{minimize} \quad & \sum_{g=1}^G (y^+_g - y^-_g + 1 - m_g) \\ \text{subject to} \quad & \sum_{n=1}^N x_{ng} = m_g \quad \forall g=1,\ldots,G \\ & \sum_{g=1}^G x_{ng} \le 1 \quad \forall n = 1,\ldots, N \\ & y_g^- \le nx_{ng} \le y^+_g \quad \forall g=1,\ldots,G, n = 1,\ldots,N \\ & x_{ng} \in \{0,1\} \quad \forall g=1,\ldots,G, n = 1,\ldots,N \\ & y^+_g, y^-_g \ge 0 \quad \forall g=1,\ldots,G \end{align}$$

The objective function minimizes the number of "extra" beds between the first and last bed used by a group. The total size of the "range" used by the group is $y^+_g - y^-_g+1$, and we want this to be as close as possible to $m_g$. For example, if the group has 5 people and uses beds 3, 4, 5, 6, 7, then the group is consecutive, and we have $y_g^- = 3$, $y_g^+=7$, so $y_g^+ - y_g^- + 1 - m_g = 0$, whereas if the group uses beds 3, 4, 5, 8, 9, then the objective function "score" is 2, because there are two skipped beds.

Note that the objective function penalty is the same if 1 group skips 2 beds as it is if 2 groups each skip 1 bed. Therefore, it's not really minimizing the number of splits, but the number of skips.

The first constraint says that each group $g$ must be assigned to exactly $m_g$ beds. The second constraint says that each bed can have at most one group assigned to it. The next constraint says that $y^-_g$ must be no larger than the smallest bed number used for group $g$, and $y^+_g$ must be no smaller than the largest. Because of the sign of the corresponding terms in the objective function, these will always equal the min and max bed indices.

---

Second Model

This model uses the same parameters, and the following additional decision variable:

• $z_{ng}$ = number of "stranger-neighbors" for bed $n$, if someone from group $g$ is assigned to bed $n$ (and 0 otherwise),

where a "stranger-neighbor" is a person from a group $\ne$$g$ who is assigned to bed $n-1$ or $n+1$. For bed $n=1$, "bed 0" counts as a stranger-neighbor, and for bed $n=N$, "bed $N+1$" counts as a stranger-neighbor. To model this, assume there is a dummy group $g=0$, and set $x_{00} = x_{N+1,0} = 1$, i.e., put a person from group 0 in beds 0 and $N+1$.

So, if group $g$ is assigned to a consecutive set of beds, then the total number of stranger-neighbors for the people in group $g$ will be exactly 2; and for each skip in the assignments, the number of stranger-neighbors will increase by 2. In other words, the number of skips is equal to the total number of stranger-neighbors, minus 2, divided by $G$. This is our objective function.

$$\begin{align} \text{minimize} \quad & \frac1G \sum_{g=1}^G \sum_{n=1}^N (z_{ng} - 2) \\ \text{subject to} \quad & \sum_{n=1}^N x_{ng} = m_g \quad \forall g=1,\ldots,G \\ & \sum_{g=1}^G x_{ng} \le 1 \quad \forall n = 1,\ldots, N \\ & x_{00} = x_{N+1,0} = 1 \\ & z_{ng} \ge \sum_{h\in G\setminus\{g\}} (x_{n-1,h} + x_{n+1,h}) - 2 (1 - x_{ng}) \quad \forall g=1,\ldots,G, n = 1,\ldots,N \\ & x_{ng} \in \{0,1\} \quad \forall g=1,\ldots,G, n = 1,\ldots,N \\ & z_{ng} \ge 0 \quad \forall g=1,\ldots,G, n = 1,\ldots, N \end{align}$$

The first two constraints are the same as in the first model. The third constraint assigns the dummy group. The fourth constraint says that if $x_{ng}=1$, then $z_{ng}$ must be at least equal to the number of stranger-neighbors—the number of people of other groups that are assigned to beds $n-1$ and/or $n+1$—(but really it will equal this number, since we want to minimize $z_{ng}$); and if $x_{ng}=0$, then $z_{ng}$ can equal 0.

---

Personally I like the second model a little more—I like counting "splits" rather than "skips". But it has more decision variables. On the other hand, I think you'll be solving small instances ($N=14$, $G\le 14$?) so either formulation should solve plenty quickly.