Algoritem razpoložljivosti in priporočilo sob @ MMT

V MakeMyTrip ponujamo raznolik nabor hotelskih nakupovalcev in jim pomagamo dokončno oblikovati načrte glede na njihov raznolik namen potovanja, zasedenost in zahteve po informacijah. Ob tem najpomembnejše potrebe uporabnikov, ki jih moramo izpolniti za vse, sta enaki - razpoložljivost hotela in cena sobe glede na proračun. V tem postu objavljamo nekaj vpogleda v to, kako smo povečali splošno razpoložljivost hotela na naši platformi in uporabili dinamično programiranje, da bi rešili težavo iskanja "najcenejše kombinacije sob", da bi ponudba postala močnejša in uporabnejša za naše stranke.

Najprej razumemo, zakaj so razpoložljivost hotela in cene sob, še posebej najcenejša, tako pomembni.

Razpoložljivost hotela: Najpomembnejše je, da se na strani s seznami hotelov pokaže dovolj izbire hotelov. Ničelna ali nizka razpoložljivost hotelov povzroči veliko število kupcev na samem seznamu, kar vodi do morebitne poslovne izgube.

Cena sobe: Večina potnikov primerja cene sob v hotelu po spletnih turističnih agencijah (OTA) in opravijo transakcijo na OTA, ki ponuja najnižjo ceno. Glede na to, da se veliko število rezervacij zgodi v sobah z najcenejšo ceno, je pomembno, da na strani s podrobnostmi o hotelu pokažete / izpostavite najcenejšo ceno sobe, s čimer se stranka lahko hitro odloči.

Nizka razpoložljivost hotela

Odkrivanje težav

V MakeMyTrip beležimo veliko podatkov in jih redno analiziramo, da bi prišli do uporabnih vpogledov. Ena naših nedavnih ugotovitev je bila nizka ali ničelna razpoložljivost hotela na strani s seznami hotelov za veliko število mestnih iskanj. Razloga sta bila predvsem dva:

  • Manj zalog je na voljo v vrhuncu sezone / dolgih vikendih
  • Manjkajoče cene v sistemu inventarja MakeMyTrip za zahtevano zasedenost (npr. Hotelier ni konfiguriral cen za 3 odrasle osebe)

Vzemimo primer, da to bolje razumemo. Spodaj je posnetek inventarja, ki ga je hotelier naložil v naš sistem za hotel 'X' (A stoji za odrasle in C za otroka).

Slika (1): posnetek posnetka

Iskanje uporabnikov 1 (2 sobi: soba 1–1A, soba 2–1A) - V tem primeru, čeprav imamo na voljo 3 (čeprav različne vrste) sob, smo vrnili nič hotelskih razpoložljivosti, saj smo primerjali iskalne kriterije glede na vsako tip sobe in nobena od sob ni imela števila zalog ≥2.

Uporabniško iskanje 2 (Soba 1- 3A) - Tudi v tem primeru smo vračali nič razpoložljivosti hotelov, saj hotelir ni nastavil cen za zgornja iskalna merila.

V obeh primerih je bilo mogoče izpolniti merila za iskanje uporabnikov s kombiniranjem različnih vrst prostorov. Težava postane veliko bolj zapletena, saj ima vsak hotel svoj prag starosti otrok in ustrezne cene.

Rešitev v treh točkah

  1. Spremenite iskalne kriterije - Prenehali smo ujemati natančne kriterije iskanja uporabnikov glede na vsako vrsto sobe in začeli smo iskati s preoblikovano iskalno zahtevo. To še posebej velja za iskanja z večjo zasedenostjo, če je razpoložljivost na splošno nizka.
  2. Sestavite algoritem kombiniranja najcenejših sob - Za naše stranke je najcenejša ponudba najboljša. Za rešitev tega in težave glede razpoložljivosti hotela je bilo smiselno sestaviti algoritem, ki uporabnikom predstavi najcenejšo kombinacijo sob.
  3. Prosite hotelirje, da konfigurirajo cene za večjo zasedenost - Ker 60% uporabnikov potuje samostojno ali kot par, hotelirji na splošno optimizirajo cene in zaloge za eno in dvojno zasedenost. Da bi strankam pomagali doseči boljše rezultate iskanja glede zasedenosti> 2, smo hotelirje prosili, da konfigurirajo vse možne kombinacije zasedenosti, ki jih podpirajo.

