不同车型新能源车在城市冷链物流配送中的路径优化

闫淼， 初良勇,2

(1.集美大学航海学院，福建 厦门 361021; 2.福建航运研究院，福建 厦门 361021)

0 引 言

随着城市化进程的不断推进，物流行业向“绿色化”转型升级已是大势所趋，新能源车凭借其低污染优势迅速占据市场，并逐渐取代传统燃油货车，成为满足城市配送需求和解决环境污染问题的首选运输工具。因此，如何在物流配送中高效利用新能源车受到国内外学者的广泛关注。

新能源车在配送过程中存在续航能力短、电池容量小、充电不便等短板。为在有限条件下对新能源车进行合理调度，提高经济效益，部分学者基于充电设施的选址问题和充电行为选择问题进行研究：杨珺等[1]构建了纯电动汽车物流配送系统的换电站选址与配送路径优化模型，并利用禁忌搜索算法和改进Clark-Wright节省算法的两阶段启发式算法来求解模型。ADLER等[2]研究了对应不同充电站数量的电动汽车最短路径问题。HOF 等[3]设计了一种自适应可变邻域搜索算法来解决电动汽车电池更换站的选址与路径双层规划问题。LÖFFLER等[4]考虑到完全和部分充电的可能性，开发了大邻域搜索和颗粒禁忌搜索的简单混合算法，以解决由此产生的带时间窗和单次充电的电动汽车路线问题。同时，也有部分学者的研究侧重于新能源车的配送路径规划方面：BELTRAN等[5]提出将电动车应用于城市交通运输中。ARTMEIER等[6]在构建电动汽车的路径优化模型时，考虑车辆的续驶里程、充电时长、制动时的能量回收等因素，确定成本最低的配送路线。KOÇ等[7]提出一种基于模拟退火启发式的精确求解方法来解决新能源车的路径优化问题。肖建华等[8]构建了基于城市道路限行的多能源多车型混合车辆路径优化模型，将城市分区域、分车型等限行因素引入车辆路径问题中，并提出变邻域搜索算法求解该模型。LI等[9]提出一种融合模因算法和序贯变量邻域下降法的混合优化算法解决混合动力电动车辆的路径优化问题。马冰山等[10]结合多配送中心联合服务模式的特点和纯电动物流车辆的行驶特征，构建了带时间窗的半开放式多配送中心纯电动车辆路径优化模型。ZHANG等[11]考虑服务时间、电池能量消耗和行驶时间等不确定因素的影响，建立了基于模糊优化的数学模型。

冷链物流是随着制冷技术的发展而建立起来的，已被众多产品配送所选用。因此，如何将新能源车应用到城市冷链物流中，已成为当前研究的重点。冯杰等[12]研究了供应商使用同一车型的纯电动冷藏车进行配送，为生鲜产品的路径优化问题提供了思路。赵志学等[13]依据时变交通路网特点，设计了基于路段划分策略的行驶时间计算方法，构建时变交通下电动车在城市生鲜配送中的路径优化模型，根据模型特点设计了自适应改进的蚁群算法。

综上，虽然已有研究将新能源车应用到城市物流配送中，但鲜有研究考虑在满足客户时间窗的条件下，将新能源车应用到城市冷链物流中，也缺少考虑新能源车在配送过程中充电需求的研究。同时，当前的研究未考虑根据客户的实际需求量选择合适的车型进行配送，不能达到充分利用车辆资源、降低配送成本的目的。基于此，本文讨论在客户时间窗限制下，新能源车的充电需求对车辆配送过程的影响；结合冷链配送的实际情况，考虑不同车型新能源车在运输过程中的耗电，以及在装卸搬运过程中为维持温度恒定而产生的耗电，构建不同车型新能源车在冷链物流配送中的路径优化模型，并利用改进的蚁群算法求解相对最优解，验证模型的有效性。

