时变交通下生鲜配送电动车辆路径优化方法

赵志学，李夏苗

(1.中南大学交通运输工程学院，长沙410205；2.湖南工商大学移动商务智能湖南省重点实验室，长沙410205)

0 引 言

电动车凭借其节能、绿色、环保的优势，在物流终端配送过程中得到广泛利用，并逐渐替代了传统燃油车.但电动车存在充电时间较长，电池容量较小和续航里程相对较短的短板.如何在技术条件的限制下合理地进行电动车调度，配送路径规划，广受国内外研究学者的关注.

电动车辆路径问题是传统车辆路径问题的延伸与拓展.Borja Beltran[1]提出将电动车应用于城市交通运输中，建立了运输距离最短的优化模型.Desaulniers G.[2]在研究带时间窗电动车辆路径问题(Electric Vehicle Routing Planning, EVRP)优化中，考虑了4 种不同充电策略，并在客户点时间窗约束下对4种充电策略进行优化，从而得到最佳充电方式.揭婉晨等[3]区分不同车型电池容量，单位耗电率和车载等因素，设计分级定价法求解该问题最优解.Hiermann等[4]根据不同车型电动车能耗和载重的差异性，研究合理配置车队结构进行配送.Afroditi等[5]考虑车载、充电方式和电量等约束，构建电动车路径规划模型.近几年，国内外学者开始将冷链物流与电动车辆路径问题结合起来研究.Poks A.等[6]研究带有电冷却装置的电动卡车冷链配送车辆路径的数学模型.冯杰等[7]研究生鲜供应商通过同质电动车向零售商进行生鲜配送的冷链物流路径优化问题.

综上，以下问题还待深入研究：多数文献是独立研究EVRP和生鲜冷链配送路径问题，两者结合文献较少；关于电动车配送的外界环境，大多忽视路网动态交通时变特征对电动车实际配送过程的影响；多数生鲜冷链配送文献，只考虑生鲜配送过程中的服务时间窗，忽略了客户对生鲜产品新鲜度最低限制要求.因此，本文考虑客户最低新鲜度需求，以总成本为目标建立时变交通下生鲜配送电动车辆路径优化模型，并设计自适应改进蚁群算法求解.

1 符号说明与模型构建

1.1 模型假设

某生鲜配送企业具有充足同质电动车，所有车辆满电状态从配送中心出发为客户进行配送.每个客户点的位置、服务时间窗、生鲜产品需求量和最低新鲜度限制均已知，时变交通路网数据可从交通部门获得，车辆在配送过程中根据实际情况利用社会充电站进行快速充电，制定总成本最小的配送计划.对研究问题做如下约定：

(1)配送网络中只有一个配送中心，所有配送电动车起止点均为配送中心；

(2)配送过程中满足电量约束，当所剩电量不能满足配送要求时，车辆到耗电量最低的充电站进行快充，充满电后继续完成配送任务；

(3)每隔10 min更新路网交通状态；

(4)客户点需求量均小于车辆载重量，有服务时间窗和最低新鲜度限制的要求.

1.2 符号及参数

(1)集 合.

N,C,F——分别为路网所有节点、客户点和充电站的集合，N={0}∪C∪F，其中，0 表示配送中心；

T——工作所有时间段集合 ，T={T1,T2,…,TB}，其中，B为时间段总数；

K——电动车集合.

(2)参数.

Emax,E0——分别为电动车最大电池容量(kWh)，正常行驶的最低电量(kWh)；

P1,P2,P3——分别为车辆启用成本(元/辆)，车辆单位时间行驶成本(元/min)，耗电量单位价格(元/kWh)；

P4,P5,P6——分别为生鲜单价(元/kg)，快速充电单位电价(元/kWh)，违反客户点时间窗的单位惩罚成本(元/min)；

Q,Me——分别为电动车k的最大车载(kg)、裸车重(kg)；

——分别为道路(i,j)的直线距离(km)，路径划分策略中足够短的距离(km)，道路(i,j)中第R子路段距离(km)；

tijk,Eijk——分别为车辆k在道路(i,j)上行驶时间(min)，耗电量(kWh)；

Nchargemax,Cbattery——分别为车辆k电池最大充电次数、成本(元)；

EC,EO——分别为运输、装卸过程中单位时间能耗(kW/h).

(3)决策变量.

xijk——车辆k在道路(i,j)行驶时为1，否则为0；

yik——车辆k服务客户点i时为1，否则为0；

zik——车辆k在充电站i充电时为1，否则为0.

1.3 相关因素分析

1.3.1 时变路网交通相关分析

