考虑灰需求的电动汽车配送路径优化

王海燕，韩已晴

（福州大学 经济与管理学院，福建 福州 350000）

1 引言

随着电子商务的发展和交通运输网络的完善，物流市场不断扩大，物流配送带来的高能源消耗和高碳排放问题逐渐引起了社会的广泛关注。在新能源汽车技术进步和政府扶持政策的共同推动下，越来越多的企业致力于发展绿色物流，开始采用纯电动物流车进行城市配送。相较于传统燃油车，利用纯电动汽车进行配送具有低能耗、低碳排、低污染等优点，但行驶里程短、充电时间长、充电设施不足等问题是制约电动汽车配送进一步发展的主要障碍。为规避电动汽车的技术缺陷，促进电动汽车在物流配送行业的长足发展，众多学者针对电动汽车路径优化问题（Electric Vehicle Routing Problem，EVRP）展开了研究。

Schneider，等[1]提出了同时考虑客户时间窗和充电站的电动汽车路径优化问题；Schiffer，等[2]将充电站选址和电动汽车路径优化问题相结合进行研究；郭放[3]认为电池损耗不容忽略，提出将电动物流车的电池损耗成本纳入到目标函数。

上述研究主要是在静态确定的情况下，从时间窗约束、里程约束和充电约束等方面对电动汽车配送路径进行优化。然而，在实际的物流配送过程中，用户需求、时间窗、道路拥堵情况和配送成本等信息很可能是动态不确定的，其不确定性主要表现为动态性、随机性、模糊性或灰性。因此，考虑动态不确定信息对于电动汽车路径优化问题是很有必要的。当前，国内外关于不确定型EVRP的研究主要集中在时间窗、用户需求和交通状况的不确定性方面。Zarandi，等[4]假设顾客需求和车辆行驶时间是模糊变量，提出了不确定型电动汽车选址路径问题；邵赛[5]结合车辆行驶的实际环境，分别研究了考虑动态需求和动态行驶时间的电动汽车路径优化问题；Zhang，等[6]对模糊电动汽车路径优化问题展开了研究。

综上所述，基于EVRP的研究现状，结合实际的物流配送背景，考虑到很多时候企业只能通过残缺的历史数据了解客户需求的大概范围而无法得知其确切取值的情况，本文采用灰参数来描述客户需求，研究了客户具有灰色需求时的电动汽车路径优化问题，以最小化配送成本为目标建立了电动汽车路径优化模型，并设计了嵌套灰色模拟技术的蚁群算法进行求解。

2 问题描述及数学模型

2.1 问题描述与假设

本文以单个配送中心、多个客户点和多个充电站组成的物流配送网络为研究对象。电动物流车从配送中心出发，按照一定的顺序将货物配送给客户，任务结束后返回配送中心。配送途中，考虑到电动汽车的行驶里程限制，若车辆剩余电量不足以访问下一个客户点或返回配送中心，电动物流车可以访问附近的充电站进行充电。在满足电动物流车电量约束、载货量约束和客户时间窗约束的条件下，确定电动物流车的最佳行驶路线，使得总配送成本最小。考虑到EVRP问题的复杂性，为了便于建模和求解，作出了如下假设：

假设1 配送中心、客户点和充电站的位置均已知；

假设2 电动物流车从配送中心出发，依次服务各客户点后返回配送中心，途中可以访问充电站进行充电；

假设3 客户的需求量是灰色的，采用灰数来描述客户需求；

假设4 每个客户都存在配送的时间窗要求，若车辆未能在约定的时间窗内到达，会产生相应的惩罚费用；

假设5 车辆离开配送中心和充电站时均为满电状态；

假设6 电动物流车的充电量与充电时间成正比，耗电量与行驶距离成正比。

2.2 符号与变量说明

0：配送中心；

N：客户点集合；

R：充电站集合；

S={0}⋃N⋃R：所有节点的集合；

V：电动物流车集合；

f：每辆车的固定使用成本；

dij：节点i到节点j的行驶距离；

a：电动汽车单位距离行驶费用；

