Google Research 推出 MilleMiglia：面向中段物流的真实实例生成器

一份荷兰的poffert（荷兰小松饼）如何在第二天就送到450英里（700公里）之外的你家门口？这要归功于精细的物流优化——尤其是中间一英里环节。这一段行程覆盖的距离最长，在总成本中占比巨大，而且最重要的是，它决定了你的poffert送到时是新鲜还是已经不新鲜了。

物流研究历来聚焦于第一英里（将货物从生产者运至初始集散点）和最后一英里（配送至消费者）。这两个阶段通常都被建模为车辆路径问题（VRP）的变体。然而，中间一英里负责在区域或大陆范围内于配送中心之间进行货物的大批量运输，尽管它在物流总支出中占比可观，在运筹学研究中却受到的关注明显少得多。中间一英里优化方面的学术进展一直受制于缺乏公开的高质量数据。事实上，大多数物流公司都将自己的网络拓扑和需求量为高度敏感的专有信息。

中间一英里物流在供应链中有许多应用。从电子商务中将货物从工厂运至消费者、将货物运至市中心的零售商，到将合适的零部件从各个工厂和中央仓库运至汽车制造商和门店，都属于其范畴。它还包括对时间敏感的运动，比如在存储设施和医院之间运输温控药品。

为解决该领域缺乏标准化数据的问题，我们在“A Novel Instance Generator for Simulating Middle-Mile Logistics Networks”一文中推出了 MilleMiglia，这是一个 C++ 实例生成器，旨在为中间一英里配送问题创建逼真的基准测试。这项工作为支撑未来的研究成果奠定了基石。在本文中，我们探讨中间一英里所特有的约束条件，以及 MilleMiglia 如何成功捕捉这些约束，从而生成逼真且保护隐私的数据。源代码和文档已在 GitHub 上提供。

物流光谱：第一英里、最后一英里与中间一英里

第一英里、中间一英里和最后一英里物流之间的区别，在于单次货运的行程。在整个行程中，首要的运营目标都是高效地使用一支车队访问多个地点。设想一个制造商在典型的在线市场上销售商品以触达个体消费者的例子。

在第一英里和最后一英里物流中，某批特定货物从起点（第一英里为工厂，最后一英里为配送中心）到终点（第一英里为配送中心，最后一英里为客户）始终处于同一辆车中。这些 VRP 涉及在有限的时间跨度内（通常为一天）对一支由多辆车组成的车队进行优化。优化挑战本质上是分配与排序的问题：确定哪辆车负责哪一组货物，以及按什么顺序配送。

在我们的示例中，第一英里对应于制造商已售出物品的收集（例如 pofferts），而最后一英里则涵盖向消费者的最终交付（其中一些消费者已经饥肠辘辘了！）。在这两种情况下，都由一辆卡车将货物运往或运出区域配送中心。然而，如果制造商和消费者位于不同地区，中间英里物流则弥合相距遥远的配送中心之间的差距。例如，来自格罗宁根（荷兰）制造商的货物会先运往乌得勒支的区域配送中心，再运往巴黎（法国）的另一个中心，然后才交付给凡尔赛的一位消费者。

与第一英里和最后一英里不同，中间英里发挥着接力赛的作用。单批货物可能由多辆不同的车辆跨越一个洲际网络运输，才在出发约一周后到达最终目的地。在中间配送中心，货物可能会被卸下、按目的地分拣，并与其他货物合并，然后再装上下一辆车。这带来了复杂的同步问题：货物必须在特定时间窗口内到达配送中心，才能赶上预定的出港卡车。如果错过了预定的衔接，它就必须在配送中心等待下一个周期，从而导致严重延误。

在我们的示例中，制造商的货物一旦到达乌得勒支区域中心，就会被装上第一辆开往安特卫普（比利时）的卡车，并于当天到达。由于最近一班开往巴黎的卡车已满，并且假设客户选择了标准运输，货物便搭乘第二天的第二辆卡车从安特卫普运往巴黎。包裹在第二天夜里到达巴黎，随后进入最后一英里网络，以便次日向客户进行最终交付。

数学建模与求解器的局限

中间英里配送的数学结构在几个关键方面不同于标准 VRP。

在传统 VRP 中，例如由 OR-Tools 等开源工具或 Google Maps Platform Route Optimization（GMPRO）等专用 API 求解的 VRP，目标通常是优化车队的路线。重点在于车辆路径规划以及停靠点排序，以满足严格的客户截止时间。与最后一英里配送不同，中间英里物流具有在卡车之间转运的额外灵活性。我们将这一额外维度建模为时空图上的多商品流问题。在这些模型中：

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

硬约束

尽管许多学术 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）的领导与支持。