アマゾンのミドルマイルネットワークにおける不確実性の対応

「ラストマイル」の配送ドライバーがお客様の自宅へ向けて出発する前に、Amazon の商品は fulfillment centers（商品保管センター）と sort centers（仕分けセンター）からなるミドルマイルネットワークを通過し、お客様に商品を十分に近づけることで、当日または翌日の配送約束を実現可能にしています。長年にわたり、Amazon のエンジニアや科学者たちは、このネットワークの不確実性下での最適化に向けて計算の限界を押し広げてきましたが、ネットワークがより複雑になるにつれてその取り組みは加速しました。巨大な吹雪によって主要な高速道路が閉鎖された場合、仕分けセンターで停電が発生した場合、あるいはバズっている製品への需要が急増した場合、どうなるのでしょうか？これらの見出しを飾るような混乱は、システムに明白な衝撃を与えるため注目を集めますが、不確実性に対する計画の難しさを鮮明に示しています。しかし、最も重要な不確実性の源泉は、はるかに微妙です：需要や移動時間の日常的な変動であり、これらを注意深く見なければ、ネットワーク全体の効率を侵食していきます。私たちが発見したのは、需要の変動のみを考慮した場合でも、不確実性に対する最適化には 0.5% の潜在的な節約効果があるということです。これは小さな割合ですが、私たちは小さな割合に執着します。なぜなら、その背後には本当のお客様の体験が横たわっているからです。そして、需要の変動は、道路の遅延、処理時間の変動、無数の他の微細な変動を含むパズルの一部に過ぎません。 お客様が「今すぐ購入」をクリックする数ヶ月前から、Amazon の物流エキスパートは、ミドルマイルの経路に関する多様な質問を検討しています：トラックは倉庫間でどのルートを取るべきか？出荷はいつ出発すべきか？顧客需要を満たすために在庫はどこに配置すべきか？ネットワークの構造とタイミングを事前に形成することを「ネットワーク設計」と呼びます。私たちの課題は、完璧な条件での最適化を行うことではなく、物事が予想通りにいかない場合でも効果的であり続ける計画を立てることです。 桁外れの複雑さを伴う計算上のパズル たとえ完璧な条件に頼ることができたとしても、ミドルマイルネットワークの最適化は困難です。なぜなら、これは数百の施設を通過する数千万もの異なる製品の調整を必要とするからです。各施設には限られた容量と特定の営業時間があります。重要な難しさの一つは、関与する最適化決定の混合にあります。一部の決定は程度の問題（特定のルートに送る荷物の量）です。他の決定は二値的（この出荷経路を開くか開かないか、今すぐ出発するか貨物を待つか）です。これらを組み合わせると、「混合整数最適化問題」と呼ばれる種類の問題が生まれます。これは、解決戦略が計算時間とメモリ空間の両方で組合せ的に爆発する問題です。300 の yes-or-no 決定（はい/いいえの決定）があるだけで、すでに観測可能な宇宙の原子数よりも多い組み合わせが存在すると考えてみてください。Amazon のネットワークは数百万ものそのような決定を含んでおり、出荷が到着または出発できる時間を制限する配送ウィンドウによってさらに複雑化されています。最先端の最適化ソフトウェアでさえ、「完全な情報」を有する場合でもこの問題を解決するのは困難です。現実世界では、情報は完璧からほど遠く、紙面上では最適に見える計画も、条件が変われば崩れ去る可能性があります。 不確実性への対応の難しさ 不確実性は二つの異なる形で現れます。第一に、需要や移動時間といった変数の日常的な変動です。第二に、構造的な衝撃：天候による道路閉鎖や予期せぬ施設の停止です。学術的な研究では、一般的な戦略はネットワークが直面しうる多くのシナリオをモデル化し、それら全体で良好に機能するように解決策を「堅牢化」することです。しかし、Amazon の規模においてこのアプローチは失敗します。常に桁外れの数のことが起こり得る可能性があり、それぞれに対して個別に堅牢化を図ろうとすることは絶望的な任務です。不可能な保証を追うのではなく、私たちはより現実的な目標へとシフトします：「オプション性」です。私たちの目的は、日常的な変動や衝撃が危機ではなく効果的な適応を引き起こすような、十分な代替経路と実行可能な選択肢を備えたシステムを設計することです。 実際には、求めるべき柔軟性を確保するには、組み込みの選択肢を持つ候補となるネットワークを設計し、それらの設計を多くの plausible futures（妥当な未来）に対して stress-testing（耐性テスト）する必要があります。ここが Amazon の社内計算ツールの出番です。 ネットワーク設計の実用化 Amazon のネットワーク設計ツールは、ミドルマイルネットワークの問題をスケーラブルに解決可能にします。このツールは、単純な洞察から始まります：すべての可能な経路を検討する価値があるわけではありません。もしあなたがロードトリップ（道路旅行）の計画を立てているなら、自然と数本の合理的な経路に焦点を当てるはずです。このツールはこの原則を適用し、複数の起源からの荷物が共通の目的地へ向かうトラックを共有できる sort centers などの可能な「集約ポイント」を特定し、それらを利用する効率的な経路を見つけます。 私たちはまた、時計（時間）も尊重しなければなりません。なぜなら Amazon の施設は精密な運用スケジュールで稼働しているからです。例えば、ある仕分けセンターは午前 2 時から午前 6 時に着荷を受け入れ、午前 8 時から正午に出発トラックを運行します。理想的には、プランナーはこれらのスケジュールを細かな解像度（例えば 15 分間隔）でモデル化すべきですが、これにより可能性の爆発がもう一つ生じます。一方、24 時間間隔のような粗い解像度は、速くても役に立たない計画になります：荷物が施設の夜間閉鎖後に到着し、トラックは貨物を積む前に出発するスケジュールになってしまうからです。 Amazon のプランナーはこの頑固な問題を解決しつつ、運用の現実も支えることに成功しました。最適化アプローチは比較的粗い時間解像度で求解しますが、各候補経路に対して、15 分精度の「タイミングバウンズ（時間的制約）」— 最新の可能なトラック出発時刻と最も早い可能な到着時刻 — を事前計算して含めます。これにより、ツールが経路を選択する際、現実世界のスケジュールで機能するものを選んでいることになります。 スケーラブルなリスク認識型ネットワーク調整 これらのアルゴリズムの進歩があっても、Amazon の規模における単一の決定論的計画問題の解決には、基盤となるアルゴリズムの並列化の難しさのために数時間を要することがあります。不確実性を加えることは課題をさらに複雑にします。 ミドルマイルネットワークの不確実性を考慮する一つの素朴な方法は、より多くの荷物が大きく近い場所の間で流れると仮定して問題を単純化することです。しかし、ミドルマイルは独立したパイプの集合ではありません。製品の流れは相互作用します。ある fulfillment center での需要の急増は、近隣の施設に特定の形で影響を与えます；新しい配送ステーションが地域のパターンを変化させます。 これらの複雑な依存関係をよりよく捉えるために、モンテカルロ法（Monte Carlo methods）を通じてリスク認識型のネットワーク設計を可能にするアプローチを開発しました。Amazon のリスク認識型ネットワーク設計モデルは、需要の日常的な変動と大きな構造的衝撃の両方を表すために、多くの合成された起源-宛先フローデータの組み合わせを作成することから始まります。 モデルの重要な構成要素の一つに、ミドルマイルネットワークを二つの相互接続されたグラフとして表現する graph attention network model（グラフアテンションネットワークモデル）があります。第一のグラフは site graph（サイトグラフ）で、ノードは fulfillment centers と delivery stations を表し、エッジは shipping routes（出荷経路）と地理的な近接性の両方を表します。これにより、モデルは人口密集地周辺での需要が高いといった空間パターンを学習できます。 第二のグラフはより高いレベルで機能します：各ノードは特定の起源-宛先ペアを表します。この構造により、サイトグラフでは捉えきれないほど微妙な相関関係も把握できます。これは交通パターンの理解に似ています：二つの高速道路が近いこと（サイトグラフ）を知っていても、それらが同じ通勤者を争っているかどうか（起源-宛先グラフ）はわかりません。 例を挙げると、コネチカット州北部にあるニューヨーク市を担当する二つの近接した fulfillment centers を考えてみましょう。サイトグラフのみを使用するモデルは、各施設がニューヨーク市へ 8,000 個の荷物を送ると推定するかもしれませんが、実際には二つの施設がこの需要を共有しているため、実際の量はもっと低くなります。サイトグラフは fulfillment centers が近接していることを理解していますが、それらのニューヨーク市への流れが相互依存していることを完全に捉えていません。 起源-宛先グラフはこの問題を解決し、各施設から宛先までのペアを独自のノードとして表現することで、モデルが二つの類似した施設が同じ地域を担当する場合、その出荷は相互依存していると学習できるようにします。より広く言えば、この構造により、モデルは郊外の fulfillment centers が都市部へ配送するなど、類似した特性を持つ起源-宛先ペアは、遠く離れていても相関する需要を示す可能性があることを発見できます。 空間的な相関関係を尊重し、ネットワークの擾乱が空間的にどのように伝播するかを理解する現実的な需要シナリオを武器に、さまざまな需要条件の下でよく機能する候補となるネットワーク設計を生成することができます。 不確実性下での配送約束の維持 モデルが過去の shipping data（出荷データ）に基づいて訓練されるため、空間的な相関関係を尊重する現実的な需要シナリオを生成できます。そして何より、ツールがネットワークの擾乱が空間的にどのように伝播するかを理解しているため、新しい施設の開設や主要な地域的な気象イベントによって引き起こされた需要の変化など、ネットワークがこれまで遭遇したことのない plausible scenarios（妥当なシナリオ）も作成可能です。 これがループの欠けている半分です：一つの製品が将来の候補ネットワークを設計し、もう一つがそれらを stress-test するためのシナリオを生成します。したがって、プランナーは単一の予測を最適化するのではなく、数百の妥当なシナリオにわたってネットワーク設計を評価し、不確実性に対してネットワークを柔軟に保つ選択肢を維持できます。 全体として、これにより、平均的には効率的に見えるがストレス下では脆弱なネットワーク設計と、わずかに高い定常状態のコストがかかる可能性があるがより安定したパフォーマンスを提供するネットワーク設計を区別することが可能になります。お客様にとっては、この研究は、ピークショッピング期間や実際の混乱時を含む、より信頼性の高い配送約束として結実します。 高度な最適化技術と機械学習を組み合わせることで、Amazon は現実の世界に適応するように設計されたミドルマイルネットワークを構築しています。したがって、冬に暴風雪が地域を 2 フィートの雪で埋め尽くし、同じ日に新しい必須製品がバズったとしても、ネットワークはその衝撃を吸収し、条件が許す限り迅速に回復できます。 しかし、不確実性に対するレジリエンス（回復力）を構築する作業は完了していません。ネットワークが大きくなるにつれ、日々の配送約束を確実に維持するための計算ツールの発展への私たちのコミットメントも大きくなります。

アマゾンのミドルマイルネットワークにおける不確実性の対応

背景や根拠まで確認しますか？

このニュースを、実務の判断につなげる

調べる

選ぶ

サイト