Asansör Sevk Algoritmaları

• Asansör işletimi, basit bir çağrıya yanıt vermekten ibaret değil; kabin sayısı, yolcu akışı, yük ve hareket yönünü birlikte dikkate alan bir sevk optimizasyonu problemidir
• Tek kabin için SCAN en üst katta yön değiştirirken, LOOK gerçek talebin olduğu en yüksek katta geri döner ve genel işletim beklentisine daha yakındır
• Birden fazla kabini ele alan RSR (Relative System Response), tahmini varış süresi ve yük gibi unsurları puanlar; her 5 saniyede sevki yeniden optimize ederek geciken bir kabinin yolcularını başka bir kabine yönlendirebilir
• Kabinler sürekli doluysa veya yolcu akışı kat kat durmayı gerektirecek kadar yüksek ve kabin sayısı azsa, karmaşık RSR yerine basit LOOK daha iyi olabilir
• Hedef katın önceden girildiği hedef sevki (Destination Dispatch) daha fazla bilgi sağlar ancak atanmış kabini değiştirmek zordur; bu nedenle çok yüksek binalar ve 8’den fazla kabinli gruplar gibi bazı örnekler dışında bekleme süresi genelde geleneksel yukarı/aşağı düğmelerinden daha uzundur

---

Tek kabin nerede yön değiştirir?

• 1961’de patenti alınan SCAN, lobiden başlayıp en üst kata kadar çıkar, ardından yön değiştirip aşağı iner; güzergâhındaki yolcuları alır ve indirir
• LOOK, en üst kata mutlaka gitmez; yalnızca talep edilen en yüksek kata kadar çalışıp sonra geri döner
• İnsanların genel olarak bildiği ve beklediği asansör çalışma biçimi LOOK’a daha yakındır

Birden fazla kabin için temel sevk

• Birden fazla asansör varsa hangi kabinin hangi çağrıyı üstleneceğini ayarlamak gerekir
• Temel sistemlerde merkezi zamanlayıcı, her kabinin duracağı katları belirler ve yeni çağrıyı en yakın kabine atar
• Ancak yalnızca mesafeye dayalı sevk, yakındaki kabinin dolu olması gibi durumları yeterince yansıtmakta zorlanır

Bekleme süresini değerlendirme yöntemi

• Asansör algoritmalarının en sezgisel değerlendirme metriği, çağrıdan kabinin varışına kadar geçen bekleme süresidir
• Basitçe, kabinin 30 saniye veya 90 saniye içinde geldiği oran ölçülebilir
• Daha titiz değerlendirme için binlerce seferin bekleme süreleri toplanıp dağılım ve histogram incelenir
  • p90’ın 2 dakika olması, yolcuların %90’ının 2 dakika içinde beklediği anlamına gelir
  • p50’nin 1 dakika olması, çağrıların yarısında kabinin 1 dakika içinde geldiği anlamına gelir
• Yolcular, ortalama bekleme süresinden çok, olağandışı derecede uzun bekledikleri p90 örneklerini daha güçlü hatırlama eğilimindedir

Yolcu akışı zamana göre nasıl değişir?

• Büyük ofis binalarında sabahları hareketin büyük kısmı lobiden üst katlara doğrudur
• Akşamları iş çıkışı nedeniyle üst katlardan aşağı yönlü akış baskın hale gelir
• Öğle saatlerinde yukarı ve aşağı yönler karışır; diğer zamanlarda ise katlar arası hareket daha fazladır
• Bekleme süresi dağılımı, zaman dilimine ve trafik desenine göre büyük ölçüde değişir; özellikle sabah işe geliş saatlerinin istatistikleri kötüdür

RSR hangi kabini seçer?

• Otis’in RSR (Relative System Response) sistemi, her kabinin yolcu almak için ne kadar uygun olduğunu puanlar; puan ne kadar düşükse uygunluk o kadar yüksektir
• Biniş puanı birden fazla unsurun birleşimiyle hesaplanır
  • Çağrı katına tahmini varış süresi
  • Kabindeki yolcu sayısına göre yük cezası
  • Aynı yönde aynı kata giden bir kabin zaten varsa uygulanan kümelenme önleme cezası
  • Hareket yönü eşleşme bonusu
  • Çağrı katının iki kat yakınında bulunan boş kabin bonusu
  • Düşük yük bonusu
• Kümelenme önleme (anti-bunching), başka bir kabin zaten aynı yönde aynı kata gidiyorsa ek atamayı sınırlar
• RSR, her 5 saniyede tüm sevki yeniden optimize eder
  • Kabin A gecikirse, başlangıçta A’nın alması planlanan yolcular kabin B’ye yeniden atanabilir
  • Bu sürekli yeniden optimizasyon, yolcu akışını sorunsuz hale getirmenin temelidir

