A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

ملخص تقني: طريقة حوسبية لحل مشكلة التزويد المشترك العشوائية في الأبعاد العالية

صياغة المشكلة
تتناول الورقة مشكلة التزويد المشترك العشوائية (SJRP)، وهي تحدٍ كلاسيكي في إدارة المخزون يتضمن تنسيق أنظمة مخزون متعددة العناصر حيث يتم تكبد تكلفة تزويد ثابتة بشكل مشترك للعناصر التي تُطلب معاً. في الصيغة ذات الزمن المنفصل التي يتم النظر فيها، يقوم مدير المستودع بمراجعة مستويات المخزون بشكل دوري ويقرر ما إذا كان سيضع طلبيات لمجموعات فرعية من عدد $d$ من العناصر. يواجه النظام طلبات عشوائية، وتكاليف حيازة خطية، وعقوبات تأخير (نقص في المخزون). والهدف هو تقليل إجمالي التكلفة المتوقلة المخصومة على مدى أفق زمني غير محدود.

تكمن الصعوبة الجوهرية في "لعنة الأبعاد". ففي ظل وجود تكاليف تزويد ثابتة غير صفرية، تصبح القرارات على مستوى العنصر مترابطة، مما يؤدي إلى نمو مساحات الحالة والقرار المرتبطة بـ "عملية ماركوف لاتخاذ القرار" (MDP) بشكل أسي مع عدد العناصر ($d$). وبناءً على ذلك، تصبح تقنيات البرمجة الديناميكية القياسية غير قابلة للتطبيق حوسبياً في الإعدادات عالية الأبعاد (على سبيل المثال، $d \ge 50$)، وقد اعتمدت الأدبيات الحالية إلى حد كبير على سياسات استدلالية (heuristics) ذات ضمانات نظرية محدودة حول المثالية.

المنهجية
للتغلب على هذه العوائق الحوسبية، يقترح المؤلفون طريقة حوسبية مبتعة تعتمد على المحاكاة، تجسر الفجوة بين التحكم في المخزون في الزمن المنفصل ونظرية التحكم بالنبضات (impulse control theory) في الزمن المستمر والتعلم العميق.

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

2. التمثيل الاحتمالي عبر المعادلات التفاضلية العشوائية الخلفية (BSDEs) المقيدة: على عكس طرق الـ BSDE العميقة القياسية التي تعتمد على المساواة شبه المؤكدة، يتم توصيف دالة القيمة لهذه المشكلة كأقل حل لـ BSDE مقيد. يؤدي هذا إلى هوية عشوائية تتضمن "عدم مساواة" شبه مؤكد بدلاً من المساواة. وتحديداً، دالة القيمة $V(x)$ هي الحد الأعلى للقيم $v$ التي تحقق شرط هدف عشوائي يتضمن العملية المرجعية، والتكاليف الجارية، وتكاليف القفز.

3. المحلل باستخدام الشبكة العصبية العميقة: يطور المؤلفون خوارزمية حوسبية لحل هذه الـ BSDE المقيدة باستخدام الشبكات العصبية العميقة.

   • دالة الخسارة: تم بناء دالة خسارة مبتكرة للتعامل مع قيد عدم المساواة، وهي تتضمن حداً جزائياً لانتهاكات عدم المساواة العشوائية، موازناً بمعامل جزاء قابل للضبط $\beta$.
   • العملية المرجعية: تُستخدم عملية مرجعية مصممة بعناية (سياسة طلب وصول إلى مستوى معين عشوائية مدفوعة بعملية بواسون) لتوليد مسارات العينة. تم هندسة هذه العملية لتحقيق التوازن بين الاستكشاف والاستغلال، مما يضمن تدريب الشبكات العصبية على المناطق ذات الصلة من مساحة الحالة.
   • استراتيجية التدريب: لضمان الاستقرار، يستخدم المؤلفون جدولاً مشتركاً لمعامل الجزاء $\beta$ ومعدل التعلم. يتم زيادة الجزاء تدريجياً مع خفض معدل التعلم، مما يسمح للشبكة أولاً بتعلم الهيكل العام ثم فرض قيود عدم المساواة بصرامة.

