Dostupnosť hotela a odporúčanie izieb Algoritmus @ MMT

V spoločnosti MakeMyTrip obsluhujeme rozmanitú skupinu hotelových nakupujúcich a pomáhame im dokončiť plány vzhľadom na ich rôznorodé cestovné účely, obsadenosť a požiadavky na informácie. Ako už bolo povedané, dve najdôležitejšie potreby používateľov, ktoré musia byť uspokojené pre všetkých, sú rovnaké - dostupnosť hotela a cena izby podľa jedného rozpočtu. V tomto blogovom príspevku zdieľame niektoré informácie o tom, ako sme zvýšili celkovú dostupnosť hotela na našej platforme a pomocou dynamického programovania vyriešili problém s nájdením „najlacnejšej kombinácie miestností“, aby bola ponuka pre našich zákazníkov výkonnejšia a užitočnejšia.

Najprv pochopme, prečo sú tak dôležité dostupnosť hotelov a ceny izieb, najmä najlacnejšie.

Dostupnosť hotela: Je nevyhnutné ukázať zákazníkovi na stránke so zoznamom hotelov dostatok hotelov, z ktorých si môže vybrať. Nulová alebo nízka dostupnosť hotelov vedie k veľkému poklesu počtu zákazníkov na samotnej stránke so zoznamom, čo vedie k potenciálnej obchodnej strate.

Cena za izbu: Väčšina cestujúcich porovnáva ceny izieb v hoteloch prostredníctvom online cestovných kancelárií (OTA) a vykonáva transakciu s OTA, ktorá ponúka najlacnejšiu cenu. Vzhľadom na to, že v izbách s najnižšou cenou sa uskutoční značný počet rezervácií, je dôležité ukázať / zvýrazniť najlacnejšiu cenu izieb na stránke s podrobnosťami o hoteli, aby sa zákazníci mohli rýchlo rozhodnúť.

Nízka dostupnosť hotela

Zisťovanie problémov

V spoločnosti MakeMyTrip zaznamenávame veľké množstvo údajov a pravidelne ich analyzujeme, aby sme získali prehľadné informácie. Jedným z našich nedávnych zistení bola nízka alebo nulová dostupnosť hotela na stránke so zoznamom hotelov pre významný počet vyhľadávaní v meste. Dôvodom boli predovšetkým dva dôvody:

  • Počas sezóny / dlhých víkendov je k dispozícii menej inventára
  • Chýbajúce sadzby v inventárnom systéme MakeMyTrip pre požadovanú obsadenosť (napr. Hoteliér nenakonfiguroval sadzby pre 3 dospelých)

Urobme príklad, aby sme to lepšie pochopili. Nižšie je uvedený prehľad inventára nahraného hotelierom v našom systéme pre hotel X (A znamená pre dospelých a C pre dieťa).

Obr. 1: Snímka zásob

Vyhľadávanie používateľov 1 (2 izby: Izba 1–1A, Izba 2–1A) - Aj keď máme k dispozícii 3 izby (aj keď rôzne typy), vrátili sme nulovú dostupnosť hotela, pretože sme porovnávali kritériá vyhľadávania podľa každého typ izby a žiadny z izieb nemal počet zásob ≥2.

Vyhľadávanie používateľov 2 (Izba 1- 3A) - Aj v tomto prípade sme vracali nulovú dostupnosť hotelov, pretože hoteliér nenakonfiguroval sadzby pre vyššie uvedené kritériá vyhľadávania.

V obidvoch prípadoch existoval spôsob, ako splniť kritériá vyhľadávania používateľov kombináciou rôznych druhov miestností. Tento problém sa stáva oveľa komplexnejším, pretože každý hotel má svoj vlastný vek pre deti a príslušné ceny.

Trojbodové riešenie

  1. Zmena kritérií vyhľadávania - Zastavili sme porovnávanie presných kritérií vyhľadávania používateľov s každým typom miestnosti a začali sme hľadať pomocou transformovanej požiadavky vyhľadávania. Toto sa deje najmä v prípade vyhľadávaní s vyššou obsadenosťou, keď je ich dostupnosť všeobecne nízka.
  2. Zostavte najlacnejší algoritmus kombinácie izieb - pre našich zákazníkov je najlacnejšia ponuka najlepšia. Aby sa toto vyriešilo a problém dostupnosti hotela, malo zmysel zostaviť algoritmus, ktorý používateľom ponúkne najlacnejšiu kombináciu izieb.
  3. Požiadajte hoteliérov, aby nakonfigurovali ceny pre vyššiu obsadenosť - Keďže 60% používateľov cestuje samostatne alebo ako pár, hoteléri vo všeobecnosti optimalizujú ceny a inventár pre jednu a dvojnásobnú obsadenosť. S cieľom pomôcť zákazníkom získať lepšie výsledky vyhľadávania obsadenosti> 2 sme požiadali hoteliérov, aby nakonfigurovali všetky možné kombinácie obsadenia, ktoré podporujú.

