MilleMiglia：面向中程物流的真实实例生成器

MilleMiglia 用开源的真实基准填补了学术理论与工业物流之间的空白，让研究者能够优化复杂的中间英里网络，最终推动全球供应链变得更稳健、更高效。

快速链接

• 论文
• 代码

一块荷兰的 poffert 怎么能在 450 英里（700 公里）之外，第二天就送到你家门口？靠的是精细的物流优化——尤其是中间英里这一段。这段路程距离最长，占总成本的比例极大，而且最关键的是，它决定了你的 poffert 到手时是新鲜的还是已经放陈了。物流研究历来聚焦于第一英里（把货物从生产者运到最初的集散点）和最后一英里（送到消费者手中）。这两个阶段通常都被建模为车辆路径问题（VRP）的变体。但中间英里——在区域乃至大陆尺度上完成配送中心之间的大批量货物流动——在运筹学中受到的关注明显少得多，尽管它在物流总支出中占了相当大的比重。中间英里优化的学术进展一直受制于缺少公开的高质量数据。事实上，大多数物流公司都把自身的网络拓扑和需求规模视为高度敏感的专有信息。中间英里物流在供应链中有很多应用场景，从电商和市中心零售商把货物从工厂送到消费者手中，到把正确的零部件从各个工厂和中央仓库送到汽车制造商和门店。它也包括对时间敏感的运输，比如在仓储设施和医院之间运送温控药品。

中间公里物流填补了第一公里与最后一公里之间的空白。

针对这一领域缺乏标准化数据的问题，我们在《A Novel Instance Generator for Simulating Middle-Mile Logistics Networks》一文中提出了 MilleMiglia——一个用 C++ 编写的实例生成器，用于为中间公里配送问题构建贴近现实的基准。这项工作是一块基石，为后续研究铺路。本文讨论中间公里特有的约束条件，以及 MilleMiglia 如何刻画这些约束，从而生成真实且不涉及隐私的数据。源代码与文档已发布在 GitHub 上。

物流的谱系：第一公里、最后一公里与中间公里

第一公里、中间公里和最后一公里物流的区别，在于单件货物的运输旅程。在整个旅程中，首要的运营目标都是高效调度一支车队访问多个地点。设想一家制造商在常见的电商平台上销售商品，直接触达个体消费者。在第一公里和最后一公里物流中，一件货物从起点（第一公里是工厂，最后一公里是配送中心）到终点（第一公里是配送中心，最后一公里是客户）始终由同一辆车运输。这类 VRP 要在有限的时间跨度内——通常是一天——优化一支由多辆车组成的车队。优化难点本质上是分配与排序：哪辆车负责哪些货物，按什么顺序。在我们的例子里，第一公里对应的是收集制造商已售出的商品（比如 pofferts），最后一公里则是把货最终送到消费者手中（其中有些人已经饿得不行了！）。两种情况下，都是由一辆卡车往返于区域配送中心。但如果制造商和消费者身处不同区域，中间公里物流就要在相距遥远的配送中心之间架起桥梁。例如，来自荷兰格罗宁根某制造商的货物，会先运到乌得勒支的区域配送中心，再运往法国巴黎的另一个中心，最后才送到凡尔赛的消费者手中。与第一公里和最后一公里不同，中间公里更像一场接力赛。一件货物在抵达最终目的地之前，可能由多辆不同的车在一个横跨大陆的网络中接力运输，而这时距离发货也许已经过去一周。在中转配送中心，货物会被卸下，按目的地分拣，与其他货件合并，再装上下一辆车。这就带来一个复杂的同步问题：货物必须在特定时间窗内抵达配送中心，才能赶上计划中的下一班卡车。一旦错过衔接，它就得在配送中心等到下一个周期，造成严重延误。在我们的例子里，制造商的货物抵达乌得勒支区域中心后，被装上当天开往比利时安特卫普的第一班卡车。由于最近一班去巴黎的卡车已经满载，而且假设客户选择了标准配送，货物便在第二天从安特卫普搭第二班车前往巴黎。包裹在第二天夜里到达巴黎，进入最后一公里网络，次日送达客户。

一件货物的旅程：从荷兰 Groningen 的制造商到法国 Versailles 的客户，一块 poffert 的大部分路程都在货运代理的中程网络中完成。

数学建模与求解器的局限

中程配送的数学结构与标准 VRP 有几处关键差异。传统 VRP——无论是 OR-Tools 这类开源工具，还是 Google Maps Platform Route Optimization（GMPRO）这类专用 API 所求解的问题——目标通常是为车队优化路线，重点在于车辆路径和停靠顺序，以满足客户紧迫的时限。与尾程配送不同，中程物流多了一层在卡车之间转运的灵活性。我们把这一维度建模为时空图上的多商品流问题。在这类模型中：

• 节点： 表示特定时间段内的某个配送中心。
• 弧： 表示车辆随时间的移动，或货物在配送中心被暂存（按目的地存储／分拣）。

硬约束

许多学术 VRP 只定义少量约束，但中程运营中的约束一旦放松，就会扭曲实际运营问题的结构：

1. 固定时刻表： 车辆通常按固定时刻表运行，必须遵守。
2. 配送中心吞吐量： 配送中心在给定小时内能分拣或越库的货量有物理上限。
3. 同步： 一辆车的到达，是货物由另一辆车发出的前提。

由于这些依赖关系，现有的 VRP 求解器无法用于中程。该问题需要确定一串中间配送中心，并在多辆车上分配货物，时间跨度往往超过一天。

MilleMiglia：生成逼真的基准测试

数据驱动的分布

MilleMiglia 采用多种统计分布，使合成网络在贴近真实配送网络的同时，不泄露任何隐私信息：

• 空间分布： 配送中心通过引力模型或空间聚类来放置，以反映真实的人口与工业密度。
• 需求： 货运以起讫点对的形式生成，遵循真实的体积与重量分布。
• 路线循环： 生成器创建的是结构化的车辆时刻表，而非节点之间的任意连接；连接的两端要么是两个大型配送中心，要么是一个大型配送中心及其周边规模较小的配送中心。

这些分布在来自工业参与者的公开信息与私下披露的数据之间进行插值。

性能与规模

MilleMiglia 用 C++ 编写，使用 Protocol Buffers 进行数据序列化，因此多样化的数据可以全部存入每个实例的单个文件中。生成的实例因而紧凑，易于被不同编程语言编写的求解器读取。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）的领导与支持。