こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ（@s_osa_ ）です。
生鮮食品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。
このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。
解決したい問題
配送ルートとは
クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。
クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ
ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川県、埼玉県、千葉県の一部地域に700以上のステーションがあり、それらのステーションに対して複数のハブから配送をおこなっています。
ステーションはコンビニやマンションなどに設置されている冷蔵庫で、クックパッドマート配送の大きな特徴のひとつです。
クックパッドマートのステーション（冷蔵庫）
サービスの利用方法は次のような流れになります。
アプリから商品を注文する
最寄りのステーションに商品が届く
都合の良いタイミングで受け取る
この仕組みにより、1品から送料無料を実現できたり、配達時間に在宅しておく必要がなくなったりといった特徴が実現されています。
一部地域を抜粋してハブとステーションを地図にプロットすると以下のようになります。白抜きされた大きな点がハブ、小さくて黒い点がステーションです。
ハブとステーションの位置
すべてのステーションに商品を届けるためには、ハブ（白抜きされた大きな点）を出発してステーション（黒い点）を網羅するルートを作る必要があります。
たとえば、以下のような感じです。
配送ルートのイメージ
配送ルートに求めるもの
配送ルートを組むにあたり、どんなルートでも良いかというと当然そんなことはなく、いくつかの制約や目標があります。具体的には以下のようなものです。
所要時間（所定の時間内に配送完了できる）
積載量（商品をあふれさせず積みきれる）
ステーションの営業時間
コスト効率
スケーラビリティ
それぞれの性質について簡単に解説します。
所要時間
現在のクックパッドマートでは12:00から商品を受け取れるようにしており、08:00から12:00までの4時間でステーションへの配送をしています。生成するルートはこの時間内に配送を終えられるように組む必要があります。
積載量
車に積める量には限度があります。
クックパッドマートでは商品をコンテナ（カゴ）に入れて運んでいます。常温商品はコンテナをそのまま積み込めば良いですが、冷蔵商品はコンテナをシッパーと呼ばれる保冷容器に入れた上で蓄冷材と一緒に運ぶ必要があるのでより多くの体積を必要とします。
シッパー（保冷容器）に収まっているコンテナ
こういった温度帯ごとの体積の違いといった事情も考慮した上で商品を車両に積みきれるようにルートを組む必要があります。
ステーションの営業時間
配送先のステーションには、納品できる時間帯に制限があるステーションも存在します。
たとえば、マンションで09:00以降にならないと管理人さんがいないため入れない、ドラッグストアの営業時間が10:00から、といったケースなどがあります。
こういった各ステーションの営業時間を考慮して、納品できる時間に着くようにする必要があります。
コスト効率
配送は車両と人間を動かす必要があるので、かなりコストがかかります。毎日ルートが1本減ればその1本分、月で延べ30本分のコストが削減できます。
したがって、できるだけ少ないルート数で配送できるようにしたいという要求があります。
スケーラビリティ
上記のような制約や目標を考慮しながらルートを組むのは人間にはあまりにも難しいです。
いにしえの時代、クックパッドマートの配送ルートは人間によって手組みされていましたが、ステーションの数が300くらいの頃で、熟練のルート職人が2日かけてやっとルートを組み終わるといった状況でした。
サービスは今後も拡大していくため、ステーションが増加してもルートを組み続けられる仕組みが必要です。
ブロック分割
さて、これからルートを組んでいくわけですが、複数のハブから700箇所のステーションに運ぶとなると「それぞれのステーションにはどのハブから運ぶのか」ということが問題になってきます。
そこで、ルート生成に先立って、それぞれのステーションをハブに対応付ける前処理を入れます。我々はこれをブロック分割と呼んでいます。
先にブロック分割の結果を図示しておくと次のようになります。同じ色の点が同じブロックに属するステーションです。
ブロック分割のイメージ
ブロック分割の方針
基本的な考え方はとてもシンプルで「それぞれのステーションに近いハブから運ぶ」というものです。この方針はわりと素直に受け入れてもらえるものだと思います。
ただ、この方針を実装していくにあたり、考慮・対応すべきことがいくつかあるので、それらの点について書いていきます。
「近い」とは
「近いハブから運ぶ」と言っても、本当に関心があるのは距離ではありません。実は「ルートに求めるもの」のところでも距離には一切触れていません。
では代わりに何に触れているかといえば、時間です。所定時間内に運びきるという制約を考えるためには距離よりも時間に着目する必要があります。
移動時間の求め方
最も素朴な移動時間の求め方はハブやステーションの緯度経度から直線距離を求めて、平均速度で割るというものです。この方法は正確性は低いですが実装が楽で早くリリースできるので最初期はこの方法で計算していました。
ただし、この直線距離を使う方法には大きな問題があります。最も顕著な例としては、東京や神奈川から千葉に商品を運ぼうとすると車が東京湾の海上を走れることになってしまいます。言うまでもなく車は海上を走れないので、実際には沿岸部の道路だったり東京アクアラインだったりを通って迂回する必要があり、計算結果にかなり大きな誤差が生じてしまいます。また、東京湾ほど大きくないものだと「川は橋がある箇所でしか渡れない」「行きたい方向に走っている太い道路がない」などの誤差要因もあります。
そこで、道路を考慮した移動時間を計算するために Open Source Routing Machine (OSRM) を使っています。
http://project-osrm.org/
OSRM は OpenStreetMap (OSM) の地図データを用いて経路計算をしてくれるルーティングエンジンです。Google Maps の経路検索をイメージしてもらうとわかりやすいと思います。
OSRM はフロントエンドまで含めたプロジェクトになっていますが、バックエンドの API だけでも利用することが可能です。クックパッドマートでは社内にデプロイした OSRM の API を使って移動時間を計算しています。また、この API は数十msと比較的高速にレスポンスを返してくれますが、ルート生成の過程では大量の移動時間の計算が発生するため、必要になる移動時間は事前に計算して DB に入れておいて、計算時には一括でメモリに載せてしまうなどのパフォーマンス上の工夫もいくつかおこなっています。
各ハブのキャパシティ考慮
近くのハブから運びたいというのは間違いなく真です。ただし、「運びたい」と「運べる」は別の話です。
現実の各ハブが無限の荷量をさばけるかというと決してそんなことはなく、実際にはさばける荷量（キャパシティ）には上限があります。そこで、各ハブがさばける荷量に収まるようにステーションの紐付け先を調整します。
この調整はわりと素朴なアルゴリズムでおこなっています。具体的には、事前に各ハブに移動時間に対する係数を持たせておいた上で、キャパシティを超えているハブがあった場合、そのハブの係数を増やします。そして、変更後の係数を使って移動コスト（係数を反映した重み付き移動時間）を再計算した上で、紐付け先を計算し直してキャパシティに収まっているかチェックして……というのを繰り返します。細かいところの動作は全然違いますが、k-means 法などをイメージしてもらうとわかりやすいかと思います。
ルート生成
ブロック分割によって、それぞれのステーションにどのハブから商品を運ぶかということが決まったので、各ブロック内でルートを組んでいきます。
初めにも貼りましたが、再掲しておくと、たとえばこんなルートになります。
配送ルートのイメージ（再掲）
配送ルートの組み方
配送ルートを組む問題を一般に配送計画問題（Vehicle Routing Problem, VRP）と呼びます。組み合わせ最適化問題の一種で、最適解を現実的な時間（多項式時間）で求めることはできない問題です。
一方で、VRP という名前がついているくらいには有名な問題なので、近似解を求めるライブラリなどは存在しています。クックパッドマートでは OR-Tools というライブラリの Ruby wrapper を使用しています。公式の C++, Python 実装ではなく非公式の Ruby 版を使っているのは既存実装との繋ぎ込みやチームのメンバー構成などを考慮した結果です。
VRP の最も難しい部分である解の探索はライブラリがやってくれるので、我々アプリケーション開発者は自分たちのサービスが必要としているルートの条件を整理・変形して、ライブラリが解ける一般的な問題に落とし込んでいきます。
一般的な問題への落とし込み
基本的な考慮事項は前述の所要時間・積載量・ステーションの営業時間などです。これらを OR-Tools が求めるカタチにして渡していきます。
たとえば、移動時間の計算に OSRM を使う話をしましたが、OSRM が返す移動時間は実際にかかる移動時間よりも少なめに出ることが多いので、その差を補正するための係数をかけています。
また、移動時間は OSRM で算出することができますが、実際には移動時間とは別に各ステーションでの納品にかかる作業時間があります。そこで、作業時間を考慮したトータルの所要時間を入力として渡すようにします。
さらに、一般的な VRP は配送完了後に出発地点に帰ってくるルート、つまり1周するルートを組むようにできています。しかし、クックパッドマートで必要な制約は「12:00までにステーションに配送完了」であって「12:00までにハブに戻る」ではないので、最終配送の後の戻りルートを時間計算に含めないようにする必要があります。
こうして、自分たちのサービスで必要なことをひとつずつ一般的な問題に落とし込んでいきます。
運送会社へのルートの割り当て
クックパッドマートでは実際の配送業務自体は運送会社に外注しています。また、外注先の運送会社は複数社あります。そこで、生成したそれぞれルートをどの会社に割り振るかということを考える必要があります。いわゆるマッチング問題の一種ですが、ここでもいくつかの考慮事項があります。
たとえば、それぞれの運送会社には「行きたいハブ」と「行きたくないハブ」があります。これは運送会社の立地や営業エリアなどの特性によって生じるものです。運送会社と継続的な関係を結んでいくためには各運送会社にとって無理がないルートを割り振る必要があります。
この問題を解決するために、確保しているそれぞれの車両とハブの組み合わせについて「行きたくない度」（選好）を事前に登録しておき、その点数ができるだけ小さくなるようにルートを割り当てています。
また、「あるステーションは入館証が必要で、入館証を持っているのはA社のみ」のような制約もあるので、そういった点も考慮して各ルートを運送会社に割り振っています。
やっていないこと
ここまでルート生成でやっていることについて書いてきましたが、一方で意図的にやっていないこともあります。
代表的なものが具体的な走行ルートの指示です。各ステーションの配送順序や住所とその住所の Google Maps URL などは提供していますが、具体的な走行ルートは指定・指示していません。これは交通状況は常に変化するため効果的なルート指定が難しい上、運送会社やドライバーの方は運転・配送についてはプロなので指定する必要性が低いというのが理由です。
また、それぞれのブロックは独立しているのでルート生成は並列化可能ですが、今のところ特に困っていないので直列で計算しています。
おわりに
クックパッドマートで配送ルートを自動生成している仕組みについて簡単に紹介してきました。
どの領域でもそうだと思いますが、流通というドメインにも特有の問題や難しさ、そして楽しさがあります。また、問題解決のためには事業ドメインと技術ドメインの両方を考慮して解決方法を探っていく必要があります。現実世界のモノを運ぶという課題に対して、ソフトウェアを軸足にして取り組んでいくのは非常に楽しいです。
このエントリで紹介できたのは流通という領域のごく一部です。少しでも興味が湧いた方がいたらぜひご連絡ください。採用サイトからの正規ルートでも良いですし、@s_osa_ まで雑に DM していただくなどでも大丈夫です。よろしくお願いします。
2022年クックパッドマート連載の他のエントリ
