Алгоритам расположивости хотела и препорука за собе @ ММТ

У МакеМиТрип-у пружамо услугу разноврсним купцима хотелских купаца и помажемо им да доврше планове с обзиром на разнолику сврху путовања, попуњеност и потребе за информацијама. Како је речено, две најважније потребе корисника које морају бити задовољене за све су исте - доступност хотела и цена собе према сопственом буџету. У овом посту на блогу делимо неке увиде о томе како смо повећали општу доступност хотела на нашој платформи и користили динамично програмирање да решимо проблем проналажења 'најјефтиније комбинације соба' како би понуда била моћнија и кориснија за наше купце.

Хајде да прво разумемо зашто су доступност хотела и цене соба, посебно најјефтинија, толико битне.

Доступност хотела: Најважније је показати купцу довољно хотела за избор на страници с пописом хотела. Нулта или ниска доступност хотела доводи до великог броја падова купаца на самој страници листинга, што доводи до потенцијалног губитка пословања.

Цена собе: Већина путника упоређује цене соба за хотел преко онлајн туристичких агенција (ОТА) и обављају трансакције на ОТА који нуде најјефтинију цену. С обзиром на то да се значајан број резервација одвија у собама са најјефтинијом ценом, важно је приказати / истакнути најјефтинију цену собе на страници детаља о хотелу како би се кориснику помогло да донесе брзу одлуку.

Мала расположивост хотела

Откривање проблема

На МакеМиТрип евидентирамо пуно података и редовно их анализирамо како бисмо дошли до увидљивих увида. Једно од наших недавних сазнања била је ниска или нулта доступност хотела на страници с пописом хотела за значајан број претрага града. Постоје два разлога за то:

  • Мање залиха доступно током шпице сезоне / дугих викенда
  • Недостају стопе у МакеМиТрип систему инвентара за тражено усељење (нпр. Хотелијер није конфигурисао цене за 3 одрасле особе)

Узмимо пример да бисмо то боље разумели. Следеће је кратак снимак инвентара који је хотелијер пренео у наш систем за хотел „Кс“ (А означава одрасле особе и Ц за дете).

Сл. (1): Снимак инвентара

Корисничка претрага 1 (2 собе: Соба 1–1А, Соба 2–1А) - У овом случају, иако имамо на располагању 3 (иако различите врсте) соба, враћали смо нулту доступност хотела јер смо успоређивали критеријуме претраживања са сваком тип собе и ниједан тип собе није имао број инвентара ≥2.

Корисничка претрага 2 (Соба 1- 3А) - И у овом случају смо враћали нулту доступност хотела јер хотелијер није конфигурисао цене за горње критеријуме претраге.

У оба случаја постојао је начин да се испуне критеријуми за претраживање корисника комбинацијом различитих врста соба. Проблем постаје много сложенији јер сваки хотел има свој праг старости деце и одговарајуће цене.

Решење у три тачке

  1. Промените критеријуме претраге - Престали смо да успоређујемо тачне критеријуме за претраживање корисника према свакој врсти собе и започели смо претрагу са трансформисаним захтевом за претрагом. Ово се посебно ради за претраживања веће попуњености, уколико је расположивост углавном мала.
  2. Изградите алгоритам комбинације најјефтинијих соба - За наше купце је најјефтинија понуда најбоља. Да би се решило ово и проблем доступности хотела, имало је смисла изградити алгоритам који ће корисницима представити најјефтинију комбинацију собе (а).
  3. Затражите од хотелијера да конфигуришу цијене за већу попуњеност - Будући да 60% корисника путује соло или као пар, хотелијери углавном оптимизирају цијене и залихе за једнокреветну и двоструку попуњеност. Да бисмо помогли купцима да добију боље резултате претраживања за заузетост> 2, замолили смо хотелијере да конфигуришу све могуће комбинације заузећа које подржавају.

Ево како смо мислили да би целокупно решење требало да делује.

Слика (2): Дијаграм тока

(1) и (2) су означени зеленом бојом. Зависно од канала из којег се хотел користи, можда ћемо имати или не морамо имати потребне информације за покретање алгоритма комбинације најјефтинијих соба. Да бисмо обрадили такве случајеве, изградили смо неке додатне алгоритме за генерисање / предвиђање потребних података (број инвентара је један од њих).

Пословни утицај

Реализирали смо (1) и (2). Као што се очекивало, расположивост хотела на нашој страници за пописивање више од две одрасле особе нарасла је вишеструко. Такође смо почели да добијамо 5% додатних ноћења сваки дан. Све у свему, дошло је до скока од преко 50% у броју резервација које имају више од 2 одрасле особе.

Слика (3): Тренд резервација пре и после објављивања функције

Рачунарски изазови и приступ

Проблем са препоруком најјефтинијих соба је комбинаторички проблем оптимизације.

С обзиром на Н хотелских соба и П (одрасли + дете) гостију, пронађите најјефтинију комбинацију соба за смештај П гостију.

Да бисмо покренули било који алгоритам оптимизације, морали смо да добијемо атрибуте података који су потребни за:

  • Генеришите све могуће просторе за собу
  • Израчунајте цену за такве случајеве

