Constant-Factor Algorithms for Revenue Management with Consecutive Stays

تخيل أنك مدير محطة قطار صاخبة أو سلسلة فنادق شهيرة. في كل يوم، يأتي آلاف الأشخاص، كل منهم يريد حجز مقعد أو غرفة لفترة زمنية محددة. البعض يريد الرحلة بأكملها؛ والبعض الآخر يريد مجرد بضع محطات. العائق؟ لديك عدد محدود من المقاعد أو الغرف، وبمجرد منح أحدها، فإنه يذهب ولا يعود لتلك الفترة الزمنية المحددة. هذا هو جوهر إدارة الإيرادات عبر الشبكات (Network Revenue Management): وهو فن تقرير من تقول له "نعم" ومن تقول له "لا"، لكي تحقق أكبر قدر من المال دون أن تنفد مخزونك من الأشخاص الذين قد يدفعون أكثر ويصلون لاحقاً.

في عالم الرياضيات وعلوم الحاسوب، هذه أحجية كلاسيكية. عادةً، أفضل طريقة لحلها هي النظر إلى المستقبل بأكمله، ومعرفة من سيصل بالضبط ومتى، ثم وضع جدول زمني مثالي. لكن في العالم الحقيقي، لا يمكنك رؤية المستقبل. عليك اتخاذ قرارات فورية، شخصاً تلو الآخر، دون معرفة من سيأتي بعد ذلك. هذا ما يسمى بمشكلة "أونلاين" (Online Problem). لسنوات، كافح علماء الرياضيات لإيجاد قاعدة بسيطة وسريعة تضمن لك تحقيق مبلغ جيد من المال، حتى دون معرفة المستقبل. السؤال الكبير كان: هل يمكننا إيجاد استراتيجية تضمن أن تكون "جيدة بما يكفي" (كسر ثابت من أفضل نتيجة ممكنة) بغض النظر عن طول مدة الحجوزات أو مدى دهاء العملاء؟

هذه الورقة البحثية التي أعدها مينغ هو وتونغوين وو تتناول هذا السؤال تحديداً. لقد بحثا في طريقتين مختلفتين لسلوك العملاء. في السيناريو الأول، الأمر يشبه تذكرة قطار: إما أن تقبل الراكب وتخصص له مقعداً محدداً، أو ترفضه. وفي السيناريو الثاني الأكثر تعقيداً، الأمر يشبه فندقاً صغيراً أو "Airbnb": حيث تعرض للعميل قائمة بالغرف المتاحة، وهو يختار الغرفة التي تعجبه أكثر بناءً على تفضيلاته الخاصة. طور المؤلفان خوارزميات حاسوبية جديدة وسريعة للتعامل مع هذه المواقف. وقد أثبرا أن أساليبهما تضمن رياضياً تحقيق ما لا يقل عن 63.2% من الأموال التي كان سيحققها المخطط "المثالي" الذي يعرف المستقبل في حالة تذكرة القطار البسيطة. وعندما يتاح للعملاء حق الاختيار من قائمة، تنخفض هذه النسبة إلى 27.1%. وحتى عندما تكون مدة الإقامة عشوائية وغير متوقعة، لا تزال خوارزمياتهما تنجح في تأمين حصة جيدة من الإيرادات المحتملة، مما يثبت أنك لست بحاجة لأن تكون عرافاً لتدير عملاً مربحاً — أنت فقط بحاجة إلى الرياضيات الصحيحة.

أحجية المقاعد المفقودة

فكر في المشكلة كأنها أحجية "بازل" ضخمة ومتغيرة، حيث تستمر القطع في تغيير شكلها. في عالم "القبول أو الرفض" (مثل مثال القطار)، في كل مرة يطلب فيها راكب مقعداً من المحطة (أ) إلى المحطة (ف)، عليك أن تقرر فوراً: "هل أعطيه المقعد 101؟ أم أدخره لشخص قد يريده لاحقاً؟". إذا منحته إياه مبكراً جداً، فقد تفوت فرصة حجز لمجموعة كبيرة. وإذا تمسكت به بشدة، فقد تترك المقعد فارغاً للأبد.

أدرك المؤلفان أنه بدلاً من محاولة التنبؤ بالمستقبل، يمكنك استخدام خدعة ذكية تسمى "الاسترخاء السائل" (Fluid Relaxation). تخيل أن المقاعد ليست كتلًا صلبة بل سائل يتدفق. يمكنك حساب مقدار هذا "السائل" من المقاعد الذي يجب حجزه لأنواع مختلفة من المسافرين بناءً على الاحتمالات. ثم بنيا خوارزمية "الاقتراح والاستبعاد" (Proposal-Discarding). إليك كيف تعمل باللغة البسيطة:

قبل أن يقترب العميل حتى من المنصة، يقوم الحاسوب بمحاكاة سيناريو "ماذا لو". يسأل كل مقعد متاح: "إذا ظهر عميل من هذا النوع، هل ستكون مستعداً لاستقباله؟". يرمي كل مقعد عملة معدنية بناءً على الرياضيات ليقرر ما إذا كان سيرفع يده. إذا رفعت مقاعد متعددة أيديها، يختار الحاسوب المقعد الذي سيحقق أكبر قدر من المال. وإذا لم يرفع أحد يده، يتم الاعتذار للعميل بلباقة.

ولكن إليك التحول السحري: حتى لو لم يتم اختيار مقعد ما للعميل الحقيقي، يتظاهر الحاسوب بأنه قد استُخدم بالفعل. يقوم بتحديد ذلك المقعد كـ "مشغول" في محاكاته الداخلية. هذا يحافظ على نزاهة الرياضيات ويمنع النظام من أن يصبح جشعاً للغاية. حالة "الانشغال الافتراضي" هذه تضمن عدم قيام الخوارزمية بالحجز المزدوج للمقاعد عن طريق الخطأ في حساباتها، مما يحافظ على استقلالية الاحتمالات ويجعل الرياضيات قابلة للحل.

عندما يختار العملاء

الجزء الثاني من الورقة البحثية أكثر متعة لأنه يضيف عنصر الاختيار البشري. تخيل فندقاً لا تكتفي فيه بتعيين غرفة للضيف، بل تعرض عليه قائمة بثلاث غرف متاحة: واحدة بإطلالة، وأخرى بشرفة، وثالثة أرخص ثمناً. يختار الضيف بعد ذلك الغرفة التي يفضلها. هذا هو سيناريو "القائم على نموذج الجذب الأساسي" (BAM-based).

هذا الأمر أكثر صعوبة لأن اختيار الضيف يعتمد على القائمة الكاملة التي تعرضها عليه. إذا عرضت عليه غرفة فاخرة، فقد يختارها. إذا عرضت عليه غرفة فاخرة وغرفة رخيصة، فقد يختار الرخيصة. اضطر المؤلفان لابتكار طريقة جديدة لربط خيارات الحاسوب "الافتراضية" بخيارات الضيف الحقيقية. استخدموا تقنية تسمى "الاقتران العشوائي" (Randomized Coupling). فكر في الأمر كخدعة ساحر: يولد الحاسوب قائمة عشوائية من الغرف لتقديمها، لكنه يفعل ذلك بطريقة تضمن رياضياً أن يتوافق اختيار الضيف مع خطة الحاسوب، رغم أن الضيف يتخذ خياراً حراً.

لقد وجدا أنه على الرغم من أن هذا الاختيار يزيد من التعقيد، إلا أن خوارزميتهما لا تزال تعمل. في سيناريو "القائمة"، أثبتا أن سياستهما تحقق ما لا يقل عن 27.1% من الإيرادات المثالية. وإذا كانت مدة الإقامة عشوائية أيضاً (مثل ضيف يقول: "قد أبقى يومين، أو ربما خمسة أيام")، فإن الضمان ينخفض قليلاً، لكنه يظل إيجابياً: 17.1% لسيناريو القائمة و 39.9% لسيناريو القطار البسيط.

لماذا هذا مهم؟

قبل هذه الورقة البحثية، كانت أفضل الضمانات لهذا النوع من المشكلات ضعيفة جداً. كانت تعتمد على طول مدة الحجوزات. إذا حجز الناس لرحلات طويلة جداً، فإن الضمان يتقلص ليصبح شبه معدوم. كان الأمر يشبه القول: "استراتيجيتنا رائعة، إلا إذا بقيت لمدة شهر، فحينها ستصبح عديمة الفائدة".

أثبت المؤلفان أن هذا ليس صحيحاً. لقد أثبتا أنه يمكنك الحصول على ضمان "بمعامل ثابت" (Constant-factor guarantee). وهذا يعني أنه بغض النظر عن طول مدة الإقامة، وبغض النظر عن عدد الموارد التي تملكها، فإن استراتيجيتك ستستحوذ دائماً على نسبة ثابتة وصحية من أفضل مبلغ ممكن. كما أظهرا أنه لا يمكنك فعل أفضل من 63.2% في الحالة البسيطة (مما يثبت أنه من "الصعب" الاقتراب من 100%)، مما يعني أن حلهما قريب جداً من أفضل إجابة يمكننا أن نأمل بها.

باختصار، لقد أخذوا مشكلة واقعية فوضوية وغير متوقعة وأعطوها هيكلاً رياضياً صلباً. لقد أثبتوا أنه باستخدام الخوارزمية الصحيحة، لست بحاجة لأن تكون مثالياً لتكون مربحاً؛ أنت فقط بحاجة لأن تكون ذكياً بما يكفي لتعرف متى تقول "نعم"، ومتى تقول "لا"، وكيف تترك العملاء يختارون دون أن تخسر مالك.