At MakeMyTrip, we serve a diverse set of hotel shoppers and help them finalize plans given their varied travel purpose, occupancy and information requirements. That being said, the two most important user needs which must be met for all are same — hotel availability and room price as per one’s budget. In this blog post, we share some insights on how we increased the overall hotel availability on our platform and used dynamic programming to solve the problem of finding the ‘cheapest combination of rooms’ to make the offering more powerful and useful to our customers.
Let us first understand why hotel availability and room prices, especially the cheapest one, are so important.
Hotel Availability: It is paramount to show the customer enough hotels to choose from on the hotel listing page. Zero or low availability of hotels results in a lot of customer drops on the listing page itself, leading to a potential business loss.
Room Price: Most of the travelers compare room prices for a hotel across online travel agencies (OTAs) and do a transaction on the OTA offering the cheapest price. Considering a significant number of bookings happen on rooms with cheapest price, it becomes important to show/highlight the cheapest room price on the hotel details page to help customer make a quick decision.
Low Hotel Availability
At MakeMyTrip, we log a lot of data and analyze it regularly to come up with actionable insights. One of our recent findings was low or zero hotel availability on the hotel listing page for a significant number of city searches. There were primarily two reasons for this:
- Less inventory available during peak season/long weekends
- Missing rates in MakeMyTrip inventory system for the requested occupancy (e.g. hotelier has not configured rates for 3 adults)
Let’s take an example to understand this better. Given below is a snapshot of the inventory uploaded by hotelier in our system for hotel ‘X’ (A stands for adult and C for child).
User search 1 (2 Rooms: Room 1–1A, Room 2–1A) — In this case, even though we have 3 (although different types) rooms available, we were returning zero hotel availability as we were matching the search criteria against each room type and none of the room type had inventory count ≥2.
User Search 2 (Room 1- 3A) — In this case too, we were returning zero availability of hotels since the hotelier did not configure rates for the above search criteria.
In both cases, there was a way to fulfill the user search criteria by combining different kind of rooms. The problem becomes much more complex as each hotel has its own child age threshold and corresponding prices.
- Change the search criteria — We stopped matching the exact user search criteria against each room type and started searching with transformed search request. This is especially done for higher occupancy searches were availability is generally low.
- Build the cheapest room combination algorithm — For our customers, the cheapest deal is the best one. To help solve this and the problem of hotel availability, it made sense to build an algorithm to present users with the cheapest combination of room(s).
- Ask hoteliers to configure prices for higher occupancy — Since 60% of the users travel solo or as a couple, hoteliers generally optimize rates and inventory for single and double occupancy. To help customers get better search results for occupancy>2, we asked hoteliers to configure all possible occupancy combinations that they support.
Here is how we thought the overall solution should work.
(1) and (2) are highlighted in green. Depending on the channel the hotel is being consumed from, we may or may not have the required information to run the cheapest room combination algorithm. To handle such cases we have built some additional algorithms to generate/predict the required data (inventory count being one of them).
We implemented both (1) and (2). As expected, the hotel availability grew multifold on our listing page for search requests of more than 2 adults. We also started getting 5% additional room nights everyday. Overall, there was a jump of over 50% in the number of bookings having more than 2 Adults.
Computational challenges and approach
The cheapest room recommendation problem is a combinatorial optimization problem.
Given N hotel rooms and P (adult + child) guests, find the cheapest combination of rooms to accommodate P guests.
To run any optimization algorithm, we needed to get data attributes required to:
- Generate all possible occupancies for a room
- Calculate price for such cases
For this, we started consuming hotel and room level attributes such as child age threshold, maximum adults/children allowed in a room, availability count of each type of room, extra adult price etc. Each hotelier can independently configure its tariff details like, occupancies till which he won’t charge extra (base occupancy), to which child age he will consider guest as child, extra child price, extra adult price, max adults/children that can be accomodated in each room. All these need to be taken care while generating and calculating price of each room and occupancy. Handling these attributes increased the computationally complexity multifold. Additional challenge was to keep search api latencies intact. These computations are to be done real time and for request containing 200–250 hotels.
While we always had dynamic programming in mind to solve this problem, we did consider the brute force solution and a few greedy approaches to see if they sufficed/worked for our use cases.
Brute Force Solution: This involved creating every possible combination for the given inventory with all tariff plans. These rooms would then need to be clubbed with different occupancy combinations as well. This resulted in exponential time complexity.
This was feasible but not scalable. Also it will add significant latency of search api.
Greedy Approaches: We explored a few strategies but found a counter case in each of them. The basic problem was that we don’t have rooms sorted in order of price and pax (guest) occupancy. Moreover, any superior room/suite can accommodate more people compared with a standard room.
The Cheapest Room Combination Algorithm
Let us understand a few terms and notations before we jump to the algorithm.
We modeled the problem of finding the cheapest combination of rooms around the very famous 0–1 knapsack problem . The items (N) and weights (W) in the knapsack problem loosely map to the set of physical rooms in the hotel and different possible occupancy combinations (starting from 0 and leading up to the requested occupancy). There were, however, some unique constraints in our case which required special handling .
- Sub-items/Virtual rooms: Each item is unique in the 0–1 knapsack problem but that’s not true in our case. A physical room (item) needs to be considered with all possible occupancies and tariffs to ensure uniqueness in the set of items. This results in creation of virtual rooms for each physical room. The N in the 0–1 knapsack problem actually maps to the set of virtual rooms in our case.
- Ensuring physical room is used once : This is a direct implication of (1). While we use virtual rooms for all calculations and decisions in the algorithm, it needs to be ensured that a physical room is used only once for each combination of rooms and need to find best alternate in case of any conflict.
- Edge cases while filling the remaining occupancy: We had to handle a few edge cases while referring to the sub-problems which had been solved already. e.g. a lot of hotels don’t allow bookings with room having only children. We also need to handle cases where we have fulfilled the adult occupancy through a virtual room and only child occupancy is left.
Key Steps to Build the Algorithm
- Get result of transformed search request.
- Create a 2-dimensional matrix T with all possible room occupancies as columns (W) and virtual rooms as rows (N).
- At each cell of the 2-dimensional matrix, we consider two possibilities — to select the corresponding virtual room as part of the optimal solution or to discard it. We compute the cost associated with and without that virtual room and choose the cheapest. Each matrix cell stores the key attributes of rooms which are used to fulfil the occupancy of that cell.
The matrix is filled in a bottom-up fashion using the below recurrence relation:
4. Return the result after traversing the matrix.
For the above input parameters, the following 2-dimensional matrix will be created. The column in orange captures the price corresponding to each virtual room as per the configurations done by hotelier.
Cells highlighted in green show the cheapest combination of rooms for the specified search criteria. Room identifiers mentioned in the cell describe which rooms are to be considered and their subscripts define the occupancy of each room. Cells highlighted in blue are the ones used to compute the green cell recursively (using the recurrence relation mentioned above).
This algorithm worked pretty well in production without impacting 99th percentile latency of our search API. Even after caching these recommendation results, we are still processing around 15K unique hotel combinations every minute.