フードデリバリー Chompy を支えるアルゴリズムに迫る

この記事は、とあるお蔵入りになった記事の転載(+少し再編集)です。
旧社名になっていますが、内容は面白いものになっていると思いますのでぜひご覧ください。

---

毎日でも使いたい、国内発の新しいフードデリバリーサービス Chompy（チョンピー）。フードデリバリーをより身近にしてくれるその鍵は、Chompy独自の配達の仕組みにありました。

今回のインタビューでは、Chompyを運営する株式会社シンのエンジニア zaq1tomoさん・morikuniさんを相手に、Chompyが提供する"らくとく便"とそのアルゴリズムについて深堀りしていきます。

Chompy: https://chompy.jp/

ハブ・アンド・スポーク方式による配達の仕組み

-- お二人はどんな仕事をされているんですか？

zaq1tomoさん： Chompyで提供している "らくとく便"の開発をしています。実装だけでなくロードマップ作成やリリース調整などのPM的な動きもしています。

morikuniさん： 私はクルーさんに配達を依頼するアサインのマイクロサービスをまるっと開発しています。最近の仕事だとCloud Runを活用してアーキテクチャを刷新しました。
※ クルー：Chompyにおける配達員を指す

-- Chompyで提供しているらくとく便とはどのようなサービスでしょうか？

zaq1tomoさん： 配達予定時刻の1時間前までに事前注文していただくと、通常よりもお得に利用できるサービスです。複数店舗に注文しても “まとめてお届け” するので楽というのがコンセプトになります。
従来のフードデリバリーはひとつの注文に対して1回の配達という構造なのですが、Chompy のらくとく便では、それらとは別のアプローチを取っています。具体的には、配達時に中継地点を設けて複数のお店から商品を集めてくるステップと、それを配達するステップで配達を行っているのが特徴です。
まとめて注文・まとめて配達することで配送コストを削減でき、お客様にとって毎日でも使いやすい仕組みになっています。

-- クルーさんが複数の店舗を回るので計算も複雑になりそうですね。

morikuniさん： 前段ではどういうルートでお店を回って中継地点に運ぶか、どういうルートで中継地点から配達するかというルーティングの問題を解決しています。後段では、クルーさんをアサインするアルゴリズムが動いていて、どのクルーがお店から中継地点に運ぶか、どのクルーさんが中継地点からお客様に配達するかという問題を解決しています。

-- クルーさんへの報酬体系はどうなっているんですか？

zaq1tomoさん： 距離・拠点数・所要時間に応じた基本報酬と時間帯・気候などを考慮したブーストボーナスの合算で報酬を決定しています。らくとく便は短い時間で効率的に複数の拠点を回れるので、単位時間あたりで計算すると通常よりも高い報酬が得られやすいモデルになっていますね。

Cloud Runを活用した配送の最適化

-- らくとく便とアサインはどのようなアーキテクチャで動いていますか？

zaq1tomoさん： メインのAPI含むほとんどの機能はGAEで動いています。らくとく便のルーティングを行うためのマイクロサービスは、Cloud Runで動くようになっています。コンテナの中では配送計画問題を解くソルバーが動いていて、いくつかの制約条件から最適なルートを生成しています。

morikuniさん： アサインでは最適化されたルート情報を用いて、クルーさんへのアサインを行っています。言語はGoを使っていて、らくとく便と同じくCloud Runで動いています。今年の3月にアーキテクチャを刷新しました。

-- らくとく便とアサインはどのように連携しているんでしょうか？

zaq1tomoさん： らくとく便は問題が大きいので、最適化結果を一時的にGCSにダンプしています。その後、Cloud Pub/Subを活用してアサインのマイクロサービスに処理を渡しています。

Chompyのアルゴリズムの難しさと面白さ

-- クルーさんのアサインで難しいところはどのあたりですか？

morikuniさん： 配達遅延を無くそうと思うと、注文が入った時点でクルーさんをアサインをしてしまうのが効率的です。一方、Chompyの場合はクルーさんが5分以上お店で待機した場合は追加で報酬を支払う待機料金の仕組みがあるんです。そのため、お客様には遅延なく配送したいけれど、クルーさんには調理完了に合わせてお店に着いてほしいという制約のもとで問題を解く必要があります。そこらへんが結構難しかったりはしますね。

-- Chompyのアルゴリズムで面白いなと思うポイントはどこですか？

morikuniさん： リアルタイム性が高く変数も多く複雑な問題を解くところですね。

zaq1tomoさん：配達中だったクルーさんが数分後には配達可能な状態になっていたりもするんですよね。配達中のクルーさんの完了も予想しながら、ここぞというタイミングでアサインする必要がありますね。

-- アルゴリズムの最適化をするにあたって、どのコストを最小化しようと考えているんでしょう？

morikuniさん： 最小化したいのは配達料金と配達時間ですね。クルーさんの拘束時間という考え方をしてもいいですね。クルーさんが少しの間しか拘束されないのであれば、配達効率は上がります。そのため、できるだけ短い拘束時間で、時間内に配達を完了させられるようにアサインを最適化し、配達にかかるコストを下げようとしています。

-- 計算には地図データ（道路情報）も使ってるんですか？場所によっては渋滞や一方通行が非常に多そうで、考慮する必要があるのかなと思いました。

morikuniさん： 直線距離で近似しているところもあれば、正確なルート距離を使っているところもありますね。

zaq1tomoさん： 自転車とバイクでも通れる道が違ったりしますしね。厳密にルート距離する場合もあれば、必要に応じてある程度の地理情報から近似計算している場合もあります。

（後編に続きます）