链上镖师 / Chain Biaoshi
TRE|中型运输企业挂车配送：异构车队路径优化
用候选路线枚举加集合划分模型，把取送货、时间窗、尾板、挂车和工时约束压进分钟级路径优化。
这篇TRE论文把中型运输公司的真实派车难题建成丰富VRP，并用路线池枚举加集合划分优化，在最多55个节点的实例上实现平均16.7%的成本节省。
- 01：研究对象是德国一家中型物流企业的取送货路线计划，包含异构车辆、挂车、硬时间窗、尾板需求、载重托盘约束和司机工时约束。
- 02：方法先生成可行候选路线，再用集合划分模型选择总成本最低的路线组合，目标成本包括车辆公里成本、挂车公里成本和人工时间成本。
- 03：三组真实运营日实验显示，matheuristic相对历史计划平均节省16.7%，求解时间保持在三分钟以内；纯数学模型平均再优2%至3%，计算代价明显更高。
研究背景
中型运输公司每天面对的派车问题，常常比标准车辆路径问题更杂。订单有取货点和送货点，部分客户有硬时间窗，车辆能力、尾板配置、挂车兼容性和司机工时都会影响一条路线能否执行。人工排线在时间压力下容易漏掉合并运输机会，车辆容量利用率和总成本都会受影响。
论文选择一家德国中型物流服务商作为案例场景。作者把研究目标放在中型企业可落地的自动化路线计划工具上，让计划结果在几分钟内可用，并且完整满足企业实际运营约束。
这类问题的关键难点在于约束之间会相互牵制：能装下货物的车未必有尾板，能挂车的车数量有限，时间窗和9小时最大行程又会继续压缩可选路线空间。
核心问题
论文要解决的核心任务，是把全部运输作业分配给合适的车辆和挂车组合，并生成满足取送货先后关系、时间窗、容量、托盘、尾板和最大行程约束的路线。目标函数最小化总运营成本，成本由车辆行驶成本、挂车行驶成本和司机人工时间成本构成。
01每个订单包含取货节点和送货节点，取货必须先于送货。
02同一父订单下的子订单需要由同一辆车服务。
03车辆和挂车有不同载重、托盘位、速度、公里成本和人工成本。
04需要尾板的节点只能由带尾板车辆服务。
05每条路线的总时长上限为9小时。
作者把这个问题定位为面向真实企业的丰富VRP。它同时包含取送货、异构车队、挂车、设备兼容、容量传播、时间窗和工时限制，重点在于让模型输出的路线可以直接被调度人员理解和执行。
方法框架
论文提出的matheuristic采用两段式结构。第一段按照订单和节点组合构造候选路线，并对每条路线做完整可行性检查；第二段把通过检查的路线交给集合划分模型，从路线池中选择覆盖全部节点且总成本最低的组合。
1按同一订单和相近取送货节点生成节点组。
2在节点组内枚举满足取货先于送货的排列。
3加入仓库起终点形成完整路线。
4按时间窗、最大行程、载重、托盘和尾板约束筛掉不可行路线。
5对每个车辆类别和节点组合保留最短有效路线。
6用集合划分模型选择最终路线组合。
来源：Fig. 5，候选路线需要依次通过时间窗、最大行程、载重、托盘和尾板等车辆约束检查。
来源：Fig. 6，每个车辆类别和节点组合只保留最短有效候选路线，用于压缩后续集合划分模型的路线池。
这种设计利用了案例中的一个业务事实：可行路线通常只包含少量停靠点。因此，作者可以在有界节点组内系统枚举排列，把可行性判断前置到路线生成阶段，减少后续优化模型需要处理的无效组合。
案例或实验设置
实验使用三天真实运营数据，分别称为Instance I、II和III。前两组各有27个总订单和55个总节点，第三组有22个总订单和45个总节点；尾板需求节点分别为8、10和4个。每个节点服务时间按企业规划假设取10分钟，节点间距离由经纬度大圆距离乘以1.3的绕行系数得到。
来源：Table 4，三组真实运营实例覆盖订单数、子订单数、节点数、尾板需求、重量、托盘、时间窗和距离统计。
来源：Table 5，案例车队包含29辆机动车和9个挂车，其中7辆车可挂车、14辆车带尾板。
来源：Table 6，不同车辆类别在载重、托盘位、平均速度、公里成本和人工成本上存在明显差异，挂车按0.12欧元/公里计成本。
车队由厢式货车、运输车、3.5吨以内卡车、7.5吨以内卡车、16吨以内卡车和挂车构成。车辆公里成本从0.40欧元到0.80欧元不等，人工成本从每小时13欧元到19欧元不等，这些差异决定了优化模型会在车辆能力和路线成本之间做精细选择。
结果分析
作者先测试分组规模参数N。N越大，候选路线池越丰富，成本有机会下降，计算时间也会快速上升。实验显示，N超过6后成本改善的边际收益下降，运行时间增长更明显，因此论文把N=6作为后续比较的默认参数。
来源：Fig. 8，分组规模N增大后，候选路线数量和运行时间上升，成本改善在N=6之后趋于放缓。
来源：Table 7，不同实例规模下，matheuristic、纯数学模型和公司历史运营方案在路线数、总成本和求解时间上形成对比。
来源：Fig. 10，随着实例规模变化，matheuristic的总成本持续低于历史运营方案，并接近纯数学模型结果。
matheuristic平均节省
16.7%
相对公司历史运营计划
纯数学模型平均节省
18.4%
在8小时限制内可求解时
管理启示
结果显示，matheuristic在最多55个节点的实例上能把求解时间控制在秒级到分钟级，适合中型运输企业的日常派车节奏。纯数学模型平均可再降低2%至3%的成本，可计算时间难以支撑实时排线，因此更适合作为小规模或离线评估基准。
来源：Fig. 11，matheuristic在平均节省率和运行时间之间取得可执行的折中，支撑分钟级决策支持定位。
来源：Fig. 12，成本分解显示优化方案通过车辆成本、挂车成本和人工成本结构调整来获得节省。
来源：Table 8，取消挂车后总成本平均上升17.09%，车辆成本平均上升28.30%，时间成本平均上升22.25%。
来源：Fig. 13，无挂车情景下成本和用车压力上升，说明挂车兼容车辆与挂车资产对中型运输公司的经济价值。
论文：Solving a rich vehicle routing problem with a heterogeneous fleet and trailers in medium-sized transport companies
作者：Robin Aninger，Stefan Voigt
期刊：Transportation Research Part E
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
