王星又

（海南大学管理学院，海南 海口 570100）

1 概述

为缓解温室效应，控制CO2等温室气体的排放，打造低碳社会，我国于2020 年9 月22 日提出双碳战略目标。在全球范围的交通领域内，由道路运输导致的二氧化碳排放超过了总排放量的70%，各国政府和企业开始考虑用电动物流车代替传统燃油车完成城市配送业务[1]。

充电设施可分为充电站和换电站两类，王琪瑛等[2]研究了在软时间窗下的电动车换电站选址问题，杨磊等[1]研究了电动物流车充电和换电设施选址模型。孙世泽[3]研究了电动物流车充电设施布局与配送路径优化的问题，李得成等[4]研究了电动车与燃油车混合车辆路径问题。侯登凯等[5]则研究了多中心混合车队联合配送的路径优化问题。Hu 等[6]考虑需求不确定使用鲁棒的方法对车辆路径问题进行研究。

本文构建了需求不确定时带软时间窗的电动物流车充电站选址与路径规划模型，其目标是成本最小化，通过使用box 和budget 方法构建需求不确定集，并使用SA-VND 算法进行求解。

2 模型描述与建立

2.1 问题描述

某配送中心有K 辆相同车型的电动物流车，车辆电池的最大容量为Q，最大载重量为W，并且匀速行驶，需求点共N 个，需求点的需求量为变动的ω～i，要求到达时间为[Ei，Li]，车辆在该时间段外到达需要支付相应的机会成本费用或惩罚费用。每辆车均从配送中心满电出发，最终返回配送中心。受电池容量的限制，车辆中途可能需要访问充电站并选择快充或慢充，其充电成本与行驶距离呈线性关系。要求选择合理的充电站位置和配送路线，使得在满足需求的同时最小化配送成本。

2.2 符号说明

Xijk：决策变量，若车辆k 从i 行驶至j，值为1，否则为0

Yijr：决策变量，若车辆在路径r 中选择在i 充电，值为1，否则为0

Zijr：决策变量，若车辆在路径r 中选择在i 慢充，值为1，否则为0

2.3 两阶段模型建立

第一阶段首先考虑无充电行为时，受载重量、需求不确定和软时间窗等因素影响的车辆调度及路径规划模型。

其中，式(1)分别表示在无充电行为下的车辆用电成本，时间机会成本，惩罚成本和车辆固定成本；式(2)表示每个需求点只能由一辆车辆服务，式(3)表示每辆车从配送中心出发，最终返回配送中心，式(4)表示流守恒，进入需求点的车辆数量始终等于离开该点的车辆数；式(5)表示离开点i 的实际时间，式(6)表示到达点j 的实际时间；式(7)表示回路中每辆车访问的需求点的需求量之和不能超过车辆的最大载重量；式(8)表示配送车辆总数；式(9)，(10)表示需求的不确定集，式(11)分别表示车辆的用电成本，时间机会成本，惩罚成本和车辆固定成本；式(13)，(15)，(16)分别表示车辆离开配送中心0，充电站n 以及到达需求点i+1 时的电量水平，式(12)表示在需求点进行服务时不消耗电量；式(17)，(18)表示离开点i 的实际时间以及到达点i+1 的实际时间；式(19)表示当离开需求点i 后的剩余电量不足以访问下一需求点以及任何充电站时，则在该点前往充电站，否则可以继续前往下一需求点。

3 SA-VND 算法设计

模拟退火算法是模拟金属退火的过程，从一较高初始温度开始，随着温度下降，通过使用Metropolis 法则跳出局部最优解，寻找全局最优解。变邻域算法是通过使用不同的邻域搜索算子，提高计算的效率与精度。传统的模拟退火算法效率不高，加入变邻域搜索的方法对其进行改进可提高求解效率。

3.1 初始解的构造

初始解生成步骤如下：①将n 个需求点分配给k 辆车，表示配送中心，i 表示需求点，则路径可表示为0-i-0，一共有n 条路径；②如果路径0-i-0 长度超过电动车物流车的最大行驶里程则需在该需求点选择进行充电;③在满足最大装载量的前提下，对已有的路径进行合并。

3.2 混合变邻域搜索算子

在模拟退火算法的基础上加入变邻域搜索的2Opt、Insert、Swap 三个算子，通过扰动来产生新邻域结构，提高搜索的效率和质量。

3.3 流程图

本文SA-VND 算法的流程图如图1 所示。

图1 SA-VND 算法流程图

4 实验案例

本案例考虑配送中心0 和20 个需求点，使用欧氏几何坐标表示各点位置，并生成了平均需求以及时间窗的上下界，具体数据如表1 所示。

表1 算例数据

假设配送中心电动物流车型号相同，其中最大续航里程为200km，最大载重量为2.5t，平均车速为80km/h，单位里程成本为0.14 元，车辆早到的单位时间机会成本为25 元/h，迟到的单位惩罚成本为45 元/小时，车辆的固定出行成本为150 元/车，电量由0%至100%快充需0.75h，慢充需4h。

通过使用SA-VND 算法进行求解，得出本案例的最优路线以及充电桩选址与充电模式的选择，分别为0-2(快充)-13 (快充)-7-8-12 (慢充)-0，0-20-6-9-10 (慢充)-0，0-11-14-19(慢充)-0，0-15-17-5-18(慢充)-0，0-1-16-4(快充)-3-0，快充充电站选址为点2、4 和13，慢充充电站选址为点10、12、18 和19。如图2 所示。

图2 车辆配送路线图

通过图3 可知，总行驶成本为938.384 元，在第1092 次迭代处达到收敛，为了进一步验证本文算法的求解效率，对比了遗传算法，传统的模拟退火算法，粒子群算法，其CPU时间分别为7.46s、9.78s、10.23s、8.76s，成本分别为是938.38、956.22、1002.34、980.67，因此求得解的各项指标均为最优。可以得出，本文算法在求解此类问题时可行高效。

图3 SA-VND 迭代曲线

5 结论

本文综合考虑混合充电方式与需求不确定等因素，建立路径规划与电桩选址的两阶段鲁棒模型。本文提出了SA-VND 算法，采取三种变邻域算子提高搜索的效率。为验证本文模型的有效和算法的高效构建了算例，并对比了不同和算法，得出本文算法在求解此类问题时可行高效，因此本文的模型与算法具有一定的实用价值，能为相关行业提供一定参考价值。