Constant-Factor Algorithms for Revenue Management with Consecutive Stays

कल्पना कीजिए कि आप एक व्यस्त रेलवे स्टेशन या एक लोकप्रिय होटल श्रृंखला के प्रबंधक हैं। हर दिन, हजारों लोग आते हैं, जिनमें से प्रत्येक एक विशिष्ट समय अवधि के लिए एक सीट या एक कमरा बुक करना चाहता है। कुछ पूरी यात्रा चाहते हैं; कुछ बस कुछ स्टॉप। पेच यह है कि आपके पास सीमित संख्या में सीटें या कमरे हैं, और एक बार जब आप एक दे देते हैं, तो वह उस विशिष्ट समय स्लॉट के लिए चला जाता है। यही नेटवर्क रेवेन्यू मैनेजमेंट (Network Revenue Management) का सार है: यह निर्णय लेने की कला कि किसे "हाँ" कहना है और किसे "ना", ताकि आप बड़े खर्च करने वालों के आने तक अपनी इन्वेंट्री खत्म किए बिना अधिक से अधिक पैसा कमा सकें।

गणित और कंप्यूटर विज्ञान की दुनिया में, यह एक क्लासिक पहेली है। आमतौर पर, इसे हल करने का सबसे अच्छा तरीका पूरे भविष्य को देखना है, यह जानना है कि वास्तव में कौन कब आएगा, और फिर एक आदर्श शेड्यूल बनाना है। लेकिन वास्तविक दुनिया में, आप भविष्य नहीं देख सकते। आपको एक समय में एक ग्राहक के हिसाब से मौके पर निर्णय लेना होता है, यह जाने बिना कि अगला कौन आने वाला है। इसे एक "ऑनलाइन" समस्या कहा जाता है। वर्षों से, गणितज्ञों ने एक सरल, तेज़ नियम खोजने के लिए संघर्ष किया है जो यह गारंटी दे सके कि आप एक अच्छा पैसा कमा रहे हैं, भले ही आप भविष्य न जानते हों। मुख्य सवाल यह रहा है: क्या हम एक ऐसी रणनीति पा सकते हैं जो यह गारंटी दे सके कि वह "काफी अच्छी" है (सर्वोत्तम संभव परिणाम का एक स्थिर हिस्सा), चाहे बुकिंग कितनी भी लंबी क्यों न हो या ग्राहक कितने भी पेचीदा क्यों न हों?

मिंघ हू (Ming Hu) और टोंगवेन वू (Tongwen Wu) का यह शोध पत्र ठीक इसी सवाल को संबोधित करता है। वे दो अलग-अलग तरीकों को देखते हैं जिनसे ग्राहक व्यवहार कर सकते हैं। पहले परिदृश्य में, यह एक ट्रेन टिकट की तरह है: या तो आप यात्री को स्वीकार करते हैं और उन्हें एक विशिष्ट सीट आवंटित करते हैं, या आप उन्हें अस्वीकार कर देते हैं। दूसरे, अधिक जटिल परिदृश्य में, यह एक बुटीक होटल या एयरबीएनबी (Airbnb) जैसा है: आप ग्राहक को उपलब्ध कमरों का एक मेनू दिखाते हैं और वे अपनी पसंद के आधार पर सबसे अच्छा कमरा चुनते हैं। लेखकों ने इन स्थितियों को संभालने के लिए नए, तेज़ कंप्यूटर एल्गोरिदम विकसित किए। उन्होंने सिद्ध किया कि उनके तरीके साधारण ट्रेन-टिकट वाले मामले में "परफेक्ट" भविष्य जानने वाले योजनाकार द्वारा कमाए जाने वाले पैसे का कम से कम 63.2% कमाने की गणितीय गारंटी देते हैं। जब ग्राहक मेनू से चुनने का विकल्प रखते हैं, तो यह गारंटी गिरकर 27.1% हो जाती है। यहाँ तक कि जब ठहरने की अवधि यादृच्छिक (random) और अप्रत्याशित होती है, तब भी उनके एल्गोरिदम एक ठोस राशि सुरक्षित करने में सक्षम होते हैं, जो यह साबित करता है कि लाभदायक व्यवसाय चलाने के लिए आपको भविष्यद्रष्टा होने की आवश्यकता नहीं है—आपको बस सही गणित की आवश्यकता है।