LOOK ile RSR arasındaki performans farkı

• Bekleme süresi analiz aracı kullanılarak LOOK ve RSR’nin 30 saniye ve 90 saniye içinde varış oranları karşılaştırılabilir
• Yolcu yoğunluğu arttıkça LOOK, RSR’nin önüne geçmeye başlar
  • Kabinler her zaman doluysa ve her katta duruyorsa, RSR’nin ek kurallarının sağladığı etki azalır
• Kabin grubu başına asansör sayısının az olduğu küçük binalarda da LOOK’un RSR’den daha iyi olma eğilimi vardır; basit yöntem daha uygun olabilir
• Bekleme süresinin yanı sıra, bindikten sonra hedef kata kadar geçen seyahat süresi de ölçülebilir
  • LOOK ve RSR bu metrikte de farklı özellikler gösterir, ancak somut karşılaştırma ele alınmaz

Hedef sevki, daha fazla bilgiye rağmen neden dezavantajlıdır?

• Hedef sevki, her kattaki kiosktan önce hedef kat girildiğinde binilecek asansörü atayan bir yöntemdir
• Optimizasyon sistemi, kabin gelmeden önce her yolcunun hedefini bilebilir; ancak bekleme süresi genellikle geleneksel yukarı/aşağı düğmesi yönteminden daha uzundur
• Çok yüksek binalarda kabin grubu başına 8 veya daha fazla asansör olduğu durumlar gibi kiosk yönteminin avantajlı olduğu istisnalar da vardır
• Performans düşüşünün temel nedeni sevkin katılığıdır
  • Geleneksel yöntem, her 5 saniyede kabin rotalarını ve yolcu atamalarını yeniden optimize edebilir
  • Hedef sevkinde yolcu, ilk atanan kabine binmek zorundadır
  • Çağrıdan 30 saniye sonra işletim koşulları değişse bile atanmış kabin esnek biçimde değiştirilemez
• Hedef bilgisi gibi ek bilginin faydasından daha büyük olan, yeniden atama esnekliğini kaybetmenin maliyetidir

Simülasyonda ayarlanabilen öğeler ve kapsam

• Genel simülasyonda kat sayısı, kabin sayısı ve dakika başına yolcu akışı ayarlanarak 30 saniye ve 90 saniye içinde varış oranları görülebilir
• Gerçek asansör algoritmalarında daha fazla unsur dikkate alınır; burada ele alınan kapsam tüm alanın yalnızca bir bölümüdür
• Çağrı düğmesi girişi iletilir, ancak asansör birden fazla işletim koşulunu birlikte hesapladığı için hemen gelmeyebilir

[GN⁺]

Hacker News görüşleri

• Son yarım yüzyılın yaklaşık yarısında asansörler bilgisayar olmadan, yalnızca rölelerle kontrol ediliyordu; bu tür algoritmalar da kablolanmış mantık devreleriyle uygulanıyordu
  Devre şemaları gibi ilginç ayrıntılar Otis'in eski patentlerinde görülebilir

• Lisede bilgisayar bilimi dersinde birkaç asansör algoritması simülasyonunu kişisel proje olarak uygulamıştım
  Döner sabit diskler, dikey yerine milin etrafına sarılmış çok uzun bir asansöre benzer ve SCAN aslında bir disk zamanlama algoritmasıdır: https://en.wikipedia.org/wiki/Elevator_algorithm

  • Üniversitede de mikrodenetleyici ve LED vb. kullanarak benzer bir proje yapmıştım; çok eğlenceliydi

