Otel Müsaitliği ve Oda Tavsiyesi Algorithm @ MMT

MakeMyTrip'te çeşitli otel müşterileriyle hizmet veriyoruz ve çeşitli seyahat amaçları, doluluk ve bilgi gereksinimleri göz önüne alındığında planlarını tamamlamalarına yardımcı oluyoruz. Bununla birlikte, herkes için karşılanması gereken en önemli iki kullanıcı ihtiyacı aynıdır - otel uygunluğu ve bir kişinin bütçesine göre oda fiyatı. Bu blog yazısında, platformumuzdaki genel otel kullanılabilirliğini nasıl artırdığımız ve bazı teklifleri müşterilerimiz için daha güçlü ve kullanışlı hale getirmek için 'en ucuz oda kombinasyonunu bulma' sorununu çözmek için dinamik programlama kullandığımızla ilgili bazı bilgileri paylaşıyoruz.

Önce otel müsaitliği ve oda fiyatlarının, özellikle de en ucuz olanın neden bu kadar önemli olduğunu anlayalım.

Otel Müsaitliği: Müşteriye, otel giriş sayfasında seçebilecekleri yeterli oteli göstermek çok önemlidir. Otellerin sıfır veya düşük kullanılabilirliği, giriş sayfasının kendisinde çok fazla müşteri düşüşüne yol açarak potansiyel bir iş kaybına yol açar.