在时变交通下，不同时间段内车辆行驶速度不同，行驶时间难以获得，全天各时段行驶速度函数为

式中：vij(t)——t时刻车辆在道路(i,j)行驶速度(km/h)；

vijB——时间段B内车辆在道路(i,j)行驶速度(km/h).

车辆在足够短的距离内行驶时，采用平均速度刻画，即把路段开始行驶即时速度作为路段的平均速度[8]，因此，设计一种路径划分方法求解路段行驶时间.

Step 1根据ϑ(ϑ=0.2 km)[8]和dij把道路(i,j)分为U个子路段，其中，为向上取整.则每个子路段长度为

Step 2开始路段计算.出发时间为离开节点i时间：和式(1)确定，转Step 3.

Step 3其余路段计算.

Step 3.1令ω=1.

Step 3.2如果1+ω ＜U，则ω=ω+1 ，转 Step 3.2；否 则1+ω=U，.

Step 4计算终止，返回路段行驶时间tijk.

1.3.2 耗电性能和充电需求分析

电动车耗电不仅与车辆自身属性有关，还与其实际车载和速度有关，故实际车载Qk的电动车k以速度v行驶在平坦道路时，运行功率[9]为

式中：g——重力加速度(m/s2)；

η——传动系统机械效率；

f、Cd、A——分别表示汽车滚动阻力系数，空气阻力系数，汽车迎风面积(m2).

可得时变路网下，车辆k在道路(i,j) 上行驶的功耗Eijk为

根据城市配送实际，电动车剩余电量不能满足服务下一客户点时，需采用在途快速充电模式进行充电.快速充电过程中，电动车k在充电站i快速充电时间为.

1.3.3 生鲜产品新鲜度分析

生鲜新鲜度与冷藏温度和运输时间相关[10].假设生鲜在配送过程中维持恒定温度，则生鲜产品新鲜度的损耗系数∂可认为是常数；生鲜新鲜度与配送时间相关，引入生鲜产品新鲜度衰减函数为

式中：Fi——车辆服务客户点i时的生鲜新鲜度.

1.4 模型构建

以配送总成本为目标函数，构建时变交通下考虑客户最低新鲜度需求的电动车配送车辆路径模型.

(1)目标函数.

式(7)为目标函数总成本；式(8)为固定成本，行驶时间成本和时间惩罚成本；式(9)为行驶能耗成本和制冷成本，其中，制冷成本包含运输过程和装卸过程的耗电成本；式(10)为货损成本；式(11)为快速充电成本和电池消耗成本，其中，电池消耗成本与快速充电次数正相关.

(2)约束条件.

式(12)表示客户点最低新鲜度需求；式(13)表示每个客户点只接受由同一辆电动车服务；式(14)表示配送货物重量不能超过车辆最大载重量；式(15)表示电动车离开节点i到达节点j之间电量关系；式(16)表示电动车到充电站充满电后离开；式(17)表示车辆在每个节点电量约束；式(18)表示车辆到达和离开节点i时间关系；式(19)表示车辆离开节点i到达节点j时间关系；式(20)～式(22)为决策变量.

2 算法设计

2.1 三约束决策因子

判断车辆k离开客户点i后对下一客户点j的配送，主要取决于3种约束：车载约束，电量约束和客户点最低新鲜度需求约束(简称新鲜度约束).

式(23)中第1 个不等式为车载约束，第2 个不等式为电量约束，第3个不等式为客户点最低新鲜度需求约束.因此本文引入三约束因子σ对上述问题进行求解，其中，分别为当前蚂蚁m已访问客户点集合和未访问客户点集合；Cmin[i]k为从客户点i出发耗电量最低的充电站.

(1)当满足三约束时，σ=3，客户点j为下一个服务点.

(2)当满足载重和电量约束，不满足新鲜度约束时，σ=2，车辆返回配送中心，并增派一辆新车继续配送，客户点j仍为未访问节点.

(3)当满足载重约束，不满足电量约束，则蚂蚁m需要到Cmin[i]k进行充电后继续配送客户点j，更新j点信息.判断是否满足新鲜度约束，如果满足则σ=1，则Cmin[i]k和j依次作为蚂蚁m访问的节点，；否则σ=0，蚂蚁m返回配送中心，并增派一辆新车继续配送，j仍为未访问节点.

(4)返回σ值.

2.2 状态转移策略

蚂蚁m从客户点i到客户点j转移概率为

式中：τij,ηij——分别为信息度浓度和能见度，ηij=1/dij；

α,β——分别为信息浓度和能见度重要性因子，引入自适应信息素启发式因子和期望启发式因子对蚁群算法进行改进[11]：，其中，Nmax，N分别为蚁群算法最大迭代次数和当前迭代次数.