• Varış katları rastgele belirlendiği için hedef kat rezervasyonlu sevkin genel olarak kötü çıktığını merak ediyorum
  Gerçek binalarda çoğu kişi zemin kattan değil, zemin kata gider; zemin katta ise aynı katta çalışan kişiler öğle arasında birlikte çıkıp yine birlikte aynı kata dönme eğilimindedir. Hedef kat rezervasyonlu sevk, aynı hedefe giden büyük grupları bir araya toplayabildiği için bu tür kalıplarda avantajlıdır

  • Bu varsayım oteller için daha da uygunsuz. Sabahları hareket sadece lobi ile odalar arasında olmaz; insanlar kahvaltıya inip tekrar çıkar, sonra yine iner, yani çift yönlü trafik oluşur
    Bazı otellerdeki kiosk sistemi, sabah kahvaltı yoğunluğuna göre kullanıcı arayüzünü de değiştirir
  • Hedef kat rezervasyonlu sevk kullanan kruvaziyer gemileri de çok daha konforluydu. Eski algoritmaları kullanan gemilerde yoğun saatlerde beklemek işkence ama bu sayede merdivenleri daha çok kullanıyorsun
  • Üst katlardaki bir kişinin, bir iki kat yukarı ya da aşağı gitmektense zemin kata dönme olasılığı çok daha yüksektir ama simülasyondaki bekleyen yolcular bunu düzgün yansıtmıyor gibi görünüyor
    Öğle yemeğine giden ya da dönen insanların kümeleşme etkisi de gerçekten vardır ve sabah ya da akşamdan çok gün ortasında belirgindir
  • Zemin kattan aynı hedefe büyük grupların gitmesi, hedef kat rezervasyonlu sevkin daha iyi olmasının en büyük nedenlerinden biri bence
    Ofisler veya oteller bu sisteme geçtikten sonra bekleme süresinin ciddi biçimde azaldığını söyleyen yazılar da var
  • Ölçütün yolculuk süresi değil de bekleme süresi olmasıyla ilgili olup olmadığını merak ediyorum. Hedef kat rezervasyonlu sevk, yolculuk sırasında gereksiz durakları azaltır
    Yakın zamanda ziyaret ettiğim yeni bir binada da bu sistem kullanılıyordu. Üniversitede elektrik mühendisliği okuyan bir ev arkadaşım, çağrı düğmeleri, motor ve konum algılaması için siyah karelerle işaretlenmiş şeffaf bir disk bağlayarak breadboard üzerinde bir asansör devresi yapmıştı; muhtemelen basit bir algoritmaydı

• Asansör zamanlamasıyla ilk kez tanışıyorsanız bu oyunu öneririm: https://play.elevatorsaga.com/

  • Temel varsayım basit ama seviyeler ilerledikçe tatmin edici biçimde zorlaşıyor ve biraz rastgele arıza da olduğu için daha meydan okuyucu hale geliyor. Keşke böyle daha çok oyun olsa
  • Çok iyi görünüyor ama yine de https://en.wikipedia.org/wiki/Elevator_Action oyununu daha çok seviyorum
  • Harika, ama benim için en iyi asansör zamanlama oyunu SimTower
  • Konferans yapılan bir otelde asansör beklerken her seferinde bu oyuna geri dönüyorum
  • Kendi asansör zamanlayıcını programladığın bir oyunun eğlenceli olup olmayacağını hep merak etmiştim ve kimsenin yapmadığını sanıyordum; yanılmış olmaktan memnunum

• iOS·Android için asansör kontrolü ve otomasyon oyunu Sky Lobby'yi geliştirirken bu konu üzerine çok düşündüm
  Oyuncunun beklediği harekete en yakın olan LOOK benzeri bir algoritma benimsedim, ancak seçim belirsiz olduğunda uzun süredir bekleyen katlara öncelik vererek oyunda önemli olan p90'ı iyileştirdim. Ama iki katı aynı anda hizmet veren çift katlı asansörler, şaftlar arası aktarma katları ve ekspres şaftlar eklenince en iyi ya da en sezgisel algoritmanın ne olduğu çok daha belirsiz hale geliyor. Bu gerçek bir sistem değil oyun olduğu için, yeterince iyi bir sezgisel yöntem bulup oyuncular hoşlanmadığında işletim planını elle geçersiz kılmalarına izin verdim; çoğu memnun kaldı

• Asansör beklerken her seferinde yolcunun binmesi ve varışına kadar geçen bekleme süresini en aza indiren bir algoritma yapmanın ne kadar baş ağrıtıcı olacağını düşünüyorum
  Bazen bunu yapanların insanları bilerek daha uzun bekleten şeytani sadistler olup olmadığını bile düşünüyorum

  • Asansörün yolcu yükünü de hesaba katması iyi olurdu
    Büyük bir konferanstan sonraki sabah herkes aşağı inmeye çalışıyordu ama tıklım tıklım dolu kabin her katta düzenli olarak duruyordu. 10 kişilik bir asansör zaten 10 kattaki çağrı yolcularını almışsa, her katta “yer yokmuş, sonrakine bineyim” döngüsünü yaşatmak yerine doğrudan zemin kata gidip 5 dakika kazandırabilmeli. Özellikle 2. katta hareket kısıtlılığı olan birinin uçağa yetişmesi gerekiyorsa bu ciddi bir sorun olur
  • Başka ekipmanlarla asansörleri entegre eden harici entegrasyon yazılımları birkaç kez geliştirdim
    Tüm asansörlerin konumunu ve hareketini görünce çizelgenin şaşırtıcı derecede sıkı olduğunu fark ediyorsunuz. Lobide beklemek sonsuz gibi geliyor ama sevk açısından etkinlik hiç durmuyor ve binanın kullanıldığı saatlerde asansörler neredeyse hiç boş kalmıyor. Sadece durum panelini izlemek bile ilginç. Ayrıca asansör teknisyeni “sabah erken buluşalım” dediğinde, bu genelde sabah 4 civarı demektir; insanlar işe gelmeden önce işi bitirmeye çalışırlar
  • Asansör zamanlama yazılımı aptal olduğu için değil, bu işe zaten muazzam düşünce harcandığı için böyle
    Asansörler pahalıdır ve bina sahipleri dürtüsel biçimde fazla yatırım yapmaz; bu yüzden genelde beklenen talebi karşılayacak kadar, bazen de ondan az, asgari asansör sayısı kurulur
  • Bekleme süresinin yanı sıra aşınma ve enerji tüketimi gibi amaç fonksiyonlarını da optimize ediyor olabilirler

