Kullanılabilirliği ve Oda Önerisi Algoritması @ MMT

MakeMyTrip'de, çeşitli otel alışverişçileri grubuna hizmet veriyor ve farklı seyahat amaçları, doluluk ve bilgi gereklilikleri göz önüne alındığında planları tamamlamalarına yardımcı oluyoruz. Bununla birlikte, herkes için karşılanması gereken en önemli iki kullanıcı ihtiyacı aynıdır - otel müsaitliği ve bütçeye göre oda fiyatı. Bu blog yazısında, platformumuzdaki genel otel kullanılabilirliğini nasıl arttırdığımız ve müşterilerimize daha güçlü ve kullanışlı hale getirmek için "odaların en ucuz kombinasyonunu" bulma sorununu çözmek için dinamik programlama kullandığımız konusunda bazı görüşler paylaşıyoruz.

Öncelikle otel uygunluğu ve oda fiyatlarının, özellikle de en ucuzunun neden bu kadar önemli olduğunu anlayalım.

Otel Durumu: Müşteriye otel listeleme sayfasından seçebileceği yeterli otel gösterilmesi çok önemlidir. Otellerin sıfır olması veya düşük olması, liste sayfasında çok sayıda müşterinin düşmesine neden olarak olası bir işletme kaybına neden olur.

Oda Fiyatı: Seyahat edenlerin çoğu çevrimiçi seyahat acenteleri (OTA'lar) içindeki bir otel için oda fiyatlarını karşılaştırır ve en düşük fiyatı sunan OTA'da bir işlem yapar. En ucuz fiyatı olan odalarda önemli sayıda rezervasyon yapılması göz önüne alındığında, müşterinin hızlı karar vermesine yardımcı olmak için otel bilgileri sayfasında en ucuz oda fiyatını göstermek / vurgulamak önemlidir.

Düşük Otel Durumu

Problem Keşfi

MakeMyTrip'da, çok fazla veri kaydediyoruz ve işlemlerin gerçekleştirilebilmesi için düzenli olarak analiz ediyoruz. Son bulgularımızdan biri, çok sayıda şehir araması için otel listeleme sayfasında düşük veya sıfır otel mevcudiyeti idi. Bunun öncelikle iki sebebi vardı:

  • Yoğun sezonda / uzun hafta sonlarında daha az envanter mevcut
  • Talep edilen doluluk oranı için MakeMyTrip envanter sistemindeki eksik oranlar (örneğin, otel sahibi 3 yetişkin için fiyatları yapılandırmamış)

Bunu daha iyi anlamak için bir örnek alalım. Aşağıda verilen, otel sahibi tarafından sistemimize otel olan “X” için yüklenen envanterin bir görüntüsüdür (A yetişkin ve çocuk için C anlamına gelir).

Ş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) oda olmasına rağmen, her birinde arama kriterleri ile eşleşirken sıfır otel müsaitliği veriyoruz. oda tipinde ve oda tipinde hiçbirinde stok sayımı ≥2 olmamıştır.

Kullanıcı Arama 2 (Oda 1- 3A) - Bu durumda, otel işletmecisi yukarıdaki arama kriterleri için fiyatları yapılandırmadığı için otellerin sıfır kullanılabilirliğini iade ediyoruz.

Her iki durumda da, farklı oda türlerini birleştirerek kullanıcı arama kriterlerini yerine getirmenin bir yolu vardı. Her otel kendi yaş sınırı eşiğine ve buna uygun fiyatlara sahip olduğundan sorun çok daha karmaşık hale geliyor.

Üç noktalı çözüm

  1. Arama kriterlerini değiştir - Her oda tipine göre kullanıcı arama kriterlerini tam olarak eşleştirmeyi bıraktık ve dönüştürülmüş arama isteği ile aramaya başladık. Bu özellikle yüksek doluluk oranlı aramalar için yapılabilirliği genellikle düşüktür.
  2. En ucuz oda kombinasyon algoritmasını oluşturun - Müşterilerimiz için en ucuz anlaşma en iyisidir. Bunu ve otel kullanılabilirliği sorununu çözmek için, kullanıcılara en ucuz oda kombinasyonunu sunmak için bir algoritma oluşturmak mantıklı geldi.
  3. Otelcilerden 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 oranları tek başına ve iki kişi için envanteri optimize eder. Müşterilerin doluluk oranı> 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 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 gereken bilgilere sahip olabilir ya da olmayabilir. Bu gibi durumlarda, gerekli verileri üretmek / tahmin etmek için bazı ek algoritmalar geliştirdik (envanter sayımı bunlardan biri).

İşletme Etkisi

Hem (1) hem de (2) yi uyguladık. Beklendiği gibi, otel müsaitliği 2 yetişkinden fazla arama istekleri için listemizde çok yönlü büyüdü. Ayrıca her gün% 5 ek oda gecesi almaya başladık. Genel olarak, 2 Yetişkinten fazla olan rezervasyonların sayısında% 50'den fazla bir sıçrama oldu.

Şekil (3): Özellik açıklaması öncesi ve sonrası rezervasyon eğilimi

Hesaplamalı zorluklar ve yaklaşım

En ucuz oda önerisi sorunu bir kombinasyonel optimizasyon problemidir.

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

Herhangi bir optimizasyon algoritması çalıştırmak için gerekli olan veri niteliklerini almamız gerekiyor:

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

