Algoritma Ketersediaan Hotel dan Cadangan Bilik @ MMT

Di MakeMyTrip, kami melayani pelbagai jenis pembeli hotel dan membantu mereka menyelesaikan rancangan memandangkan keperluan perjalanan, penghunian dan keperluan maklumat yang berbeza-beza. Oleh itu, dua keperluan pengguna terpenting yang mesti dipenuhi untuk semua adalah sama - ketersediaan hotel dan harga bilik mengikut anggaran seseorang. Dalam catatan blog ini, kami berkongsi beberapa pandangan tentang bagaimana kami meningkatkan keseluruhan ketersediaan hotel di platform kami dan menggunakan pengaturcaraan dinamik untuk menyelesaikan masalah mencari 'kombinasi bilik termurah' untuk menjadikan penawaran lebih hebat dan bermanfaat bagi pelanggan kami.

Mari kita fahami terlebih dahulu mengapa ketersediaan hotel dan harga bilik, terutama yang paling murah, sangat penting.

Ketersediaan Hotel: Adalah sangat penting untuk menunjukkan cukup banyak pilihan kepada pelanggan di halaman senarai hotel. Ketersediaan hotel yang sifar atau rendah menyebabkan banyak pelanggan jatuh pada halaman penyenaraian itu sendiri, yang menyebabkan potensi kerugian perniagaan.

Harga Bilik: Sebilangan besar pelancong membandingkan harga kamar untuk hotel di seluruh agensi pelancongan dalam talian (OTA) dan melakukan transaksi di OTA dengan menawarkan harga termurah. Memandangkan sebilangan besar tempahan berlaku di bilik dengan harga termurah, menjadi penting untuk menunjukkan / menonjolkan harga bilik termurah di halaman butiran hotel untuk membantu pelanggan membuat keputusan cepat.

Ketersediaan Hotel Rendah

Penemuan Masalah

Di MakeMyTrip, kami mencatat banyak data dan menganalisisnya secara berkala untuk mendapatkan pandangan yang boleh ditindaklanjuti. Salah satu penemuan terbaru kami adalah ketersediaan hotel yang rendah atau sifar di halaman senarai hotel untuk sejumlah besar carian bandar. Terdapat dua sebab utama:

  • Kurang persediaan yang terdapat pada musim puncak / hujung minggu yang panjang
  • Hilang kadar dalam sistem inventori MakeMyTrip untuk penghunian yang diminta (mis. Hotel tidak menetapkan harga untuk 3 orang dewasa)

Mari kita ambil contoh untuk memahami perkara ini dengan lebih baik. Diberikan di bawah adalah gambar inventori yang dimuat naik oleh pengusaha hotel dalam sistem kami untuk hotel 'X' (A bermaksud dewasa dan C untuk kanak-kanak).

Rajah (1): Gambaran inventori

Carian pengguna 1 (2 Bilik: Bilik 1–1A, Kamar 2-1A) - Dalam kes ini, walaupun kami memiliki 3 (walaupun berlainan jenis) bilik, kami mengembalikan ketersediaan hotel sifar kerana kami memenuhi kriteria carian dengan masing-masing jenis bilik dan tidak ada jenis bilik yang mempunyai jumlah inventori ≥2.

Carian Pengguna 2 (Ruangan 1- 3A) - Dalam kes ini juga, kami mengembalikan ketersediaan hotel yang sifar kerana pengusaha hotel tidak mengatur harga untuk kriteria carian di atas.

Dalam kedua kes tersebut, ada cara untuk memenuhi kriteria pencarian pengguna dengan menggabungkan berbagai jenis ruangan. Masalahnya menjadi lebih rumit kerana setiap hotel mempunyai ambang usia anak sendiri dan harga yang sesuai.

Penyelesaian tiga mata

  1. Ubah kriteria carian - Kami berhenti mencocokkan kriteria carian pengguna yang tepat dengan setiap jenis bilik dan mula mencari dengan permintaan carian yang diubah. Ini terutama dilakukan untuk pencarian penghunian yang lebih tinggi jika ketersediaannya pada umumnya rendah.
  2. Bina algoritma gabungan bilik termurah - Bagi pelanggan kami, tawaran termurah adalah yang terbaik. Untuk membantu menyelesaikan ini dan masalah ketersediaan hotel, masuk akal untuk membina algoritma untuk mempersembahkan pengguna dengan kombinasi bilik paling murah.
  3. Minta pengusaha hotel untuk mengkonfigurasi harga untuk penghunian yang lebih tinggi - Oleh kerana 60% pengguna melakukan perjalanan solo atau sebagai pasangan, pengusaha hotel umumnya mengoptimumkan harga dan inventori untuk penghunian single dan double. Untuk membantu pelanggan mendapatkan hasil carian yang lebih baik untuk penghunian> 2, kami meminta pengusaha hotel untuk mengkonfigurasi semua kemungkinan kombinasi penghunian yang mereka sokong.

