考虑电池损耗的电动冷藏车路径及充电策略

王嘉月，史 立

上海海事大学 物流科学与工程研究院，上海201306

电动汽车具有“零废气排放”的优点，得到世界各国政府对新能源汽车开发的推崇[1]。随着我国国民收入提高，冷链物流拥有很大发展空间，将电动冷藏车用于生鲜产品配送已成为物流发展趋势。

电动冷藏车受到电池容量的限制，需在送货途中前往充电站进行充电。现阶段充电技术尚未成熟，严重影响电动冷藏车的续航里程，进而影响运营成本。如何科学有效地规划配送路径，减少充电次数、降低电池损耗成为冷链物流发展的研究热点。胡纪玲[2]建立了包括固定成本、行驶成本、制冷成本、时间窗成本和货损成本在内的电动冷藏车路径规划模型，并通过改进粒子群算法进行了求解。冯杰等[3]将充电成本加入传统VRP模型目标函数中，建立有软时间窗约束的生鲜产品纯电动冷藏车路径规划模型，采用蚁群算法测试算例证明模型的实用性。

目前研究电动冷藏车VRP问题的文献较少，可从普通电动汽车路径问题以及传统冷藏车配送路径问题的文献中寻找研究的方法。Lin等[4]提出了考虑车辆负载对电池消耗影响的EVRP模型，以最小的行驶时间成本、最小的能源成本和最优的电动汽车调度策略为目标，并通过Austin TX案例分析说明车辆负载对路径策略的影响。Schneider等[5]提出了带有时间窗和充电站的电动汽车路径问题（EVRPTW），同时考虑了车辆的有限运载能力以及客户时间窗约束，并设计了一种混合启发式算法，将变邻域搜索算法与禁忌搜索启发式算法相结合，对模型进行了有效的求解。杨珺等[6]结合电动汽车换电站选址以及配送路径问题建立了整数规划模型，并设计了一种禁忌搜索-改进C-W节约的两阶段启发式算法对模型进行求解。冯鹏翔[7]在考虑装载容量等因素基础上整体规划了电动汽车的选址和路径，以减少建设配送系统的总成本。郭放等[8]将充电时间和电池损耗成本纳入目标函数并使用多阶段启发式算法进行求解，结果证明了在配送距离不变或略有增加的情况下，考虑充电时间与深度放电成本的模型可较大幅度减少充电时间与电池损耗成本，降低企业运营成本。Miroslaw等[9]在保证生鲜产品质量以及满足客户的送货服务时间窗要求的基础上，将冷藏车车厢温度控制作为约束条件建立成本最小化的车辆路径模型。Osvald等[10]将运输过程新鲜蔬菜的易腐性作为构建模型的关键因子，采用基于禁忌搜索算法的启发式算法对带有时间窗约束的数学模型进行了求解，并利用改进的Solomon问题验证了算法的性能。

综合来看，电动车路径优化问题研究大多集中于路线长度的最短化，很少将充电对电池造成的损耗纳入运营成本考虑范围。文章建立的电动冷藏车路径优化模型与现有研究主要区别在于将电池损耗成本加入电动冷藏车的路径优化目标函数中，通过分析不同充电上限情况的各项成本，得到电动冷藏车的最佳充电策略。

1 电动冷藏车配送路径优化模型

电动冷藏车路径优化模型以运输成本、制冷成本、货损成本、惩罚成本、充电时间成本、电池损耗成本构成的总成本最小为目标函数。

1.1 模型假设

（1）配送中心配送单一产品，有k辆相同的电动冷藏车，最大载重量和电池容量均已知；

（2）客户需求都会被满足且只能由一辆车服务；

（3）冷藏车从配送中心出发，最终回到配送中心；

（4）每个客户有时间窗约束，未在规定时间内送达会产生相应的惩罚费用；

（5）配送中心对客户的需求、位置以及充电站位置已知，车辆从某一点出发，其下一客户位置已确定，不会改变；

