エレベーターのアルゴリズム

日経の技術記事にエレベータに関する面白い記事があったので
以下に抜粋して転載．

大きなビルに勤める方は、朝はいつもエレベーター前が大渋滞、ボタンを押しても
なかなか来ない…．こんな経験は誰しもあるだろう．

どうすればエレベーターにスムーズに乗れるのか．この答えはエレベーターのアルゴリズムを
理解できれば、おのずと見えてくる．

アルゴリズムとは、「何らかの問題を解決する手順」を指し、この手順をコンピュータが
理解できるように記述したものがプログラムだ．エレベーターは、高度なアルゴリズムに
よって実装されたプログラムで動いている．

ボタンを押してもなかなか来ないエレベーターは実在するものの、イライラ解消に向けた
アルゴリズムの改良は進んでいる．今回は、三菱電機製のエレベーターを例に、
搭載されている最先端のアルゴリズムを解説する．

・近い階のカゴが来るわけではない

エレベーターのアルゴリズムは、各階に設置された呼び出しボタンが押されると、
どのカゴを呼び出せばよいかを瞬時に判断するようになっている．

ただし、エレベーターに1つのカゴしかない場合は、アルゴリズムを工夫する余地は
あまりない．利用していない時に、止まっておく停止階を指定するぐらいだ．

例えば、「呼び出される確率が高いロビー階などに、あらかじめカゴを停止させておく」
といったアルゴリズムが考えられる．

高度なアルゴリズムが必要になるのは、エレベーターのカゴが複数台ある場合．
大きなオフィスビルやデパートなどでは、3〜8台のカゴが配置されていることもある．

このような場合は、最適な配車（エレベーター業界では、エレベーターのカゴを人が
乗り込む車に見立てて「配車」と呼ぶ）を実現するアルゴリズムが重要になる．

三菱電機のエレベーターの場合、アルゴリズムの良しあしを決定する重要な要素が
「長待ち率」と「平均待ち時間」だ．長待ち率とは、エレベーターを待っている人
の中で60秒以上待っている人の割合を指す．

様々な研究の結果から「人はエレベーターを待っている時間が60秒以上になると
イライラ度が急激に増す」という．

そこで、カゴを60秒以上待っている人を減らすことが重要となる。．
これに対して平均待ち時間は、エレベーターを呼んだ人が平均して何秒待っているか
という時間のことだ．もちろん、平均待ち時間は短いほうが良い．

三菱電機製エレベーターのアルゴリズムは、これら2つの時間をポイント（値）と
して算出し、一番小さいポイントのカゴを配車する（ポイントの詳しい算出方法は後述）．
ポイントが小さいほど、長くエレベーターを待っている人が少なくなり、平均待ち時間も
短くなるカゴになるからだ．

例えば、A号機を配車するとポイントが2000、B号機を配車するとポイントが1000に
なる場合、B号機のカゴを配車するという具合だ．

このように最近のエレベーターは全体の最適化が優先されるため、必ずしも近くの階に
いるカゴがやって来るとは限らない．他の階で長い待ち時間が発生していれば、その階に
優先して配車される．

最適化のためには、時として呼び出しがあった階を通過しなければならないこともある．
乗り場にカゴが何階にいるのかを知らせるインジケーターのないエレベーターが増えて
いるのは、これが理由だ．インジケーターがあると、利用者にカゴの通過が分かってしまう．

待っているのに通過されてしまうと、利用者は余計にイライラするだろう．
逆に言えば、インジケーターがあると「最適化できることが限られてしまう」．
つまり、インジケーターがないエレベーターのほうが頭の良いエレベーターといえる．

・「枝刈り」で計算量を削減

ポイントの算出方法について、もう少し詳しく見ていく．先ほどエレベーターは「長待ち率」と
「平均待ち時間」を基準に配車するカゴを決定すると説明した．もっと厳密に言うと、
それ以外にも十数個のパラメーターを使ってポイントを算出している．

ちなみにそれらとは、長待ち率、平均待ち時間、カゴの散在度、停止回数、満員通過率、
乗車時間、省エネ率…．

例えば、エレベーターのカゴが上位階や下位階に固まっていないか、カゴに乗っている人の
乗車時間が長くなっていないか、カゴが満員で呼び出し回数を通過してしまう確率は
高くないか、といったパラメーターだ．

エレベーターは、カゴが上位階または下位階に固まってしまうと、長待ちが多く発生して
しまうことが知られている．このような問題も考慮して、配車するカゴを決定しなければ
ならない．

そこで、最適化の妨げになる要因をパラメーターとしてポイントを算出し、それを整数値に
置き換えて呼び出すカゴを決定する．わざわざ整数値に変換するのは、エレベーターの制御
プログラムがC言語で記述されているから．C言語では、小数を利用するよりも整数値の
ほうが高速に計算できる．

パラメーターが増えると、計算に時間がかかるようになる．そこで、エレベーターの

アルゴリズムは、計算中に明らかに最適ではないと判断できた場合は、途中で計算を打

ち切るように実装されている．これを「枝刈り」と呼ぶ．

例えば、ポイントが5000以上は最適でないと分かっていたとする．もし、A〜D号機の
ポイントを計算している最中に、C号機やD号機のように5000以上になったら、
これらの詳細な計算を止めてしまう．

その分、A号機とB号機のポイント計算にリソースを使うわけだ．エレベーターの

アルゴリズムでは、このように計算を効率化して素早く呼び出すカゴを決定している．

・ストレスなくエレベーターに乗る方法

最後に、どうすればイライラせずにエレベーターに乗れるかを、アルゴリズムの観点から
考えてみる．要点は「1つのカゴにはできる限り大人数で乗る」、「ピーク時間の前後5分を
避ける」、「健常者がエレベーターの車椅子用のボタンを押さない」の３つだ．

「1つのカゴにはできる限り大人数で乗る」から説明する．ここまで解説したように、
エレベーターのアルゴリズムは全体の最適化を重要視している．つまり、自分だけ目的階に
早くたどり着くといったことは基本的にできない．ならば、全体の最適化の手助けをすれば
よい．

できることの1つがカゴに乗る人数の調節だ．エレベーターのアルゴリズムは、1つのカゴに
定員の8割以上が乗車する想定で作られている．つまり、混雑時に定員の半数しか
乗っていないカゴが増えてしまうと、うまく最適化できない事態に陥る．

なので、あの上司とは一緒に乗りたくないと思うことがあっても「最適化につなげるために、
我慢して乗ってほしい」ということらしい（笑）．

一方、「ピーク時間の前後5分を避ける」はどうだろう．近年の研究では「ビルの居住人口
の15％がピークの5分間にエレベーターを利用する」という結果が出ている．利用時間を
ピーク時の前にずらすだけでも、ストレスなくエレベーターに乗れる確率が高まるという．

また、「健常者がエレベーターの車椅子用のボタンを押すのはやめてほしい」という．
車椅子用のボタンを押すと、扉の開閉時間が遅くなるだけでなく、同じ階に2台のカゴを
配車してしまう．

全体最適化の妨げになってしまい、「エレベーター遅延の原因になる」のだそう．

これは目からうろこだなぁ．気を付けましょう、皆さん．

．