容量约束电动汽车路径问题的Q-Learning超启发式优化模型与动态规划充电策略

A Q-Learning Hyper-Heuristic Optimization Model and Dynamic Programming Charging Strategy for the Capacitated Electric Vehicle Routing Problem

摘要: 本文研究容量约束电动汽车路径问题(CEVRP)，在车辆载重与电池电量双重约束下，建立以车队总行驶距离最小为目标的0-1混合整数规划模型。令客户集、充电站副本集和扩展节点集分别为$C$ 、$F^{\prime }$ 和$V$ 。以$x_{ij}$ 表示弧选择变量，以$w_i$ 和$b_i$ 表示载重与剩余电量状态，目标函数为$minZ={\displaystyle {\sum }_{\left(i,j\right)\in A}{d}_{ij}{x}_{ij}}$ ，并以唯一服务、流守恒、载重递推和电量递推约束定义可行域。针对该NP难组合优化问题，将低层启发式算子选择建模为有限马尔可夫决策过程$ℳ= \left(S,A,P,R,\gamma \right)$ ，依据Bellman最优方程更新$Q\left(s,a\right)$ ，实现自适应算子调度。对候选客户路径，先插入充电站恢复电量可行性，再以动态规划递推优化固定客户序列的充电站组合；初始化阶段依据实例特征确定构造策略的采样权重。在17个IEEEWCCI2020基准实例上进行30次独立运行，并采用Friedman总体检验及经Holm校正的双侧Wilcoxon符号秩事后检验，在显著性水平$\alpha =0.05$ 下评估算法差异。数值结果表明，所提算法在Best与Mean指标上具有总体竞争优势，且所得解满足车辆数、容量与电量约束。

Abstract: This paper studies the capacitated electric vehicle routing problem (CEVRP) and formulates a 0-1 mixed-integer programming model that minimizes total fleet travel distance subject to vehicle-capacity and battery-energy constraints. Let $C$ , $F^{\prime }$ , and $V$ denote the customer set, charging-station-copy set, and extended node set, respectively. The binary arc variable $x_{ij}$ and state variables $w_i$ and $b_i$ describe routing, residual load, and residual energy. Unique-service, flow-balance, load-recursion, and energy-recursion constraints define the feasible region, with objective $minZ={\displaystyle {\sum }_{\left(i,j\right)\in A}{d}_{ij}{x}_{ij}}$ . For this NP-hard combinatorial optimization problem, low-level heuristic selection is modeled as a finite Markov decision process $ℳ= \left(S,A,P,R,\gamma \right)$ , and $Q\left(s,a\right)$ is updated by the Bellman optimality equation to adaptively schedule operators. For candidate customer routes, charging-station insertion restores energy feasibility, and a dynamic-programming recurrence then optimizes the charging-station combination for the fixed customer sequence. Instance features determine construction-strategy sampling weights during initialization. Thirty independent runs are conducted on 17 IEEE WCCI 2020 benchmark instances. Differences are evaluated using the Friedman omnibus test and Holm-adjusted two-sided Wilcoxon signed-rank post-hoc tests at $\alpha =0.05$ . The results show that the proposed algorithm is overall competitive in Best and Mean, and every reported solution satisfies the fleet-size, capacity, and energy constraints.