链上镖师 / Chain Biaoshi
TRB|众包配送的时间窗约束：旅行时间不确定下的分布鲁棒路径优化
用Wasserstein不确定集与CVaR控制迟到风险，并以分支定价割算法求解
本文研究旅行时间分布未知条件下的众包配送车辆路径规划，通过Wasserstein分布鲁棒优化与CVaR时间窗约束控制迟到风险。
- 01：研究对象是由公司司机与店内顾客共同完成的末端配送车辆路径问题。
- 02：模型将旅行时间分布的不确定性纳入时间窗约束，使用CVaR衡量迟到风险。
- 03：Wasserstein支持集可描述旅行时间之间的耦合关系，并通过安全缓冲提前收紧截止时间。
- 04：分支定价割算法在基准算例上验证了模型的求解能力与服务表现。
- 05：风险厌恶水平提高会带来更高运营成本，并改善多项准时服务指标。
众包配送为何需要考虑旅行时间风险
众包配送系统由公司常规司机与店内顾客组成的偶发司机共同服务订单。顾客、司机目的地与配送节点都可能带有时间窗，路线安排需要兼顾订单覆盖、车辆容量、司机补偿和按时服务。旅行时间存在波动时，基于单一平均值规划的路线容易在实际执行中出现延误。本文将总运输成本与偶发司机补偿纳入目标函数，并把时间窗违约风险放入优化约束。
01配送对象：客户订单与偶发司机目的地
02核心约束：流平衡、需求满足、车辆容量与时间窗
03优化目标：控制总运输成本，降低延误风险
04实验规模：最多100个客户节点，最多20名偶发司机
图2：带时间窗和旅行时间的路线R=（0，1，2）（来源：Fig. 2）。
旅行时间不确定集如何收紧配送截止时间
论文采用Wasserstein距离构造旅行时间分布的不确定集，允许模型围绕历史样本考虑一组可能的真实分布。支持集可加入不同弧旅行时间之间的耦合约束，避免模型采用历史数据无法支持的过度乐观组合。模型再使用CVaR描述服务开始时间的尾部风险，使长时间延误对路线可行性的影响得到保留。
1历史旅行时间样本 → 构造经验分布
2Wasserstein半径与支持集 → 定义可能分布范围
3CVaR约束 → 评估服务开始时间的尾部风险
4等价重构 → 将分布鲁棒约束转化为样本平均约束与安全缓冲
图1：旅行时间支持集示例（来源：Fig. 1）。
从弧模型到可求解的路线组合模型
弧模型负责表达客户服务、车辆流动、容量限制和偶发司机补偿。由于服务开始时间函数包含沿路线的最大累计到达时间，直接使用混合整数规划求解存在困难。论文将模型转化为基于路线的集合划分形式，每条路线携带客户覆盖、司机使用、成本与时间窗可行性信息，再通过列生成逐步补充有价值的路线。
阶段 1 受限主问题：从有限路线集合开始
阶段 2 定价子问题：搜索具有改善潜力的新路线
阶段 3 受限记忆子集行割：强化线性规划下界
阶段 4 分支规则：优先切割集，再处理弧变量
阶段 5 根节点启发式：列生成与VNS联合生成上界
表6：不同范数下的模型性能（来源：Table 6）。
基准算例与算法求解表现
实验基于Solomon车辆路径时间窗算例中的C1、R1和RC1类别，选择紧时间窗实例构造29个基础算例，并分别截取25、50和100个客户节点，形成87组测试规模。旅行时间采用非对称两点分布生成，实验默认使用200个样本、Wasserstein半径0.001、风险厌恶水平0.2、l1范数、偶发司机补偿因子1.2与2小时计算时限。
25个客户节点
29/29
50个客户节点
28/29
表4显示，RM模型在25个客户节点规模下29个算例全部求得最优解，50个客户节点规模下完成28个算例的最优求解，100个客户节点规模下完成10个算例的最优求解。论文进一步报告，分支定价割算法求解RO与RM模型的平均计算时间分别为600.59秒和592.44秒。
图4：RM模型指标的归一化结果（来源：Fig. 4）。
风险厌恶水平怎样改变成本与准时服务
在风险厌恶水平α从0提高到0.5的实验中，RM模型的多项迟到概率与迟到时长指标整体下降，运营成本逐步上升。论文报告，平均成本增加约1%时，综合服务水平改善约19%；平均成本增加约2%和3%时，服务水平改善约42%和60%。结果说明，风险参数为配送决策提供了成本与准时服务之间的调节旋钮。
约1%成本增幅
约19%
约3%成本增幅
约60%
图3：RM模型不同风险厌恶水平下的归一化指标（来源：Fig. 3）。
与确定性路径和服务中心模型的比较
与确定性模型DM相比，RM模型在各类准时服务指标上表现更好，成本增幅控制在3%以内。RM模型以每个客户的截止时间风险为约束，因而在最差客户表现指标MaxProb上具有优势。与以服务指标总和为中心、设置成本预算的SM-OCP相比，RM在最差客户迟到概率上表现更好，SM-OCP在部分总量指标上更具优势。
图5：RM与SM-OCP在两点分布下的性能比较（来源：Fig. 5）。
图6：相关对数正态分布下RM与SM-OCP的性能比较（来源：Fig. 6）。
参数敏感性与众包司机配置
论文进一步考察Wasserstein半径、偶发司机数量和司机容量上限对路线方案的影响。半径参数反映决策者对分布误差的防护强度，偶发司机数量关系到可用配送资源，容量上限会改变客户覆盖与司机目的地到达顺序。图7和图8分别提供不确定性保护强度、司机数量变化下的成本与服务表现，图10把容量变化落实到具体路线与到达时刻。
图7：不同Wasserstein距离下的模型性能（来源：Fig. 7）。
图8：不同OD数量下的模型性能（来源：Fig. 8）。
图10：RM模型不同OD容量下的路线方案（来源：Fig. 10）。
模型适用条件与研究边界
该模型适用于客户需求、司机集合与服务时间窗已知，旅行时间具有历史样本，配送方需要在运营成本与准时服务之间进行权衡的众包配送场景。模型通过支持集表达旅行时间下界与弧之间的耦合关系，支持集结构需要结合业务数据设定。
✓需要准备旅行时间样本，并设定Wasserstein半径与风险厌恶水平。
✓需要明确客户与偶发司机的服务时间窗、容量和补偿规则。
✓需要评估计算规模，100节点实例的最优求解数量低于25节点规模。
✓论文实验聚焦基准算例与设定的旅行时间分布，其他需求动态性、司机实时可用性与更大规模场景的外推范围，论文未报告。
论文：Distributionally robust vehicle routing with crowdshipping and time windows
作者：Bingjie Zhou，Yu Zhang，Roberto Baldacci，Jiafu Tang
期刊：Transportation Research Part B
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