Q：车辆最大载重；

⊗qi：客户点i的灰需求量；

B：电动物流车电池最大容量；

b1ik和b2ik：分别表示车辆k到达和离开节点i时的电量；

e：单位距离的电量消耗系数；

g：充电桩的充电速率；

ESik：车辆k在充电站i的充电量；

β：公共充电站的单位充电费用；

[E Ti,LTi]：客户满意时间窗；

α1、α2：分别为车辆早于和晚于客户满意时间窗到达时的单位时间惩罚成本；

tsik：车辆k在客户点i的服务时间；

tcik：车辆k在充电站i的充电时间；

tijk：车辆k从节点i到节点j的行驶时间；

M：一个足够大的实数；

2.3 数学模型

根据上述问题的假设和分析，建立了考虑灰需求的电动汽车路径优化模型。

其中，式（1）为总成本目标函数，总成本包括车辆固定成本、运输成本、违反客户时间窗的惩罚成本和电动物流车充电成本；式（2）表示每个客户点仅由一辆车服务一次；式（3）为各节点进出平衡约束；式（4）表示每辆车的实际载重不得超过车辆最大载重；式（5）表示电动汽车离开配送中心和充电站时均为满电状态；式（6）表示电动汽车在客户点处进行服务时不额外消耗电量；式（7）表示车辆k离开节点i和到达下一个节点j的电量关系；式（8）表示电动汽车的剩余电量不超过电池容量；式（9）表示车辆k离开节点i和到达下一个节点j的时间关系；式（10）表示车辆k到达和离开节点i的时间关系；式（11）表示车辆的充电时间；式（12）和式（13）表明决策变量为0-1变量。

3 模型转换与求解

3.1 模型转换与处理

上述EVRP模型，车辆载重约束中含有客户灰需求⊗qi，在到达客户点之前，无法得知其确切取值，这导致该模型无法直接进行求解。因此，在进行求解之前，需要先将模型进行转化。根据灰色机会约束规划理论，将该模型转化为可进行求解的灰色机会约束规划模型[7-8]。

其中，f为总配送成本；Pr{·}表示事件{·}发生的概率，此处表示灰色约束条件成立的概率；α为置信水平；⊗q=[⊗ q1,⊗q2,...,⊗qn]表示客户的灰需求量，Cj(X)≤0表示除灰色约束之外的其他约束。

针对转化后的模型，当且仅当Pr{gi(X ,⊗q)≤0,i=1,2,...,t}≥α，即车辆配送货物的重量之和不超过车辆最大载重的概率大于等于α时，得到的方案才可行。

3.2 灰色模拟检验

对于转化后的模型，可以采用灰色模拟技术[7]来实现灰色约束条件的检验。通过对灰数进行白化处理，得到客户灰需求量的白化值矩阵，再通过白化值矩阵来检验灰色约束条件成立的概率。假设每个客户点生成N个白化值进行N次实验，N'为实验过程中灰色约束条件成立的次数。若N'/N≥α，则灰色约束成立，否则不成立。具体步骤如下：

Step1 参数初始化，设置N'=0；

Step2 利用白化权函数生成各客户点的白化值矩阵；

Step3 根据白化值矩阵，检验灰色机会约束条件成立的概率。若Pr{gi(X ,⊗q )≤0,i=1,2,...,t}≥α成立，则N'++；

Step4 重复Step2、Step3共N次；

Step5 若N'/N≥α则成立，否则不成立。

3.3 模型求解

带充电站的电动汽车路径优化问题是典型的NP-hard问题，同时考虑客户的灰色不确定需求，进一步增加了求解的难度。蚁群算法采用分布式并行计算机制，利用信息正反馈来优化寻优过程，相较于其他启发式算法，蚁群算法的求解速度较快、全局搜索能力也较强[9]。因此，本文拟采用蚁群算法求解电动汽车路径优化问题，并在传统蚁群算法的基础上，设计了嵌套灰色模拟技术的蚁群算法进行求解。具体步骤如下：

Step1 初始化算法参数。包括蚂蚁数量、初始信息素浓度、算法迭代次数、灰色模拟次数、置信水平等。

