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