Takto sme si mysleli, že celkové riešenie by malo fungovať.

Obr. 2: Vývojový diagram

(1) a (2) sú zvýraznené zelenou farbou. V závislosti od kanála, z ktorého sa hotel konzumuje, môžeme alebo nemusíme mať požadované informácie na spustenie najlacnejšieho algoritmu kombinácie miestností. Na riešenie takýchto prípadov sme vytvorili niekoľko ďalších algoritmov na generovanie / predpovedanie požadovaných údajov (jedným z nich je aj inventarizácia).

Dopad na podnikanie

Implementovali sme (1) aj (2). Ako sa dalo očakávať, dostupnosť hotela sa na našej stránke s výpisom zvýšila mnohonásobne, keď žiadala o hľadanie viac ako 2 dospelí. Každý deň sme tiež začali dostávať 5% dodatočných izieb. Celkovo došlo k skoku o viac ako 50% v počte rezervácií s viac ako 2 dospelými.

Obr. 3: Trend rezervácie pred a po uvoľnení funkcie

Výpočtové výzvy a prístup

Najlacnejším problémom s odporúčaním miestnosti je problém kombinatorickej optimalizácie.

Vzhľadom na N hotelových izieb a hostí P (dospelých + deti) nájdite najlacnejšiu kombináciu izieb na ubytovanie hostí P.

Aby sme mohli spustiť akýkoľvek optimalizačný algoritmus, potrebovali sme získať dátové atribúty potrebné na:

  • Vygenerujte všetky možné obsadenie miestnosti
  • Vypočítajte cenu pre tieto prípady

Za týmto účelom sme začali konzumovať atribúty na úrovni hotelov a izieb, ako sú napríklad veková hranica pre deti, maximálny počet dospelých / detí povolených v izbe, počet voľných izieb v každom type izby, cena pre dospelých navyše atď. do ktorého nebude účtovať príplatok (základné obsadenie), do ktorého detského veku bude považovať hosťa za dieťa, cenu za dieťa navyše, cenu pre dospelých, maximálne pre dospelých / deti, ktoré môžu byť ubytované v každej izbe. Pri generovaní a výpočte ceny každej miestnosti a obsadenosti je potrebné sa o tieto postarať. Zaobchádzanie s týmito atribútmi mnohonásobne zvýšilo výpočtovú zložitosť. Ďalšou výzvou bolo udržať nedotknuteľnosť vyhľadávacích schopností. Tieto výpočty sa uskutočňujú v reálnom čase a na požiadanie, ktoré obsahujú 200 - 250 hotelov.

Aj keď sme vždy mysleli na dynamické programovanie, aby sme tento problém vyriešili, zvážili sme riešenie hrubou silou a niekoľko chamtivých prístupov, aby sme zistili, či pre naše prípady použitia stačili / pracovali.

Brute Force Solution: Toto zahŕňalo vytvorenie každej možnej kombinácie pre daný inventár so všetkými tarifnými plánmi. Tieto miestnosti by potom museli byť spojené aj s rôznymi kombináciami obsadenia. To malo za následok exponenciálnu časovú zložitosť.

Obr. 4: Priblíženie hrubou silou má za následok exponenciálnu časovú zložitosť

Bolo to uskutočniteľné, ale nie škálovateľné. Pridá tiež výraznú latenciu vyhľadávacích api.

Greedy prístupy: Preskúmali sme niekoľko stratégií, ale v každej z nich sme našli opačný prípad. Základným problémom bolo, že nemáme izby usporiadané podľa ceny a obsadenosti (hosťa). Okrem toho môže akákoľvek nadštandardná izba / apartmán pojať viac ľudí v porovnaní so štandardnou izbou.

Najlacnejší algoritmus kombinácie izieb

Predtým, ako prejdeme k algoritmu, pochopme niekoľko pojmov a zápisov.

