MilleMiglia：一种用于中程物流的真实实例生成器

MilleMiglia 通过提供开源且逼真的基准测试，弥合了学术理论与工业物流之间的鸿沟，使研究人员能够优化复杂的中间里程网络，最终构建更稳健、高效的全球供应链。

快速链接

• 论文
• 代码
• 分享 复制链接 ×

一个荷兰小松饼如何能在第二天就出现在 450 英里（700 公里）外的你门口？这得益于精心优化的物流——尤其是中间里程环节。这段旅程距离最长，占据了整体成本的大部分，更重要的是，它决定了你的小松饼是新鲜送达还是已经变干。

物流研究历史上主要关注第一英里（将货物从生产者运送到初始集散点）和最后一公里（配送至消费者）。这两个阶段通常被建模为车辆路径问题（VRP）的变体。然而，尽管中间里程在区域或大陆尺度上处理分销中心之间的大批量货物运输，代表了物流总支出的相当大一部分，但在运筹学研究中却受到的关注较少。中间里程优化的学术进展因缺乏公开的高质量数据而受阻。事实上，大多数物流公司将其网络拓扑结构和需求体量视为高度敏感的商业机密。

中间里程物流在供应链中有着广泛的应用。这些应用包括电商中将商品从工厂运送到消费者或市中心零售商，以及将正确的零部件从各个工厂和中央仓库运送到汽车制造商和商店。它还涉及对时间敏感的运动，例如在仓储设施和医院之间运输需要温控的药品。

中间里程物流连接了第一英里和最后一公里。

为解决该领域标准化数据缺失的问题，我们在《一种用于模拟中间里程物流网络的新型实例生成器》一文中介绍了 MilleMiglia，这是一个 C++ 实例生成器，旨在为中间里程配送问题创建逼真的基准测试。这项工作作为基础构件，旨在推动未来研究成果的产生。在本文中，我们将探讨中间里程的独特约束，以及 MilleMiglia 如何成功捕捉这些约束以生成逼真且保护隐私的数据。源代码和文档已在 GitHub 上提供。

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

第一英里、中间里程和最后一公里物流的区别在于单个包裹的旅程。在整个旅程中，主要的运营目标是高效地利用车队访问多个地点。考虑这样一个例子：一家制造商通过在典型的在线市场上销售商品来触达个体消费者。

在第一英里和最后一公里物流中，特定的包裹从起点（第一英里的工厂，最后一公里的配送中心）到终点（第一英里的配送中心，最后一公里的客户）始终留在同一辆车中。这些 VRP 涉及在有限的时间跨度内（通常是一天）优化由几辆车组成的车队。优化挑战本质上是分配和排序问题：确定哪辆车处理哪些包裹集合，以及处理的顺序。

在我们的示例中，第一公里对应于收集制造商已售出的商品（例如 pofferts），而最后一公里则涵盖向消费者的最终交付（其中一些消费者可能相当饥饿！）。在这两种情况下，一辆卡车负责将货物运往或运出区域配送中心。然而，如果制造商和消费者位于不同的地区，中间里程物流便连接起遥远配送中心之间的空白。例如，来自荷兰格罗宁根（Groningen）制造商的货物首先会运至乌得勒支（Utrecht）的区域配送中心，然后前往法国的巴黎（Paris）另一个配送中心，最后再交付给凡尔赛（Versailles）的消费者。

与第一公里和最后一公里不同，中间里程的功能类似于接力赛。一批货物在到达最终目的地之前，可能会由多种不同的车辆在一个大陆网络中进行运输，这通常发生在出发一周之后。在中间配送中心，货物可能会被卸下、按目的地分拣，并与其他货物合并，然后再装载到下一辆车上。这就产生了一个复杂的同步问题：货物必须在特定的时间窗口内到达配送中心，以便赶上其预定的 outgoing 卡车。如果错过了预定的衔接班次，货物就必须在配送中心等待下一个周期，从而导致严重的延误。

在我们的示例中，一旦制造商的货物抵达乌得勒支区域中心，它们就会被装上开往安特卫普（比利时）的第一辆卡车，并于当天到达。由于发往巴黎的最紧迫卡车已满，假设客户选择了标准运输，那么货物将在第二天从安特卫普乘坐第二辆卡车前往巴黎。包裹在第二天夜间抵达巴黎，随后进入最后一公里网络，于次日完成对客户的最终交付。

货物的生命周期：从荷兰格罗宁根的制造商到法国凡尔赛的顾客，一个 poffert 的大部分旅程是在货运代理的中间里程网络中完成的。

数学建模与求解器限制

中间里程交付的数学结构在几个关键方面不同于标准的车辆路径问题（VRP）。

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

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

硬约束

尽管许多学术定义的 VRP 约束较少，但中间里程的操作约束很难在不扭曲当前操作问题结构的情况下放宽：

1. 固定时刻表：车辆通常按照必须遵守的固定时间表运行。
2. 配送中心吞吐量：配送中心在给定小时内能够分拣或越库操作的体积存在物理限制。
3. 同步性：一辆车的到达是另一辆车发出货物的先决条件。

由于这些依赖性，现有的 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）的领导与支持。

• 标签：
• 算法与理论