（6）车厢外环境温度变化只对冷冻设备消耗造成影响，运输过程中冷藏车厢内温度恒定，货物腐坏只与运输时间有关；

（7）车辆从配送中心出发时为满电状态，电量不足可进入充电站直接充电；

（8）不考虑交通拥堵情况，配送时间段道路通畅。

1.2 参数符号

（1）模型集合。

O：配送中心集合，用{}o表示单一配送中心；

L：表示客户点的集合；

E：充电站集合；

V：所有顶点的集合，V=O⋃L⋃E；

D：表示路段的集合；

K：配送车辆集合，配送车辆用k表示，k∈K。

（2）模型涉及的其他相关参数，如表1所示。

表1 参数说明Table 1 Parameter specification

1.3 数学模型

其中公式（1）为目标函数，表示电动冷藏车配送总成本最小；式（2）～（7）分别表示运输成本、制冷成本、货损成本、惩罚成本、充电时间成本、电池损耗成本，式（7）根据文献[11]电池容量衰退成本模型构建，以此估计电池损耗成本；式（8）～（21）为约束条件：式（8）表示每个客户只能被一辆访问；公式（9）为车辆约束，提供服务的电动冷藏车数量不得超过配送中心车辆总数；式（10）表示每个节点到达的车辆数和离开该节点的车辆数一致；公式（11）表示配送冷藏车只能从配送中心出发一次且最后回到配送中心；公式（12）表示装载量不能超过车辆的最大载重量；公式（13）表示装载量与客户需求量之间的关系，冷藏车从客户点j离开时的载重量等于车辆离开i点时的剩余载重量减去客户j的需求量；式（14）表明电动冷藏车从配送中心出发时电量为充满状态；公式（15）表示冷藏车在客户点服务期间不消耗电量；式（16）表示车辆行驶里程与耗电量之间的关系；式（17）确保电动冷藏车有足够的电量访问每个节点；式（18）表示电动冷藏车进入充电站可以直接充电，无需排队等待；式（19）表示如果车辆提前到达客户点，则需要等待至客户要求的开始服务的时间；式（20）表示冷藏车到达下一客户点j的时间为上一客户点i开始工作的时间、客户点i的卸货时间以及车辆从客户点i到客户点j的行驶时间三者的总和；式（21）表示如果车辆进入充电站充电，则冷藏车到达下一客户点j的时间等于车辆到达充电站的时间加上车辆充满电的时间以及车辆从充电站到客户点j的行驶时间；公式（22）和（23）为0-1决策变量。

2 粒子群算法设计

2.1 算法原理

粒子群算法的基本原理是粒子通过种群中个体之间的信息共享和协作在解空间搜索最优解。陈自郁[12]认为粒子群算法的基础是粒子间的信息共享，有效利用信息是信息共享机制的核心问题。文章结合闫雪丽等[13]提出的随机历史全局最优与局部最优相结合的粒子群算法（RCHGLBPSO）对模型进行求解，通过增加一种粒子共享信息的类型来扩大搜索的区域，防止算法早熟收敛。粒子i随机选取互不相同的m（固定的）个粒子作为邻域子群，通过比较子群中的粒子的适应度值，找到邻域的全局最优位置并将其应用到位置更新公式中。假设在D维搜索空间中，有n个粒子组成的种群，其中第i个粒子在D维空间位置为Xi=(xi1,xi2,…,xiD)，表示问题的一个潜在解；第i个粒子的飞行速度为Vi=(vi1,vi2,…,viD)，第i个粒子的个体极值为Pi=(pi1,pi2,…,piD)，种群的群体极值为Pg=粒子速度和位置更新公式如下：

其中，t为迭代次数；w为惯性权重；c1和c2是非负常数，称为学习因子；r1和r2是分布于[0,1]区间的随机数；Pl=(pl1,pl2,…,plD)表示算法运行到第t次找到第l个粒子的邻域最优位置赋予历史全局和邻域全局信息不同的权重。

