כיצד אלגוריתמים של מעליות מחליטים איזו מעלית תגיע לקריאה

מאמר שפורסם ב-john.fun/elevators בוחן מה קורה בין לחיצה על כפתור הקריאה לבין הגעת התא, ומשווה את האלגוריתמים שקובעים איזו מעלית תשרת איזה נוסע. המסקנה מנוגדת לאינטואיציה: בבניינים רבים דווקא הכללים הפשוטים ביותר מניבים את זמני ההמתנה הקצרים ביותר.

תא אחד: SCAN ו-LOOK

האלגוריתם הפשוט ביותר, SCAN, נרשם כפטנט ב-1961. התא מתחיל בלובי, עולה עד הקומה העליונה, ואז מתהפך ויורד, אוסף ומוריד נוסעים בדרך. LOOK הוא הווריאציה שרוב הנוסעים חווים בפועל: התא עולה רק עד הקריאה הגבוהה ביותר ואז מסתובב.

ניקוד תאים באמצעות RSR

כשיש כמה תאים, המערכת הבסיסית ביותר משתמשת במתזמן מרכזי שמקצה כל קריאה חדשה למעלית הקרובה ביותר. גישה מתוחכמת יותר היא Relative System Response (RSR) של אוטיס, שנותנת לכל תא ציון על מידת התאמתו לאיסוף הנוסע — ככל שהציון נמוך יותר, כך טוב יותר. הציון משלב את זמן ההגעה המשוער לנוסע עם קנס על עומס בתא, קנס על הצטברות תאים באותו כיוון, בונוס על התאמת כיוון, בונוס לתא פנוי בקרבת מקום ובונוס לעומס נמוך.

RSR גם מבצע אופטימיזציה מחדש כל חמש שניות, כך שנוסע שהוקצה תחילה לתא אחד יכול לעבור לתא אחר אם הראשון מתעכב. לפי המאמר, שלב האיזון הזה הוא ששומר על זרימת התנועה.

מדידת המתנה, ולמה הפשטות מנצחת

המאמר טוען שיש לשפוט את זמן ההמתנה כהתפלגות ולא כממוצע: p90 של שתי דקות פירושו ש-90 אחוז מהנוסעים ממתינים שתי דקות או פחות, בעוד p50 של דקה פירושו שמחצית מההמתנות קצרות מדקה. נוסעים זוכרים את המקרים הגרועים ולא את הממוצע, ולכן הזנב של ההתפלגות חשוב.

הבדיקות במאמר מראות שככל שקצב התנועה עולה, LOOK יכול להשיג תוצאות טובות יותר מ-RSR: כשהתאים מלאים והם עוצרים כמעט בכל קומה, כללי הניקוד הנוספים פחות משמעותיים. LOOK גם נוטה לנצח את RSR בבניינים קטנים עם פחות תאים בכל קבוצה. הקצאה לפי יעד — קיוסקים שמראים לך לאיזה תא להיכנס עוד לפני הכניסה — בדרך כלל גרועה יותר לזמני ההמתנה מאשר כפתורי מעלה ומטה מסורתיים, למעט בבניינים גבוהים מאוד עם שמונה תאים או יותר בכל קבוצה. הסיבה היא שהקיוסק כופה הקצאה קבועה, בעוד המערכת הרגילה יכולה לבצע אופטימיזציה מחדש כל חמש שניות. בעמוד מופיעה סימולציה אינטראקטיבית עם כל הפרמטרים.