そこそこの規模のビルにオフィスがあったりすると「エレベーター渋滞問題」に遭遇することが頻繁にあります。特に朝9時直前の1階とか、お昼時とか、17~18時とか、多くの人がエレベーターを使うため、エレベーターの需要が足りなくなって、エレベーター待ちに一時的な渋滞ができてしまう問題です。
エレベーター渋滞問題については「エレベーター 渋滞」でググると多くの人や団体が困っていることがわかります。それなりに頻繁に起こりやすい問題であると思っています。
エレベーター渋滞問題については「エレベーター 渋滞」でググると多くの人や団体が困っていることがわかります。それなりに頻繁に起こりやすい問題であると思っています。
で、この渋滞の中で待たされている立場にいると「なかなかやって来ない!やってきても満員で乗れない!そのくらいのこともわからないのか!?」という感情になることがあります。
一方、この「渋滞時に効率的なエレベーター稼働アルゴリズム」を考える立場になってみると・・・ これは決して単純な問題ではなく、かなり複雑で難しいんじゃないか、ということに気付きます。そもそも何階建てのビルで、エレベーターは何基あって、定員は何人で、どのくらいのスピードで動いて、そして人はどんなパターンでやってきて・・・ と、変数になる要素がかなり多いのです。 そしてこれらの前提が決まった上でアルゴリズムを考える必要があります。誰かがどこかの階でエレベータのボタンを押した時、動いていないエレベーターがあればそれを向かわせればいいのですが、全て人が乗って動いている状態の中で、どのエレベーターをそのフロアに向かわせるべきなのか?その結論は一定時間後に(状況が変わって)見直す必要があるのではないか? ・・・などなど。「正解」といえる答を見つけるのが非常に難しいアルゴリズムのように思えたのでした。
そこで、今回作ってみたのが「エレベーター・シミュレーター」です:
https://github.com/dotnsf/velev
一方、この「渋滞時に効率的なエレベーター稼働アルゴリズム」を考える立場になってみると・・・ これは決して単純な問題ではなく、かなり複雑で難しいんじゃないか、ということに気付きます。そもそも何階建てのビルで、エレベーターは何基あって、定員は何人で、どのくらいのスピードで動いて、そして人はどんなパターンでやってきて・・・ と、変数になる要素がかなり多いのです。 そしてこれらの前提が決まった上でアルゴリズムを考える必要があります。誰かがどこかの階でエレベータのボタンを押した時、動いていないエレベーターがあればそれを向かわせればいいのですが、全て人が乗って動いている状態の中で、どのエレベーターをそのフロアに向かわせるべきなのか?その結論は一定時間後に(状況が変わって)見直す必要があるのではないか? ・・・などなど。「正解」といえる答を見つけるのが非常に難しいアルゴリズムのように思えたのでした。
そこで、今回作ってみたのが「エレベーター・シミュレーター」です:
https://github.com/dotnsf/velev
HTML と JavaScript で作ったエレベーターのシミュレーターです。ウェブブラウザ上で動くアプリケーションですが、HTTP サーバー上に用意する必要はなく、ローカルの index.html ファイルを直接開くことでも実行できます(後述のカスタマイズを試行錯誤する場合、むしろローカルファイルで実行する方が気楽に実行できると思ってます)。以下、ローカルファイルで開く方法で説明します。
【エレベーター・シミュレーターの動かし方】
実行する場合は上記の github リポジトリから git clone (またはダウンロード)します。カスタマイズをする場合はファイルを開く前にカスタマイズするのですが、いったん省略します。そしてウェブブラウザを起動して CTRL+O を実行し、ダウンロードしたリポジトリの index.html ファイルを指定して開きます。
最初の画面がこちらです。"settings" というタブが選択されている状態で、稼働開始前の設定画面です(この画面の初期値は settings.js ファイルを書き換えることで変更可能です)。エレベーターの基数(台数)、ビルフロア数、1基あたりの定員、1フロア移動に掛かる時間(秒)、乗降時にかかる時間(秒)が表示されており、必要であればここで変更することも可能です:
なお、この画面からもわかるかもしれませんが、このシミュレーターでは全てのエレベーターが同じ条件で動きます(実際には乗車人数によって乗降スピードが変わることもあるかもしれませんが無視します)。またエレベーターが停止して乗降する場合、その乗降人数に関係なく停止時間は一定としています。設定値は平均時間とお考えください。またエレベーターは最初は1階に止まっているものとします。
また、このシミュレーターではエレベーター稼働中は以下のルールが適用されて動きます:
- 人は各フロアで2本の待ち行列を作ってエレベータの到着を待つ。
- 目的方向(上 or 下)ごとに1本の待ち行列を作る。
- 目的方向(上 or 下)のボタンが押されてなかったら押して待つ。
- 待ち行列へは到達順に並び、途中で順序が入れ替わることはない。
- 人が待っているフロアに停止(上にも下にも向かっていない)中か、または目的と同じ方向に向かっていて人数に空きのあるエレベータが到達した場合、そのエレベータに乗ることができる。
- エレベータへは待ち行列の先頭から順に乗る。
- 1回のエレベータで乗り切れなかった場合、乗り切れるぶんだけが乗って、待ち行列を詰めて次のエレベータを待つ。
次に "waiting queue" タブを選択します。ここでは「稼働開始から何秒後に、どのフロアから、どのフロアへ行こうとしている人がやってくるか」が表で表示されています:
こちらの値はこの画面から直接編集したり、増やしたり、減らしたりすることは現状できません。ここをカスタマイズする場合は velev.js ファイルの冒頭部分に定義されている waiting_queue 配列変数を直接編集する必要があります。
なお初期状態の velev.js ファイルでは以下のように定義されています:
: //. 各フロアにやってくる人 var waiting_queue = [ /* { sec: 開始から何秒後にやってくる, src: どのフロアから, dst: どのフロアへ行こうとしているか } の配列 この例ではスタート直後に11人が1階にやってきて、それぞれの目的階へ移動する。 その後、10秒後に5階から1階へ行く人、20秒後に4階から1階へ行く人、30秒後に5階から1階へ行く人が現れる */ { sec: 0, src: 1, dst: 5 }, { sec: 0, src: 1, dst: 3 }, { sec: 0, src: 1, dst: 5 }, { sec: 0, src: 1, dst: 4 }, { sec: 0, src: 1, dst: 2 }, { sec: 0, src: 1, dst: 3 }, { sec: 0, src: 1, dst: 4 }, { sec: 0, src: 1, dst: 4 }, { sec: 0, src: 1, dst: 5 }, { sec: 0, src: 1, dst: 5 }, { sec: 0, src: 1, dst: 3 }, { sec: 10, src: 5, dst: 1 }, { sec: 20, src: 4, dst: 1 }, { sec: 30, src: 5, dst: 1 } //. 最後に待つこの利用者を迎えに行く必要がある ]; :
コメントにも記載している内容ですが、念の為内容を紹介します。初期状態では全部で 14 人の乗降者が定義されています。最初の 11 人は sec = 0 、つまり開始直後に 1 階( src = 1 )にやってきます。目的階(dst)は様々ですが、1人が2階、3人が3階、3人が4階、4人が5階となっています。 そして稼働開始から 10 秒後に5階から1階へ向かう人、同 20 秒後に4階から1階へ向かう人、同 30 秒後に5階から1階へ向かう人がそれぞれ1名ずつやってくる、という内容になっています。
エレベーターの稼働をスタートするには右上の "Start" ボタンをクリックします。以下、クリック直後の様子を経過時間に合わせて紹介します。
稼働がスタートすると画面が切り替わり、エレベーターのシミュレート画面になります。画面右上に経過秒数が表示され、大きく各フロア毎の待ち人数(上向きは赤、下向きは青)、そして各エレベーターの乗車人数と現在のフロアが確認できます。以下の画面は稼働直後で2台のエレベーターはまだ1階に止まっています。そして1階には既に上向きのエレベーターに乗りたい11人が集まって乗り込もうとしています:
初期状態ではエレベーターの1基あたり定員は10人でした。なので11人の先頭10人が1番のエレベーターへ、最後の1人(3階へ向かう人)が2番のエレベーターに乗り込みます:
エレベーターの移動中は色が変わります。上向きは赤っぽく、下向きは青っぽくなります。停止中は灰色になります。2台のエレベーターが上向きに稼働を開始しました:
2階には同時に着きます。エレベーター1には2階で降りる人が含まれていたので乗降状態になります。エレベーター2は2階を通過します:
エレベーター1はまだ乗降状態ですが、エレベーター2は唯一の乗客の目的地3階へ着きました。ここで全ての乗客を降ろして(目的地がなくなり)停止状態になります:
稼働開始から10秒が経過しました。ここで5階に「下向きのエレベーターに乗りたい」という人が1名到着します:
エレベーター1は各階停車する状態なので少しずつ乗客が減っていきます。エレベーター2は停止したままです:
20秒が経過すると、今度は4階に「下向きのエレベーターに乗りたい」という人が1名現れます:
エレベーター1が5階に到着しました。これで上向きの全乗客が目的階へ到達しました。同時にこの5階には下向きのエレベーターを待っていた人がいたので乗り込み、エレベーター1は下向きに方向を変えます:
エレベーター1が4階に到達すると、やはりここで停止し、下向きのエレベーターを待っていた乗客を載せて再び動き出します:
稼働開始から30秒後、5階から1階へ向かう人がもう1名現れます。初期状態ではこの通算14人目の乗客が最後の乗客です:
稼働開始から35秒後、エレベーター1が1階に到着し、乗客の降車も完了します(停止状態になります)。ただ5階にはまだ下向きエレベーターを待っている乗客がいます:
最初の13人までは「エレベーターを使いたい人のいる階にエレベーターがはじめからある or 稼働中のエレベーターがそのフロアに到着する」条件が成立したためエレベーターに乗ることができました。しかしこの14人目の乗客が待つ5階へは明示的にエレベーターを向かわせない限り、いつまでも乗ることはできません:
というわけで、実は初期状態はそのままでは全ての乗客を運びきれないパターンが設定されています。いったんブラウザをリロード(F5)して稼働を止めましょう。
【エレベーター・シミュレーターのカスタマイズ】
では、このシミュレーターの肝であるカスタマイズをして最後の乗客まで運べるアルゴリズムを作ってあげましょう。
カスタマイズはローカルにダウンロードした velev.js ファイルをテキストエディタで開きます。すると waiting_queue 配列変数の下に以下3つのイベント関数が定義されていることがわかります:
関数 | 説明 |
---|---|
fireOneSecond( second ) | 稼働経過後、1秒ごとに実行される関数。パラメータの second は経過秒数 |
fireCallButtonPush( floor, updown ) | ある階で上向き(または下向き)のボタンが押された時に実行される関数。パラメータの floor は階数、updown は -1 の時は下向きボタンが、 1 の時は上向きボタンが押された意味 |
fireElevatorButtonPush( num, floor ) | あるエレベーター内で階のボタンが押された時に実行される関数。パラメータの num はエレベーター番号、floor は押されたボタンの階 |
これらの関数は初期状態では事実上「何もしない」ような内容ですが、この中を JavaScript で書き換えることで命令を実行することができます。通常の JavaScript 関数に加えて、このシミュレーターでは以下の関数を利用することができます:
関数名 | 目的 | 返り値 |
---|---|---|
getElevatorsStatus() | 全エレベータの稼働状況を得る | 以下★が示すオブジェクトの配列 |
goFloor( idx, floor ) | 特定のエレベータを特定階に向かわせる。パラメータの idx はエレベーター番号、floor は目的階 | なし |
★ { num: エレベータ番号, floor: 現在いるフロア(移動中の場合は最後にいたフロア), updown: -1: 下降中、0: 停止中、1: 上昇中, people: 乗車中の人の配列(※1), move_count: フロアとフロアの間を移動している場合のカウント数(move_second に達したら次の階), stop_count: 乗降中で停止している場合のカウント数(stop_second に達したら移動開始), buttons: エレベータ内のボタン状態の配列(※2), mode: 0: 停止中、1: 移動中、2: 乗降中 } ※1 people は以下のオブジェクトの配列 { src_floor: エレベータに乗る前にいたフロア, dst_floor: エレベータを降りるフロア, waitsec: エレベータに乗るために待ちはじめてからの経過秒, mode: 0: 乗車待ち、1: 乗車中、2: 目的フロア到着 } ※2 buttons は以下のような数値配列で、0 は押されていない、1 は押されている状態を示す。 [ 0, 0, 1, 0, 1 ] ←この例だと 3 階と 5 階のボタンが押されている。
で、カスタマイズのサンプルが velev.js ファイル内にコメントで含まれているので、まずはこのサンプルを使ってカスタマイズしてみます。velev.js ファイル内の fireCallButtonPush() イベント関数内に含まれているコメント部分を変更して有効にします(分かりにくい人は 62 行目の内容を消して、消したものと同じ内容を 49 行目に書いて保存してください):
↑こうだった部分を、、
↓こう変更して保存する
このカスタマイズは fireCallButtonPush() イベント関数、つまりエレベーター前にやってきた人が上(または下)の行先方向ボタンを押した時に実行される関数に対して追加記述されています。そしてその内容ですが、50 行目で getElevatorsStatus() 関数を実行して全エレベーターの状況を取得し、52 行目からのブロックで各エレベーター毎の稼働状態を確認しています。そして「現在停止している( mode = 0 の)エレベーターがあったら見つける」処理を行って、そのようなエレベーターが存在していた場合は、そのエレベーターをボタンが押された階に向かわせる、という内容を記述しています。
※そのエレベーターがその階に到着すると、乗客が乗り込んで目的階のボタンを押してくれるので、これ以上のカスタマイズをしなくてもその階まで移動してくれます。
velev.js ファイルにこのカスタマイズをした上でもう一度動かしてみます。すると10経過秒後、5階から下へ向かう人がやってきた時に既に停止しているエレベーター2がこのカスタマイズによって再稼働して空の状態で5階へ向かうようになります:
エレベーター1がまだ4階にいる時にエレベーター2は5階へたどり着いて、この乗客を乗せ、下降を開始します:
20秒経過後に4階にやってくる乗客もエレベーター2が拾うことができました。エレベーター2はこのまま2人を乗せて1階へ向かいます。またエレベーター1は5階に到着後、停止状態になります:
エレベーター2はそのまま1階へ到着して停止します。一方、30秒経過後に5階から1階へ向かう人が現れます。初期状態ではこの人を乗せることが最後までできなかったのですが、今回はエレベーター1が5階に待機していたため、そのまま稼働状態になって乗せることができました:
1人の乗客を乗せたエレベーター1はそのまま下降して1階へ向かい・・・:
通算44秒後に全ての人の運搬が完了しました!エレベーターに乗るまでの最長と平均、目的階へ到達するまでの最長と平均それぞれの時間が表示されて確認できました:
ただ、これでカスタマイズが完了しているわけではありません。このサンプルはあくまで「誰かがエレベーター待ちのボタンを押した時に停止しているエレベーターがあればそれを向かわせる」というカスタマイズに過ぎません。全基稼働中にボタンが押されてしまうと対応できない、という問題が残されています。今回の乗客例であればたまたま全員が最後まで到着できるのですが、全てのケースに対応できるわけではないのでした。
ではそこまで対応したエレベーターを(可能な限り効率的に)カスタマイズするにはどうすればよいのか・・・ その答はここには書かないことにします。ぜひ皆さんに使っていただいて、皆さんの考える効率的なエレベーター稼働アルゴリズムを実装してみていただきたいと思っています。
コメント