飲食店の待ち行列
前職のちょっとした共同研究プロジェクトでデータ解析とシミュレーションをしていた時に、飲食店の待ち行列を効率的に処理する方法を開発していた。
企業秘密にならない範囲かつありふれたやり方といえる部分だけリファレンスとしてここに提示しておく。
問題設定
(1) それぞれのテーブル（席）にはIDが振られており、何名まで座れるかが決められている。
(2) 利用客はグループの一塊として扱い、同じテーブルを利用する。
(3) テーブルが空いたら、極力先着順で利用客を案内する。
(4) 全テーブルの最大キャパシティを超える人数のグループは、グループを分割する。
上記のようなシンプルなケースを想定する。 現実の問題では、テーブルの空間的な配置も考慮して1テーブルのキャパシティをオーバーしたグループにはテーブルを連結して案内するなどの対応がとられるが、ここでは取り扱わない。
某回転寿司のペ〇パー君のチェックイン->ご案内のフローを想像すれば良いだろう。
自動アサインの流れ
単純に、以下のような手法を採ればよい。
(1) テーブル毎に最大利用可能人数と最小利用可能人数を設定して識別子を割り当てる。
(2) 利用客の待ち行列は、到着（チェックイン）順を表すindexと利用人数、及び識別子を割り当てる。
(3) テーブルが空き状態になってから経過した時間が大きい順に、空きテーブルを選択する
(4) 選択されたテーブルの利用可能人数の範囲に収まる利用客グループを、indexが小さい順にスキャンする
(5) 利用可能人数の条件に収まる利用客グループがあれば、割り当てる。なければその空きテーブルをスキップする。
(6) 次に空き状態になってから経過時間の大きなテーブルを選択し、(4)に戻る。
上記処理を全テーブルまで適用した後、「割り当てられた利用客グループとテーブルの組」、「スキップされた空きテーブル」、「割り当てられなかった利用客グループ」を戻り値として返す。
「最小利用可能人数に引っ掛かって割り当てられなかった少人数の利用客グループ」については、戻り値に含まれる「スキップされた空きテーブル」に余裕があれば最小利用可能人数の条件を緩和もしくはゼロにして再度処理する。
また、待ち行列を絶対的な先着順にせずに、利用人数の多い方から優先度を上げて割り当てるという手法もあり、順番（または待ち時間）と利用人数からスコアを算出して割り当てる順番を決定するという手法も有効である。 この場合、実データを用いて充填率の高くなる最適なパラメタを見つける、もしくは、複数のパラメタセットで並行に実行して充填率の良いものを解として出力するという方法がよりプラクティカルであろう。
要するに、席のジオメトリを不問とするならばこの手の問題の制約条件はかなり簡素化できるので、店舗内のテーブル全ての状態をプログラムが把握する必要は無く、ただ単に「席が空いたタイミングで、空席と待ち行列のデータだけを渡す」ことで概ねそれらしい解が得られるということ。ソルバ自体は状態を持つ必要は（基本的に）無い。
具体的なコード
perlのコードをgithubに公開しておいた。
https://github.com/adokoy001/auto-assignment-solver/blob/master/solver.pl
いわゆるペライチPSGIアプリとして作成してあるので、Plackをインストールして以下のコマンドでHTTPのサーバーとして実行できる。
$ plackup solver.pl
Starmanをインストールしているのであればlistenポートを8080として、以下のようにしてプロダクションモードで実行できる。
$ starman --pid=solver.pid --daemonize --port 8080 solver.pl
HTTPサーバーのAPIとして動作するので、手持ちの案件でこのような機能要件がポッと出てきたらそのまま使ってみるのも良いかもしれない。
お試しサイト
また、以下のサイトでデプロイしているので、試してみるとよい。
textareaを拡大して以下のような形式でJSONを作成し、submitすれば待ち行列の自動アサイン結果がJSON形式で返ってくる。
{
"available_table" : [
{"table_id" : 201, "idle_time" : 300, "min_cap" : 2, "max_cap" : 4, "type" : "t"},
{"table_id" : 202, "idle_time" : 200, "min_cap" : 4, "max_cap" : 6, "type" : "l"},
{"table_id" : 203, "idle_time" : 500, "min_cap" : 4, "max_cap" : 6, "type" : "l"},
{"table_id" : 204, "idle_time" : 100, "min_cap" : 1, "max_cap" : 1, "type" : "c" },
{"table_id" : 205, "idle_time" : 250, "min_cap" : 1, "max_cap" : 1, "type" : "c" }
],
"queue" : [
{"guest_id" : 301, "index" : 1, "use_num" : 5, "acceptable" : { "c" : 0, "t" : 1, "l" : 1 }},
{"guest_id" : 302, "index" : 2, "use_num" : 2, "acceptable" : { "c" : 0, "t" : 1, "l" : 1 }},
{"guest_id" : 303, "index" : 3, "use_num" : 1, "acceptable" : { "c" : 1, "t" : 1, "l" : 1 }},
{"guest_id" : 304, "index" : 4, "use_num" : 2, "acceptable" : { "c" : 0, "t" : 1, "l" : 1 }},
{"guest_id" : 305, "index" : 5, "use_num" : 4, "acceptable" : { "c" : 0, "t" : 1, "l" : 1 }}
]
}
available_tableが空きテーブル、queueが利用客の待ち行列。
typeやacceptableについては某回転寿司チェーン等でよくあるカウンター席やテーブル席などのタイプ指定を表しており、
利用客が「カウンター席・テーブル席のどちらでも」を選んだ時は"acceptable" : { "c" : 1, "t" : 1}などとして表現できるようにしている。