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

يتناول مقال منشور على john.fun/elevators ما يحدث بين الضغط على زر النداء ووصول الكابينة، ويقارن الخوارزميات التي تحدد أي مصعد يخدم أي راكب. وتأتي النتيجة مخالفة للحدس: في كثير من المباني تحقق القواعد الأبسط أقصر أوقات انتظار.

كابينة واحدة: SCAN وLOOK

سُجلت براءة الخوارزمية الأبسط، SCAN، عام 1961. تبدأ الكابينة من الطابق الأرضي وتصعد إلى الطابق الأعلى ثم تنعكس وتهبط، وهي تلتقط الركاب وتُنزلهم في الطريق. أما LOOK فهي النسخة التي يختبرها معظم الركاب فعلياً: تصعد الكابينة إلى أعلى طلب مسجل فقط ثم تعود.

تقييم الكابينات بنظام RSR

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

كما يعيد RSR التحسين كل خمس ثوانٍ، بحيث يمكن تحويل راكب خُصص في البداية لكابينة ما إلى كابينة أخرى إذا تأخرت الأولى. وبحسب المقال، فإن خطوة إعادة الموازنة هذه هي ما يحافظ على انسيابية الحركة.

قياس الانتظار ولماذا يفوز البسيط

يرى المقال أن وقت الانتظار ينبغي تقييمه كتوزيع لا كمعدل: فقيمة p90 البالغة دقيقتين تعني أن 90 في المئة من الركاب ينتظرون دقيقتين أو أقل، وقيمة p50 البالغة دقيقة واحدة تعني أن نصف أوقات الانتظار أقل من دقيقة. والركاب يتذكرون أسوأ الحالات لا المعدل، ولذلك يهم ذيل التوزيع.

تُظهر المقارنات في المقال أنه مع ارتفاع معدل تدفق الركاب قد يتفوق LOOK على RSR: فحين تكون الكابينات ممتلئة وتتوقف في كل طابق تقريباً تصبح قواعد التقييم الإضافية أقل تأثيراً. كما يميل LOOK إلى التفوق على RSR في المباني الصغيرة التي تضم كابينات أقل في كل مجموعة. أما التوزيع حسب الوجهة — عبر أكشاك تخبرك أي كابينة تستقل قبل الدخول — فهو عموماً أسوأ لأوقات الانتظار من أزرار الصعود والهبوط التقليدية، باستثناء المباني الشاهقة جداً التي تضم ثماني كابينات أو أكثر في المجموعة. والسبب أن الكشك يفرض تخصيصاً ثابتاً، بينما يستطيع النظام التقليدي إعادة التحسين كل خمس ثوانٍ. وتتضمن الصفحة محاكاة تفاعلية بجميع المعاملات.