Лифт яагаад заримдаа уддаг вэ? Хуваарилах алгоритмын нууц

Оройн цагаар 20 давхар байшингийн лифтний товчлуур дарахад 3 лифт зэрэгцэн зогсож байгаа ч тэдгээрийн зөвхөн нэг нь ирдэг — заримдаа хамгийн ойрхон нь биш. Энэ нь санамсаргүй байдал биш, харин олон лифттэй системд аль лифтийг илгээхийг шийддэг тусгай логикийн үр дүн юм.

Ганц лифттэй үед асуудал энгийн: лифт нэг чиглэлд хөдөлж, замдаа тааралдсан бүх хүсэлтэд үйлчилдэг (энэ бол SCAN алгоритм буюу Лифтний алгоритм). Гэвч байшинд 2-3 лифт зэрэг ажиллаж байвал систем нэмэлт асуулттай тулгардаг: "Аль лифтийг илгээх нь хамгийн үр ашигтай вэ?"

Энэ шийдвэрийг гаргахдаа систем дараах хүчин зүйлсийг харгалздаг:

1. Зай (Distance): Аль лифт хүсэлт гаргасан давхарт хамгийн ойрхон байна.

2. Чиглэл (Direction): Лифт аль хэдийн тухайн чиглэлд хөдөлж байгаа эсэх — жишээ нь, доошоо явж буй лифтийг дээшээ явах хүсэлтэд ашиглахгүй.

3. Ачаалал (Load): Лифт хэдийнэ хэдэн хүнтэй, хэдэн зогсоолтой байгаа.

4. Хүлээх хугацаа (Wait time estimate): Хэрэв лифт бүрийг илгээвэл нийт хүлээх хугацаа хэд байх тооцоолол.

Ийм олон лифттэй системийг бүлгийн удирдлага (Elevator Group Control) буюу зарим орчин үеийн барилгад Destination Dispatch гэж нэрлэдэг. Энд алгоритм нь зөвхөн "хамгийн ойрхон" биш, харин бүх системийн нийт хүлээх хугацааг хамгийн бага байлгах зорилготой оновчлолын бодлого шийддэг.

Python дээр 3 лифттэй системд аль лифтийг илгээхийг сонгох энгийн симуляцийг дараах байдлаар бичиж болно:

Энэ жишээнд 2-р лифт хамгийн ойр биш ч эсрэг чиглэлд явж, ачаалалтай тул шийтгэл авч, харин 3-р лифт зогсонги (idle) байсан тул сонгогдож байна — яг л амьдрал дээр таны хажуугийн лифт биш, илүү "оновчтой" лифт ирдэгтэй адил.

Ганц лифттэй SCAN логикийг Дональд Кнут 1960-аад онд диск удирдлагын онол дотор дүрсэлсэн бол өндөр барилгууд олон болсоор орчин үеийн лифтний системүүд Destination Dispatch гэдэг илүү ухаалаг арга руу шилжсэн — энд хэрэглэгч лифтэнд орохоосоо өмнө очих давхраа урьдчилан оруулдаг тул систем хэн хэнтэй хамт явахыг илүү оновчтой бүлэглэж чаддаг. Ирээдүйд AI ашигласан таамаглалт хуваарилалт (жишээ нь, хажуугийн барилгын өдрийн хуваарь дээр үндэслэн урьдчилан лифт бэлдэх) улам түгээмэл болох төлөвтэй.