为防止算法陷入局部最优，结合轮盘赌法对状态转移策略进行改进，公式为

式中：R0——[0,1]固定算法参数；

R1——[0,1] 随机数；

S——轮盘赌操作.

2.3 信息素更新策略

为使搜索过程更具指导性，所有蚂蚁完成周游后，对建立路径组成的路段信息素进行更新.更新规则[11]为

式中：ρ——挥发因子；

W——常数；

M——蚂蚁总数量；

Zm——蚂蚁m产生总配送成本；

——此次迭代前路段(i,j)的信息素；

——经过此次迭代后更新的信息素；

Lm——蚂蚁m在此次迭代中经过路线.

2.4 改进蚁群算法设计

Step 1算法初始化.

所有蚂蚁均从配送中心出发.初始化算法参数：最大迭代次数Nmax，当前迭代次数N，蚂蚁总数M，当前蚂蚁数m，车辆数量标识vn，三约束因子σ等.

Step 2构建可行解.

Step 2.1判断蚂蚁m未访问节点集合是否为空：如为空，转Step 2.5；否则，转Step 2.2.

Step 2.2根据状态转移策略选择下一要服务的客户点j.

Step 2.3计算客户点j三约束因子σ：如果σ=3 ，j即为蚂蚁下一访问客户点，，转Step 2.1；如果σ=1，则把Cmin[i]k，j依次作为蚂蚁访问节点，转Step 2.1；如果σ=2 或σ=0 时，蚂蚁返回配送中心，同时新增一辆车继续配送，vn=vn+1，转Step 2.1.更新，根据车辆第一个服务客户点时间窗计算出发时间.

Step 2.4m=m+1，如果m ＜M，vn=0 ，转Step 2.1.

Step 3目标适应度计算.

使用式(7)计算每只蚂蚁搜索路径的目标适应度值，此次迭代过程中记录最优适应度值和相应的最优搜索路径，N=N+1.

Step 4更新全局信息素.

按照信息素更新策略对本次迭代过程中所有蚂蚁经过的路径信息素进行更新.

Step 5算法终止判断.

如果N ＜Nmax，转Step 2；否则，算法终止.通过每代适应度最优值和最优路径找出全局最优值和最优路径.

3 实验仿真

3.1 实验设置

算例来源文献[12]的电动车辆路径数据库，采用R类型(R208)算例作为仿真数据.其中，0 为配送中心，1～100 为客户点，101～120 为充电站.为模拟实际情况，做如下修改：

(1)实际配送中，需在直线距离的基础上乘以迂回系数δ(δ=1.3)得到实际距离.

(2)设定配送工作开始时间为06:00(对应0 min)，每10 min 为一个时间段.根据城市交通规律，将07:00-09:00(第7～18 时段)和17:00-19:00(第67～78 时段)设为交通拥堵时段(车速为30 km/h)，其余为正常时段.令ϖ=0.1，设计3 种车速，即[50(1-ϖ),50(1+2ϖ),50(1-3ϖ)] ，根据时间段B值，利用求余函数π=mod(B,3)，当π取值为[0,1,2]时，对应正常时段3种车速.

(3)算例中一个重量单位为10 kg.

相关参数值如表1所示.

3.2 大型数据算例路径规划

为验证本文算法的稳定性，运行程序10 次，平均运行时间为363.57 s，说明算法能够在较短时间内得到最优电动车路径规划方案.程序运行10 次中取得最优的物流配送规划路径如图1 所示，配送成本分析如图2 所示，具体路径优化方案如表2 所示.

表1 模型和算法的参数值Table 1 Model and algorithm parameter values

图1 R208 最佳路径图Fig.1 R208 optimal routing planning

通过计算，配送总成本为4 913.98 元，使用8辆电动车，固定成本1 600 元，时间管理成本(包含时间成本和惩罚成本)2 041.77 元，运输和制冷能耗成本301.03元，货损成本515.04元，电池耗费成本225元，快速充电成本231.09元.

由图2 可知，每辆车运行总成本中，时间成本和车辆固定成本占比最高，能耗成本、快速充电成本和电池损耗成本比例较低，说明物流配送成本主要影响因素就是行驶时间.由图1 和表2 可知：①车辆1，4，6和8运输过程中需要充电，说明车辆在途充电能在较短时间内增加剩余里程，扩大配送范围.②从开始时间可知，车辆1、2、3、5和7都是在0时刻开始从配送中心出发进行配送，其余车辆出发时间都各不相同.如果车辆4，6 和8 在0 时刻出发，将额外支付3 214.45 元时间惩罚费用，总配送成本也会超出65.0%，说明物流企业应根据路网状况，客户点时间窗等实际情况合理安排出发时间，从而降低配送成本.③车辆1、2、3、5和7仅进入早高峰拥堵时段，车辆4和8都仅进入晚高峰拥堵时段，车辆6 几乎避开交通拥堵时段.说明部分客户时间窗在拥堵时段内，车辆服务时间必须在该时段进行，同时也说明本文方法能有效的规避拥堵时段.

