როგორ წყვეტს ლიფტის ალგორითმი, რომელი კაბინა მოვა გამოძახებაზე

john.fun/elevators-ზე გამოქვეყნებული სტატია იმას განიხილავს, რა ხდება ღილაკის დაჭერასა და კაბინის მოსვლას შორის, და ადარებს ალგორითმებს, რომლებიც წყვეტენ, რომელი ლიფტი მოემსახურება რომელ მგზავრს. დასკვნა ინტუიციის საწინააღმდეგოა: ბევრ შენობაში ყველაზე მარტივი წესები ყველაზე მოკლე ლოდინს იძლევა.

ერთი კაბინა: SCAN და LOOK

უმარტივესი ალგორითმი — SCAN — 1961 წელს დაპატენტდა. კაბინა პირველი სართულიდან იწყებს, ბოლო სართულამდე ადის, შემდეგ უკან ბრუნდება და გზაზე მგზავრებს იყვანს და ატარებს. LOOK არის ვარიანტი, რომელსაც მგზავრების უმეტესობა რეალურად ხვდება: კაბინა მხოლოდ ყველაზე მაღალ დარეგისტრირებულ სართულამდე ადის და მერე ბრუნდება.

კაბინების შეფასება RSR-ით

რამდენიმე კაბინის შემთხვევაში უმარტივესი სისტემა ცენტრალურ დისპეტჩერს იყენებს, რომელიც ყოველ ახალ გამოძახებას უახლოეს ლიფტს ანიჭებს. უფრო დახვეწილი მიდგომაა Otis-ის RSR (Relative System Response), რომელიც თითოეულ კაბინას აფასებს იმით, თუ რამდენად შესაფერისია მგზავრის ასაყვანად — რაც ქულა ნაკლებია, მით უკეთესი. ქულა აერთიანებს მგზავრამდე მისვლის სავარაუდო დროს, კაბინაში დატვირთვის ჯარიმას, იმავე მიმართულებით მოძრაობის „დაჯგუფების“ ჯარიმას, მიმართულების დამთხვევის ბონუსს, ახლოს მდგარი უმოქმედო კაბინის ბონუსს და დაბალი დატვირთვის ბონუსს.

RSR ასევე ყოველ ხუთ წამში ხელახლა ოპტიმიზაციას ახდენს, ამიტომ მგზავრი, რომელიც თავდაპირველად ერთ კაბინას მიენიჭა, სხვაზე გადამისამართდება, თუ პირველი შეფერხდა. სტატიის მიხედვით, სწორედ ეს გადანაწილების ნაბიჯი ინარჩუნებს მოძრაობის სიმჭიდროვეს.

ლოდინის გაზომვა და რატომ იმარჯვებს მარტივი

სტატია ამტკიცებს, რომ ლოდინის დრო განაწილებად უნდა შეფასდეს და არა საშუალოდ: p90 ორი წუთი ნიშნავს, რომ მგზავრების 90 პროცენტი ორ წუთამდე ელოდება, p50 ერთი წუთი კი — რომ ლოდინების ნახევარი ერთ წუთზე ნაკლებია. მგზავრებს ყველაზე ცუდი შემთხვევები ახსოვთ და არა საშუალო, ამიტომ განაწილების „კუდი“ მნიშვნელოვანია.

სტატიაში მოყვანილი ტესტები აჩვენებს, რომ მგზავრთნაკადის ზრდასთან ერთად LOOK-მა შეიძლება RSR-ს გადაასწროს: როცა კაბინები სავსეა და თითქმის ყველა სართულზე ჩერდება, დამატებითი წესები ნაკლებად მოქმედებს. LOOK ასევე ხშირად ჯობია RSR-ს პატარა შენობებში, სადაც თითო ჯგუფში ნაკლები კაბინაა. დანიშნულების მიხედვით განაწილება — კიოსკები, რომლებიც შესვლამდე გეუბნებიან, რომელ კაბინაში უნდა ჩაჯდეთ — ლოდინის დროისთვის ჩვეულებრივ უარესია, ვიდრე ტრადიციული ზევით და ქვევით ღილაკები, გარდა ძალიან მაღალი შენობებისა, სადაც ერთ ჯგუფში რვა ან მეტი კაბინაა. მიზეზი ისაა, რომ კიოსკი ფიქსირებულ მინიჭებას აწესებს, ჩვეულებრივი სისტემა კი ყოველ ხუთ წამში ხელახლა ოპტიმიზაციას ახდენს. გვერდზე ყველა პარამეტრით მართვადი ინტერაქტიული სიმულაციაა განთავსებული.