运筹优化CVRPTWOR-Tools物流整数规划

如何用运筹优化解决物流排车问题：CVRPTW 算法从理论到落地

背景

物流排车是一个经典的运筹优化问题——给定一批订单和一组车辆，如何规划每辆车的配送路线，使得在满足各种约束的前提下，总成本最低。

这个问题在学术上叫 CVRPTW（Capacitated Vehicle Routing Problem with Time Windows），听起来高深，但拆开来看，核心就是两个字：装得下和送的完。

这篇文章把我们在实际项目中解决这个问题的思路整理出来，包括业务约束的抽象、算法选型、关键创新点，以及踩过的一些坑。

问题拆解：装得下 + 送的完

装得下

最直观的约束：每辆车的装载量不能超过其承载能力。但真实业务比这复杂得多。

问题1：超单车承运能力

有些订单的商品体积或重量超过了单辆车的承载能力。这时候不能简单地把整个订单分配给一辆车，需要拆分。

我们设计了一个整数规划"打包"模型，从最小的商品粒度出发，自动决定如何拆分和组合订单，使得需要的车辆数最少。覆盖三种场景：

  • 单点位、单订单、单商品就超载
  • 单点位、单订单超载（多个商品加起来超）
  • 单点位整体超载（多个订单加起来超）

问题2：单维度装车的盲区

如果只按体积或只按件数来约束装车，会遇到实际装不下的情况：

  • 油、大米等密度大的商品，按体积算装得下，但严重超重，车开不动
  • 鸡蛋等易碎品，堆叠到一定高度就不能再放了

我们的解决方案是引入双重维度约束（体积+重量，或件数+重量），同时考虑密度和堆叠限制，系统性地解决"装得下"的问题。

送的完

装上车只是第一步，还得保证能在规定时间内送到。

问题1：时间窗口约束

每个配送点位都有履约时间窗口——最早可送达时间（通常是市场开门时间）和最晚要求送达时间。司机必须在这个窗口内完成配送。

我们引入 CVRPTW 的时间窗口约束，确保每个点位的作业完成时间严格落在要求的时间窗口内。

问题2：点位作业时间差异大

不同点位的作业难度差异很大——有的点位卸货方便，5分钟搞定；有的点位要爬楼梯、等电梯，可能要30分钟。如果用统一的时间估算，要么排得太松（车辆利用率低），要么排得太紧（送不完）。

我们的做法是：统计历史较长一段时间内，不同司机、各种情况下每个点位的作业时间，按点位取中位数，然后拆分到每件、每客户维度。这样就能比较合理地反映每个点位的真实作业难度。

问题3：留有余地

再精确的估算也挡不住突发情况——堵车、找不到停车位、客户不在。我们在每条线路的作业时间基础上，额外安排缓冲时间，保证司机即使遇到突发情况也能完成履约。

问题4：真实距离与时间

两点之间的直线距离不等于实际行车距离。我们接入高德地图 API，获取两两点位间的实际行车距离和行车时间，作为算法的输入。

算法选型：为什么用 OR-Tools

CVRPTW 是 NP-hard 问题，精确求解在大规模场景下不现实。我们选择 Google 的 OR-Tools 运筹优化求解框架，原因：

  • 成熟稳定：Google 维护，社区活跃，文档完善
  • 求解效率高：内置高效的启发式算法（如 Guided Local Search），能在合理时间内给出高质量解
  • 灵活可定制：支持自定义约束、目标函数、搜索策略
  • Python 接口友好：与业务代码集成成本低

OR-Tools 的核心思路是：先构造初始解（贪心策略），再通过局部搜索不断优化（交换、 relocate、cross-exchange 等算子），最终收敛到一个近似最优解。

关键创新点

1. 打包模型与路径优化的联合求解

传统做法是先决定怎么装车、再决定怎么排路线，两步分离。但装车方式会影响路线长度，路线长度又会影响装车策略。我们把打包模型和路径优化联合求解，在搜索过程中同时优化装车方案和路线规划。

2. 个性化点位作业时间

不是用一个统一的"每点位30分钟"，而是基于历史数据为每个点位计算个性化的作业时间估算。这使得排车结果更贴近实际，司机按照 AI 排线结果履约时，真的能送完。

3. 双维度装车约束

同时考虑体积和重量（或件数和重量），避免了单维度约束下的"装得下但超重"或"不超重但装不下"的问题。

实际效果

在宁波仓的试点中，AI 排车算法替代人工排车后：

  • 车均装载件数提升10%以上——同样的订单，需要的车辆更少
  • 履约达标率保持稳定——"送的完"约束有效
  • 年节省物流费用千万以上——直接体现为成本节约

总结

物流排车问题的核心是约束建模——把业务语言翻译成数学约束。"装得下"对应容量约束和装车模型，"送的完"对应时间窗口约束和作业时间估算。在这个基础上，用 OR-Tools 的启发式算法高效求解，再通过一些创新（打包模型、双维度、个性化作业时间）提升解的质量。

对于类似场景（城配物流、冷链配送、生鲜到家），这套方案可以作为参考蓝本快速复用。关键不在于算法本身有多新，而在于对业务约束的理解和建模——这是从理论到落地最核心的一步。