• Dört asansörün üstünde planlanan durak katları ayrı ayrı gösteriliyor ve beklerken bile asansör ile kat ataması değiştiriliyor, bu da sesli olarak bildiriliyor. En iyi sevki mümkün kılmak için yapılmış bir özellik gibi görünüyor

• Asansörlerdeki en büyük sorun algoritmadan çok, insanların gitmek istedikleri yöne göre yukarı-aşağı çağrı düğmesine basma mantığını anlamaması
  “Daha hızlı gelir” diye iki düğmeye birden basınca, vakaların yarısında önce ters yöne gidiyor ve içeridekiler için de gereksiz duraklar ekliyor

  • Bunu gerçekten yapan birini gördüğümü sanmıyorum
  • Böyle durumlarda insanların anlamadığını varsaymak yerine, anlıyorlarsa bunun neden rasyonel olabileceğini tersten düşünmek çoğu zaman cevabı verir
    Muhtemelen sahte yükleme göstergesinin psikolojisine benziyor. Ne zaman geleceğini bilmeden beklemek sıkıcı ve bunaltıcı ama ters yöne giden bir asansöre binince en azından ilerleme varmış gibi hissediliyor. Sonuçta daha uzun sürse bile bir şeylerin oluyor olması daha az sinir bozucu
  • Kapı açılınca içeridekilere yukarı mı aşağı mı gittiğini soranlar da oluyor. Hemen önlerinde yön oku gösteriliyor
  • Alt katlarda birinden aşağı inmesi gerekiyorsa ve çıkış yoğun saatiyse, aşağı giden asansörler sürekli dolu olabilir
    Buna karşılık yukarı yönlü talep azsa, önce yukarı çıkıp sonra tam tur dönmek, yer açılır umuduyla beklemekten daha rasyonel bir strateji olabilir
  • Yoğun binalarda yoğun saatlerde asansör kapasitesi yetersiz olduğunda, zemin kata gitmek için önce yukarı çıkıp sonra aşağı inmek en kötü sonucu azaltabilir ya da ortalamada daha hızlı olabilir
    Bu durumda hem yukarı hem aşağı düğmesine basmak aptallık değil, mantıklıdır

• Algoritmanın performansından bağımsız olarak insanların bekleme süresini algılama psikolojisi de önemli
  Hiçbir şey yapmadan beklemek çok sinir bozucudur ama aynı süre boyunca bir şeyle meşgul olmak ilerleme hissi verir ve memnuniyetsizliği azaltır. Havalimanlarında da yolcuları kapıdan çıkınca doğrudan bagaj bandına götürüp ilk çanta gelene kadar bekletmek yerine, bilerek daha uzun ve dolambaçlı bir rota kullandıklarında toplam süre aynı kalsa bile memnuniyetin arttığı örnekler var

• Birçok asansör algoritmasında toplam aşınma ve bakım maliyeti sık tartışılmaz
  Hareket arttıkça hidrolik yağ değişimi ve parça arızaları hızlanabilir. Verimli algoritmalar, saat dilimine ya da diğer asansörlerin konumuna göre önceden yeniden konumlandırma da yapabilir; örneğin biri aşağı inerken bir diğerini yukarı gönderebilir. Talep sinyaline dayalı algoritmalar bu hareketleri en aza indirir. Bekleme süresini biraz artırsa bile bakımı azaltan denge önemlidir ve maliyeti üstlenen bina sahibinin yolcu bekleme süresine aynı ölçüde önem vermemesi muhtemeldir

  • Bakım sırasında bir asansörü hizmet dışı bırakmak gerektiği için o dönemdeki ortalama bekleme süresi de artar