गायब सीटों की पहेली

इस समस्या को एक विशाल, बदलते हुए जिग्सॉ पहेली (jigsaw puzzle) की तरह सोचें जहाँ टुकड़े अपना आकार बदलते रहते हैं। "एक्सेप्ट-ऑर-रिजेक्ट" (स्वीकार करें या अस्वीकार करें) की दुनिया में (ट्रेन के उदाहरण की तरह), हर बार जब कोई यात्री स्टेशन A से स्टेशन F तक की सीट मांगता है, तो आपको तुरंत निर्णय लेना होता है: "क्या मैं उन्हें सीट 101 दूँ? या क्या मैं इसे किसी ऐसे व्यक्ति के लिए बचा कर रखूँ जो बाद में इसे चाह सकता है?" यदि आप इसे बहुत जल्दी दे देते हैं, तो आप बड़े ग्रुप बुकिंग का अवसर खो सकते हैं। यदि आप इसे बहुत कसकर पकड़ कर रखते हैं, तो आप सीट को हमेशा के लिए खाली छोड़ सकते हैं।

लेखकों ने महसूस किया कि भविष्य की भविष्यवाणी करने के बजाय, आप "फ्लुइड रिलैक्सेशन" (fluid relaxation) नामक एक चतुर ट्रिक का उपयोग कर सकते हैं। कल्पना कीजिए कि सीटें ठोस ब्लॉक नहीं बल्कि बहता हुआ तरल पदार्थ हैं। आप संभावनाओं के आधार पर गणना करते हैं कि उस "तरल" सीट का कितना हिस्सा विभिन्न प्रकार के यात्रियों के लिए आरक्षित किया जाना चाहिए। फिर, उन्होंने एक "प्रपोजल-डिस्कार्डिंग" (प्रस्ताव-त्याग) एल्गोरिदम बनाया। यह कैसे काम करता है, इसे सरल अंग्रेजी (और हिंदी) में समझते हैं:

इससे पहले कि कोई ग्राहक काउंटर पर आए, कंप्यूटर एक "क्या होगा अगर" वाला परिदृश्य सिम्युलेट करता है। यह प्रत्येक उपलब्ध सीट से पूछता है, "यदि इस प्रकार का ग्राहक आए, तो क्या आप उन्हें स्वीकार करने के लिए तैयार होंगे?" प्रत्येक सीट गणित के आधार पर एक सिक्का उछालती है (coin flip) यह तय करने के लिए कि क्या वह अपना हाथ उठाएगी। यदि कई सीटें हाथ उठाती हैं, तो कंप्यूटर उस एक को चुनता है जो सबसे अधिक पैसा कमाएगा। यदि कोई हाथ नहीं उठाता है, तो ग्राहक को विनम्रता से मना कर दिया जाता है।

लेकिन यहाँ एक जादुई मोड़ है: भले ही एक सीट को वास्तविक ग्राहक के लिए नहीं चुना गया हो, कंप्यूटर यह मान लेता है कि उसे चुन लिया गया था। यह उस सीट को अपने आंतरिक सिमुलेशन में "बिजी" (व्यस्त) के रूप में चिह्नित करता है। यह गणित को ईमानदार रखता है और सिस्टम को बहुत अधिक लालची होने से रोकता है। यह "वर्चुअल बिजी" स्थिति यह सुनिश्चित करती है कि एल्गोरिदम अनजाने में अपनी गणनाओं में एक ही सीट को डबल-बुक न कर दे, जिससे संभावनाएँ स्वतंत्र रहती हैं और गणित हल करने योग्य बना रहता है।

जब ग्राहक चुनने का अधिकार रखते हैं

शोध पत्र का दूसरा भाग और भी मजेदार है क्योंकि इसमें मानवीय चुनाव जुड़ जाता है। एक ऐसे होटल की कल्पना करें जहाँ आप केवल कमरा आवंटित नहीं करते; आप अतिथि को तीन उपलब्ध कमरों की एक सूची दिखाते हैं: एक दृश्य (view) वाला, एक बालकनी वाला, और एक सस्ता। अतिथि फिर वह चुनता है जो उसे सबसे अच्छा लगता है। यह "बीएएम-आधारित" (BAM-based - बेसिक अट्रैक्शन मॉडल) परिदृश्य है।

