Application of Min Cost Flow to hostel bookings

Question

A hostel made a mistake concerning their bookings for 2017 and took many reservations without checking for free rooms in these periods. Every reservations is made for exactly one room and one period of time. All rooms are equal but were sold for different prices. The hostel now wants to cancel some bookings so everybody will have a room but at the same time the hostel wants to minimize its lost earnings. How would you solve the problem? Is it possible that no guest needs to change rooms during his stay?

I want to model the situation as a MinimumCostFlow-Problem. Where each vertex represents a day. We also add vertices s and t as the source and sink. Edges between the verticees representing days should have infinite capacity and zero costs.

But I am still unfamiliar with the MinCostFlow-Problem and thus unsure how I need to set the flow constraints and other elements and appreciate any help.

Answer 1

Create the following interval graph $G=(V,E)$:

• $V$ is the set of vertices, each reservation has a start node $v_1$ and end node $v_2$;
• $E$ is the set of arcs, there is one between each start and end node of a reservation with a unitary capacity, and one between nodes $u_2$ and $v_1$ if and only if reservation $u$ ends before reservation $v$ (if $time(u_2)\le time(v_1)$);
• Add a source node $s$ linked to all start nodes and sink node $t$ linked to all end nodes.

A path from $s$ to $t$ is a feasible schedule for the hotel: a set of consecutive reservations that can occupy the same room. You want as many of those possible, so a maximum flow will give you as many feasible reservations possible.

We have not considered the fact that reservations have different prices. To do so, add a cost $c_{v_1v_2}$ on each arc $(v_1,v_2)$, the price of the reservation (with a negative sign). You now want a maximum flow at minimum cost (as many reservations possible, at the best price possible).

This will give you schedules where guests remain in the same room. If you allow them to change, decompose the arcs $(v_1,v_2)$ in paths $v_{t_1}-v_{t_2}---v_{t_n}$ with one extra node $v_{t_i}$ per period of time, and add arcs $(u_{t_i},v_{t_j})$ accordingly with a unitary cost (to penalize changes of rooms).

A maximum flow at minimum cost will give you the desired solution.

Answer 2

I am unable to comment on Kuifje's answer, but hopefully the following is interesting.

I agree with the modelling approach taken by Kuifje. In addition, to account for the limited room capacity, a further arc that connects the sink, $t$, to the source, $s$, can be added with a capacity equal to the number of available rooms. This assumes that the rooms are identical. When observing your final answer, paths through the "network" can be extracted manually to give individual room schedules.

Also, it should be sufficient to add a node for each booking instead of creating arcs. The example path from the comment on Kuifje's answer would be $s$ - $u$ - $v$ - $t$, where $u$ can connect to $v$ if the booking $v$ occurs after $u$ finishes. This gives the same result.