Algoritme penjadwalan elevator

• Operasi elevator bukan sekadar merespons panggilan, melainkan masalah optimasi penjadwalan yang mempertimbangkan jumlah kabin, arus penumpang, muatan, dan arah pergerakan secara bersamaan
• SCAN untuk satu kabin berbalik arah di lantai teratas, sedangkan LOOK berbalik di lantai tertinggi yang benar-benar memiliki permintaan, sehingga lebih dekat dengan ekspektasi umum tentang cara elevator beroperasi
• RSR (Relative System Response) untuk banyak kabin memberi skor berdasarkan estimasi waktu tiba, muatan, dan faktor lain, lalu mengoptimalkan ulang penjadwalan setiap 5 detik sehingga penumpang dari kabin yang tertunda dapat dialihkan ke kabin lain
• Jika kabin terus-menerus penuh, berhenti di hampir setiap lantai karena arus penumpang sangat tinggi, dan jumlah kabin sedikit, LOOK yang lebih sederhana bisa lebih baik daripada RSR yang kompleks
• Destination Dispatch, yaitu memasukkan lantai tujuan terlebih dahulu, memperoleh lebih banyak informasi tetapi sulit mengubah kabin yang telah ditetapkan; kecuali pada beberapa kasus seperti gedung supertinggi atau grup dengan 8 kabin ke atas, waktu tunggunya umumnya lebih lama daripada tombol naik/turun tradisional

---

Di mana satu kabin berbalik arah

• SCAN, yang dipatenkan pada 1961, berangkat dari lobi, naik hingga lantai teratas, lalu berbalik turun sambil menaikkan dan menurunkan penumpang di sepanjang rutenya
• LOOK tidak selalu naik sampai lantai teratas, tetapi hanya berjalan sampai lantai tertinggi yang diminta lalu berbalik
• Cara operasi elevator yang umumnya diketahui dan diharapkan orang lebih dekat dengan LOOK

Penjadwalan dasar untuk banyak kabin

• Jika ada beberapa elevator, sistem harus mengatur kabin mana yang menangani panggilan mana
• Dalam sistem dasar, penjadwal pusat menentukan lantai berhenti untuk tiap kabin dan menugaskan panggilan baru ke kabin terdekat
• Namun, penjadwalan yang hanya berbasis jarak sulit mencerminkan kondisi seperti kabin terdekat yang sudah penuh

Cara mengevaluasi waktu tunggu

• Metrik evaluasi paling intuitif untuk algoritme elevator adalah waktu tunggu dari panggilan hingga kabin tiba
• Secara sederhana, sistem dapat mengukur persentase kabin yang tiba dalam 30 detik atau 90 detik
• Untuk evaluasi yang lebih ketat, kumpulkan waktu tunggu dari ribuan perjalanan lalu periksa distribusi dan histogram
  • Jika p90 adalah 2 menit, artinya 90% penumpang menunggu tidak lebih dari 2 menit
  • Jika p50 adalah 1 menit, artinya pada separuh panggilan, kabin tiba dalam 1 menit
• Penumpang cenderung lebih kuat mengingat kasus p90, yaitu saat mereka menunggu jauh lebih lama daripada rata-rata

Arus penumpang yang berubah menurut waktu

• Pada pagi hari di gedung perkantoran besar, sebagian besar pergerakan berasal dari lobi menuju lantai atas
• Pada sore hari, arus dari lantai atas ke bawah menjadi dominan karena orang pulang kerja
• Saat makan siang, perjalanan naik dan turun bercampur, sedangkan pada waktu lain banyak terjadi perpindahan antarlantai
• Distribusi waktu tunggu sangat berubah menurut waktu dan pola lalu lintas, dan statistiknya buruk terutama pada jam masuk kerja pagi

Bagaimana RSR memilih kabin

• RSR (Relative System Response) dari Otis memberi skor seberapa cocok tiap kabin untuk menjemput penumpang; makin rendah skornya, makin cocok kabinnya
• Skor penjemputan dihitung dari kombinasi beberapa faktor
  • Estimasi waktu tiba ke lantai pemanggil
  • Penalti muatan berdasarkan jumlah penumpang yang sedang naik
  • Penalti anti-pengelompokan yang diterapkan ketika sudah ada kabin yang menuju lantai yang sama dalam arah yang sama
  • Bonus kesesuaian arah pergerakan
  • Bonus untuk kabin menganggur yang berada dalam jarak dua lantai dari lantai pemanggil
  • Bonus muatan rendah
