MilleMiglia：中距離物流向けのリアルなインスタンス生成器

MilleMiglia は、オープンソースの現実的なベンチマークによって学術理論と産業物流の間の空白を埋める。研究者が複雑なミドルマイルネットワークを最適化できるようにし、ひいては世界のサプライチェーンをより強靭で効率的なものへと押し進める。

リンク

• 論文
• コード

オランダの poffert が、450 マイル（700 キロ）離れたあなたの家の玄関に翌日届くのはなぜか。それを支えているのは精緻な物流最適化、とりわけミドルマイルの区間だ。この区間は距離が最も長く、総コストに占める割合がきわめて大きく、そして何より、手元に届いた poffert が新鮮か古びているかを決める。物流研究は伝統的にファーストマイル（生産者から最初の集積拠点まで貨物を運ぶ区間）とラストマイル（消費者に届ける区間）に焦点を当ててきた。この二つの段階は通常、vehicle routing problem（VRP）の変種としてモデル化される。だがミドルマイル——地域規模から大陸規模で配送センター間を大量の貨物が流れる区間——は、物流支出全体のかなりの割合を占めているにもかかわらず、オペレーションズリサーチでは明らかに注目が少ない。ミドルマイル最適化の学術的な進展は、公開された高品質のデータが存在しないことに長く妨げられてきた。実際、ほとんどの物流企業は自社のネットワークトポロジーと需要規模を、きわめて機密性の高い専有情報と見なしている。ミドルマイル物流にはサプライチェーン上の応用場面が数多くある。EC や中心市街地の小売業者が工場から消費者へ商品を届ける場合から、自動車メーカーや販売店へ各工場と中央倉庫から正しい部品を届ける場合まで幅広い。倉庫施設と病院の間で温度管理された医薬品を運ぶような、時間に敏感な輸送も含まれる。

ミドルマイル物流はファーストマイルとラストマイルの間の空白を埋める。

この分野に標準化されたデータが存在しないことを受けて、私たちは論文「A Novel Instance Generator for Simulating Middle-Mile Logistics Networks」で MilleMiglia を提案した。C++ で書かれたインスタンス生成器で、ミドルマイル配送問題のための現実に即したベンチマークを構築する。この取り組みは、今後の研究の道を開く礎となるものだ。本記事ではミドルマイル固有の制約条件と、MilleMiglia がそれをどう表現し、プライバシーを侵害しない現実的なデータを生成するかを論じる。ソースコードとドキュメントは GitHub で公開している。

物流のスペクトル：ファーストマイル、ラストマイル、ミドルマイル

ファーストマイル、ミドルマイル、ラストマイルの違いは、個々の貨物の輸送経路にある。経路全体を通じて、第一の運用目標は車両群を効率よく運用し複数の地点を訪問することだ。よくある EC プラットフォームで商品を販売し、個々の消費者に直接届ける製造元を考えてみよう。ファーストマイルとラストマイルの物流では、貨物は起点（ファーストマイルでは工場、ラストマイルでは配送センター）から終点（ファーストマイルでは配送センター、ラストマイルでは顧客）まで一貫して同じ車両で運ばれる。こうした VRP は、限られた時間枠——通常は 1 日——の中で複数の車両からなる車両群を最適化する。最適化の難しさは本質的に割り当てと順序付けにある。どの車両がどの貨物を担当し、どの順序で回るのか。私たちの例では、ファーストマイルは製造元が販売済みの商品（たとえば pofferts）を集めることにあたり、ラストマイルはそれを最終的に消費者（すでに腹ぺこになっている人もいる！）へ届けることにあたる。どちらの場合も、1 台のトラックが地域配送センターとの間を往復する。しかし製造元と消費者が異なる地域にいれば、ミドルマイル物流は遠く離れた配送センター間の橋渡しをする。たとえばオランダ・Groningen の製造元からの貨物は、まず Utrecht の地域配送センターへ運ばれ、次にフランス・Paris の別のセンターへ、最後に Versailles の消費者へ届けられる。ファーストマイルやラストマイルと違い、ミドルマイルは駅伝に近い。貨物は最終目的地に着くまでに、大陸をまたぐネットワークの中で複数の異なる車両に次々と積み替えられ、そのころには出荷から 1 週間が経っていることもある。中継配送センターでは貨物が降ろされ、目的地別に仕分けられ、他の貨物とまとめられて次の車両に積まれる。ここから複雑な同期の問題が生じる。貨物は特定の時間枠の中で配送センターに到着しなければ、予定された次のトラックに間に合わない。接続を逃せば、配送センターで次のサイクルまで待つことになり、大きな遅延になる。私たちの例では、製造元の貨物は Utrecht の地域センターに着くと、その日にベルギー・Antwerp へ向かう最初のトラックに積まれる。Paris 行きの直近のトラックはすでに満載で、顧客が標準配送を選んだとすると、貨物は翌日 Antwerp から 2 便目に乗って Paris へ向かう。荷物は翌日の夜に Paris に到着し、ラストマイルネットワークに入り、翌日顧客に届く。