Step2 单只蚂蚁从配送中心出发，根据状态转移策略选择下一个要访问的客户节点。

Step3 利用灰色模拟技术进行检验，若灰色机会约束条件成立，将选中的客户点加入到当前路线中并更新禁忌表；若灰色机会约束条件不成立，蚂蚁返回配送中心并在禁忌表中加入0。

Step4 重复Step2、Step3直至单只蚂蚁完成对所有客户点的访问。禁忌表中每两个0之间的数字就代表每辆车访问客户点的顺序。

Step5 判断车辆在配送过程中是否需要充电。计算每条路径上两节点之间的电量消耗，判断车辆到达各客户点时的剩余电量。若剩余电量不足以支撑车辆访问下一个客户点，则需要在两个节点之间插入充电站进行充电。

Step6 对m只蚂蚁全部执行上述操作，计算每只蚂蚁对应的总配送成本，选出所有蚂蚁中总配送成本最小的蚂蚁所对应的配送路线。

Step7 更新全局信息素，进行下一次迭代。

Step8 判断是否达到终止条件。若未达到最大迭代次数，继续进行循环；若达到最大迭代次数，输出所有迭代中的最优配送方案，终止算法。

4 算例求解与结果分析

4.1 算例概述

本文研究的是考虑灰需求和充电站的电动汽车路径优化问题，目前尚无标准测试算例。为验证模型和算法的有效性，随机选取了Solomon标准算例集RC2-2-5中的客户点数据，结合本文的研究内容和实际物流公司城市配送的特点，对数据进行进一步的调整和扩展，得到1个配送中心、30个客户点和10个公共充电站的测试数据（1D-30C-10P）。配送中心、客户点和充电站的信息见表1和表2。

表1 配送中心、充电站坐标

表2 客户点坐标及灰需求量

4.2 算例求解

本文应用MATLAB R2018a编程软件进行仿真，通过多次试验，选择了一组较好的参数值，设定蚁群算法参数为α=1，β=4，ρ=0.7，蚂蚁数量为45只，算法迭代次数为200次。在求解灰色机会约束规划模型时，需要事先确定置信水平α，即灰色机会约束条件成立的概率。考虑到不同决策者风险偏好程度的不同，为研究决策者风险偏好对最优配送路径的影响，改变置信水平α的取值，分别取α为0.6、0.8和0.95，并在不同的置信水平下分别进行10次仿真实验，得到的最优结果见表3和表4。

表3 不同置信水平下的最小成本

表4 不同置信水平下的最优配送方案

从表3、表4可以看出，随着置信水平α的增加，总配送成本也呈现出递增的趋势。置信水平越低，意味着配送过程中违反灰色机会约束的可能性越大，越可能出现无法满足客户配送需求的情况，企业在降低配送成本的同时，承担着较大的客户流失的风险；置信水平越高，总配送成本也越高，客户的需求越能被满足，企业承担的风险相对较低。因此，在进行决策时，不同的企业可以根据自身的风险承受能力以及领导者的决策偏好选择不同的置信水平，得到该置信水平下的最优配送方案。

5 结语

利用电动物流车进行城市配送，需要考虑到车辆中途访问充电站进行充电的情况，因此区别于传统的车辆路径问题。本文在电动汽车城市配送问题中，考虑了客户的灰色不确定需求，建立了考虑灰需求的电动汽车路径优化模型，根据灰色机会约束规划理论将其转化为对应的灰色机会约束模型，并设计了嵌套灰色模拟技术的蚁群算法寻找最优配送方案。本文为决策者在灰色不确定的情况下进行决策提供了参考，决策者可以依据企业自身的情况及决策风险偏好选择合适的置信水平，置信水平越高，总配送成本越高，企业承担的风险越小。

由于交通状况、电动汽车的充电及能耗等因素的影响，现实中的电动汽车配送网络较为复杂，未来将进一步考虑配送时间窗、车辆充放电过程的不确定性，以更加贴合实际物流环境中的电动汽车配送问题。