• Anti-bunching menekan penugasan tambahan jika kabin lain sudah menuju lantai yang sama dalam arah yang sama
• RSR mengoptimalkan ulang seluruh penjadwalan setiap 5 detik
  • Jika kabin A tertunda, penumpang yang semula akan dijemput A dapat dialihkan ke kabin B
  • Optimasi ulang berkelanjutan seperti ini adalah kunci untuk membuat arus penumpang lebih lancar

Perbedaan performa LOOK dan RSR

• Dengan alat analisis waktu tunggu, rasio kedatangan dalam 30 detik dan 90 detik untuk LOOK dan RSR dapat dibandingkan
• Semakin tinggi arus penumpang, LOOK mulai mengungguli RSR
  • Jika kabin selalu penuh dan berhenti di semua lantai, manfaat dari aturan tambahan RSR berkurang
• Di gedung kecil dengan jumlah elevator per grup kabin yang sedikit, LOOK juga cenderung lebih baik daripada RSR, sehingga pendekatan sederhana bisa lebih cocok
• Selain waktu tunggu, waktu perjalanan setelah naik hingga mencapai lantai tujuan juga dapat diukur
  • LOOK dan RSR menunjukkan karakteristik berbeda pada metrik ini juga, tetapi perbandingan spesifiknya tidak dibahas

Mengapa destination dispatch merugikan meski punya lebih banyak informasi

• Destination Dispatch adalah metode di mana penumpang memasukkan lantai tujuan terlebih dahulu di kios pada tiap lantai, lalu sistem menetapkan elevator yang harus dinaiki
• Sistem optimasi dapat mengetahui semua tujuan tiap penumpang sebelum kabin tiba, tetapi waktu tunggunya umumnya lebih lama daripada metode tombol naik/turun tradisional
• Ada pengecualian ketika metode kios lebih menguntungkan, misalnya pada gedung yang sangat tinggi dengan 8 kabin atau lebih per grup kabin
• Penyebab utama penurunan performa adalah kekakuan penjadwalan
  • Pada metode tradisional, rute kabin dan penugasan penumpang dapat dioptimalkan ulang setiap 5 detik
  • Dalam destination dispatch, penumpang harus naik kabin yang pertama kali ditetapkan
  • Meski kondisi operasi berubah 30 detik setelah panggilan, kabin yang ditetapkan tidak dapat diganti secara fleksibel
• Kerugian akibat hilangnya fleksibilitas penugasan ulang lebih besar daripada manfaat informasi tambahan berupa tujuan

Parameter dan cakupan simulasi

• Dalam simulasi keseluruhan, jumlah lantai, jumlah kabin, dan arus penumpang per menit dapat diatur untuk memeriksa persentase kedatangan dalam 30 detik dan 90 detik
• Algoritme elevator nyata memiliki lebih banyak pertimbangan, dan cakupan yang dibahas di sini hanyalah sebagian dari keseluruhan bidang
• Input tombol panggilan memang diteruskan, tetapi karena elevator menghitung berbagai kondisi operasi sekaligus, kabin mungkin tidak langsung tiba

[GN⁺]

Komentar Hacker News

• Selama kira-kira separuh dari setengah abad terakhir, elevator dikendalikan hanya dengan relay tanpa komputer, dan algoritme seperti ini pun diimplementasikan sebagai rangkaian logika berkabel
  Detail menarik seperti diagram rangkaiannya bisa dilihat di paten-paten lama Otis

• Saat kelas ilmu komputer di SMA, saya mengimplementasikan beberapa simulasi algoritme elevator sebagai proyek pribadi
  Hard disk berputar mirip elevator yang sangat panjang yang melilit spindle, bukan vertikal, dan SCAN memang merupakan algoritme penjadwalan disk: https://en.wikipedia.org/wiki/Elevator_algorithm

  • Di universitas pun saya mengerjakan proyek serupa memakai mikrokontroler dan LED, dan itu sangat menyenangkan

