複数階のオフィスライフ向上!時間に依存する最短経路問題をダイクストラ法で解く!

テナントに複数階入っている会社があります。移動方法が複雑であったり何かと不便です。ダイクストラ法を使ったSlackコマンドを実装しました。

October 25, 2019
algorithm dijkstra

最適なパスを何も考えず知り、爆速で移動する

※ 所属している組織に関する発言ではないので注意してください. いろんなインターンを通してビル事情を知り、まとめてます.

目次

tl;dr

「複数階のオフィス移動を最適化するために時間に依存する最短経路問題をフルスクラッチからダイクストラ法で解いた!」という記事です.
このサービスはSlackコマンドになっていて、バックエンドはCloud Run、Cloud Datastoreを使って実現しました.

最短経路のサジェッション

はじめに

複数階に会社のフロアが分かれているような大きな会社で何社か就業をしたことがあります. 多くのエレベーターがあり、止まる階が時間帯によって違うなどルールがあります.
それによって「エレベータベストプラクティス」というものが各社で生まれています.z軸だけの話だけではなく、同じ階でもホールやロビーというエレベータの集合のような概念がある場合もあります.

エレベーターのルールがわからない、どのようにXX階に辿り着く事ができるのかわからないというよくある話でした.
なんとなくソフトウェアの力で解決できないかなと思って、昨晩コードを書きました.

フルスクラッチからアルゴリズムを実装(Typescript)、Cloud Runへデプロイ、Slackからの認証、Cloud Datastoreとの接続などしました.

詳細は取り上げませんが、備忘録としてブログにしています.

複数階オフィスの問題

1. 移動にルールがある

複数階あるオフィスではエレベーター使用のルールがあることがあります. 一般的なのは以下のようなものです.

  • 偶数階にしか止まらないエレベーターと奇数階にしか止まらないエレベーターがある
  • 時間帯に応じて止まる階が変動する

これがいくつもの問題を引き起こします.

例えば、xx階で普段業務をしているとしましょう.
この日はyy階にいる別チームとの打ち合わせでyy階の会議室へ行くことになりました.
理想は以下のようにxx階からyy階へ直接行くことでしょう.
しかし、この建物のルールではxx階で止まるエレベーターとyy階で止まるエレベーターが異なるため直接行くことができません.

xx階からyy階は直接移動できない

では、どのように移動するのでしょう.
以下のようにxx階とyy階へ共通に止まるエレベーター階zzへ移動してからyy階へ向かいます.

xx階から一旦zz階へ行ってからyy階へ移動

ここまで単純だったらいいでしょう. しかし、もし…

  • より多くのルールがあったり…
ある階へ行くのに色々ルールが存在するときもある
  • 複数の行き方があったり…
ある階へいくのに複数の行き方があり、悩んでしまう

する場合はどうでしょう…どのようにして最適な経路を見出しますか?

2. 時間帯によってルールが異なる

時間帯で制限されるときもある

例えば、通勤の時間帯はエレベーターを負荷分散するようにルールを課していることが多いです.

10時や19時などは制限されることがあります.  

それ以外の時間では自由に行き来できたり、ルールが自由なこともあります.

このように、ルールが時間帯や曜日によって変化するためルールを覚え、理解する必要があります.

私たちは何を望むのか

最適なパスを何も考えず知り、爆速で移動する

何も考えずにその時の最短経路が提案されること

この状態にあれば、私たちはルールなんか知らずとも、楽(=頭を一切使わず)に、自分の時間を無駄にすることなく効率よく移動をすることができます.

複数階オフィスで働く社員はこれを待っているのです. まるでテレポートをするかの如く、移動できるソリューションを…

ソリューション

出発先と終着点を入力すると

  • そのときの移動経路
  • かかる予想時間

を指定してくれるSlackコマンドを作成しました.

アルゴリズム

時間に依存するダイクストラ法で最短経路問題を解いています. また、時間に依存するのはそのグラフ構造だけではなく、いわゆる重み付きグラフ構造の重さも変化するようにしています.

どういうことかを解説します.

単一始点最短経路問題を解くダイクストラ法とは

簡単にいうとスタート地点Sからゴール地点Gまでいくのにかかる最短経路問題を解くものです.

その際に、以下のような重み付きグラフ構造で経路はモデル化され、計算されます.

グラフとは、ノードとエッジの集合で構成されるデータ構造です. そして、それらのエッジに重み(=コスト)があるものを重み付きグラフ構造といいます.

例えば、1をスタート地点、5をゴール地点にすると、どの道を通れば最短(=最低コスト)でたどり着くことができるのかを計算できるアルゴリズムがダイクストラ法です.

時間に依存する重み付きグラフ構造とは

1. ノードとエッジが時間に依存する

ノードは以下のように定義しています.

export interface Vertex {
    nominal: string
    edges: Edge[]
    distance?: number
    prevVertex?: Vertex
}

そしてエッジは以下のように定義しています.

export interface Edge {
    terminal: Vertex
    weight: number
    addRule?: (now: dayjs.Dayjs) => boolean
}

ここでaddRule?が見慣れないと思いますが、時間に対してEdgeが有効化・無効化するようになっています.

ノードの数やエッジの隣接状況が時間に応じて変化するというものです.

重み付きグラフ構造

止まる階、そもそも使えるエレベーターなどが異なります.

2. 重みが日々刻々と変化する

時間によって、重みが異なります. イベントをしている、使えるエレベーター数が限られている、使う人がなぜかその日は多いなどです.

時間にノードやエッジが依存するグラフ構造い

このように重みは時間の関数になっていることもあるのです.

さらに拡張する

同じ階で複数のホール(=エレベーターの集合)があるため、その移動も考慮しました.

同じ階での移動が存在する

また特定の駅からの時間を追加できたり、自席への時間も追加をすることができます.

同じ階での移動が存在する

一つのノードとしか隣接していないものはグラフ構造にしてもあまり意味がないかもしれませんが、今後の「拡張性」を考えると取り込んでいても良さそうと思って取り込みました.

駅や自席も今後追加できる

アーキテクチャ

以下のようなアーキテクチャで構成しました. イベント駆動なのでサーバーレスアーキテクチャで構築をして、インスタンスを用意するまでもなかったのでCloud Datastore(ネイティブモード)を使用しています.

簡単なアーキテクチャ図

こだわった点は特にないです. 強いて言うなら、サーバーレスアーキテクチャにしたこと、Cloud Datastoreの課金モデルを考え、イベントに応じてのみに課金されるアーキテクチャにしたことです.

つまりCloud SpannerやCloud SQLなどのデータベースや、GCE, GAEなどを使用していないので、誰もコマンドを使っていないときは基本的には課金されることはありません.

コストは機能の一つです.

実際に使ってみる

最短経路を解いてもらう

以下のようにコマンドを実行します.

/teleport 39 20HallB

引数として「XX階からYY階」の情報を渡しています. 結果は以下のようになります.

最短経路のサジェッション

いまは予想所要時間等も追加し終わっています.

まとめ

アルゴリズムの力を、実際のアプリケーションに落とし込めて嬉しいです.

この機能が社内で使われることを祈っています.
何より、開発自体がとても楽しかったです.

最後までありがとうございました!