本文研究的问题可被描述为：一个配送中心拥有多辆新能源车，不同车型的车辆有其相应的额定载质量、最大可充电量等限制；车辆从配送中心发出，为若干个客户进行服务，客户时间窗已知，车辆完成任务后返回配送中心；合理设置充电站，以满足车辆在配送过程中的充电需求。为保证生鲜产品的新鲜度和顾客的满意度，以配送总成本最低为目标，建立带软时间窗的整数规划模型对城市冷链物流配送路径进行优化。

1 模型构建

1.1 符号说明

已知一个配送中心(用“1”表示)、客户点集合N和充电站集合A；V={1}∪N∪A为所有节点的集合，i,j∈V；M为车辆类型集合，m∈M；Lm表示车型为m的车辆集合，l∈Lm。Cs,m表示车型为m的车辆的发车成本；Ct,m表示车型为m的车辆单位距离运输成本；Cc为车辆的单位时间充电成本；dij为节点i与节点j之间的距离；Qm表示车型为m的车辆最大载质量；em表示车型为m的车辆的电池最大容量；qi为节点i的需求量；v为车辆的平均行驶速度；ta,iml、ea,iml分别为车型为m的第l辆车到达节点i时的时间和剩余电量；tv,iml、ev,iml分别为车型为m的第l辆车离开节点i时的时间和剩余电量；rm1表示车型为m的车辆在运输过程中所产生的单位时间可变耗电量；rm2表示车型为m的车辆在装卸搬运过程中所产生的单位时间可变耗电量；ts,i为在节点i的服务时间；tc,i为在节点i的充电时间；[te,i,tv,i]为节点i允许服务的时间窗；ε为等待成本和延误成本惩罚系数；δ为在[0.25,0.30]区间内的一个随机数。

决策变量：xijml，若车型为m的第l辆车由节点i驶向节点j，则xijml=1，否则xijml=0；yiml，i∈N，若车型为m的第l辆车为节点i服务，则yiml=1，否则yiml=0；ziml，i∈A，若车型为m的第l辆车在节点i充电，则ziml=1，否则ziml=0。

1.2 数学模型

以配送总成本最低为目标，考虑新能源车配送时的电量消耗，构建不同车型新能源车在冷链物流配送中的路径优化模型。若无特别说明，j∈V，i∈V，m∈M，l∈Lm。

min

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

ea,iml≤ev,iml-rm1(dij/v)xijml+em(1-xijml),

(7)

∀i,j∈N

ea,iml≥δem

(8)

(9)

tv,iml=max{ta,iml,te,i}+ts,iyiml+tc,iziml

(10)

ta,iml=tv,iml+(dij/v)xijml

(11)

(12)

xijml,yiml,ziml∈{0,1}

(13)

式(1)为目标函数，表示配送总成本最低，配送总成本包括固定成本、运输成本、惩罚成本和充电成本。式(2)～(15)为模型约束条件：式(2)和(3)表示所有客户均得到服务且仅被一辆车服务；式(4)表示到达节点与离开节点的车辆相同；式(5)表示车辆的初始出发点和最终到达点均为配送中心；式(6)为车辆载质量约束；式(7)表示车辆的电量与行驶里程之间的关系；式(8)考虑到不同车型新能源车的电池特性及驾驶员的里程焦虑，保证车辆的剩余电量不低于该车辆最大电池容量的25%～30%；式(9)表示车辆离开节点的电量；式(10)和(11)分别表示车辆的离开和到达时间；式(12)为每个节点的时间窗约束；式(13)为决策变量约束。

2 算法设计

本文研究的问题是典型NP难问题，传统精确算法难以对该类问题进行快速求解，故应用元启发式算法求解。蚁群算法[14](ant colony optimization, ACO)具有正反馈性和自组织性，是解决车辆路径问题的有效算法之一，但也存在初期收敛速度较慢、易陷入局部最优等问题。海洋掠食者算法[15](marine predators algorithm，MPA)拥有强大的搜索能力和较好的开发性能。因此，本文设计一种融合MPA与ACO的算法(记为MPA-ACO)对模型进行求解。

2.1 MPA预搜索路径