यह कठिन है क्योंकि अतिथि का चुनाव उस पूरी सूची पर निर्भर करता है जो आप उन्हें दिखाते हैं। यदि आप उन्हें एक शानदार कमरा दिखाते हैं, तो वे उसे चुन सकते हैं। यदि आप उन्हें एक शानदार कमरा और एक सस्ता कमरा दिखाते हैं, तो वे सस्ता वाला चुन सकते हैं। लेखकों को कंप्यूटर के "आभासी" (virtual) विकल्पों को अतिथि के वास्तविक विकल्पों से जोड़ने का एक नया तरीका आविष्कार करना पड़ा। उन्होंने "रैंडमाइज्ड कपलिंग" (randomized coupling) नामक तकनीक का उपयोग किया। इसे एक जादूगर के करतब की तरह समझें: कंप्यूटर उन कमरों की एक यादृच्छिक सूची बनाता है जो पेश की जानी है, लेकिन वह ऐसा इस तरह से करता है कि गणितीय रूप से यह गारंटी मिले कि अतिथि का चुनाव कंप्यूटर की योजना के अनुरूप होगा, भले ही अतिथि अपनी स्वतंत्र पसंद बना रहा हो।

उन्होंने पाया कि हालांकि यह विकल्प जटिलता बढ़ाता है, फिर भी उनका एल्गोरिदम काम करता है। "मेनू" परिदृश्य में, उन्होंने सिद्ध किया कि उनकी नीति इष्टतम राजस्व का कम से कम 27.1% अर्जित करती है। यदि ठहरने की अवधि भी यादृच्छिक है (जैसे कोई अतिथि कहता है, "मैं 2 दिन रुक सकता हूँ, या शायद 5"), तो गारंटी थोड़ी कम हो जाती है, लेकिन फिर भी सकारात्मक रहती है: मेनू परिदृश्य के लिए 17.1% और साधारण ट्रेन परिदृश्य के लिए 39.9%।

यह क्यों मायने रखता है

इस शोध पत्र से पहले, इस प्रकार की समस्याओं के लिए सर्वोत्तम गारंटी बहुत कमजोर थी। वे बुकिंग की अवधि पर निर्भर करती थीं। यदि लोग बहुत लंबी यात्राओं के लिए बुकिंग करते थे, तो गारंटी लगभग शून्य तक गिर जाती थी। यह कहने जैसा था कि, "हमारी रणनीति बेहतरीन है, जब तक कि आप एक महीने के लिए न रुकें, तब तो यह बेकार है।"

लेखकों ने दिखाया कि यह सच नहीं है। उन्होंने सिद्ध किया कि आप एक "कॉन्स्टेंट-फैक्टर" (स्थिर कारक) गारंटी प्राप्त कर सकते हैं। इसका मतलब है कि चाहे ठहरने की अवधि कितनी भी लंबी हो, चाहे आपके पास कितने भी संसाधन हों, आपकी रणनीति हमेशा एक निश्चित, स्वस्थ प्रतिशत को कैप्चर करेगी। उन्होंने यह भी दिखाया कि साधारण मामले के लिए आप 63.2% से अधिक नहीं कर सकते (यह सिद्ध करते हुए कि 100% के करीब पहुँचना "कठिन" है), जिसका अर्थ है कि उनका समाधान वास्तव में उस सर्वोत्तम संभव उत्तर के बहुत करीब है जिसकी हम उम्मीद कर सकते हैं।

संक्षेप में, उन्होंने एक अव्यवस्थित, अप्रत्याशित वास्तविक दुनिया की समस्या को लिया और उसे एक ठोस गणितीय आधार दिया। उन्होंने दिखाया कि सही एल्गोरिदम के साथ, लाभदायक होने के लिए आपको पूर्ण होने की आवश्यकता नहीं है; आपको बस यह जानने के लिए पर्याप्त स्मार्ट होने की आवश्यकता है कि कब "हाँ" कहना है, कब "ना" कहना है, और ग्राहकों को यह चुनने देने के बिना कि आप अपना नुकसान कर बैठें।