Takole smo mislili, da mora celostna rešitev delovati.

Slika (2): Diagram pretoka

(1) in (2) sta označena z zeleno. Glede na kanal, iz katerega je hotel porabljen, lahko imamo ali ne bomo imeli potrebnih informacij za zagon najcenejšega algoritma kombinacije sob. Za obravnavo takšnih primerov smo zgradili nekaj dodatnih algoritmov za generiranje / napovedovanje potrebnih podatkov (število zalog je eden od njih).

Poslovni učinek

Izvedli smo oba (1) in (2). Kot smo pričakovali, se je razpoložljivost hotela na naši strani s seznami večkrat povečala za iskalne zahteve več kot 2 odraslih. Začeli smo tudi dobiti 5% dodatne noči vsak dan. Na splošno je prišlo do več kot 50-odstotnega skoka števila rezervacij z več kot dvema odraslima osebama.

Slika (3): Trend rezervacij pred in po izdaji funkcije

Računalniški izzivi in ​​pristop

Težava s priporočilom glede najcenejših sob je težava kombinatorne optimizacije.

Glede na N hotelskih sob in P (odrasli + otrok) gostov poiščite najcenejšo kombinacijo sob za namestitev gostov P.

Za zagon katerega koli algoritma za optimizacijo smo morali pridobiti atribute podatkov, ki so potrebni za:

  • Ustvarite vse možne prostore za sobo
  • Izračunajte ceno za takšne primere

Za to smo začeli uporabljati atribute hotela in sobe, kot so starost za otroke, največje dovoljeno število odraslih / otrok v sobi, število razpoložljivosti posameznih vrst sobe, cena za odrasle itd. Vsak hotelir lahko samostojno nastavi svoje tarifne podrobnosti, kot so do katere ne bo doplačal (osnovna zasedenost), do katere starosti otrok bo gosta smatral za otroka, ceno dodatnega otroka, ceno odraslih, največ odraslih / otrok, ki jih lahko sprejme v vsaki sobi. Vse to je treba paziti pri ustvarjanju in izračunu cene vsake sobe in nastanitve. Ravnanje s temi atributi je večkrat povečalo računsko zapletenost. Dodatni izziv je bil ohraniti nedotaknjene zamude pri iskanju. Te izračune je treba opraviti v realnem času in na zahtevo vsebovati 200–250 hotelov.

Čeprav smo vedno imeli v mislih dinamično programiranje, da bi rešili to težavo, smo razmislili o grobi sili in nekaj požrešnih pristopov, da bi videli, ali zadostujejo / delajo za naše primere uporabe.

Brute Force Rešitev: To je vključevalo ustvarjanje vseh možnih kombinacij za navedeni seznam z vsemi tarifnimi načrti. Te prostore bi nato morali opremiti tudi z različnimi kombinacijami zasedenosti. To je povzročilo eksponentno časovno zapletenost.

Slika (4): Brute force pristop povzroči eksponentno časovno zapletenost

To je bilo izvedljivo, vendar ne nadgradljivo. Prav tako bo dodal veliko zamudo pri iskanju api.

Pohlepni pristopi: Raziskali smo nekaj strategij, a v vsaki od njih smo našli nasprotni primer. Osnovna težava je bila, da nimamo prostorov, razvrščenih po cenah in številu oseb (glede na število gostov). Poleg tega lahko vsaka superior soba / apartma sprejme več ljudi v primerjavi s standardno sobo.

Najcenejši algoritem kombinirane kombinacije

Naj razumemo nekaj izrazov in notacij, preden skočimo na algoritem.

Slika (5): Terminologija za najcenejši algoritem kombinirane kombinacije