传统ACO通常将初始信息素设为一个定值，这也导致了ACO在初期收敛速度慢的问题，本文先采取MPA对车辆路径进行预搜索，再将其搜索到的路径上的初始信息素含量提高，从而提高算法的初期搜索能力。

2.1.1 优化阶段

MPA用猎物代表可行解，一个猎物代表一条路径，每个猎物都有其位置向量，以及在位置下的适应度，猎物在不同阶段采取不同的策略进行移动。若猎物适应度在新位置下更优，则更换位置，其中表现最优异的猎物将会被视为掠食者。经过多次迭代，实现路径预搜索任务。MPA分为以下3个主要阶段，其数学模型表示如下：

阶段1当迭代次数小于最大迭代次数的1/3时，种群中的掠食者速度比猎物速度快，算法进入探索阶段，其优化过程如下：

(14)

式中：掠食者和猎物均为搜索个体h，sh为其步长；RB为呈正态分布的布朗运动随机向量；Eh为n×d维的顶级掠食者矩阵，n为种群规模，d为个体维度值；Ph为猎物矩阵；P为等于0.5的常数；R为0至1内的均匀随机向量。

阶段2当迭代次数大于最大迭代次数的1/3而小于其2/3时，掠食者速度与猎物速度相同，猎物基于Lévy游走策略负责开发，掠食者则基于布朗游走策略负责探索，算法进入探索与开发阶段，其优化过程如下：

(15)

(16)

式中：RL为符合Lévy游走的随机向量；c为控制掠食者运动步长的自适应参数。

阶段3当迭代次数大于最大迭代次数的2/3时，掠食者速度比猎物速度慢，算法进入开发阶段，其优化过程如下：

(17)

2.1.2 鱼类聚集装置效应及涡流效应

为避免算法在寻优过程中出现过早收敛的情况，加入鱼类聚集装置(fish aggregating devices, FAD)和涡流效应来改变动物觅食行为：

Ph=

(18)

式中：Fs为0.2，表示优化过程中受FAD影响的概率；U为二进制向量；r为0到1内的随机数；Pr1和Pr2表示猎物矩阵的随机索引；Xmax和Xmin为包含维度上下限的向量。

2.2 蚂蚁寻优策略及信息素更新方式

2.2.1 可行路径的构建

考虑到新能源车在配送过程中存在电量耗尽的风险，在选择下一个配送点时，应考虑该点距离其最近充电站的距离，距离越小被选择的概率越大。将转移概率根据车辆所在地点不同分为：充电站与配送点的转移概率和配送点之间的转移概率。

(1)蚂蚁k从充电站i到配送点j的转移概率

pkij(t)=

(19)

式中：τij(t)为在t时刻在节点i与节点j上存留的信息素；ηij(t)为启发函数，ηij(t)=1/dij；tth,j为客户j的时间窗宽度；tw,j为客户j的等待时间；Ak为蚂蚁k接下来有权访问的客户点的集合；α、β分别表示信息素和启发信息在蚂蚁寻找路径中的重要程度；γ、λ分别为时间窗宽度、等待时间在蚂蚁寻找路径中的重要程度。

(2)蚂蚁k从配送点i到配送点j的转移概率

pkij(t)=

(20)

式中：ξj(t)为电量补给难易函数，ξj(t)=1/mindjp，mindjp为客户点j到最近的充电站p的距离，djp越大说明选择客户点j时在途中耗尽电量的风险越大，电量补给越难；θ为电量补给难易因子。

2.2.2 信息素更新方式

信息素指引着蚂蚁的移动，在完成所有节点的配送后，将按照当前蚂蚁所选择的路径对全局信息素进行更新。信息素蒸发公式及更新公式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij,

0<ρ≤1

(21)

Δτij=Q/DT

(22)

式中：ρ为信息素蒸发率；Δτij为本次循环中蚂蚁所选定路径的信息素增加量；Q为常数；DT为该蚂蚁所构建完整路径的总距离。

2.3 MPA-ACO设计

