電梯調度最佳化系統

​

以演算法提升運輸效率與使用者滿意度

The Coding Poop

廖衡、黃宇綸、林祺祐

大綱

• 研究動機
• 問題描述
• 專題目標
• 方法和工具
• 電梯策略介紹
• 角色與責任
• 專題狀態
• 下一步

研究動機

核心問題

專題目標

• 演算法方面

​

• 針對較簡化的電梯調度問題，優化現有的電梯調度策略

​

• 分析兩種電梯調度策略對搭乘者滿意度的影響

​

• 實作方面

​

• 將設計出的調度策略以視覺化的方式實現，讓大眾都能了解我們的研究成果與價值

​

問題描述

• 根據不同的搭電梯需求量分佈（模擬日常生活會遇到的乘客人數情境），設計出一款能夠最大化乘客滿意度、滿足乘客需求的電梯調度策略，並和目前電梯策略在不同乘客分布下做比較

​

​

​

​

實驗設計

實驗上我們可以操作的自變量包含：

• 樓層數
• 電梯數
• 電梯載客量上限
• 乘客刷出週期
• 每層樓進入/離開電梯的比重
• e.g. 一般時期平均分佈、尖峰時期特定樓層人流較多

​

實驗設計

我們列出了幾項指標來評估策略的好壞：

• 平均等待時長
• 公平性（等待時間標準差）
• 系統運作效率
• 最大等待時間

​

​

​

方法和工具

​

• 策略實作：C++、python
• 視覺化工具：Vibe Coding�

策略介紹

SCAN Algorithm

​

電梯會先選擇一個方向（向上或向下）移動

​

在移動過程中，會依序停靠該方向上的請求樓層

​

電梯會一直移動到建築的最頂樓或最底樓

​

到達邊界樓層後，電梯會反轉方向

​

然後再沿著另一個方向，繼續服務剩下的樓層請求

​

​

​

​

​

​

策略介紹

LOOK Algorithm

​

電梯會先選擇一個方向（向上或向下）移動。

​

在移動過程中，會依序停靠該方向上的請求樓層。

​

電梯會先「查看前方是否還有請求」。

​

如果已經到達該方向最後一個請求樓層，就會停止繼續前進。

​

然後立即反轉方向，開始服務另一方向的請求。

​

​

​

​

​

策略介紹

新策略：POOH

​

電梯優先載送乘客到達終點

​

電梯中沒有乘客時，會依照歷史人流數（動態調整）、目前等待人數、樓層與電梯距離、...等數據決定每層樓的權重，並依照權重隨機決定每個電梯的終點樓層，往終點樓層移動

​

實作流程圖

(流程圖)

​

數據(config.txt)->乘客生產器(PassengerGenerator.cpp)

->原始策略(CoreStrategy.cpp) -> 生成事件序列

->新策略(BetterStrategy.cpp) ->

​

->視覺化工具播放，計算數據

​

​

​

實作細節

• 數據檔案 config.txt
• 樓層數
• 每幀的期望生成旅客數量
• 電梯數量
• 電梯載客數上限
• 每層樓進出人流比重

實作細節

• 旅客生成器 PassengerGenerator.cpp
• 依數據檔案的資料生成旅客
• 每個旅客依照比重隨機選擇起點與終點
• 策略程式(CoreStrategy.cpp/BetterStrategy.cpp)
• 針對相同的旅客，決定每個電梯走向
• benchmark.py
• 呼叫多次實驗
• 彙整數據

實作細節

• 視覺化工具

讀取的事件內容按幀渲染

計算每位乘客平均等候、最大等候、滿意度指標

實驗結果

以20層樓、4台電梯、容量15人，每幀生成旅客數量期望值3人為例，人流刷出分布分成四種

​

1.平均分布

2.其中一層樓離開比例高

3.其中一層樓進入比例高

4.其中兩層樓進出比例高

每次實驗進行 30 輪，每輪 300 幀

實驗結果

情境一：平均分布

每層樓進出比重皆為1

實驗結果

情境二：上班時間

1樓的進入人流比重為100，其他樓層進出比重為1�

實驗結果

情境三：下班時間

1樓的離開人流比重為100，其他樓層進出比重為1�

實驗結果

情境四：10 樓有大型活動

1樓和10樓的進出人流比重為100，其他樓層進出比重為1

​

​

​

​

​

策略比較

視覺化工具影片

分工與責任

• 林祺祐：問題定義與需求分析、資料視覺化
• 黃宇綸：演算法設計與實作、效能評估與指標設計
• 廖衡：演算法設計與實作、資料蒐集與研究文獻回顧
• 共同責任：結果分析與報告撰寫、系統展示與視覺化介面

專題總結

為了改善電梯的公平性與效率問題：

• 設計出了新的 POOH 演算法
• 實作視覺化工具、電梯模擬系統並進行整合
• 實際進行實驗並驗證 POOH 能提升電梯效率與公平性

未來展望

• 實際應用我們的策略來改善現在的電梯

​

• 收集不同場所及時間段的人流資訊

​

• 一些新的策略（例如優先停在人流高的）

​

• 結合歷史人流紀錄來加強判斷

​

• 利用 Machine Learning 來決定電梯走向

​

• 結合不只一種運送策略

​

參考資料

• WIKI- Elevator algorithm (https://en.wikipedia.org/wiki/Elevator_algorithm)
• WIKI - LOOK algorithn (https://en.wikipedia.org/wiki/LOOK_algorithm)
• Designing a Smart Elevator System (Lift Scheduling at Scale) (https://medium.com/%40anuragkumbhare2043/designing-a-smart-elevator-system-lift-scheduling-at-scale-b9b26e008e88)
• SCAN (Elevator) Disk Scheduling Algorithms (https://www.geeksforgeeks.org/dsa/scan-elevator-disk-scheduling-algorithms/)
• Developer interview : R & D : Elevators, Escalators : Hitachi Global (https://www.hitachi.com/businesses/elevator/rd/interview4/index.html)

Thank You

github

https://github.com/hengliao0615/YTP_the_coding_poop