Oda Fiyatı: Gezginlerin çoğu, bir otel için oda fiyatlarını çevrimiçi seyahat acenteleri (OTA'lar) üzerinden karşılaştırır ve OTA'da en ucuz fiyatı sunan bir işlem yapar. En ucuz fiyata sahip odalarda önemli sayıda rezervasyon yapıldığı düşünüldüğünde, müşterinin hızlı bir karar vermesine yardımcı olmak için otel ayrıntıları sayfasında en ucuz oda fiyatını göstermek / vurgulamak önemli hale gelir.

Düşük Otel Müsaitliği

Problem Bulma

MakeMyTrip'te, çok fazla veri kaydeder ve eyleme geçirilebilir öngörüler bulmak için düzenli olarak analiz ederiz. Son bulgularımızdan biri, önemli sayıda şehir araması için otel giriş sayfasında düşük veya sıfır otel kullanılabilirliği idi. Bunun başlıca iki nedeni vardı:

  • Yoğun sezonda / uzun hafta sonlarında daha az stok mevcut
  • İstenen doluluk oranı için MakeMyTrip envanter sisteminde eksik fiyatlar (ör. Otel işletmecisi 3 yetişkin için fiyatları yapılandırmamış)

Bunu daha iyi anlamak için bir örnek alalım. Aşağıda, otelci tarafından 'X' oteli için sistemimizde yüklenen envanterin bir görüntüsü verilmiştir (A, yetişkin anlamına gelir ve C, çocuk içindir).

Şekil (1): Envanter anlık görüntüsü

Kullanıcı arama 1 (2 Oda: Oda 1–1A, Oda 2–1A) - Bu durumda, 3 (farklı tipte olmasına rağmen) mevcut odalarımız olmasına rağmen, arama kriterlerini her biriyle karşılaştırdığımız için sıfır otel kullanılabilirliği döndürüyorduk oda tipi ve hiçbir oda tipi envanter sayısı count2 idi.

Kullanıcı Arama 2 (Oda 1- 3A) - Bu durumda da, otelci yukarıdaki arama kriterleri için oranları yapılandırmadığından otellerin sıfır kullanılabilirliğini iade ediyorduk.

Her iki durumda da, farklı oda tiplerini birleştirerek kullanıcı arama kriterlerini yerine getirmenin bir yolu vardı. Her otel kendi çocuk yaş eşiğine ve ilgili fiyatlara sahip olduğundan sorun çok daha karmaşık hale gelir.

Üç noktadan çözüm

  1. Arama ölçütlerini değiştirme - Her bir oda tipiyle tam kullanıcı arama ölçütlerini eşleştirmeyi durdurduk ve dönüştürülmüş arama isteği ile aramaya başladık. Bu özellikle kullanılabilirlik genellikle düşük olduğu için daha yüksek doluluk aramaları için yapılır.
  2. En ucuz oda kombinasyonu algoritmasını oluşturun - Müşterilerimiz için en ucuz fırsat en iyisidir. Bu ve otel kullanılabilirliği sorununu çözmeye yardımcı olmak için, kullanıcılara odaların en ucuz kombinasyonlarını sunmak için bir algoritma oluşturmak mantıklıydı.
  3. Otelcilerden daha yüksek doluluk için fiyatları yapılandırmalarını isteyin - Kullanıcıların% 60'ı yalnız veya çift olarak seyahat ettiğinden, otelciler genellikle tek ve çift kişilik konaklamalar için oranları ve envanteri optimize eder. Müşterilerin doluluk> 2 için daha iyi arama sonuçları elde etmelerine yardımcı olmak için otelcilerden destekledikleri tüm olası doluluk kombinasyonlarını yapılandırmalarını istedik.

Genel çözümün nasıl çalışması gerektiğini burada düşündük.

Şekil (2): Akış Şeması

(1) ve (2) yeşil renkle vurgulanmıştır. Otelin tüketildiği kanala bağlı olarak, en ucuz oda kombinasyonu algoritmasını çalıştırmak için gerekli bilgiye sahip olabiliriz veya olmayabiliriz. Bu gibi durumları ele almak için gerekli verileri oluşturmak / tahmin etmek için bazı ek algoritmalar geliştirdik (envanter sayısı bunlardan biri).

İş Etkisi

Hem (1) hem de (2) uyguladık. Beklendiği gibi, 2'den fazla yetişkinin arama talebi için otel kullanılabilirliği liste sayfamızda çok katlı hale geldi. Biz de her gün% 5 ek oda gece almaya başladı. Genel olarak, 2'den fazla Yetişkin bulunan rezervasyon sayısında% 50'den fazla bir sıçrama oldu.

Şekil (3): Özellik sürümünden önceki ve sonraki rezervasyon eğilimi

Hesaplamalı zorluklar ve yaklaşım

En ucuz oda önerisi problemi bir kombinatoryal optimizasyon problemidir.

Verilen N otel odaları ve P (yetişkin + çocuk) konukları, P misafirlerini ağırlamak için en ucuz oda kombinasyonunu bulun.

Herhangi bir optimizasyon algoritmasını çalıştırmak için aşağıdakiler için gerekli veri özelliklerini almamız gerekiyordu:

  • Bir oda için olası tüm misafirleri oluşturun
  • Bu gibi durumlar için fiyat hesapla

Bunun için, çocuk yaşı eşiği, bir odada izin verilen maksimum yetişkin / çocuk, her bir oda tipinin uygunluk sayısı, ekstra yetişkin fiyatı vb. Gibi otel ve oda seviyesi özelliklerini tüketmeye başladık. Her otelci, doluluk gibi tarife ayrıntılarını bağımsız olarak yapılandırabilir. o kadar çocuk, ekstra çocuk fiyatı, ekstra yetişkin fiyatı, her odada konaklayabilir max yetişkin / çocuk olarak kabul edecek çocuk yaş, ekstra (taban doluluk) ücret olmaz. Tüm odaların ve dolulukların fiyatları oluşturulurken ve hesaplanırken bunların hepsine dikkat edilmelidir. Bu özniteliklerin kullanılması, hesaplama karmaşıklığı çok katlı özelliğini artırdı. Ek zorluk arama api gecikmelerini sağlam tutmaktı. Bu hesaplamalar gerçek zamanlı olarak ve 200–250 otel içeren talep için yapılacaktır.

Bu sorunu çözmek için her zaman dinamik programlama düşünürken, kaba kuvvet çözümünü ve kullanım durumlarımız için yeterli / yeterli olup olmadığını görmek için birkaç açgözlü yaklaşımı ele aldık.

Brute Force Çözümü: Bu, verilen envanter için tüm tarife planlarıyla mümkün olan her kombinasyonun oluşturulmasını içeriyordu. Bu odaların daha sonra farklı doluluk kombinasyonları ile kullandırılması gerekecektir. Bu, üstel zaman karmaşıklığına neden oldu.

Şekil (4): Kaba kuvvet yaklaşımı, üstel zaman karmaşıklığına neden olur

Bu uygulanabilirdi ancak ölçeklenebilir değildi. Ayrıca, arama API'sında önemli bir gecikme ekleyecektir.

Açgözlü Yaklaşımlar: Birkaç strateji araştırdık ancak her birinde bir karşı dava bulduk. Temel sorun, biz fiyat ve pax (misafir) doluluk sırasına göre sıralanmış oda yok oldu. Ayrıca, herhangi bir superior oda / süit standart odaya göre daha fazla kişiyi ağırlayabilir.

En Ucuz Oda Kombinasyonu Algoritması

Algoritmaya geçmeden önce birkaç terim ve notasyonu anlayalım.

Şekil (5): En Ucuz Oda Kombinasyonu Algoritması Terminolojisi

Çok ünlü 0–1 sırt çantası problemi etrafında en ucuz oda kombinasyonunu bulma problemini modelledik. Sırt çantası problemindeki öğeler (N) ve ağırlıklar (W), oteldeki fiziksel oda setine ve olası farklı doluluk kombinasyonlarına (0'dan başlayarak istenen doluluk oranına kadar) gevşek bir şekilde eşleşir. Ancak bizim durumumuzda özel kullanım gerektiren bazı benzersiz kısıtlamalar vardı.

  1. Alt öğeler / Sanal odalar: Her bir öğe 0–1 sırt çantası probleminde benzersizdir, ancak bu bizim durumumuzda doğru değildir. Maddeler kümesinde benzersizliği sağlamak için tüm olası doluluklar ve tarifelerle birlikte fiziksel bir oda (eşya) göz önünde bulundurulmalıdır. Bu, her fiziksel oda için sanal odaların yaratılmasıyla sonuçlanır. 0–1 sırt çantası problemindeki N aslında bizim durumumuzdaki sanal odalar setiyle eşleşir.
  2. Fiziksel odanın bir kez kullanılmasını sağlamak: (1) 'in doğrudan bir sonucudur. Algoritmadaki tüm hesaplamalar ve kararlar için sanal odaları kullanırken, fiziksel bir odanın her oda kombinasyonu için sadece bir kez kullanıldığından ve herhangi bir çatışma durumunda en iyi alternatifi bulmamız gerektiğinden emin olunmalıdır.
  3. Kalan dolguyu doldururken uç durumlar: Daha önce çözülmüş olan alt sorunlara değinirken birkaç uç vakayı ele almak zorunda kaldık. örneğin bir çok otel sadece çocuklu oda rezervasyonlarına izin vermez. Ayrıca, yetişkin doluluğunu sanal bir oda üzerinden gerçekleştirdiğimiz ve yalnızca çocuk doluluk kaldığı davaları ele almamız gerekiyor.

Algoritmayı Oluşturmak için Temel Adımlar

  1. Dönüştürülmüş arama isteğinin sonucunu alın.
  2. Sütunlar (W) olarak mümkün olan tüm oda dolulukları ve satırlar (N) olarak sanal odalar bulunan 2 boyutlu bir T matrisi oluşturun.
  3. 2 boyutlu matrisin her hücresinde, karşılık gelen sanal odayı optimum çözümün bir parçası olarak seçmek veya atmak için iki olasılığı düşünüyoruz. Bu sanal odayla ve o sanal oda olmadan ilgili maliyeti hesaplıyoruz ve en ucuzunu seçiyoruz. Her matris hücresi, o hücrenin doluluğunu yerine getirmek için kullanılan odaların temel özelliklerini depolar.

Matris, aşağıdaki yineleme ilişkisi kullanılarak aşağıdan yukarıya doğru doldurulur:

Şekil (6): Hesaplama Formülü

4. Matrisi geçtikten sonra sonucu döndürün.

Misal:

Şekil (7): Oda / Tarife seviyesi detayları

Yukarıdaki giriş parametreleri için aşağıdaki 2 boyutlu matris oluşturulacaktır. Turuncu sütun, otelci tarafından yapılan yapılandırmalara göre her sanal odaya karşılık gelen fiyatı yakalar.

Şekil (8): 3 Yetişkin ve 2 Çocuk için girişleri gösteren 2D Matris. Boş Girdiler 'X' olarak işaretlendi.

Yeşil ile vurgulanan hücreler, belirtilen arama kriterleri için en ucuz oda kombinasyonunu gösterir. Hücrede bahsedilen oda tanımlayıcıları hangi odaların dikkate alınacağını açıklar ve abonelikleri her odanın doluluk oranını tanımlar. Mavi ile vurgulanan hücreler, yeşil hücreyi özyinelemeli olarak hesaplamak için kullanılan hücrelerdir (yukarıda belirtilen nüks ilişkisini kullanarak).

Bu algoritma, arama API'mizin 99. persentil gecikmesini etkilemeden üretimde oldukça iyi çalıştı. Bu öneri sonuçlarını önbelleğe aldıktan sonra bile, her dakika yaklaşık 15 bin benzersiz otel kombinasyonu işliyoruz.

Ajay Singh ve Abhijeet Sharad'a bu blogun taslağına yardım ettiği için teşekkür ederiz.