ある貨物の旅：オランダ・Groningen の製造元からフランス・Versailles の顧客まで、poffert の大半は貨物代理店の中距離ネットワークを通って運ばれる。

数理モデリングとソルバーの限界

中距離配送の数理構造は、標準的な VRP と比べていくつか決定的に異なる。従来の VRP——OR-Tools のようなオープンソースツールであれ、Google Maps Platform Route Optimization（GMPRO）のような専用 API であれ、そこで解かれる問題——の目的は通常、車両の経路と停車順を最適化して顧客の厳しい時間制約を満たすことにある。last mile 配送と違い、中距離物流にはトラック間で貨物を積み替えられるという自由度が一段加わる。この次元を、時空間グラフ上の多品種流問題としてモデル化する。このモデルでは：

• ノード： 特定の時間帯における配送センターを表す。
• アーク： 時間の経過に伴う車両の移動、または配送センターで貨物が一時保管（目的地別の保管・仕分け）されることを表す。

ハード制約

多くの学術的な VRP は制約をわずかしか定義しないが、中距離オペレーションの制約は、緩めれば実際の運用問題の構造そのものが歪む：

1. 固定ダイヤ： 車両は通常、固定のダイヤで運行され、それに従わなければならない。
2. 配送センターのスループット： 配送センターが1時間あたりに仕分けまたはクロスドッキングできる貨物量には物理的な上限がある。
3. 同期： ある車両の到着が、別の車両から貨物を送り出す前提条件になる。

こうした依存関係のため、既存の VRP ソルバーは中距離には使えない。この問題では、中間配送センターの連なりを決め、貨物を複数の車両に割り当てる必要があり、時間軸はしばしば1日を超える。

MilleMiglia：現実的なベンチマークの生成

データ駆動型の分布

MilleMiglia は複数の統計分布を用いて、合成ネットワークを実際の配送ネットワークに近づけつつ、いかなるプライバシー情報も漏らさない：

• 空間分布： 配送センターは重力モデルまたは空間クラスタリングによって配置され、実際の人口密度と産業密度を反映する。
• 需要： 貨物は起点・終点のペアとして生成され、実際の体積と重量の分布に従う。
• ルート循環： 生成器が作るのはノード間の任意の接続ではなく、構造化された車両ダイヤであり、接続の両端は大規模配送センター同士か、大規模配送センターとその周辺の小規模配送センターのいずれかである。

これらの分布は、産業界の参加者から公開された情報と非公開で開示されたデータの間を補間する。

性能と規模

MilleMiglia は C++ で書かれ、データのシリアライズに Protocol Buffers を使うため、多様なデータをすべてインスタンスごとの単一ファイルに収められる。生成されるインスタンスはコンパクトで、異なるプログラミング言語で書かれたソルバーからも読みやすい。CVRP（_容量_制約付き）、VRPTW（_時間枠_付き）、PDPTW（時間枠付き集配）など、運用要件を捉えるために VRP インスタンスには多くの変種があるが、それらとは異なり、中距離輸送のデータ形式は興味深い制約をすべて同一のファイル形式に埋め込む。固定の車両ダイヤ、配送センターのスループット上限、複雑な同期の前提条件、そのすべてが問題構造の基本的な構成要素である。狙いはコミュニティに一連のインスタンスを提供することにある：

• 小規模インスタンス： 厳密解法を試すための、学界でいう「トイ」問題。
• 産業規模インスタンス： 大陸全体を覆う大規模問題。良質な解を見つけるには高度なヒューリスティックまたはメタヒューリスティックが必要になる。
• その間の任意の規模、つまり中規模かつ／または中程度の難易度のインスタンス。

生成器は学習用途にも使える。機械学習アルゴリズムを訓練するための大規模データセットを作成できるからだ。

共同研究と今後のソルバー

MilleMiglia は、中距離物流の標準ベンチマークスイートに向けた第一歩であり、CVRPLIB（容量制約付き車両経路問題ライブラリ）が VRP コミュニティに提供してきたものに相当する。このプロジェクトは、Google と UniBrescia、ENPC Paris の学術パートナーとの継続的な協力から生まれた。インスタンス生成に加えて、現在は中距離オペレーション問題に特化したソルバーと API も開発している。このソルバーは、中距離貨物輸送に固有の構造を活かすことを狙っている。インスタンス生成器をオープンソース化することで、より広い研究コミュニティが中距離の運用課題に目を向け、より堅牢で効率的なグローバルサプライチェーンにつながることを期待している。中距離問題のチャレンジを立ち上げ、長く見過ごされてきたものの最適化が急がれるこの領域に、学界と産業界のソルバー開発者がより関心を持つようにしたい。この分野に関心のある人は、GitHub リポジトリのサンプルインスタンスから始められる。

謝辞

本研究は主に、Aymane Lotfi が Google の学生研究員だった期間と、Matteo Petris（現在は ENPC Paris 在籍）によって、継続的な協力の一環として行われた。本研究への貢献に対して Thibaut Cuvelier と Bruno De Backer に感謝する。指導と支援に対して Claudia Archetti（現在は UniBrescia 在籍）に特に感謝する。