拥堵不确定性下固定路线电动车辆充电的随机对偶动态规划方法

《Transportation Research Record》：A Stochastic Dual Dynamic Programming Approach for Fixed-Route Electric Vehicle Charging under Congestion Uncertainty

　　

在实际不确定性下部署重型电动卡车在运营上具有挑战性，尤其是当多辆车竞争有限的公共充电资源并面临不确定等待时间时。研究人员研究了固定路线车辆充电问题（FRVCP），并将其建模为充电拥堵不确定性下的多阶段随机规划。配送系统被建模为由物理路线里程碑触发的离散事件过程，充电拥堵不确定性由马尔可夫转移表示。为处理由此产生的混合整数结构，研究人员采用随机对偶动态规划（SDDP）作为战术规划方法，同时在凸性要求内容纳离散车辆动态。在加利福尼亚物流网络上的计算实验表明，所提方法在多个地理多样化的配送路线上均有效。与多阶段随机整数规划基准相比，SDDP在路线实例数量增加时实现了有竞争力的解质量并减少了训练时间。样本外模拟进一步证明，从SDDP导出的策略在朝向更拥堵情景的分布偏移下保持鲁棒。总体而言，本研究确立了SDDP作为在拥堵不确定性下为重型电动车队生成高质量运营策略的可处理且可扩展的框架。

研究背景方面，重型电动卡车（HDET）在中短途与长途货运中的电动化转型面临基础设施缺口、运营约束与驾驶行为等挑战。公共充电站数量有限且容量受限、分布不均，其拥堵水平随交通量波动，引入显著不确定性。加利福尼亚州强制2045年中重型卡车零排放，但既定配送轨迹常由上游供应链锁定，问题自然落入固定路线车辆充电问题（FRVCP）：路线外生给定，仅能沿固定轨迹决策充电点与补能量。既有文献多聚焦电动车辆路径问题（EVRP）的路由设计，而中段物流中空间序列已定，核心难点转为充电时序与电量管理。现有FRVCP研究多为确定性，少数考虑拥堵不确定者未系统拓展至多阶段随机设定与大规模分解算法。因此，研究人员在拥堵不确定下建立HDET的中段货运充电与路由多阶段随机规划框架，对比SDDP与其整数扩展SDDiP及多阶段随机整数规划（MSIP）的求解质量与可扩展性。

关键技术方法上，研究人员基于加利福尼亚快消品公司合成配送网络，筛选68条配送通道与169个交付点中的20条路线实例，嵌入25个HDET适用公共充电站；路网取自OpenStreetMap，高程梯度来自SRTM3，能耗按机械功率模型（含滚动阻力、空气阻力、坡度与再生制动）离线计算为弧级参数δ_ij（kWh）。拥堵不确定性用三状态（自由流、中度、重度）阶段依赖马尔可夫链建模，转移矩阵具三对角结构；每状态利用率ρ映射至M/M/c排队期望等待时间w_s,t(ω_t)，服务率随利用率凸衰减并截断。决策采用Observe-Then-Act（先观测拥堵状态再行动）形式，状态含位置pos_v,t、累计时间τ_v,t、电量e_v,t，动作含弧选择x、充电指示y、充电时长ct、能量松弛z；目标为最小化总运营时间，Bellman递归式(8)刻画成本-to-go。算法端并行实现SDDP（连续凸松弛）与SDDiP（整数割），以MSIP作基准。

研究结果部分，问题设定小节将配送网建为有向图G=(N,A)，节点含交付点与充电站，阶段初揭示拥堵机制ω_t∈{1,…,R}，由P_t转移，三状态例见式(1)三对角矩阵；参数生成小节分能耗与等待时间，能耗由式(2)(3)算δ_ij，等待时间由式(4)(5)服务率退化、式(6)Erlang C、式(7)队列期望等待，封顶120分钟；数学公式小节给出目标式(8)及状态/动作/约束（电量动态、最小储备E_res、节点流转、充电逻辑）；算法设计小节阐述SDDP用Benders类对偶割近似未来成本函数，SDDiP增加整数相容割以处理x,y离散性，两者均在凸包内包容车辆离散动态。

讨论与结论部分，研究人员指出：在加州多样地形路网上，SDDP相较MSIP在解质量上具竞争力，且随路线实例增多训练时间显著下降，证明其可扩展性；样本外测试在分布偏移至更拥堵情形时策略仍鲁棒，说明马尔可夫拥堵建模与Observe-Then-Act信息结构能捕获实际调度所需适应性。SDDiP虽更精确但计算负担重，SDDP在战术层提供可处理近似。该研究确立SDDP作为拥堵不确定下HDET固定路线充电的可扩展框架，为中段零排放货运提供建模与算法指引，弥补了FRVCP由确定式走向多阶段随机分解的空白，对公共充电依赖型车队运营具实践意义。论文发表于《Transportation Research Record》。