一份荷兰 poffert（荷兰煎饼）如何能在 450 英里（700 公里）之外，第二天就送到你家门口？这要归功于精心的物流优化，尤其是中间一英里（middle-mile）环节。这一段行程覆盖的距离最长，占整体成本的很大一部分，更重要的是，它决定了你的 poffert 送到时是新鲜还是已经不新鲜。
物流研究历来集中在第一英里（将货物从生产者运到初始集货点）和最后一英里（配送给消费者）。这两个环节通常都被建模为车辆路径问题（VRP）的变体。然而，中间一英里负责在区域乃至洲际范围内的配送中心之间大批量转运货物，尽管占物流总支出的相当一部分，它在运筹学领域获得的关注却少得多。中间一英里优化的学术进展一直受制于缺乏公开的高质量数据。事实上，大多数物流公司都把自己的网络拓扑和需求量视为高度敏感的专有信息。
中间一英里物流在供应链中有许多应用：从把货物从工厂运给电商消费者和市中心的零售商，到把合适的零部件从各个工厂和中央仓库运给汽车制造商和维修店。它还包括对时效敏感的运输，例如在仓储设施与医院之间运送需要温控的药品。
为了解决该领域缺乏标准化数据的问题，我们在《A Novel Instance Generator for Simulating Middle-Mile Logistics Networks》一文中推出了 MilleMiglia，这是一个 C++ 实例生成器，用于为中间一英里配送问题创建贴近现实的基准测试。这项工作是推动未来研究成果的基础构件。在本文中，我们将探讨中间一英里的独特约束，以及 MilleMiglia 如何成功地刻画这些约束，从而生成既真实又保护隐私的数据。源代码和文档可在 GitHub 上获取。
物流链条：第一英里、最后一英里与中间一英里
第一英里、中间一英里和最后一英里物流的区别，在于单票货物的行程。在整个行程中，首要的运营目标是高效地利用车队访问多个地点。以一家制造商为例，它在典型的线上市场销售商品，触达个人消费者。
在第一英里和最后一英里物流中，一票特定货物从起点（第一英里是工厂，最后一英里是配送中心）到终点（第一英里是配送中心，最后一英里是客户）始终待在同一辆车上。这类 VRP 需要在有限的时间跨度（通常是一天）内优化由若干车辆组成的车队。优化挑战本质上是分配与排序问题：确定哪辆车负责哪一批货物，以及按什么顺序配送。
在我们的例子中，第一英里对应的是收取制造商已售出的商品（例如 pofferts），最后一英里则负责最终送达消费者（其中有些人可是饿坏了！）。在这两种情况下，都是一辆卡车往返于区域配送中心。然而，如果制造商和消费者位于不同区域，就需要由中间一英里物流来连接相距遥远的配送中心。例如，来自格罗宁根（荷兰）某制造商的货物，会先运到乌得勒支的区域配送中心，再前往法国巴黎的另一个中心，最后才送到凡尔赛的消费者手中。
与第一英里和最后一英里不同，中间一英里更像一场接力赛。一票货物在到达最终目的地之前，可能要由洲际网络中的多辆不同车辆运送，出发一周后才可能抵达。在中转配送中心，货物可能需要卸下、按目的地分拣，并与其他货物合并，然后再装上下一辆车。这就带来了复杂的同步问题：货物必须在特定时间窗口内到达配送中心，才能赶上按计划发出的卡车。如果错过了预定的衔接班次，就只能在配送中心等待下一个周期，造成严重延误。
在我们的例子中，制造商的货物到达乌得勒支区域中心后，会装上第一辆前往安特卫普（比利时）的卡车，当天抵达。由于最近的一班开往巴黎的卡车已经装满，而且假设客户选择了标准配送，这批货物会在第二天搭乘第二辆卡车从安特卫普前往巴黎。包裹在第二天夜里到达巴黎，随后进入最后一英里网络，于次日最终送到客户手中。
一票货物的一生：从格罗宁根（荷兰）的制造商到凡尔赛（法国）的客户，一份 poffert 的大部分旅程都在货运代理商的中间一英里网络中完成。
数学建模与求解器的局限
中间一英里配送的数学结构在几个关键方面不同于标准 VRP。
在传统 VRP 中，例如由 OR-Tools 等开源工具或 Google Maps Platform Route Optimization（GMPRO）等专用 API 求解的问题，目标通常是优化车队的行驶路线。重点在于车辆路径规划和停靠点排序，以满足紧迫的客户交付期限。与最后一英里配送不同，中间一英里物流还多了一层灵活性，即货物可以在卡车之间转换。我们将这一新增维度建模为时空图上的多商品流问题。在这些模型中：
- 节点：表示特定时间区间内的某个配送中心。
- 弧：表示车辆随时间的移动，或货物在配送中心的滞留（存放或按目的地分拣）。
硬约束
许多学术上的 VRP 只定义了很少的约束，而中间一英里的运营约束很难放宽，否则就会扭曲所面对的实际运营问题的结构：
- 固定时刻表：车辆通常按固定时刻表运行，必须予以遵守。
- 配送中心吞吐量：配送中心在每小时内能够分拣或越库转运的货量存在物理上限。
- 同步：一辆车的到达，是另一辆车上货物发出的前提。
由于这些依赖关系，现有的 VRP 求解器无法应用于中间一英里。该问题需要一系列中转配送中心，以及跨多辆车的分配，而且往往跨越多天的时间范围。
MilleMiglia：生成贴近现实的基准测试
数据驱动的分布
MilleMiglia 使用多种统计分布，确保合成网络看起来像真实的配送网络，同时不泄露任何私有信息：
- 空间分布：配送中心的布局采用引力模型或空间聚类，以反映现实世界中的人口和工业密度。
- 需求：按照贴近现实的体积和重量分布，生成带有起点—终点对的货物。
- 轮转班次（Rotations）：生成器创建的是结构化的车辆时刻表，而不是节点之间的任意连接，这些班次要么连接两个大型配送中心，要么连接一个大型配送中心及其周边规模较小的配送中心。
这些分布在行业参与者公开的信息与私下披露的数据之间进行插值。
性能与规模
MilleMiglia 用 C++ 编写，使用 Protocol Buffers 做数据序列化，因此各种形态的数据可以存放在每个实例对应的单个文件中。这样，生成的实例体积小巧，也便于用不同编程语言编写的求解器读取。
VRP 实例有许多变体，例如 CVRP（带容量）、VRPTW（带时间窗）或 PDPTW（带时间窗的取送货），以涵盖不同的运营需求。与此不同，我们的中间一英里数据格式把所有重要约束都嵌入同一种文件格式中：固定的车辆时刻表、配送中心的吞吐量上限，以及复杂的同步前提条件，都是问题结构的基本要素。
我们的目标是为社区提供一系列不同类型的实例：
- 小型实例：相当于学术界的“玩具”问题，用于测试精确算法。
- 工业级实例：大规模的、覆盖整个大陆的问题。这类问题需要先进的启发式或元启发式算法才能找到好的解。
- 介于两者之间的任意规模，包括中等规模和/或中等难度的实例。
该生成器还支持学习场景，因为它可以创建海量数据集来训练机器学习算法。
协作研究与未来的求解器
MilleMiglia 是迈向中间一英里物流标准化基准测试套件的第一步，类似于 CVRPLIB（Capacitated Vehicle Routing Problem Library，带容量车辆路径问题库）为 VRP 社区提供的资源。
该项目源于 Google 与 UniBrescia 和 ENPC Paris 的学术合作伙伴之间正在进行的合作。除了实例生成之外，我们目前还在研发一款专门针对中间一英里运营问题的求解器和 API。该求解器旨在利用中间一英里流量的独特结构。
通过开源我们的实例生成器，我们希望鼓励更广泛的研究社区关注中间一英里的运营挑战，从而打造更稳健、更高效的全球供应链。我们还希望发起一项中间一英里问题的挑战赛，以提升学术界和工业界求解器开发者对这一被忽视却亟待优化的领域的兴趣。任何对该领域感兴趣的人，都可以先看看 GitHub 仓库中托管的示例实例。
致谢
这项研究主要由 Aymane Lotfi（其在 Google 担任学生研究员期间）和 Matteo Petris（现就职于 ENPC Paris）完成，是一项持续合作的一部分。感谢 Thibaut Cuvelier 和 Bruno De Backer 对这项工作的贡献。特别感谢 Claudia Archetti（现就职于 UniBrescia）的领导与支持。