Asansör algoritmaları çağrınıza hangi kabinin geleceğine nasıl karar veriyor

john.fun/elevators adresinde yayımlanan bir yazı, çağrı düğmesine basmakla kabinin gelmesi arasında ne olduğunu inceliyor ve hangi asansörün hangi yolcuya hizmet edeceğine karar veren algoritmaları karşılaştırıyor. Vardığı sonuç sezgiye aykırı: birçok binada en basit kurallar en kısa bekleme sürelerini üretiyor.

Tek kabin: SCAN ve LOOK

En basit algoritma olan SCAN 1961'de patentlendi. Kabin lobiden başlar, en üst kata kadar çıkar, sonra yön değiştirip inerken yolcuları alır ve bırakır. LOOK ise çoğu yolcunun gerçekte deneyimlediği varyanttır: kabin yalnızca en yüksek çağrıya kadar çıkar ve ardından geri döner.

Kabinleri RSR ile puanlamak

Birden fazla kabin olduğunda en temel sistem, her yeni çağrıyı en yakın asansöre atayan merkezi bir zamanlayıcı kullanır. Daha gelişmiş bir yaklaşım, Otis'in Relative System Response (RSR) yöntemidir: her kabine, yolcuyu almak için ne kadar uygun olduğuna dair bir puan verir ve düşük puan daha iyidir. Puan; yolcuya ulaşma tahmini süresini, kabindeki yük cezasını, aynı yönde kabin yığılması cezasını, yön uyumu bonusunu, yakında bekleyen boş kabin bonusunu ve düşük yük bonusunu birleştirir.

RSR ayrıca her beş saniyede yeniden optimizasyon yapar; yani başta bir kabine atanan yolcu, o kabin gecikirse başka bir kabine yönlendirilebilir. Yazıya göre trafiği akıcı tutan şey tam da bu yeniden dengeleme adımıdır.

Beklemeyi ölçmek ve basitliğin kazanması

Yazı, bekleme süresinin ortalamayla değil dağılımla değerlendirilmesi gerektiğini savunuyor: iki dakikalık bir p90, yolcuların yüzde 90'ının iki dakika veya daha az beklediğini; bir dakikalık p50 ise bekleme sürelerinin yarısının bir dakikanın altında olduğunu gösterir. Yolcular ortalamayı değil en kötü durumları hatırlar, bu yüzden dağılımın kuyruğu önemlidir.

Yazıdaki karşılaştırmalar, yolcu akışı arttıkça LOOK'un RSR'den daha iyi performans gösterebildiğini ortaya koyuyor: kabinler doluyken ve neredeyse her katta dururken ek puanlama kuralları daha az fark yaratıyor. LOOK ayrıca her grupta daha az kabin bulunan küçük binalarda RSR'yi geçme eğiliminde. Hedefe göre dağıtım — girmeden önce hangi kabine bineceğinizi söyleyen kiosklar — çok yüksek binalar ve grup başına sekiz veya daha fazla kabin dışında, bekleme süreleri açısından geleneksel yukarı-aşağı düğmelerinden genellikle daha kötü. Bunun nedeni, kioskun sabit bir atama dayatması; oysa geleneksel sistem her beş saniyede yeniden optimizasyon yapabiliyor. Sayfada tüm parametreleri açık bir etkileşimli simülasyon yer alıyor.