先通过MPA预求解出车辆配送路径，然后将相应路径上的信息素含量提高。蚂蚁从固定配送中心出发并随机选择配送车型，从满足载质量、距离、电量和客户时间窗约束的需求点中，根据寻优策略中的概率进行选择，在完成当前需求点的配送服务后，将该点置入禁忌表。若电量不足以完成配送，则应根据就近原则选择充电站补充电量。若不能满足客户点需求，则应返回配送中心。蚂蚁可在配送中心重新选择车辆进行补货作业，并继续选择需求点执行配送服务，当所有需求点均被服务后，蚂蚁停止配送服务。算法步骤如下：

步骤1初始化算法相关参数：ACO迭代次数、信息启发式因子、蚂蚁数、期望启发式因子等参数。

步骤2根据MPA预搜索出的路径设置初始信息素。

步骤3蚂蚁从配送中心出发，随机选择不同车型的车辆。

步骤4根据转移概率(式(19)和(20))选择满足约束条件且不在禁忌表内的需求点，放置到当前解中，并录入禁忌表。

步骤5在蚂蚁搜索到的可行路径中找到最优路径后，根据式(21)和(22)更新全局信息素。

步骤6判断是否已经达到最大迭代次数。如果未达到，则转到步骤2；否则停止运算，输出当前值作为最优路径。

3 算例验证与结果分析

3.1 实验设置

采用实际数据并结合算例进行分析。实际数据来自厦门市某生鲜食品公司的40个订单数据，如表1所示。算例改编自SOLOMON[16]的带时间窗的车辆路径问题(vehicle routing problem with time window, VRPTW)数据集。为模拟实际配送情况，做出如下修改：(1)车辆在充电站的充电时间受车辆充电效率、到达充电站的剩余电量影响，设定车辆离开充电站时，电池为满电状态。(2)假设配送中心拥有A、B两种车型的新能源车，车厢内温度需要根据外界气温的变化控制在-4 ℃至4 ℃，平均行驶速度为45 km/h，车辆单位充电成本为1元/(kW·h)，平均充电速度1.5 kW·h/min。(3)早于或晚于客户时间窗服务所产生的单位时间惩罚成本为ε=0.5元/min。车辆相关参数见表2。

表1 实际订单数据

表2 车辆相关参数

3.2 实际应用

根据厦门市某生鲜食品公司实际节点数，设置蚂蚁数量K=75。根据多次实验，设置基本参数如下：α=1，β=4，γ=1，ρ=0.3，最大迭代次数为100次。程序运行20次，取其中的最优路径。最优路径图见图1，具体优化结果见表3。

图1 最优路径图

表3 车辆路径优化结果

通过计算可得，配送总成本为2 337.1元，使用7辆电动车，固定成本为1 520元，运输成本为401.95元，惩罚成本为294.81元，行驶里程为680.21 km，其中有2辆车在配送过程中进行了充电，充电成本为120.34元。数据表明，本文提出的模型和算法在综合考虑了不同车型的指派、客户时间窗和新能源车的充电需求的基础上，有效减少了行驶里程，提高了客户满意度。本文所构建的不同车型新能源车在冷链物流配送中的路径优化模型对该生鲜食品公司在降低配送总成本方面具有重要参考价值。同时，本研究为采用新能源车作为运输工具的物流配送企业的实际操作提供了优化模型和算法支持。

3.3 模型对比分析

为明确不同车型新能源车在冷链物流配送中的作用，将原模型的决策变量xijml改为xijl，构建单一车型新能源车在冷链物流配送中的路径优化模型(简称为“单一车型配送模型”)，与上述所构建的不同车型新能源车在冷链物流配送中的路径优化模型(简称为“多车型配送模型”)的结果进行对比，采用MPA-ACO求解，并以SOLOMON[16]的VRPTW数据集为参照。SOLOMON的数据集设计了R(随机分布)、RC(混和分布)和C(成群分布)3种类型的客户点分布，其中：R类客户点的地理位置分布较为分散；C类的为堆分布，表现为客户的地理位置向一个或者多个小范围内聚集；RC类的为半堆分布，表示客户的地理位置是混合分布的。对比结果见表4。

