オフィスランチ便の配車の仕組みをまとめてみる
この記事は数理最適化 Advent Calendar 2020の16日目の記事です。
こんにちは、Chompyというフードデリバリーアプリの運営をやってるSYN, Inc. CTOの @yagitatsu です。今回は、Chompyリリース前からトライアル先行で運用していたオフィス向けのランチ宅配サービスであるオフィスランチ便の、配車の仕組みについてまとめてみます。
そもそもオフィスランチ便て何？
昨年から運用している、オフィス向けのランチ宅配サービスです。
こんなかんじのwebページがあり、注文できるようになっています。
※ちょうどオフィスランチ便をChompyのらくとく便として統合したところなので、現在は新規の会社さまはこのwebページを使うことができません。Chompyアプリから注文が必要です。
注文から配達の流れは、以下の通りです。
1. 11:00までに注文する
2. 注文データを元に、配車スクリプトを回し、その結果を元にslackにてクルー(配達員のこと。以下、クルー)に配達依頼する
3. クルーは店舗から商品を受け取り、中継地点へ運ぶ
4. 中継地点から各オフィスへ注文をまとめて運ぶ (12:00-12:30)
本記事では、この2にある「配車スクリプト」について記載しています。
配車のモデル化
まずは、配車(というか、配達？)のモデル化を行いました。ここでは、副業の方が開発前にまとめてくれたものをそのまま掲載します。
※ここで「会社」と記載しているのは、このサービスを利用契約している法人のことです。
・Input
ー 中継地点の集合 P = {1, 2, 3}
… 各中継地点 p ∈ Pに収容可能なアイテムの体積 cp>0
ー 会社の集合 T
… 各会社 t ∈ Tが利用可能な中継地点の集合 Pt ⊆ P
ー 店舗の集合 S
… 各店舗 s ∈ Sに対して、商品受け取り可能時刻 Ts >= 0
ー 全アイテムの集合 I
… 各アイテム i ∈ I の体積 vi > 0 ( i ∈ I)
… アイテムを売っている店舗 si ∈ S ( i ∈ I)
ー 配達員の集合 D
… 各配達員d ∈ Dの配達可能体積 ud>0 (d ∈ D)
ー 任意の地点 l1 ∈ S ∪ Pと任意の地点 l2 ∈ S ∪ Pの時間 d( l1 , l2 )
ー 各会社 t ∈ T の各アイテム i ∈ I の注文数 ot, i ∈ {0, 1, …}
・Output
ー 各配達員 d ∈ Dに対して
… どの順番でどの店舗に
… どのアイテムをどれだけ持って
… どの中継地点 p ∈ Pにもっていくか
・目的関数 (=KPI)
ー「配達員の中で最も配達に時間がかかる配達員の配達時間最小化」
・制約条件 (=必ず守るべき条件)
ー すべてのアイテムは配達員によって配達される
ー 配達員の最終地点はどこかひとつの中継地点 p ∈ P
ー 会社 t ∈ T のアイテム i ∈ I の注文はその会社が利用可能な中継地点Pt ⊆ Pへ配達しなければならない
ー 各配達員d ∈ Dが運ぶアイテムの体積の和は配達可能体積 ud 以下
ー 各中継地点p ∈ Pに配達されるアイテムの体積の和は収容可能なアイテムの体積cp以下
ー 各配達員は最大配達可能時間 m 分以内に中継地点へ配達
配車スクリプトのシステム構成
元々はcliで時間になったら手動実行していたのですが、毎日昼に実行するのが辛くなってきて、最終的に上記のような構成で自動化されました。
スクリプトがcloud runで動くようになっており、その仕組みは以下を参考にしました。
配車スクリプトの処理の流れ
以下の流れで実行して、最終的にslackにpostされるようになっています。
1. インプットデータの生成
2. 1のデータを元に、最適化スクリプトを実行
3. outputをslackにpost
平日11:00に注文受付が終了し、この処理を数分で完了させてクルー(配達員)のみなさんに指示を出す流れになっています。12:00-12:30にごはんを届けないといけないため、たまに処理がこけたりすると、つらいです。
1. インプットデータの生成
以下のデータをfetchしてきてGoogle Cloud Storageに保持するようにしています。
・当日の注文データ (店舗ID、商品数)
ー 商品ごとのサイズは考慮していない
・店舗データ (店舗ID、店舗名、位置情報、ピック可能時間)
・中継地点(届ける前に、店舗からピックしたごはんを仕分け直す場所)のデータ
ー 位置情報、ID
・会社データ
・ワーカーデータ (バイクか自転車かで、運べる商品数を変更できるように)
・各店舗、中継地点間の移動時間
ー Google distance matrix APIから２点間の徒歩の移動時間を取得し、この移動時間を2で割ったものを自転車の移動時間とした。
ー (書いてて思ったけど、バイクも同じデータを使ってるから変えてもよかったかもしれない)
各店舗、中継地点間の移動時間と注文データ以外は、spreadsheetでマスタ管理してました。
超初期は、注文データもcsvでダウンロードして、店舗ごとの数を集計してspreadsheetにセットした後でスクリプトを叩くという手動運用でやってました。
2. 1のデータを元に、最適化スクリプトを実行
処理の流れは大まかには以下のようになっています。
1. 各店舗の注文を中継地点を考慮しつつバッチとしてまとめる。以降の処理で、各配達員に対して注文バッチの列（=訪れる店舗の順番）と訪問する中継地点を決定する。
2. 1.で得られた注文のバッチを空いている各配達員に割り当て、適当に中継地点も決める。（初期解生成）
3. 指定した反復回数の数だけ、以下の三つの探索を等確率で行い、（制約条件を考慮しつつ）目的関数がよくなる場合はその探索方向に移動する。
1. ランダムに2人の配達員を選び、ランダムにお互いの注文バッチ２つを交換する。
2. ランダムに1人の配達員を選び、ランダムに注文バッチ２つを交換する。（=訪問する順番を変える）
3. ランダムな二人の配達員を選び、ランダムに一方の注文バッチを選び、もう一方の配達員へ渡す。
この前、Optimization Nightというイベントに参加していて、こういう風に徐々に解を改善していくアルゴリズムを「山登り法」と呼ぶのだと知りました。
これはそんなにアルゴリズムに詳しくない人でもシンプルに実装できて、同じような問題を解く必要がでてきたときによさそうだなーと思いました。
3. slackに結果をpost
タイトル以上に深ぼることはなさそうなので割愛します。
このスクリプトを作った効果
初期は注文の仕分けと配車を人間がやっていました。どの店舗が近くにあって、というのを予め把握しておけばできなくはないのですが、注文数が増えてくると難しくなります。
さらに、事前にクルーが集まっている中で時間制限があり、なるはやでやらないといけなかったのが辛かったのですが、機械がやってくれるようになって運用の安定感が圧倒的に増しました。
一方で、このオペレーション担当がすごい熟練者だと、「自分が仕分けた方が効率よさそう」と思ってたりするようで、配車スクリプトがこけたときは手動でやってくれたこともありました。誰でもできることではないですが、効率の面では改善点もまだまだありそうですが、そこまで効率改善に開発リソースを避けなかったので、このまま運用して今に至ります。
まとめ
この記事では、SYNで運用してるWebサービスのオペレーションに使ってる配車スクリプトの紹介をしました。個人的には、当時こういう案件に関わったのが初めてだったので、参考になる方がいるのかはよくわからないですが、勉強になってよかったです。
Chompyのらくとく便の配車システムは、また別で作られています。こちらでは問題をうまく単純化し、OR-Toolsを利用することにより、よりシンプルなものにすることができました。この配車システムの変遷については以下の記事にまとめているので、興味があればぜひご覧ください。
SYNにはこういう仕事がちょいちょいあるので、面白そうと思った方はぜひ話しましょう。