- Vận hành thang máy không chỉ là phản hồi lệnh gọi đơn giản mà là một bài toán tối ưu điều phối phải đồng thời xét đến số cabin, luồng hành khách, tải trọng và hướng di chuyển
- Với một cabin, SCAN sẽ đổi hướng ở tầng cao nhất, còn LOOK quay lại ở tầng cao nhất thực sự có yêu cầu nên gần với cách vận hành mà người dùng thường kỳ vọng hơn
- RSR (Relative System Response) cho nhiều cabin sẽ chấm điểm dựa trên thời gian đến dự kiến, tải trọng, v.v. và tái tối ưu việc điều phối mỗi 5 giây, nhờ đó có thể chuyển hành khách của cabin bị chậm sang cabin khác
- Nếu cabin liên tục kín chỗ hoặc lưu lượng hành khách lớn đến mức phải dừng ở mọi tầng trong khi số cabin ít, thì LOOK đơn giản có thể tốt hơn RSR phức tạp
- Điều phối theo tầng đích (Destination Dispatch), nơi hành khách nhập trước tầng đến, có nhiều thông tin hơn nhưng khó đổi cabin đã chỉ định; vì vậy trừ một số trường hợp như nhà siêu cao tầng hoặc có từ 8 cabin trở lên, thời gian chờ thường dài hơn so với nút lên/xuống truyền thống
Với một cabin, đổi hướng ở đâu?
- SCAN, được cấp bằng sáng chế năm 1961, xuất phát từ sảnh, đi lên đến tầng cao nhất rồi đổi hướng đi xuống, đón và trả khách dọc theo lộ trình di chuyển
- LOOK không nhất thiết đi đến tầng cao nhất mà chỉ vận hành đến tầng cao nhất có yêu cầu rồi quay lại
- Cách vận hành thang máy mà mọi người thường biết và kỳ vọng nhìn chung gần với LOOK
Điều phối cơ bản cho nhiều cabin
- Nếu có nhiều thang máy, cần quyết định cabin nào sẽ nhận lệnh gọi nào
- Trong hệ thống cơ bản, bộ lập lịch trung tâm chỉ định các tầng dừng cho từng cabin và gán lệnh gọi mới cho cabin gần nhất
- Nhưng chỉ điều phối theo khoảng cách đơn thuần thì khó phản ánh đầy đủ các tình huống như cabin gần nhất đã đầy khách
Cách đánh giá thời gian chờ
- Chỉ số đánh giá trực quan nhất của thuật toán thang máy là thời gian chờ từ lúc gọi đến khi cabin đến nơi
- Đơn giản nhất có thể đo tỷ lệ cabin đến trong vòng 30 giây hoặc 90 giây
- Để đánh giá chặt chẽ hơn, người ta gom thời gian chờ của hàng nghìn lượt vận hành để xem phân phối và biểu đồ histogram
- Nếu p90 là 2 phút thì nghĩa là 90% hành khách chờ trong vòng 2 phút
- Nếu p50 là 1 phút thì ở một nửa số lệnh gọi, cabin đến trong vòng 1 phút
- Hành khách có xu hướng nhớ rõ hơn những trường hợp p90 phải chờ lâu bất thường so với thời gian chờ trung bình
Luồng hành khách thay đổi theo thời điểm trong ngày
- Ở các tòa nhà văn phòng lớn, buổi sáng chủ yếu là luồng di chuyển từ sảnh lên các tầng trên
- Buổi tối, do người tan làm, luồng đi từ tầng trên xuống dưới chiếm ưu thế
- Giờ ăn trưa thì luồng lên và xuống trộn lẫn, còn những thời điểm khác thường có nhiều chuyến đi giữa các tầng
- Phân phối thời gian chờ thay đổi lớn theo thời điểm và kiểu giao thông, đặc biệt số liệu giờ cao điểm buổi sáng thường xấu
RSR chọn cabin như thế nào?
- RSR (Relative System Response) của Otis chấm điểm mức độ phù hợp của từng cabin để đón khách, và điểm càng thấp thì càng phù hợp
- Điểm nhận khách được tính bằng cách kết hợp nhiều yếu tố
- Thời gian đến dự kiến tới tầng gọi
- Mức phạt tải trọng theo số hành khách đang ở trong cabin
- Mức phạt chống gom cụm khi đã có cabin khác đi cùng hướng tới cùng tầng
- Thưởng khi hướng di chuyển trùng khớp
- Thưởng cho cabin rảnh ở trong phạm vi hai tầng tính từ tầng gọi
- Thưởng khi tải thấp
- Chống gom cụm (anti-bunching) sẽ hạn chế gán thêm nếu một cabin khác đã đi cùng hướng tới cùng tầng
- RSR tái tối ưu toàn bộ việc điều phối mỗi 5 giây
- Nếu cabin A bị chậm, hành khách vốn dự kiến do A đón có thể được gán lại cho cabin B
- Việc tái tối ưu liên tục này là chìa khóa giúp luồng hành khách vận hành trơn tru
Khác biệt hiệu năng giữa LOOK và RSR
- Dùng công cụ phân tích thời gian chờ có thể so sánh tỷ lệ đến trong vòng 30 giây và 90 giây của LOOK và RSR
- Khi lưu lượng hành khách tăng cao, LOOK bắt đầu vượt RSR
- Nếu cabin lúc nào cũng đầy và dừng ở mọi tầng thì hiệu quả từ các quy tắc bổ sung của RSR sẽ giảm đi
- Ở các tòa nhà nhỏ với ít thang máy trong mỗi cụm, LOOK cũng có xu hướng tốt hơn RSR, cho thấy cách đơn giản có thể phù hợp hơn
- Ngoài thời gian chờ, còn có thể đo thời gian di chuyển từ sau khi lên cabin đến tầng đích
- LOOK và RSR cũng cho thấy đặc tính khác nhau ở chỉ số này, nhưng bài viết không đi sâu so sánh cụ thể
Vì sao điều phối theo tầng đích bất lợi dù có nhiều thông tin hơn?
- Điều phối theo tầng đích là cách hành khách nhập trước tầng đến ở kiosk của từng tầng, sau đó hệ thống chỉ định thang máy sẽ sử dụng
- Hệ thống tối ưu hóa có thể biết trước tầng đích của từng hành khách trước khi cabin đến, nhưng thời gian chờ nhìn chung lại dài hơn cách dùng nút lên/xuống truyền thống
- Cũng có ngoại lệ mà cách dùng kiosk có lợi, chẳng hạn các tòa nhà rất cao với từ 8 thang máy trở lên trong mỗi cụm
- Nguyên nhân cốt lõi của sự suy giảm hiệu năng là tính cứng nhắc trong điều phối
- Cách truyền thống có thể tái tối ưu tuyến đường cabin và phân công hành khách mỗi 5 giây
- Trong điều phối theo tầng đích, hành khách phải lên đúng cabin đã được chỉ định ban đầu
- Dù sau 30 giây tình hình vận hành đã thay đổi, cũng không thể linh hoạt đổi sang cabin khác
- So với lợi ích của thông tin bổ sung về tầng đích, cái giá mất đi sự linh hoạt khi tái phân bổ còn lớn hơn
Các tham số điều chỉnh và phạm vi mô phỏng
- Trong toàn bộ mô phỏng, có thể điều chỉnh số tầng, số cabin và lưu lượng hành khách mỗi phút để xem tỷ lệ đến trong vòng 30 giây và 90 giây
- Thuật toán thang máy thực tế còn phải cân nhắc nhiều yếu tố hơn, và phạm vi được đề cập ở đây chỉ là một phần của toàn bộ lĩnh vực
- Tín hiệu từ nút gọi vẫn được gửi đi, nhưng vì thang máy phải tính đồng thời nhiều điều kiện vận hành nên có thể không đến ngay lập tức
1 bình luận
Ý kiến Hacker News
Trong khoảng một nửa của 50 năm qua, thang máy được điều khiển chỉ bằng rơ-le mà không cần máy tính, và các thuật toán kiểu này cũng được triển khai bằng mạch logic đi dây sẵn
Có thể xem các chi tiết thú vị như sơ đồ mạch trong các bằng sáng chế cũ của Otis
Hồi học môn khoa học máy tính ở trung học, tôi từng tự làm nhiều mô phỏng thuật toán thang máy như một dự án cá nhân
Ổ cứng quay giống như một thang máy rất dài quấn quanh trục quay thay vì đi theo phương thẳng đứng, và SCAN thực ra là một thuật toán lập lịch đĩa: https://en.wikipedia.org/wiki/Elevator_algorithm
Tôi tự hỏi liệu kết quả cho thấy điều phối theo tầng đích nhìn chung tệ hơn có phải vì các tầng đích được đặt ngẫu nhiên hay không
Trong các tòa nhà thực tế, đa số mọi người thường đi về tầng trệt chứ không phải một tầng ngẫu nhiên, và từ tầng trệt thì những người làm cùng tầng thường ra ngoài ăn trưa cùng nhau rồi cùng quay lại đúng tầng đó. Điều phối theo tầng đích có lợi cho kiểu mẫu này vì có thể gom những nhóm lớn có cùng đích đến
Một số hệ thống kiosk ở khách sạn còn thay đổi giao diện người dùng theo giờ cao điểm bữa sáng
Hiệu ứng đi theo cụm của những người đi ăn trưa hoặc quay lại cũng có thật, và rõ rệt hơn vào giữa ngày so với buổi sáng hay buổi tối
Cũng có các bài báo nói rằng sau khi văn phòng hoặc khách sạn chuyển sang cách này thì thời gian chờ giảm mạnh
Một tòa nhà mới xây mà tôi ghé gần đây cũng dùng cách này. Hồi đại học, bạn cùng phòng học điện của tôi từng làm một mạch thang máy trên breadboard, nối nút gọi, động cơ và một đĩa tròn trong suốt có các hình vuông đen để cảm biến vị trí; chắc là nó dùng một thuật toán đơn giản
Nếu mới làm quen với lập lịch thang máy, tôi khuyên thử trò này: https://play.elevatorsaga.com/
Khi phát triển game điều khiển và tự động hóa thang máy Sky Lobby cho iOS·Android, tôi đã suy nghĩ rất nhiều về bài toán này
Tôi chọn một thuật toán tương tự LOOK, vì nó gần nhất với kiểu chuyển động mà người chơi mong đợi, nhưng khi lựa chọn không rõ ràng thì ưu tiên các tầng đã chờ lâu để cải thiện p90, vốn rất quan trọng trong game. Nhưng khi thêm thang máy hai tầng phục vụ đồng thời hai tầng, tầng trung chuyển giữa các giếng thang và cả giếng thang tốc hành, thì thuật toán tối ưu hoặc trực quan nhất trở nên khó xác định hơn nhiều. Vì đây là game chứ không phải hệ thống thực, tôi chỉ cần tìm một heuristic đủ ổn, rồi cho người chơi khả năng ghi đè kế hoạch vận hành bằng tay khi họ không thích, và đa số đều hài lòng
Mỗi lần chờ thang máy tôi lại nghĩ chắc hẳn việc tạo ra một thuật toán tối thiểu hóa thời gian chờ từ lúc hành khách lên thang đến lúc tới đích là cực kỳ đau đầu
Đôi khi tôi còn nghi những người làm ra nó là các ác nhân thích hành hạ người khác bằng cách bắt họ đợi lâu hơn
Sáng hôm sau một hội nghị lớn, ai cũng muốn đi xuống, nhưng những cabin đã kín người vẫn dừng ở mọi tầng không bỏ sót. Nếu một thang máy 10 người đã đón khách gọi từ 10 tầng rồi, thì đáng lẽ nó phải đi thẳng xuống tầng trệt để tiết kiệm 5 phút, thay vì ở mỗi tầng lại lặp lại cảnh “hết chỗ rồi, tôi chờ chuyến sau vậy”. Đặc biệt nếu ở tầng 2 có người khuyết tật phải ra sân bay thì đây là vấn đề nghiêm trọng
Khi nhìn vị trí và chuyển động của toàn bộ các cabin, lịch vận hành dày đặc đến mức đáng kinh ngạc. Đứng ở sảnh thì thời gian chờ có vẻ vô tận, nhưng từ góc nhìn điều phối thì hoạt động diễn ra liên tục không ngừng, và trong giờ sử dụng của tòa nhà, thang máy gần như không bao giờ rảnh. Chỉ ngồi nhìn bảng trạng thái thôi cũng rất thú vị. Ngoài ra, khi kỹ thuật viên thang máy nói “gặp sớm vào buổi sáng”, họ thường có ý là khoảng 4 giờ sáng, vì họ muốn xong việc trước khi mọi người đi làm
Thang máy rất đắt, và chủ tòa nhà không dễ dàng đầu tư dư thừa theo cảm hứng, nên thường chỉ lắp số lượng thang máy tối thiểu đủ xử lý nhu cầu dự kiến, đôi khi còn ít hơn thế
Phía trên 4 thang máy có hiển thị tầng dừng dự kiến của từng chiếc, và ngay cả khi đang chờ, hệ thống vẫn đổi phân công giữa thang máy và tầng rồi báo bằng âm thanh. Có vẻ đây là tính năng để cho phép điều phối tối ưu
Vấn đề lớn nhất với thang máy không phải là thuật toán mà là những người không hiểu khái niệm bấm nút gọi lên hay xuống cho đúng hướng mình muốn đi
Nếu họ bấm cả hai nút vì nghĩ như thế “thang sẽ đến nhanh hơn”, thì một nửa số lần họ sẽ lên nhầm thang đi ngược hướng trước, lại còn thêm các điểm dừng không cần thiết cho những người đã ở trong cabin
Có lẽ nó giống tâm lý của thanh tải giả. Đứng chờ mà không biết khi nào thang tới thì rất chán và bực, nhưng nếu lên được một thang dù đi ngược hướng thì vẫn có cảm giác là mình đang tiến triển. Dù cuối cùng mất nhiều thời gian hơn, trạng thái “có gì đó đang xảy ra” vẫn đỡ khó chịu hơn
Trong khi đó nếu nhu cầu đi lên ít, thì đi lên trước rồi đi vòng hết hành trình có thể là chiến lược hợp lý hơn so với đứng chờ trong hy vọng sẽ có chỗ trống
Trong trường hợp đó, việc bấm cả nút lên và xuống không phải là ngốc nghếch mà là hợp lý
Ngoài hiệu năng của thuật toán, tâm lý của con người về cách cảm nhận thời gian chờ cũng rất quan trọng
Nếu chỉ đứng yên chờ đợi thì rất bực bội, nhưng nếu làm gì đó trong cùng quãng thời gian thì người ta cảm thấy có tiến triển nên ít khó chịu hơn. Ở sân bay cũng có ví dụ như thế: thay vì để hành khách đi thẳng từ cổng ra tới băng chuyền hành lý rồi đứng chờ chiếc vali đầu tiên xuất hiện, người ta cố ý thiết kế lộ trình dài và vòng hơn; tổng thời gian vẫn như nhau nhưng mức độ hài lòng lại cao hơn
Trong nhiều thuật toán thang máy, tổng hao mòn và chi phí bảo trì thường không được bàn tới
Chuyển động nhiều hơn có thể làm dầu thủy lực phải thay sớm hơn và linh kiện hỏng nhanh hơn. Các thuật toán hiệu quả đôi khi còn tái bố trí trước theo thời điểm hoặc theo vị trí của các thang khác; ví dụ khi một cabin đang đi xuống thì có thể cho một cabin khác đi lên. Các thuật toán dựa trên tín hiệu nhu cầu sẽ giảm các chuyển động kiểu này. Cần có sự cân bằng: chấp nhận tăng thời gian chờ để giảm bảo trì, vì chủ tòa nhà là người trả chi phí có thể không coi thời gian chờ của hành khách quan trọng đến mức đó