Obr. 5: Terminológia pre najlacnejší algoritmus kombinovania miestností

Modelovali sme problém nájdenia najlacnejšej kombinácie miestností okolo veľmi známeho problému batohu 0–1. Položky (N) a hmotnosti (W) v probléme batohu voľne mapujú súbor fyzických miestností v hoteli a rôzne možné kombinácie obsadenia (od 0 do vedúce k požadovanej obsadenosti). V našom prípade sa však vyskytli určité jedinečné obmedzenia, ktoré si vyžadovali špeciálne zaobchádzanie.

  1. Podpoložky / virtuálne miestnosti: Každá položka je jedinečná v prípade problému s batohom 0–1, v našom prípade to však nie je pravda. Fyzická miestnosť (položka) sa musí posudzovať so všetkými možnými obsadenosťami a tarifami, aby sa zabezpečila jedinečnosť súboru položiek. Výsledkom je vytvorenie virtuálnych miestností pre každú fyzickú miestnosť. Problém N v batohu 0–1 v našom prípade skutočne mapuje na súbor virtuálnych miestností.
  2. Zabezpečenie fyzickej miestnosti sa používa raz: Toto je priamy dôsledok bodu (1). Aj keď využívame virtuálne miestnosti pre všetky výpočty a rozhodnutia v algoritme, je potrebné zabezpečiť, aby sa fyzická miestnosť použila iba raz pre každú kombináciu miestností a aby sa v prípade akéhokoľvek konfliktu našla najlepšia alternatíva.
  3. Prípady na hranách pri obsadzovaní zostávajúcej obsadenosti: Museli sme riešiť niekoľko okrajových prípadov a poukázať na čiastkové problémy, ktoré už boli vyriešené. napr. veľa hotelov nepovoľuje rezervácie s izbami, ktoré majú iba deti. Musíme tiež riešiť prípady, keď sme obsadenie dospelých splnili prostredníctvom virtuálnej miestnosti a zostala iba detská obsadenosť.

Kľúčové kroky na vytvorenie algoritmu

  1. Získajte výsledok transformovanej požiadavky vyhľadávania.
  2. Vytvorte dvojrozmernú maticu T so všetkými možnými obsadenosťami miest ako stĺpce (W) a virtuálne miestnosti ako riadky (N).
  3. V každej bunke dvojrozmernej matice zvažujeme dve možnosti - vybrať zodpovedajúcu virtuálnu miestnosť ako súčasť optimálneho riešenia alebo ju zlikvidovať. Vypočítame náklady spojené s virtuálnou miestnosťou a bez nej a vyberieme najlacnejšie. Každá bunka matice uchováva kľúčové atribúty miestností, ktoré sa používajú na splnenie obsadenosti tejto bunky.

Matica je vyplnená spôsobom zdola nahor pomocou nižšie uvedeného vzťahu:

Obr. 6: Výpočtový vzorec

4. Vráťte výsledok po prejdení maticou.

Príklad:

Obr. 7: Podrobnosti o úrovni izby / tarify

Pre vyššie uvedené vstupné parametre sa vytvorí nasledujúca dvojrozmerná matica. Stĺpec v oranžovej farbe zachytáva cenu zodpovedajúcu každej virtuálnej miestnosti podľa konfigurácií vykonaných hotelierom.

Obr. 8: 2D matica ukazujúca údaje pre 3 dospelých a 2 deti. Nulové položky boli označené ako „X“.

Bunky zvýraznené zelenou farbou ukazujú najlacnejšiu kombináciu izieb pre zadané kritériá vyhľadávania. Identifikátory miestností uvedené v bunke opisujú, ktoré miestnosti sa majú brať do úvahy, a ich predplatné určuje obsadenie každej miestnosti. Bunky zvýraznené modrou farbou sú tie, ktoré sa používajú na výpočet zelených buniek rekurzívne (pomocou vyššie uvedeného vzťahu rekurencie).

Tento algoritmus pracoval veľmi dobre vo výrobe bez toho, aby ovplyvnil latenciu 99. percentilu nášho vyhľadávacieho rozhrania API. Aj po uložení týchto výsledkov odporúčaní do pamäte stále spracovávame každú minútu okolo 15 000 jedinečných kombinácií hotelov.

Osobitné poďakovanie Ajayovi Singhovi a Abhijeetovi Sharadovi za pomoc pri príprave tohto blogu.