2.2 算法编码

采用文献[14]编码思想，模型中有n个客户点，为满足每个客户由且仅由一辆冷藏车完成服务的约束，将空间向量分成两个n维向量，分别用Xv和Xp表示。粒子群算法主要用于解决连续性优化问题，而VRP属于离散组合问题，在求解VRP问题时，要对相关数据进行处理。在每一次粒子位置和速度更新中，需要进行整数化处理。Xv取()1,k之间的随机数，并向上取整表示客户服务的冷藏车编号；Xp取()1,n之间的随机数，将其按从小到大排序即可表示客户点在各自配送路径上的服务次序。

2.3 算法步骤

改进粒子群算法步骤如下，流程如图1所示：

图1 算法实现流程Fig.1 Algorithm implementation process

（1）设置种群规模、最大迭代次数、邻居个数等参数，邻居个数为种群规模的30%，初始化种群，初始化粒子位置、速度。

（2）将模型中的目标函数作为适应度函数，计算粒子的适应度值，寻找个体极值、全局极值、邻域全局极值，并比较三者的大小。

（3）按公式（24）和（25）对粒子速度和位置更新。

（4）重新计算更新后的粒子的适应度值，据此找寻个体极值、全局极值、邻域全局极值，同时与上一代粒子极值进行比较，判断是否进行粒子位置的更新，并记录全局最优。

（5）判断算法是否达到最大迭代次数，若达到，算法终止并输出最优解；否则转步骤（2）继续迭代。

3 案例分析

3.1 算法性能分析

利用Rastrgrin函数、Griewankan函数验证改进粒子群算法的有效性，对改进前后算法均仿真15次。图2、图3Rastrgrin函数结果发现标准粒子群算法找到局部最优值，而改进后算法均收敛到函数的最优值且在100代时趋于稳定。图4、图5Griewankan函数结果可发现标准粒子群算法易于收敛到局部最优值，而改进后算法均收敛到函数最优值，具有很好的收敛性。综上改进后的粒子群算法具有很好的收敛性，能快速找到全局最优解。

图2 Rastrgrin函数标准PSO进化过程Fig.2 Particle swarm evolution of Rastrgrin function

图3 Rastrgrin函数改进粒子群算法进化过程Fig.3 Improved PSO evolution of Rastrgrin function

图4 Griewankan函数标准算法进化过程Fig.4 Particle swarm evolution of Griewankan function

图5 Griewankan函数改进粒子群算法进化过程Fig.5 Improved PSO evolution of Griewankan function

3.2 案例描述

假设配送中心有电动冷藏车3辆进行单一生鲜产品的配送，每辆冷藏车售价为150 000元，车辆电池的价格Pnew为50 000元，电池额定容量B为80 kWh，最大载重量Q=1.5 t,速度v=60 km/h,耗电系数h=0.6 kWh/km,固定运输成本C1=100元,单位距离行驶成本C*1=1元/km。冷藏车厢恒温为-5℃，根据文献[15]货损率η设为0.14，产品单价P=100元/t，单位时间充电成本e=1元，单位距离制冷耗电成本α=0.02元/km。在计算退役电池价值Pused时，年折旧率rdep为20%，贴现率rdis为6%，使用年限tuse为8年，Pused为5 579元。电池容量衰减到80%时不能使用，将CRR设为80%。

随机生成15个客户点，编号为1～15，随机产生5个充电站，编号为16～20，配送中心为0，位置为[50，50]，时间窗为[0，15]。各客户点的位置、货物需求量、服务时长、服务时间窗信息如表2所示。

表2 测试数据Table 2 Test data

3.3 优化结果分析

在MATLAB上编写粒子群算法，设置种群规模为80，最大迭代次数为1 000次，维数为15维，惯性权重w设为0.729 8，学习因子c1=c2=1.496 18。