Bunun için çocuk yaşı eşiği, bir odada izin verilen maksimum yetişkin / çocuk, her oda tipi için uygunluk sayısı, ekstra yetişkin fiyatı vb. Gibi otel ve oda seviyesi özelliklerini tüketmeye başladık. Her otel sahibi, meslek sahipleri gibi tarife bilgilerini bağımsız olarak yapılandırabilir. o zamana kadar ekstra ücret talep etmeyecek, hangi çocuğun yaşını çocuk olarak kabul edeceği, ekstra çocuk fiyatı, ekstra yetişkin fiyatı, her odada konaklayabilecek maksimum yetişkin / çocuk. Her bir oda ve doluluk için fiyat oluşturulurken ve hesaplanırken tüm bunların dikkate alınması gerekir. Bu özelliklerin kullanılması, hesaplama karmaşıklığını çok yönlü olarak artırdı. Ek zorluk, arama sonuçlarının bozulmamasıdır. Bu hesaplamalar gerçek zamanlı ve 200-250 otel içeren istek için yapılmalıdır.

Bu problemi çözmek için her zaman dinamik programlama yaparken, kaba kuvvet çözümünü ve kullanım durumlarımız için yeterli olup olmadıklarını görmek için açgözlü bir yaklaşım göz önüne aldık.

Brute Force Çözümü: Verilen envanter için tüm tarife planları ile mümkün olan her kombinasyonun oluşturulmasını içeriyordu. Bu odaların daha sonra farklı doluluk kombinasyonları ile de kulüpleştirilmesi gerekir. Bu, üstel zaman karmaşıklığına neden oldu.

Şekil (4): Brute kuvvet yaklaşımı üssel zaman karmaşıklığına neden olmaktadır

Bu uygulanabilir, ancak ölçeklenebilir değildir. Ayrıca, arama api'sinde önemli bir gecikme olacaktır.

Açgözlü Yaklaşımlar: Birkaç strateji araştırdık ancak her birinde bir karşı dava bulduk. Temel sorun, fiyat ve kişi (konuk) doluluk sırasına göre düzenlenmiş odaların olmamasıydı. Ayrıca, herhangi bir superior oda / süit standart odaya kıyasla daha fazla insanı ağırlayabilir.

En Ucuz Oda Kombinasyonu Algoritması

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

Şekil (5): En Ucuz Oda Kombinasyonu Algoritması İçin Terminoloji

Çok ünlü 0-1 sırt çantası problemi etrafında odaların en ucuz kombinasyonunu bulma problemini modelledik. Sırt çantası problemindeki (N) ve ağırlıklar (W) gevşek bir şekilde oteldeki fiziki odalara ve farklı olası kullanım kombinasyonlarına (0'dan başlayarak istenen doluluk seviyesine kadar) eşleştirilir. Bununla birlikte, vakamızda özel işlem gerektiren bazı benzersiz kısıtlamalar vardı.

  1. Alt Öğeler / Sanal Odalar: Her şey 0-1 sırt çantası probleminde benzersiz ancak durumumuzda doğru değil. Öğe setinde benzersizliği sağlamak için, olası tüm meslekler ve tarifelerle fiziksel bir oda (madde) dikkate alınmalıdır. Bu, her fiziksel oda için sanal odaların oluşturulmasına neden olur. 0-1 sırt çantası problemindeki N aslında bizim durumumuzdaki sanal oda setiyle eşleşiyor.
  2. Fiziksel odanın bir kez kullanılmasının sağlanması: Bu, (1) 'in doğrudan bir uygulamasıdır. Algoritmadaki tüm hesaplamalar ve kararlar için sanal odaları kullanırken, her oda kombinasyonu için fiziksel bir odanın sadece bir kez kullanılması ve herhangi bir ihtilaf durumunda en iyi alternatifi bulmasının sağlanması gerekmektedir.
  3. Kalan dolulukları doldururken kenar davaları: Zaten çözülmüş olan alt sorunlara atıfta bulunurken birkaç kenar davasıyla uğraşmak zorunda kaldık. Örneğin. birçok otel, yalnızca çocuklara sahip olan oda rezervasyonlarına izin vermemektedir. Ayrıca, yetişkin odasını sanal oda aracılığıyla yerine getirdiğimiz ve yalnızca çocuk kullanımının kaldığı davaları da ele almamız gerekiyor.

Algoritmayı Kurmanın Temel Adımları

  1. Dönüştürülmüş arama isteğinin sonucunu alın.
  2. Olası tüm oda boşluklarını sütun (W), sanal odaları da satır (N) ile 2 boyutlu bir matris T oluşturun.
  3. 2 boyutlu matrisin her bir hücresinde, iki olasılık düşünürüz - karşılık gelen sanal odayı en uygun çözümün bir parçası olarak seçmek veya atmak için. Sanal oda ile ve o odayla ilişkili maliyetleri hesaplıyoruz ve en ucuzunu seçiyoruz. Her matris hücresi, o hücrenin doluluk seviyesini yerine getirmek için kullanılan odaların temel niteliklerini saklar.

Matris, aşağıdaki yinelenme 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.

Örnek:

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

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

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

Yeşil ile vurgulanan hücreler, belirtilen arama kriterleri için en ucuz oda kombinasyonunu gösterir. Hücrede belirtilen oda tanımlayıcıları, hangi odaların dikkate alınacağını ve abonelerinin her bir odanın boşluğunu tanımladığını belirtir. Maviyle vurgulanan hücreler, yeşil hücreyi özyinelemeli olarak hesaplamak için kullanılanlardır (yukarıda belirtilen yineleme ilişkisini kullanarak).

Bu algoritma, arama API'mızın yüzde 99'luk 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 kombinasyonunu işlemekteyiz.

Bu blogun hazırlanmasına yardımcı oldukları için Ajay Singh ve Abhijeet Sharad'a teşekkür ederiz.