• Saya penasaran apakah hasil bahwa destination dispatch secara umum buruk muncul karena lantai tujuan diatur secara acak
  Di gedung nyata, kebanyakan orang yang bukan berada di lantai dasar akan pergi ke lantai dasar, sementara dari lantai dasar, orang-orang yang bekerja di lantai yang sama cenderung keluar bersama saat makan siang lalu kembali bersama ke lantai yang sama. Destination dispatch bisa mengelompokkan rombongan besar dengan tujuan yang sama, sehingga cocok untuk pola seperti ini

  • Untuk hotel, asumsi ini bahkan lebih tidak cocok. Pada pagi hari orang tidak hanya bergerak dari lobi ke kamar, tetapi turun untuk sarapan, naik lagi, lalu turun lagi, sehingga terjadi lalu lintas dua arah
    Sistem kios di sebagian hotel bahkan mengubah antarmuka penggunanya sesuai jam sibuk sarapan
  • Kapal pesiar yang memakai destination dispatch juga terasa jauh lebih nyaman. Kapal dengan algoritme lama membuat waktu tunggu saat jam sibuk terasa menyiksa, meski itu memang membuat orang lebih sering memakai tangga
  • Seseorang di lantai atas jauh lebih mungkin kembali ke lantai dasar daripada naik atau turun satu-dua lantai, tetapi penumpang yang menunggu dalam simulasi tampaknya tidak mencerminkan hal ini dengan baik
    Efek pengelompokan orang yang pergi makan siang atau kembali dari makan siang juga nyata, dan lebih menonjol di tengah hari dibanding pagi atau sore
  • Menurut saya, pola rombongan besar yang bergerak dari lantai dasar ke tujuan yang sama adalah salah satu alasan terbesar destination dispatch lebih baik
    Ada juga artikel yang menyebut waktu tunggu berkurang banyak setelah kantor atau hotel beralih ke cara ini
  • Saya penasaran apakah ini karena metrik evaluasinya adalah waktu tunggu, bukan waktu perjalanan. Destination dispatch mengurangi pemberhentian yang tidak perlu selama perjalanan
    Gedung baru yang saya kunjungi baru-baru ini juga memakai cara ini. Saat kuliah, teman sekamar saya yang mengambil teknik elektro membuat rangkaian elevator dengan tombol panggil, motor, dan piringan transparan bertanda kotak-kotak hitam untuk deteksi posisi yang terhubung ke breadboard; kemungkinan algoritmenya sederhana

• Jika baru pertama kali mengenal penjadwalan elevator, saya merekomendasikan game ini: https://play.elevatorsaga.com/

  • Premisnya sederhana, tetapi makin naik level, tingkat kesulitannya meningkat dengan memuaskan, bahkan ada sedikit kerusakan acak yang menambah tantangan. Andai ada lebih banyak game seperti ini
  • Kelihatannya dibuat dengan baik, tetapi saya tetap lebih suka https://en.wikipedia.org/wiki/Elevator_Action
  • Bagus, tetapi bagi saya game penjadwalan elevator terbaik adalah SimTower
  • Setiap kali menunggu elevator di hotel tempat konferensi berlangsung, saya jadi mencari game ini lagi
  • Saya selalu bertanya-tanya apakah game untuk memprogram sendiri scheduler elevator akan menarik, dan saya pikir belum ada yang membuatnya; senang ternyata saya salah

• Saat mengembangkan game kontrol dan otomasi elevator untuk iOS dan Android, Sky Lobby, saya banyak memikirkan masalah ini
  Saya mengadopsi algoritme mirip LOOK yang paling mendekati pergerakan yang diharapkan pemain, tetapi ketika pilihan ambigu, saya memprioritaskan lantai yang sudah lama menunggu untuk memperbaiki p90 yang penting dalam game. Namun ketika ditambah elevator dua tingkat yang melayani dua lantai sekaligus, lantai transfer antar-shaft, sampai shaft ekspres, algoritme yang optimal atau paling intuitif menjadi jauh lebih tidak jelas. Karena ini game, bukan sistem nyata, saya mencari heuristik yang cukup baik, lalu membiarkan pemain menimpa rencana operasi secara manual jika tidak suka; kebanyakan puas

• Setiap kali menunggu elevator, saya memikirkan betapa rumitnya membuat algoritme yang meminimalkan waktu tunggu sampai penumpang naik dan sampai di tujuan
  Kadang saya juga bertanya-tanya apakah orang yang mengimplementasikannya adalah sadis jahat yang sengaja membuat kita menunggu lebih lama

  • Akan bagus kalau elevator juga mempertimbangkan beban penumpang
    Pagi setelah konferensi besar, semua orang ingin turun, tetapi elevator yang sudah penuh berhenti di setiap lantai. Jika elevator berkapasitas 10 orang sudah mengangkut penumpang panggilan dari 10 lantai, seharusnya ia bisa langsung menuju lantai dasar dan menghemat 5 menit, alih-alih di tiap lantai mengulang “tidak ada tempat, saya naik yang berikutnya”. Ini bisa menjadi masalah serius, terutama jika penyandang disabilitas di lantai 2 harus mengejar penerbangan
  • Saya beberapa kali mengembangkan software integrasi eksternal yang menghubungkan elevator dengan peralatan lain
    Jika melihat posisi dan pergerakan semua elevator, jadwalnya luar biasa padat. Di lobi, menunggu terasa tanpa akhir, tetapi dari sudut pandang dispatch, aktivitasnya terus berjalan tanpa henti, dan selama jam penggunaan gedung, elevator hampir tidak pernah menganggur. Melihat panel status saja sudah menarik. Selain itu, jika teknisi elevator berkata “mari bertemu pagi-pagi”, biasanya maksudnya sekitar pukul 4 pagi, karena mereka ingin menyelesaikan pekerjaan sebelum orang-orang masuk kerja
  • Bukan karena software penjadwalan elevator itu bodoh; sudah ada banyak sekali pemikiran di dalamnya
    Elevator mahal dan pemilik gedung tidak berinvestasi berlebihan secara impulsif, jadi biasanya mereka memasang jumlah elevator minimum yang cukup untuk menangani permintaan yang diperkirakan, kadang malah kurang dari itu
  • Selain waktu tunggu, mereka mungkin juga mengoptimalkan fungsi objektif seperti keausan dan konsumsi energi