Inilah cara kami berpendapat bahawa penyelesaian keseluruhan harus berfungsi.

Rajah (2): Diagram Alir

(1) dan (2) diserlahkan dengan warna hijau. Bergantung pada saluran yang digunakan oleh hotel, kami mungkin atau mungkin tidak mempunyai maklumat yang diperlukan untuk menjalankan algoritma kombinasi bilik termurah. Untuk menangani kes seperti itu, kami telah membina beberapa algoritma tambahan untuk menghasilkan / meramalkan data yang diperlukan (jumlah inventori adalah salah satunya).

Kesan Perniagaan

Kami melaksanakan kedua (1) dan (2). Seperti yang dijangkakan, ketersediaan hotel bertambah banyak di halaman penyenaraian kami untuk permintaan carian lebih dari 2 orang dewasa. Kami juga mula mendapat 5% malam bilik tambahan setiap hari. Secara keseluruhan, terdapat peningkatan lebih dari 50% dalam jumlah tempahan yang mempunyai lebih dari 2 Dewasa.

Gambar (3): Trend tempahan sebelum dan selepas pelepasan ciri

Cabaran dan pendekatan komputasi

Masalah cadangan bilik yang paling murah adalah masalah pengoptimuman gabungan.

Memandangkan bilik hotel N dan tetamu P (dewasa + kanak-kanak), cari kombinasi bilik termurah untuk menampung tetamu P.

Untuk menjalankan algoritma pengoptimuman, kami perlu mendapatkan atribut data yang diperlukan untuk:

  • Jana semua kemungkinan pekerjaan untuk sebuah bilik
  • Kira harga untuk kes seperti itu

Untuk ini, kami mula menggunakan atribut tingkat hotel dan bilik seperti ambang usia kanak-kanak, dewasa / kanak-kanak maksimum yang dibenarkan di dalam bilik, jumlah ketersediaan setiap jenis bilik, harga dewasa tambahan dan lain-lain. Setiap pengusaha hotel boleh secara sendiri mengkonfigurasi butiran tarifnya seperti, penghunian sehingga dia tidak akan mengenakan bayaran tambahan (hunian dasar), yang mana dia akan menganggap tetamu sebagai anak, usia kanak-kanak tambahan, harga dewasa tambahan, dewasa / kanak-kanak maksimum yang dapat ditampung di setiap bilik. Semua ini perlu dijaga semasa menjana dan mengira harga setiap bilik dan penghunian. Mengendalikan atribut ini meningkatkan kerumitan komputasi yang berlipat ganda. Cabaran tambahan adalah mengekalkan latensi api carian. Pengiraan ini dilakukan secara real time dan untuk permintaan yang mengandungi 200-250 hotel.

Walaupun kami selalu memikirkan pemrograman dinamis untuk menyelesaikan masalah ini, kami mempertimbangkan penyelesaian brute force dan beberapa pendekatan tamak untuk melihat apakah mereka mencukupi / berfungsi untuk kes penggunaan kami.

Penyelesaian Brute Force: Ini melibatkan mewujudkan setiap kemungkinan kombinasi untuk inventori yang diberikan dengan semua rancangan tarif. Bilik-bilik ini kemudiannya perlu dipadankan dengan kombinasi penghunian yang berbeza juga. Ini mengakibatkan kerumitan masa eksponensial.

Gambar (4): Pendekatan kekuatan kasar menghasilkan kerumitan masa eksponensial

Ini dapat dilaksanakan tetapi tidak boleh ditingkatkan. Ia juga akan menambahkan latensi api carian yang ketara.

Pendekatan tamak: Kami meneroka beberapa strategi tetapi menemui satu kes balas di masing-masing. Masalah asasnya ialah kita tidak mempunyai bilik yang disusun mengikut harga dan penghunian orang (tetamu). Selain itu, mana-mana bilik / suite yang unggul dapat menampung lebih banyak orang dibandingkan dengan bilik standard.