3.3.1 充电策略影响性分析

将文章提出模型与传统电动冷藏车VRP模型进行对比分析。将SOC上限设置为100%、90%、80%、70%、60%，考虑到里程焦虑问题，不考虑SOC范围在10%～50%的情况。SOC上限为100%时（情景一）电池充满，这与传统电动冷藏车VRP模型假设一致。通过算法求解得到如表3所示的车辆配送的最优路径及行驶距离。同时得到了不同SOC上限的各项成本（表4）以及图6的成本对比。

图6 各项成本对比Fig.6 Cost comparison

表4 不同SOC上限各项成本Table 4 All costs of different SOC upper limit元

通过表3可知，SOC上限为80%时电动冷藏车以最短的路程完成配送，同时进入充电站充电的次数最少。对比情景一，可发现电量充至80%的路程要比情景一缩短18.63%。

表3 路径规划情况Table 3 Path planning situation

由表4可知，情景一总运营成本最高，而情景二至情景五（考虑电池损耗成本）总成本明显低于情景一，当SOC上限为80%时总运营成本最低。在总成本中，占比较大的有运输成本、电池损耗成本、充电成本，考虑电池损耗情况可有效影响配送过程的各项成本，对总运营成本、配送路径等产生作用。

分析图6可看出：（1）运输成本方面，情景三的运输成本为五种情景中最低，对比情景一可发现情景三的运输成本比传统模型的节约16.1%；（2）电池损耗成本方面，随着SOC上限的降低，电池损耗成本呈下降趋势，充满电的充电策略对电池损耗最大，而充电至60%对电池损耗最小，电池损耗成本的降幅可达89.32%，即使充电至80%也使电池损耗成本降低68.08%，因此将电池损耗成本纳入运营成本计量范围可有效减小电池损耗；（3）充电时间成本方面，由折线变化看出传统模型充电时间成本明显高于本文提出的模型，本文最低的充电时间成本比传统模型低66.87%，情景三的充电时间成本比传统模型低约65.3%，考虑电池损耗成本的充电策略在一定程度上节约了充电时间，降低了充电时间成本；（4）从制冷成本和货损成本变化趋势可以看出二者一定程度上受车辆行驶距离的影响，因此当SOC设为80%时车辆行驶里程最短，相应的制冷成本和货损成本要低于传统模型。综上所述，电动冷藏车配送时，充电策略可由充满电转变为充电至80%，虽然将SOC上限设为80%并不能使电池损耗成本最低，但由于充电策略的改变会大幅度降低电池损耗成本和充电时间成本，有效降低总运营成本。

3.3.2 算法寻优能力对比分析

将充电至80%的充电策略应用于案例中，分别利用标准粒子群算法和本文的改进粒子群算法对案例进行求解，最终得到的优化结果如表5所示。

表5 两种算法优化结果Table 5 Optimization results of two algorithms

由表5总成本比较分析可知，使用改进粒子群算法求得的解要明显优于标准粒子群算法的解，通过图7、图8的迭代收敛过程可以看出，改进粒子群算法收敛速度更快、收敛性能更好，这表明本文采用的改进粒子群算法在求解电动冷藏车路径优化问题上的可行性与有效性。

图7 标准粒子群算法迭代过程Fig.7 Standard PSO iterative process

图8 改进粒子群算法迭代过程Fig.8 Improved PSO iterative process

4 结语

在传统冷藏车路径优化问题约束条件基础上，添加了电动冷藏车的特有条件，同时考虑了生鲜产品的品质动力学模型，构建了包括电池损耗成本在内的电动冷藏车路径优化问题模型，运用增加粒子间共享信息类型的改进粒子群算法进行求解，为企业提供合理的电动冷藏车充电策略。本模型并未考虑实际充电过程中充电速率变化情况以及回程空载的问题，这也成为后期研究的重要方向。