• Di atas masing-masing dari 4 elevator ditampilkan lantai berhenti yang direncanakan, dan bahkan saat kita menunggu, penugasan elevator dan lantai diubah sambil diberi notifikasi suara. Sepertinya ini fitur yang dibuat agar dispatch optimal bisa dilakukan

• Masalah terbesar pada elevator bukan algoritmenya, melainkan orang-orang yang tidak memahami konsep menekan tombol panggil naik/turun sesuai arah tujuan
  Jika menekan kedua tombol karena “yang datang lebih cepat”, separuhnya akan lebih dulu menuju arah berlawanan, dan menambah pemberhentian yang tidak perlu bagi orang yang sudah di dalam

  • Rasanya saya belum pernah melihat orang benar-benar melakukan itu
  • Dalam situasi seperti ini, alih-alih berasumsi orang tidak paham, sering kali jawabannya muncul jika kita membalik pertanyaannya: jika mereka paham, mengapa itu bisa rasional
    Mungkin mirip psikologi indikator loading palsu. Menunggu tanpa tahu waktu kedatangan terasa membosankan dan menyebalkan, tetapi jika naik elevator yang bergerak meski ke arah berlawanan, rasanya ada kemajuan. Pada akhirnya, meski memakan waktu lebih lama, keadaan ketika sesuatu sedang terjadi terasa kurang menyebalkan
  • Saat pintu terbuka, ada juga yang bertanya kepada orang di dalam apakah elevatornya naik atau turun. Padahal tepat di depan mereka ada panah arah
  • Jika Anda ingin turun dari lantai bawah saat jam sibuk check-out, elevator yang turun bisa terus-menerus penuh
    Sebaliknya, jika permintaan naik sedikit, naik dulu lalu ikut sampai berputar kembali bisa menjadi strategi yang lebih rasional daripada menunggu sambil berharap ada ruang kosong
  • Pada jam sibuk di gedung yang padat, kapasitas elevator kurang, sehingga untuk pergi ke lantai dasar, naik dulu lalu turun bisa mengurangi hasil terburuk atau secara rata-rata lebih cepat
    Dalam kasus ini, menekan tombol naik dan turun sekaligus bukan tindakan bodoh, melainkan logis

• Terlepas dari performa algoritme, psikologi persepsi waktu tunggu orang juga penting
  Menunggu tanpa melakukan apa-apa sangat menjengkelkan, tetapi melakukan sesuatu selama durasi yang sama terasa seperti kemajuan sehingga keluhan berkurang. Di bandara pun ada contoh: alih-alih membuat penumpang langsung berjalan dari gate ke baggage belt lalu menunggu koper pertama keluar, mereka sengaja membuat rute yang lebih panjang dan memutar; total waktunya sama, tetapi penumpang lebih puas

• Dalam berbagai algoritme elevator, total keausan dan biaya pemeliharaan jarang dibahas
  Semakin banyak pergerakan, semakin cepat oli hidraulik perlu diganti dan komponen rusak. Algoritme yang efisien kadang melakukan repositioning lebih dulu bergantung pada waktu atau posisi elevator lain; misalnya, ketika satu elevator turun, elevator lain bisa dikirim naik. Algoritme berbasis sinyal permintaan meminimalkan pergerakan seperti ini. Penting menyeimbangkan pengurangan pemeliharaan meskipun waktu tunggu bertambah, dan pemilik gedung yang menanggung biaya mungkin tidak begitu memprioritaskan waktu tunggu penumpang

  • Saat pemeliharaan, satu elevator harus dikeluarkan dari operasi, sehingga waktu tunggu rata-rata selama periode itu juga meningkat