Algoritma Gabungan Bilik Termurah

Mari kita memahami beberapa istilah dan notasi sebelum kita beralih ke algoritma.

Rajah (5): Terminologi untuk Algoritma Gabungan Bilik Termurah

Kami memodelkan masalah mencari kombinasi bilik paling murah di sekitar masalah ransel 0-1 yang sangat terkenal. Item (N) dan berat (W) dalam masalah ransel secara longgar memetakan ke set bilik fizikal di hotel dan kemungkinan kombinasi penghunian yang berbeza (bermula dari 0 dan menuju ke penghunian yang diminta). Walau bagaimanapun, terdapat beberapa kekangan unik dalam kes kami yang memerlukan pengendalian khas.

  1. Sub-item / Bilik maya: Setiap item unik dalam masalah ransel 0-1 tetapi itu tidak benar dalam kes kami. Bilik fizikal (item) perlu dipertimbangkan dengan segala kemungkinan pekerjaan dan tarif untuk memastikan keunikan dalam set barang. Ini menghasilkan penciptaan bilik maya untuk setiap bilik fizikal. N dalam masalah ransel 0-1 sebenarnya memetakan ke set bilik maya dalam kes kami.
  2. Memastikan bilik fizikal digunakan sekali: Ini adalah implikasi langsung dari (1). Walaupun kami menggunakan bilik maya untuk semua pengiraan dan keputusan dalam algoritma, ia perlu dipastikan bahawa bilik fizikal hanya digunakan sekali untuk setiap kombinasi bilik dan perlu mencari alternatif terbaik sekiranya terdapat konflik.
  3. Kes tepi semasa mengisi penghunian yang tinggal: Kami terpaksa menangani beberapa kes tepi sambil merujuk kepada sub-masalah yang telah diselesaikan. contohnya banyak hotel tidak membenarkan tempahan dengan bilik yang hanya mempunyai anak. Kita juga perlu menangani kes-kes di mana kita telah memenuhi penghunian orang dewasa melalui bilik maya dan hanya tinggal anak yang tinggal.

Langkah Utama Membina Algoritma

  1. Dapatkan hasil permintaan carian yang diubah.
  2. Buat matriks 2 dimensi T dengan semua kemungkinan ruang hunian sebagai lajur (W) dan bilik maya sebagai baris (N).
  3. Pada setiap sel matriks 2 dimensi, kami mempertimbangkan dua kemungkinan - untuk memilih ruang maya yang sesuai sebagai sebahagian daripada penyelesaian yang optimum atau membuangnya. Kami mengira kos yang berkaitan dengan dan tanpa ruang maya itu dan memilih yang paling murah. Setiap sel matriks menyimpan atribut utama bilik yang digunakan untuk memenuhi penghunian sel tersebut.

Matriks diisi dengan cara bawah-atas menggunakan hubungan berulang di bawah:

Rajah (6): Formula Pengiraan

4. Kembalikan hasilnya setelah melintasi matriks.

Contoh:

Gambar (7): Maklumat tahap harga / tarif

Untuk parameter input di atas, matriks 2 dimensi berikut akan dibuat. Lajur dalam warna oren menangkap harga yang sesuai dengan setiap ruangan maya mengikut konfigurasi yang dilakukan oleh pengusaha hotel.

Rajah (8): Matriks 2D menunjukkan entri untuk 3 Dewasa dan 2 Kanak-kanak. Null Entri telah ditandakan sebagai 'X'.

Sel yang diserlahkan dengan warna hijau menunjukkan kombinasi bilik termurah untuk kriteria carian yang ditentukan. Pengecam ruangan yang disebut dalam sel menerangkan bilik mana yang harus dipertimbangkan dan langganan mereka menentukan penghunian setiap bilik. Sel yang diserlahkan dengan warna biru adalah sel yang digunakan untuk mengira sel hijau secara berulang (menggunakan hubungan berulang yang disebutkan di atas).

Algoritma ini berfungsi dengan baik dalam pengeluaran tanpa mempengaruhi latensi persentil ke-99 API carian kami. Walaupun setelah mencapai hasil cadangan ini, kami masih memproses sekitar 15K kombinasi hotel unik setiap minit.

Terima kasih khas kepada Ajay Singh dan Abhijeet Sharad kerana telah membantu menyusun blog ini.