クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ

こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ（@s_osa_）です。 生鮮食品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。 このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。 解決したい問題 配送ルートとは クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。 クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川

[komutan1]

この配送ルート最適化はIBMのような超巨大IT企業や数学の専門家の少数精鋭企業までいろんなところが何十年も取り組んでる課題で専用パッケージがいくつも出てる領域。

[mohritaroh]

ナップサップ（問題）を背負った巡回セールスマン（問題）ってかんじだった。Web企業が流通までやってるのすごいな

[threewaygood]

相変わらず技術が目的化してる会社やな。いいから儲けようよ株式会社

[skypenguins]

面白いとは思ったけど組合せ最適化問題をOSS使って内製するのとNTTデータ数理システムみたいな会社と協力するのとではどっちがいいんだろ？

[augsUK]

クックパッドのエンジニアへの投資と会社業績を見る度、投資先間違えて引き返せない感しかないなあ。

[kabayakin]

“いにしえの時代、クックパッドマートの配送ルートは人間によって手組みされていましたが、ステーションの数が300くらいの頃で、熟練のルート職人が2日かけてやっとルートを組み終わるといった状況でした。”

[prograti]

サービスの強みの根幹を支える部分を内製できる技術力は流石ですね。

[sobatech]

クックパッドってこういうスキルのエンジニアもいるんだ。

[tumo300-500]

すごい。現実的に技術を組み合わせている印象

[n-styles]

パラメータの増えた巡回セールスマン問題っぽい。量子コンピュータの領域かと思ったら、近似解を求めるアルゴリズムはあるのね。

[masa_bob]

コロナがヤバい時に生鮮食料品がコンビニ入り口すぐの非対面、おまけに探せば安いのも多いのですごくお世話になりました。

[rgfx]

まぁそういう事を自前でチャレンジしてる面白い会社は傍から見てる分には好きよ

[ikajigoku]

実用例

[ledsun]

「巡回セールスマン問題」だ（前処理も大変）。Webプログラマーに「アルゴリズムの知識は必要か？」という問いに対する解答のひとつ、かな？

[efcl]

Open Source Routing Machine (OSRM)を使った経路探索

[lifefucker]

売れてんの？

[gcyn]

「続いてるなら良い会社」みたいなとこもありますけれども。どーなんでしょうねー。

[kaerudayo]

これは好物。

[maketexlsr]

最高に楽しそう。やりたい(全部データ揃えてもらった上で、ルーチンだけを。あ、個別制約と例外はやりたくない笑)

[ardarim]

コミケ巡回買い物問題（変数：買い物リスト、サークル搬入数、限定数、列形成速度、列捌け度、島混雑度、東西移動制約、…）

[AirReader]

おもしろい

[supra]

ダイクストラの応用でできるのかしら

[sakidatsumono]

or-tools

[spark7]

「「行きたくない度」（選好）を事前に登録しておき」「具体的な走行ルートは指定・指示していません」なるほど..

[yarukinasu]

生鮮を一品注文可能！？

[ya--mada]

サラリマン、ナップサック、充填

[respectbookmark]

こんなものまで内製化するのかぁ

[t_f_m]

あとで

[roshi]

実際の配送履歴と重ねてどれくらい肉薄しているのか見てみたい。

[tettekete37564]

面白そう。ゲームにして欲しい

[programmablekinoko]

熟練の巡回ドライバーとかは道路状況とか曜日やイベントを事前に察知してその日の朝に最適なルートを考えついたりするからスゴイ。コンピュータが肉薄できるか。

[totoronoki]

「外注会社の選定やルートの割当に使ってる」状況。具体的なルート指示はしていない、と。

[t1033]

買ったほうが安く付きそうな案件だな

[napsucks]

青葉台から世田谷に走ったり、多摩川を渡って戻ったりなど、現場から見たら理不尽にも感じそうなルート指示が出てるけど、いちおうコスト計算的には最適なんだろうなぁ。