图2 成本分析图Fig.2 Cost analysis chart

表2 车辆路径优化结果Table 2 Vehicle routing optimization results

3.3 最低新鲜度需求灵敏度分析

为分析客户不同最低新鲜度需求对车辆路径规划的影响，在其他条件不变的情况下采用不同最低新鲜度限制进行求解，实验结果如表3 所示.其中，时间成本包含行驶时间成本和惩罚成本，能耗成本包含行驶能耗和制冷能耗成本.

表3 不同最低新鲜度需求仿真结果Table 3 Simulation results of different minimum freshness requirements

由表3可知：

(1)固定成本和时间成本占总配送成本比例最低为74.1%，最高为93.5%；能耗成本和货损成本占比较低，其中，能耗成本最高占比仅为6.1%，货损成本最高占比为10.5%.这说明总配送成本主要来自固定成本和时间成本，降低配送成本的关键就是控制好车辆数和配送时间.

(2)随着最低新鲜度限制提高，总配送成本随之增加，最低新鲜度限制为97%相比90%，总配送成本增加26.7%，固定成本和时间成本增加60.0%，车辆数翻了1倍.这说明随着最低新鲜度限制的提高，客户点对配送时间的要求更加严格，使每辆电动车配送行驶时间缩短，服务客户点数量减少，需要更多的电动车完成配送任务，总行驶时间和行驶距离增加，从而提高固定成本和时间成本，总配送成本也会相应增加.

(3)随着最低新鲜度限制提高，每辆电动车配送时间和服务客户点数目减少，相应的行驶距离缩短，电动车在配送过程中充电次数和充电电量降低，当电动车行驶距离减少到续航里程内时，车辆不需在途充电，故电池损耗成本和快速充电成本降低.但配送车辆数增加，固定成本和时间成本仍会增加.

总之生鲜配送企业在制定配送路径规划时，一定要考虑客户点最低新鲜度限制需求，科学调度车辆和规划路径.

3.4 不同算法对比分析

为验证本文算法的有效性，将本文算法(Improved Ant Colony Algorithm, IACA)与经典蚁群算法(Ant Colony Algorithm,ACA)[13]和禁忌搜索算法(Tabu Search Algorithm,TSA)[14]进行比较.ACA中状态转移规则里无自适应算子，且ACA和TSA 中车辆出发时间均为0.采用算例R208 进行实验，最低新鲜度取值为90%和95%，结果如表4所示.

由表4可知：①关于配送总成本，本文算法比ACA和TSA更优.当最低新鲜度限制为90%时，本文算法比ACA 总成本降低10.1%，比TSA 降低13.6%；当最低新鲜度限制为95%时，本文算法比ACA 总成本降低12.2%，比TSA 降低13.8%.说明本文算法能够降低配送成本，提高企业经济效益.②在计算时间层面，虽然本文算法相较于ACA和TSA，多考虑了状态转移概率的改进和出发时间计算，但两种算法耗时相差不多，均能在较短的时间里得到最优结果.通过引入自适应启发算子，能够有效提高蚁群算法的局部搜索能力和全局收敛的能力.

表4 不同算法对比仿真结果Table 4 Simulation results of different algorithms

4 结 论

本文在考虑客户对生鲜最低新鲜度限制的情况下，建立时变交通下生鲜物流配送的电动车辆路径优化模型，运用路段划分策略求解时变网络下车辆行驶时间，根据模型特点提高求解效率，设计三约束因子和自适应方法对蚁群算法进行改进，通过标准案例进行验证.实验结果表明：企业在调度电动车配送过程中，应充分考虑时变网络、客户时间窗等实际情况，合理安排出发时间和规划路线，从而降低配送成本，合理规避拥堵时段；随着客户对生鲜最低新鲜度限制需求提高，配送车辆数增加，配送总成本随之提高，故生鲜企业在制定配送路径时，一定要充分考虑客户最低新鲜度限制，科学合理的调度车辆和规划路线，从而有效降低成本；改进蚁群算法相比经典蚁群算法和禁忌搜索算法，配送总成本最高可分别减少12.2%和13.8%，说明本文算法能够有效降低配送成本，提高经济效益.