Oblikovali smo problem iskanja najcenejše kombinacije prostorov okoli zelo znane težave z 0–1 nahrbtnikom. Izdelki (N) in uteži (W) v nahrbtniku se ohlapno preslikajo v fizične prostore v hotelu in različne možne kombinacije zasedenosti (od 0 in vse do zahtevane zasedenosti). Vendar pa je bilo v našem primeru nekaj edinstvenih omejitev, ki so zahtevale posebno ravnanje.

  1. Podpredmeti / navidezne sobe: Vsak element je edinstven v težavah z 0–1 nahrbtnikom, vendar v našem primeru to ne drži. Fizično sobo (postavko) je treba upoštevati z vsemi možnimi zasedenostmi in tarifami, da se zagotovi edinstvenost v naboru predmetov. Posledica tega je ustvarjanje virtualnih prostorov za vsako fizično sobo. N v težavi z 0–1 nahrbtnikom se v našem primeru dejansko prikaže na navidezne prostore.
  2. Zagotavljanje fizične sobe se uporabi enkrat: To je neposredna posledica (1). Medtem ko virtualne prostore uporabljamo za vse izračune in odločitve v algoritmu, je treba zagotoviti, da se fizična soba uporablja samo enkrat za vsako kombinacijo prostorov in da je treba v primeru konflikta najti najboljše nadomestne prostore.
  3. Primeri robov, medtem ko smo zapolnili preostalo zasedenost: Morali smo obravnavati nekaj robnih primerov, pri čemer smo se nanašali na že odpravljene podprobleme. npr. veliko hotelov ne dovoljuje rezervacij s sobami samo otrok. Obravnavati moramo tudi primere, v katerih smo zasedenost odraslih izpolnili skozi virtualno sobo in je ostala samo otroška zasedenost.

Ključni koraki za izgradnjo algoritma

  1. Pridobite rezultat preoblikovane zahteve za iskanje.
  2. Ustvarite dvodimenzionalno matrico T z vsemi možnimi zasedenji sob kot stolpci (W) in virtualne sobe kot vrstice (N).
  3. Na vsaki celici dvodimenzionalne matrice upoštevamo dve možnosti - izbrati ustrezno virtualno sobo kot del optimalne rešitve ali jo zavreči. Izračunamo stroške, povezane z in brez te virtualne sobe, in izberemo najcenejšo. Vsaka matrična celica hrani ključne atribute prostorov, ki se uporabljajo za izpolnjevanje zasedenosti te celice.

Matrica se polni od spodaj navzgor z uporabo spodnjega razmerja ponovitve:

Slika (6): Računalniška formula

4. Po prečkanju matrice vrnite rezultat.

Primer:

Slika (7): Podrobnosti o sobi / tarifi

Za zgornje vhodne parametre bo izdelana naslednja dvodimenzionalna matrica. Oranžni stolpec zajame ceno, ki ustreza vsaki virtualni sobi glede na konfiguracije, ki jih je opravil hotelir.

Slika (8): 2D matrica, ki prikazuje vnose za 3 odrasle in 2 otroka. Ničelni vnosi so označeni kot „X“.

Celice, označene z zeleno, prikazujejo najcenejšo kombinacijo sob za določene iskalne kriterije. Identifikatorji prostorov, omenjeni v celici, opisujejo, katere sobe naj se upoštevajo, njihovi naročniki pa določajo zasedenost vsake sobe. Celice, označene z modro barvo, so tiste, ki se uporabljajo za računanje zelene celice rekurzivno (z uporabo zgoraj omenjene relacijske relacije).

Ta algoritem je v proizvodnji dobro deloval, ne da bi vplival na 99-odstotno latenco našega iskalnega API-ja. Tudi po predpomnjenju teh priporočilnih rezultatov še vedno obdelujemo približno 15 K edinstvenih hotelskih kombinacij vsako minuto.

Posebna zahvala Ajay Singh in Abhijeet Sharad za pomoč pri oblikovanju tega bloga.