4. استخراج السياسة: بمجرد تقريب دالة القيمة $V$ وتدرجها $\nabla V$ باستخدام الشبكات العصبية، يتم اشتقاق سياسة قابلة للتنفيذ. تتحقق السياسة من "شرط عدم اتخاذ إجراء" المستمد من معادلة هاملتون-جاكوبي-بلاك (HJB). إذا تم انتهاك الشرط، يتم وضع طلب. ويتم تحديد متجه "الوصول إلى المستوى المطلوب" عن طريق تقليل مجموع دالة القيمة المقربة وتكلفة الطلب، وهي خطوة يمكن حسابها مسبقاً بكفاءة.

المساهمات الرئيسية

• القابلية للتوسع في الأبعاد العالية: نجحت الطريقة في حل مشكلة SJRP لأبعاد تصل على الأقل إلى 50 (أي 50 صنفاً)، وهو نطاق تكون فيه الحلول المثلى التقليدية القائمة على MDP غير قابلة للتطبيق.
• تصميم مبتكر لدالة الخسارة: قدمت الورقة دالة خسارة محددة وجدول تدريب مصمم خصيصاً لإطار الـ BSDE المقيد المطلوب للتحكم بالنبضات، مما يعالج تحدي عدم المساواة شبه المؤكدة التي لا تتعامل معها طرق الـ BSDE العميقة القياسية.
• هندسة العملية المرجعية: تم تسليط الضوء على تصميم العملية المرجعية ذات القفزات المعتمدة على الحالة كابتكار حاسم لضمان التدريب الفعال وتغطية مساحة الحالة ذات الصلة.
• التنفيذ: يقدم المؤلفون مساراً كاملاً من تقريب المشكلة إلى استخراج السياسة، بما في ذلك استراتيجيات ضبط المعلمات الفائقة (hyperparameters) بالتفصيل والنتائج الحوسبية.

النتائج
تم تقييم سياسة الشبكة العصبية (NN) المقترحة على 43 مسألة اختبار بأبعاد 2 و12 و50، مع تباين في تقلب الطلب (منخفض، متوسط، مرتفع) وهياكل التكلفة.

• الأبعاد المنخفضة ($d=2$): تمت مقارنة سياسة الشبكة العصبية بالسياسة المثلى الحقيقية المستمدة من تقنيات حل MDP القياسية. تظهر النتائج أن سياسة الشبكة العصبية تعمل ضمن نطاق 1% من التكلفة المثلى وتتبع بدقة هندسة حدود القرار المثلى.
• الأبعاد العالية ($d=12$ و $d=50$): نظراً لأن الحلول المثلى غير قابلة للتطبيق، تمت مقارنة سياسة الشبكة العصبية مع أحدث الاستدلالات (heuristics): سياسات المراجعة الدورية $(R, S)$ و $(Q, S)$ والسياسات الهجينة $(R, Q, S)$ وسياسات "الطلب الممكن" (can-order) والسياسات المستقلة $(s, S)$.
  • في 12 بُعداً، طابقت سياسة الشبكة العقب أو تفوقت على أفضل نموذج استدلالي في جميع الحالات. وفي حالات التباين المتوسط والمرتفع، غالباً ما تفوقت على أفضل الاستدلالات بفارق كبير (على سبيل المثال، تحسن يصل إلى 28% عن سياسة $(R, S)$ في حالات معينة ذات تباين عالٍ).
  • في 50 بُعداً، تفوقت سياسة الشبكة العصبية باستمرار على أفضل الاستدلالات المتاحة في جميع حالات الاختبار، حيث وصلت فجوات الأداء إلى 5.59%.
• الكفاءة الحوسبية: يتوسع وقت التدريب بشكل متواضع مع البعد (حوالي 4 ساعات لـ 50 بُعداً على وحدة معالجة رسوميات واحدة)، متجنباً النمو الأسي المعتاد في الطرق القائمة على الشبكات (grid-based methods).

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