Због тога смо почели да трошимо атрибуте хотела и нивоа као што су праг старости деце, максимално допуштени број одраслих / деце у соби, број расположивих врста сваке собе, цена за одрасле итд. Сваки хотелијер може самостално да конфигурише своје тарифне детаље као што су, смештај до које неће наплаћивати додатни (основни капацитет), до које ће старости дете сматрати госта као дете, додатну цену за децу, цену екстра одрасле особе, максималан број одраслих / деце који се могу сместити у свакој соби. Све ово треба водити рачуна приликом генерисања и израчунавања цене сваке собе и смештаја. Руковање овим атрибутима вишеструко је повећало рачунски сложеност. Додатни изазов био је задржати нетакнуте могућности претраживања. Ова израчунавања треба да се врше у реалном времену и на захтев садрже 200–250 хотела.

Иако смо увек имали на уму динамично програмирање да решимо овај проблем, размотрили смо решење против грубе силе и неколико похлепних приступа да видимо да ли су они довољни / раде ли за наше примене.

Бруте Форце решење: Ово је подразумевало креирање сваке могуће комбинације за наведени инвентар са свим тарифним плановима. Те просторије би потом морале бити прекривене разним комбинацијама заузећа. То је резултирало експоненцијалном временском сложеношћу.

Сл. 4: Приступ грубим силама резултира експоненцијалном сложеношћу времена

Ово је било изводљиво, али не и скалабилно. Такође ће додати значајне латенције претраживања апи.

Похлепни приступи: Истражили смо неколико стратегија, али пронашли смо контра случај у свакој од њих. Основни проблем је био што немамо собе разврстане према цени и броју особа (госта). Штавише, свака супериор соба / апартман може примити више људи у поређењу са стандардном собом.

Најјефтинији алгоритам за комбиновање соба

Да разумемо неколико термина и ознака пре него што пређемо на алгоритам.

Сл. (5): Терминологија за најјефтинији алгоритам за комбиновање соба

Моделирали смо проблем проналажења најјефтиније комбинације просторија око врло чувеног проблема са руксаком од 0 до 1. Предмети (Н) и утези (В) у проблему руксака лагано се пресликавају на скуп физичких соба у хотелу и различите могуће комбинације заузећа (почев од 0 и водећи до тражене попуњености). Било је, међутим, неких јединствених ограничења у нашем случају, која су захтевала посебно руковање.

  1. Под-предмети / виртуелне собе: Сваки предмет је јединствен у проблему с раништем од 0 до 1, али то није тачно у нашем случају. Физичка просторија (артикал) мора се узети у обзир са свим могућим попустима и тарифама да би се осигурала јединственост у сету предмета. То резултира стварањем виртуелних соба за сваку физичку собу. Проблем Н у раништу од 0–1 у ствари се пресликава на сет виртуелних соба.
  2. Обезбеђивање физичке собе користи се једном: То је директна импликација (1). Иако користимо виртуалне собе за све калкулације и одлуке у алгоритму, мора се осигурати да се физичка соба користи само једном за сваку комбинацију соба и треба наћи најбољу алтернативу у случају било каквог сукоба.
  3. Случајеви ивица док попуњавамо преосталу попуњеност: Морали смо обрадити неколико рубних случајева, а притом се позивали на под-проблеме који су већ решени. на пример. пуно хотела не дозвољава резервације са собама које имају само децу. Такође требамо рјешавати случајеве у којима смо попуњеност одраслих испунили кроз виртуелну собу и остало је само заузимање деце.

Кључни кораци за изградњу алгоритма

  1. Добијте резултат трансформисаног захтева за претрагом.
  2. Направите дводимензионалну матрицу Т са свим могућим попуњеностима соба као ступове (В), а виртуелне собе у редовима (Н).
  3. У свакој ћелији дводимензионалне матрице разматрамо две могућности - да одаберемо одговарајућу виртуелну собу као део оптималног решења или да је одбацимо. Израчунавамо трошкове повезане са и без те виртуалне собе и бирамо најјефтинију. Свака ћелија матрице чува кључне атрибуте просторија које се користе да би се испунила попуњеност те ћелије.

Матрица се попуњава одоздо према горе коришћењем доњег односа понављања:

Слика (6): Формула за рачунање

4. Вратите резултат након преласка матрице.

Пример:

Сл. (7): Подаци о нивоу собе / тарифе

За горње улазне параметре креираће се следећа дводимензионална матрица. Колона у наранџастом обликује цену која одговара свакој виртуелној соби према конфигурацијама које је урадио хотелијер.

Слика (8): 2Д матрица која приказује уносе за 3 одрасле особе и 2 деце. Ништави уноси су означени као „Кс“.

Ћелије означене зеленом бојом показују најјефтинију комбинацију соба за наведене критеријуме претраге. Идентификатори соба наведени у ћелији описују које се собе требају узети у обзир, а њихове претплате одређују заузетост сваке собе. Станице означене плавом бојом су оне које се користе за израчунавање зелене ћелије рекурзивно (користећи горњу везу рецидива).

Овај алгоритам је прилично добро функционисао у производњи, а да није утицао на латентност 99. процента нашег АПИ-ја за претрагу. Чак и након кеширања ових препорука, још увек обрађујемо око 15К јединствених хотелских комбинација сваке минуте.

Посебна захвалност Ајаи Сингх и Абхијеет Схарад на помоћи у изради овог блога.