一份荷蘭鬆餅如何能在 700 公里外，隔天就送到你家門口？這歸功於精密的物流最佳化，特別是中段物流環節。這段旅程涵蓋最長的距離，佔總成本的巨大比例，最重要的是，它決定了你的鬆餅是新鮮送達還是變質。
過去，物流研究主要集中在首段物流（將貨物從生產商運到初步集貨點）和末段物流（送貨給消費者）。這兩個階段通常被建模為車輛路徑問題（VRP）的變體。然而，中段物流處理區域或洲際規模的物流中心之間的貨物批量運輸，儘管佔總物流支出的很大一部分，但在營運研究中受到的關注卻明顯較少。
學術界在中段物流最佳化方面的進展，一直受限於缺乏公開、高品質的資料。事實上，大多數物流公司都將其網路拓撲和需求量視為高度敏感的專有資訊。
中段物流在供應鏈中有許多應用。這些應用範圍從電子商務中將貨物從工廠運送給消費者，以及運送給市中心的零售商，到將正確的零件從個別工廠和中央倉庫運送給汽車製造商和商店。它還包括時間敏感的運輸，例如在儲存設施和醫院之間運輸溫控藥品。
為了解決此領域標準化資料的缺乏，我們在論文《一種用於模擬中段物流網路的新型情境生成器》中，介紹了 MilleMiglia。這是一個 C++ 情境生成器，旨在為中段配送問題創建擬真的基準測試。這項工作是未來研究成果的基礎。在這篇文章中，我們將探討中段物流的獨特限制，以及 MilleMiglia 如何成功捕捉這些限制，以生成擬真且保護隱私的資料。原始碼和文件可在 GitHub 上取得。
首段、中段和末段物流的區別在於單一貨件的旅程。在整個旅程中，主要的營運目標是有效率地使用車隊造訪多個地點。以製造商在典型線上市場銷售商品給個別消費者為例。
在首段和末段物流中，特定貨件從其起點（首段物流中的工廠，末段物流中的物流中心）到其目的地（首段物流中的物流中心，末段物流中的客戶）都停留在單一車輛中。這些 VRP 涉及在有限時間內（通常為一天）最佳化多輛車組成的車隊。最佳化挑戰本質上是分配和排序的問題：確定哪輛車處理哪組貨件，以及以何種順序處理。
在我們的例子中，首段物流對應於製造商已售出商品（例如鬆餅）的收集，而末段物流則涵蓋了對消費者的最終配送（其中一些人可能非常飢餓！）。在這兩種情況下，單一卡車將貨物運往或運出區域物流中心。然而，如果製造商和消費者位於不同區域，中段物流則負責連接遙遠的物流中心。例如，來自格羅寧根（荷蘭）製造商的貨物會先運到烏得勒支的區域物流中心，然後運到巴黎（法國）的另一個中心，最後再配送給凡爾賽的消費者。
與首段和末段物流不同，中段物流的功能就像一場接力賽。單一貨件可能由多輛不同的車輛在洲際網路中運輸，然後才到達最終目的地，可能在出發後一週。在中間物流中心，貨件可能會被卸下、按目的地分類，並與其他貨物合併，然後再裝載到下一輛車上。這產生了一個複雜的同步問題：貨件必須在特定的時間窗內抵達物流中心，才能趕上預定的出發卡車。如果錯過了預定的接駁，它將不得不停留在物流中心，直到下一個週期，導致嚴重的延誤。
在我們的例子中，一旦製造商的貨物抵達烏得勒支的區域中心，它們就會被裝載到第一輛開往安特衛普（比利時）的卡車上，並在當天抵達。由於最即時開往巴黎的卡車已滿，並且假設客戶選擇了標準運輸，貨物會在第二天搭乘第二輛卡車從安特衛普前往巴黎。包裹在第二天晚上抵達巴黎，然後進入末段物流網路，於第三天最終配送給客戶。
中段配送的數學結構與標準 VRP 在幾個關鍵方面有所不同。在傳統 VRP 中，例如由 OR-Tools 等開源工具或 Google Maps Platform Route Optimization (GMPRO) 等專用 API 解決的問題，目標通常是最佳化車隊的路線。重點在於車輛路徑規劃和停靠點的排序，以滿足嚴格的客戶期限。
與末段配送不同，中段物流增加了在不同卡車之間移動的靈活性。我們將這個額外的維度建模為時空圖上的多商品流問題。在這些模型中：節點代表特定時間間隔的特定物流中心；弧代表車輛隨時間的移動，或貨件在物流中心被保留（儲存/按目的地分類）。
雖然許多學術 VRP 的定義只有少量限制，但中段物流的營運限制很難放鬆，否則會扭曲當前營運問題的結構：固定班表：車輛通常按照必須遵守的固定時間表運行。物流中心吞吐量：物流中心對在特定時間內可以分類或交叉轉運的貨物量有物理限制。同步：一輛車的抵達是貨件在另一輛車上出發的先決條件。
由於這些依賴關係，現有的 VRP 求解器無法應用於中段物流。這個問題需要一系列中間物流中心和跨多輛車的分配，通常涉及多天的時間範圍。
MilleMiglia：生成擬真基準測試。
MilleMiglia 使用各種統計分佈，以確保合成網路看起來像實際的配送網路，同時不洩露任何私人資訊：空間分佈：物流中心使用重力模型或空間聚類來反映現實世界的人口和工業密度。需求：貨件以起點-目的地對生成，遵循擬真的數量和重量分佈。輪班：生成器創建結構化的車輛班表，而不是節點之間的任意連接，連接兩個主要物流中心或一個主要物流中心及其鄰近的較小規模物流中心。這些分佈在工業參與者公開資訊和私人披露資料之間進行插值。
MilleMiglia 以 C++ 編寫。它使用 Protocol Buffers 進行資料序列化，以便其多樣化的資料可以儲存在每個情境的單一檔案中。因此，生成的實例是緊湊的，並且可以輕鬆地被用不同程式語言編寫的求解器使用。
與 VRP 實例不同，VRP 有許多變體，例如 CVRP（帶容量）、VRPTW（帶時間窗）或 PDPTW（帶時間窗的取貨和配送），以捕捉多樣化的營運需求，我們的中段物流資料格式的結構將所有有趣的限制嵌入到相同的檔案格式中：固定的車輛班表、物流中心吞吐量限制和複雜的同步先決條件都是問題結構的基本要素。
其目的是為社群提供一系列情境：小型情境：相當於學術界的「玩具問題」，用於測試精確演算法。工業情境：大規模、洲際範圍的問題。這些問題需要進階的啟發式演算法或整合式啟發式演算法才能找到好的解決方案。以及介於兩者之間的任何大小，包括中等規模和/或難度的情境。該生成器還支援學習情境，因為它可以創建龐大的資料集來訓練機器學習演算法。
MilleMiglia 是邁向中段物流標準化基準測試套件的第一步，類似於 CVRPLIB（帶容量車輛路徑問題庫）為 VRP 社群提供的服務。這個專案來自 Google 與 UniBrescia 和 ENPC Paris 的學術合作夥伴之間正在進行的合作。除了情境生成，我們目前正在開發專門針對中段營運問題的求解器和 API。這個求解器旨在利用中段物流流的獨特結構。
透過開源我們的情境生成器，我們希望鼓勵更廣泛的研究社群關注中段物流的營運挑戰，從而建立更穩健、更有效率的全球供應鏈。我們希望發起一項中段物流問題的挑戰，以增加學術界和工業求解器開發人員對這個被忽視但需要最佳化領域的興趣。任何對此領域感興趣的人都可以從查看 GitHub 儲存庫中託管的範例情境開始。
這項研究主要由 Aymane Lotfi 在 Google 擔任學生研究員期間，以及 Matteo Petris（現任職於 ENPC Paris）作為正在進行的合作的一部分進行。感謝 Thibaut Cuvelier 和 Bruno De Backer 對這項工作的貢獻。特別感謝 Claudia Archetti（現任職於 UniBrescia）的領導和支持。