分析表4可得：(1)多车型配送策略下的配送总成本低于单一车型配送策略下的配送总成本，前者明显比后者低了0.55%～4.10%，表明采用不同车型进行配送，可以合理调配车辆资源，降低整体运输成本，为企业盈利带来增长空间。(2)单一车型配送策略下，不同吨位大小的车辆在不同应用场景中各有优势。通过对比采用A、B两种单一车型的车辆的使用数量和充电次数可知，采用B车型可使配送车辆数量和充电次数明显减少，表明B车型更适应长时间、远距离运输。然而，在进一步分析两种车型的各项成本后发现，A车型具有较低的固定成本和运输成本，其配送总成本比采用B车型的低0.02%～0.03%，表明在整体配送区域较小、单个客户点需求量较小的环境中，采用小吨位车型比采用大吨位车型配送更具有成本优势。

3.4 算法对比分析

为进一步验证算法的有效性，采用R112算例对MPA-ACO与传统ACO进行比较。设置1个配送中心、50个客户点、5个充电站。实验随机进行20次，求解结果对比见图2。图3为其中一次实验的迭代对比图。

表4 两种模型结果对比

图2 MPA-ACO与ACO求解结果对比

图3 MPA-ACO与ACO迭代对比

由图2可知，MPA-ACO求得的配送总成本平均低于ACO求得的配送总成本。由图3可知，本文算法在寻优能力和收敛速度上都有大幅度提高:在优化初期，得益于MPA的路径预搜索，MPA-ACO具有较强的搜索能力；在优化中后期，MPA-ACO能更早收敛，且找到的路径更优。通过实验计算可得，虽然MPA-ACO的平均运行时间为12.19 s，ACO的平均运行时间为9.06 s，但两者均能在较短时间内得到最优解。综上说明，引入MPA，能够有效提高ACO的局部搜索能力和全局收敛能力，为ACO的改进提供新思路。

3.5 充电站数量灵敏度分析

在采用不同车型新能源车进行配送的情况下，为分析充电站数量的影响，针对R、RC和C这3类客户点分布，在其他条件不变的情况下调整充电站的数量对模型进行求解。对每个算例求解10次，选择其中的最优解进行比较，结果见表5。

分析表5可得：(1)配送总成本会随着充电站数量的增加而降低，而当配送总成本降低到一定程度后变化趋于平缓。在3类客户中，当充电站数量超过6时，配送总成本的变化不再明显，这是因为在一定区域内，充电站数量的增加虽然可以为车辆提供更多的路径选择，但若该区域的充电站数量已达到饱和状态，则过多的充电站将增加充电站的建设和维护成本，降低该区域充电站的平均使用率。(2)对于呈聚集分布的C类客户而言，随着充电站数量的增加，优化效果更佳；R类和RC类客户的配送总成本受充电站数量的影响较小，当充电站数量增加至4～5时，配送总成本的下降趋于平缓。C类客户的配送总成本的下降趋势最明显，这是因为其分布具有聚类特点，在客户聚集地周围建设充电站，可明显降低车辆的运输成本和充电成本；同时随着充电站数量的增加，配送车辆也由6辆减少至5辆，表明针对聚集分布的客户，合理建造充电站可以有效减少车辆投入。

4 结 论

本文以城市冷链物流配送为研究对象，在采取新能源车进行配送的基础上，结合不同车型的优势，以包括固定成本、运输成本、惩罚成本和充电成本的配送总成本最低为目标，同时考虑了车辆载质量约束、客户时间窗限制、车辆充电需求等因素，构建了不同车型新能源车在冷链物流配送中的路径优化模型。利用融合了海洋掠食者算法(MPA)的蚁群算法(ACO)对该问题进行求解，并验证了算法的有效性。本文的研究成果可证明，将不同车型新能源车用在城市冷链物流配送中可以有效降低整体配送成本，减少车辆资源的闲置与浪费，为企业在城市配送中的资源分配提供有益启示。

表5 不同客户点分布类型下充电站数量灵敏度分析