改进麻雀搜索算法求解多目标低碳冷链物流车辆路径问题

杨超，张惠珍，钱陇骏

改进麻雀搜索算法求解多目标低碳冷链物流车辆路径问题

杨超，张惠珍*，钱陇骏

（上海理工大学 管理学院，上海 200093）

在传统冷链物流的车辆路径问题模型基础上，考虑服务节点和车辆运输过程中产生的碳排放，并加入客户满意度，在有限资源情况下最小化路径成本和最大化客户满意度。构建多目标低碳冷链物流车辆路径问题模型，将爬山算法局部搜索思想应用到麻雀搜索算法中，形成改进麻雀搜索算法，并用其对上海市某区域内的冷链物流配送路径优化问题算例进行求解。通过与改进前及其他2种智能优化算法运行结果进行对比发现，改进后的麻雀搜索算法具有更快的寻优速度和更好的寻优能力，且改进后的算法对模型的碳排放效用性更高。基于国家的低碳政策，设计出符合当下实情的低碳冷链物流运输模型，通过改进优化算法设计运输方案，验证了爬山算法局部搜索思想对麻雀搜索算法进行改进的有效性及所构建低碳冷链物流车辆路径模型的合理性。

车辆路径问题；多目标；低碳；爬山算法；局部搜索；麻雀搜索算法

车辆路径问题（Vehicle routing problem，VRP）是近年来物流运筹规划和智能优化算法应用研究的重要内容之一。通过优化运输路径可使整个物流供应链得到改善[1]，整个供应链的效率更高、成本更低，同时还能提升顾客满意度。

随着各种工业技术的发展成熟，冷链物流运输网络越来越完善。伴随着冷链物流的发展，环境问题成为目前发展道路上需要考虑解决的重要问题。Kuo等[2]在对冷链物流配送模式研究的基础上，根据不同产品具有不同的配送温度，提出并构建了多温度冷链物流配送路径优化模型，提高了整个冷链配送网络的响应度。不同的车辆有着不同的配送方式，存在不同的配送成本和风险。丁艳[3]采用归一化法对多目标成本进行了统一计算，使得优化结果更加合理。李四兰等[4]在模型构建中考虑了碳排放问题，将碳排放以碳税成本体现在模型中。王淑云等[5]根据客户需求构建了随机需求下的多温共配模型，使得模型更加合理。

由于VRP属于NP-hard问题[6]，所以在面对大规模的此类问题时，无法使用精确算法对其在规定的多项式时间内进行求解。针对VRP求解，目前常用的优化算法有遗传算法[7]、模拟退火算法[8]和禁忌搜索算法[9]等。遗传算法能够较好地避免陷入局部最优，可以适应多样化问题，但其计算复杂度较高，且对问题的编码和参数设置较敏感。模拟退火算法能够在一定程度上跳出局部最优解，在搜索过程中可根据问题的特点灵活地定义初始解和邻域搜索操作，但对于复杂问题需要合理的参数调节和退火策略。禁忌搜索算法具有较强的全局搜索能力，能够适应不同的问题约束和目标函数，通过调整禁忌表和禁忌规则的设置，灵活地求解问题，但在处理大规模问题时对计算成本和问题参数调节的要求较高。

麻雀搜索算法（Sparrow Search Algorithm，SSA）[10]是2020年提出的新型智能优化算法，针对每个优化问题的解类似于搜索空间中的一只麻雀，每只麻雀都具有各自的能量，采用函数适应度来表示能量。其中，将麻雀分为发现者和参与者，发现者的适应度通常大于参与者的适应度。SSA具有收敛速度快、参数较少且算法易实现等优点。为了提高麻雀种群的群体多样性，在领头鸟初始化过程中，文献[11]通过SSA和0-1规划提出了一般生鲜仓库选址问题的解决方案。阮信波等[12]通过对比SSA和粒子群算法（Particle swarm optimization，PSO），提出了SSA的缺点和改进方向。冯增喜等[13]根据精英反向学习策略对SSA的运行结果进行了反向对比评估，确保算法的结果更优。苏莹莹、王升旭[14]针对SSA初始种群质量问题提出了混沌映射初始化精英种群策略，提高了初始解质量，从而提升了算法的效率。陈登旭等[15]对比了爬山算法（Hill Climbing）和PSO，并分析了2种算法的计算收敛效率。

目前，SSA极少用于路径优化。Ouyang等[16]提出，SSA高度依赖种群中的最优个体，缺乏学习能力，在求解高维复杂的优化问题时容易陷入局部最优。将爬山算法对个体最优的局部搜索思想应用于SSA中，形成了改进麻雀搜索算法（Improved Sparrow Search Algorithm，ISSA）。采用ISSA求解含满意度的低碳冷链物流VRP模型案例，通过与改进前算法运算结果进行对比发现，改进后的算法具有更快的寻优速度和更好的寻优能力，通过与其他2种优化算法的结果进行对比发现该算法具有较好的有效性和模型合理性。

1 问题描述及模型构建

在经典VRP模型的基础上结合冷链物流独有的特点，并考虑以下几方面：运输过程中汽车燃油所产生的碳排放及车辆在各需求点装卸货物时产生的节点碳排放；由于需要保证冷链生鲜食品的新鲜度，所以存在运输过程中因食品新鲜程度发生变化而造成的货损成本；根据是否在客户期望时间内送达而产生的早到或迟到惩罚成本[17]；客户根据产品送达时间产生的满意度[18]。已知每个客户点的需求量和地理坐标，已知车辆的最大载重量及满载空载时的单位距离耗油量。以最小化成本和最大化客户满意度为目标进行优化，计算出最优的运输方案。在构建模型时做如下假设。

1）所有客户均由一个配送中心配送。

2） 所有车辆都为同一类型，在同等环境下单位距离燃油量及载重能力相同。

3） 所有客户点的需求均能被满足，且每个客户点只由1辆车服务。

4） 所有车辆在完成配送任务后必须返回配送中心，中途不考虑车辆损坏等特殊情况。

5） 车辆必须在客户可接受时间内服务。

6） 客户点的需求量、可接受服务时间及车辆在该点需要提供服务的时长均已知。

7） 所运输产品均为冷冻生鲜食品。

8） 配送路线上所有客户需求量之和不能超过该路线运输车辆最大载重。

9） 装卸过程的碳排放量与车辆冷库实时温度无关，只与开仓时间有关。

10）客户满意度计算原理：在顾客期望的时间内送达，则客户满意度达到最高值，定义为1；在客户其他可接受的时间内送达，则根据距离期望时间段的长短来判定客户的满意度。满意度与时间呈线性关系[19]，如果在客户可接受时间外送达，则客户满意度为0，如图1所示。

图1 送达时间与客户满意度关系

模型参数说明：表示配送中心和所有小区的集合，{0, 1, 2, … ,}，∈；表示车辆集合，∈；z表示车辆在需求点的装卸时间；t表示从到的运输时间；d表示从到的欧氏距离；表示车辆到需求点卸货时的单位时间碳排放量；Q表示小区的需求量；h表示车辆的启动成本；c表示车辆的单位距离运输成本；z表示装卸货物时单位碳排放价格；t表示车辆运输途中单位碳排放价格；s表示冷冻生鲜食品的单位售价；表示冷冻生鲜食品的腐败率；表示碳排放率；max表示车辆的最大载重量；1表示车辆满载时的单位距离油耗；0表示车辆空车时的单位距离油耗；H表示车辆在路径上的单位距离油耗；Q表示车辆在到这条路径上的实际载重量；t表示车辆到达点的时间；e表示车辆早到时单位时间的惩罚成本；l表示车辆晚到时单位时间的惩罚成本；[e,l]表示客户期望的配送到达时间；[e',l']表示客户可接受的配送到达时间；(t)表示车辆迟到或早到的惩罚函数；M表示客户满意度函数；表示车辆的行驶速度；x表示如果第辆车从小区到小区则为1，否则为0；z表示如果车辆到达点时发生货损则为1，否则为0。

在以上模型假设的基础上构建低碳冷链物流VRP模型，见式（1）～（13）。

s. t.

式（1）为最小化成本函数，其中，第1项为车辆使用成本，第2项为车辆运输成本，第3项为车辆在运输途中的碳排放成本，第4项为车辆在需求节点的碳排放成本，第5项为运输途中发生的货损成本，第6项为车辆早到或迟到的惩罚成本。式（2）为最大化满意度函数。式（3）表示每个需求点有且只有1辆车服务，式（4）表示车辆驶入某需求点后必须驶出。式（5）表示一条路径的总需求量不得超过车辆的最大载重量。式（6）表示每辆车的行驶路径最多只有1条。式（7）表示行驶时间。式（8）表示车辆行驶单位距离的油耗。式（9）为车辆早到或迟到的惩罚函数。式（10）为客户满意度的计算函数。式（11）表示运输到达需求点的时间必须在客户可接受时间范围内。式（12）、（13）为决策变量约束。

2 算法描述

2.1 爬山算法局部搜索

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，通过算法迭代，直到寻出一个最优解。具体步骤：将当前解初始化为随机解或预定义解；计算当前解的评估值（目标函数值）；在当前解的邻域内搜索更优的解；如果找到了更优的解，则将当前解更新为该解，并更新评估值；重复前2个步骤，直到达到一个无法改进的局部最优解，或满足迭代停止条件。

2.2 改进麻雀搜索算法

传统的SSA针对单目标连续优化问题的求解具有良好的收敛效果，但在针对多目标离散优化问题时，算法在运行时容易陷入局部最优，且不能快速有效地选择目标全局最优和个体最优。针对个体最优的选择，使用爬山算法局部搜索思想对SSA进行改进。

在最优非劣解集中，利用网格法[20]（在2.3.4节中详解）选取最优个体，然后利用爬山算法多目标局部搜索的优化思想[21]，对个体最优进行局部搜索操作。具体步骤：获取最优层级的个体0后，计算个体的适应度；在0中以一定的概率选择一个位置进行变异操作，得到新个体0，并计算适应度；比较0和0的支配关系，如果0支配0，则更新最优个体1=0，如果0支配0，则更新最优个体1=0，否则以0.5的概率接受1=0；对层级个体重新进行非支配排序，并输出结果。

麻雀搜索算法的最优个体经过爬山算法邻域搜索重新选择后，能够保证每次迭代都得到不劣于算法改进前的最优个体，在一定程度上避免陷入局部最优。

2.3 算法流程

2.3.1 编码与解码

由于麻雀搜索算法为连续型优化算法[22]，而VRP所求问题为离散型优化，所以采用的编码方式为排序的连续型编码，原理如图2所示。将每个个体进行连续编码后，再将其按照从小到大的顺序进行排序，并记录编号，转为自然数编码，编码长度为该路径上需要配送的客户点数量。定义0为配送中心，对染色体解码，图2中第1辆车的配送路径为{0，2，6，7，8，1，0}，第2辆车的配送路径为{0，10，3，4，9，5，0}，路径配送方案的生成均以客户可接受到达时间和车辆最大载重为约束。最后得到该方案的完整配送路线为{0，2，6，7，8，1，0，10，3，4，9，5，0}。

图2 编码与解码

2.3.2 初始化种群

初始化麻雀种群的计算见式（14）。其中，为所求优化问题的客户数量，为麻雀种群数量。矩阵的每行均由2.3.1节编码方式生成。

2.3.3 生成非劣解集

解码并计算目标函数值，包括配送路径的总成本和满意度。对解集进行非支配排序，将非劣解拷贝到Archive集中，记为A，并外部存档，形成pareto解集。

2.3.4 选取最优个体

用网格法计算次迭代A中麻雀的密度信息：将目标空间采用式（15）划分成大小相等的区域，将每个区域内包含的麻雀数量作为麻雀的密度信息。在网格中，麻雀的数量越多，则密度越大。实现过程如下。

1）计算次迭代的目标函数边界（min1，max1）和（min2，max2）。

2）计算网格的规模，见式（15）。

3）遍历A中的麻雀个体，用式（16）计算它在网格中的编号。

式中：为需要划分的网格数量；Int()为取整函数；1、2为目标函数值。

4）记录编号，并统计A中麻雀密度信息估计值。将Archive中的麻雀个体目标值的计算结果与初始麻雀种群目标值进行对比，优于初始群体中的麻雀数量越多，说明其搜索能力越强，反之则越弱。解集A用于存放A中优秀的麻雀个体，密度越低，被选择的概率越大。A∈A，计算个体A的密度估计值，将最小密度的个体存于G中，g=rand{G}表示在G中随机选择一个最优个体g。对于更新过的最优个体利用2.2节中的改进算法进行局部搜索，然后更新非支配排序。根据支配层级顺序确定麻雀种群的发现者、加入者和侦察者。

2.3.5 更新种群

更新了麻雀种群的发现者，见式（17）。其中，表示当前迭代次数；X表示第个麻雀种群在第维中的位置信息（这里的遍历发现者种群）；是[0, 1]之间的随机数；max是最大迭代次数；是服从正态分布的随机数；是元素全为1的1*维矩阵；2是麻雀种群预警值，在[0, 1]之间；T表示种群位置的安全值，在[0.5, 1]之间。当2＜T时，预警值小于安全值，环境安全，此时发现者可进行广泛搜索操作。当2≥T时，表示部分麻雀发现了捕食者，开始向种群其他麻雀发出预警，收到警报后所有麻雀开始飞往安全区域觅食。

更新加入者，见式（18）。其中，p表示当前发现者的最优位置；worst表示全局最差位置；=TT−1，是一个1*且元素都为1或−1的矩阵；为种群数量。当＞/2时，表示该麻雀个体处于适应度较差的位置。因为可能会挨饿，所以需要随机飞向其他地方觅食。

更新侦察者，见式（19）。其中，best是当前全局最优位置；是服从正态分布的随机数，用来作为控制步长的参数；是随机数，范围在[–1, 1]之间，同样用来控制麻雀移动的步长参数；f是当前麻雀个体的适应度值；w、g表示当前全局最劣适应度和全局最佳适应度；是一个为了避免分母为0的无穷小常数。当f＞g时，此时麻雀处在群体边缘，容易受到捕食者的攻击。当f=g时，表明种群中间的麻雀意识到了危险，开始向其他麻雀靠近，从而降低被攻击的危险。

2.3.6 更新非劣解集

计算新种群P1的目标函数值，并将最优非劣解保存至解集Archive中，生成A1。ISSA整体实验流程如图3所示，在对初始化个体的适应度进行非支配排序后，使用网格法选出最优个体。利用爬山算法对最优个体进行局部搜索，产生新的最优个体。对比选择适应度较大的最优个体，并再次对种群进行非支配排序。利用位置公式更新个体的位置后，计算新的种群适应度。更新非劣解集，根据迭代次数条件判断算法是否终止，并输出最优结果。

图3 ISSA流程

3 仿真试验设计与分析

为了验证ISSA对优化效果的提升，使用Matlab 2021a对算法进行编程，所有程序均在一台配置12th Gen Intel(R) Core(TM) i5-12600KF@3.70 GHz (32.0 GB)、操作系统为64位的Windows 10电脑上运行。

3.1 仿真实验算例

为了验证模型的合理性和算法改进的有效性，现对上海市某区域的55个需求点进行冷链生鲜配送模拟实验，各点位置、需求量及所需时间如表1所示。结合市场行情及相关碳税政策，得出模型所需参数数据，如表2所示。在表1中，编号0为配送中心，其他编号为需求点。

表1 小区位置、需求量及时间

Tab.1 Community location, demand and time data

表2 模型参数取值

Tab.2 Model parameter value

3.2 实验求解结果分析

对上述算例分别使用SSA和ISSA，并借助Matlab 2021a进行仿真求解。算法参数参考文献[13]设置，麻雀发现者比例D=0.2，麻雀侦察者比例D=0.1，预警值T=0.8，种群数量=80，最大迭代次数T=800。

根据表1和表2中的数据信息，对模型目标函数进行求解，得到最优配送路径，即最低成本和最大满意度。使用2种算法同时对算例进行50次求解后取均值，结果如表3所示。从表3可以看出，在相同条件下ISSA的优化结果优于SSA，在低成本前提下保持了较高的满意度，且优化结果标准差均小于SSA，说明改进后算法的运行效果更好。

表3 ISSA与SSA实验结果对比

Tab.3 Comparison of ISSA and SSA experimental results

为了方便直观地分析算法的优化过程及结果，选取其中1次实验的结果。图4和图5分别是2个算法实验的成本迭代图和满意度迭代图。可以看出，在相同的迭代次数下，ISSA相较于SSA，其收敛速度更快、效果更好；在每次算法得到最优个体后，再对其进行邻域内爬山算法搜索，这在很大程度上改善了SSA容易陷入局部最优的缺陷，使得全局最优结果更好。

2个算法实验计算结果的pareto前沿（计算结果的点集合不再受其他任意点支配）如图6所示，总成本为轴，平均满意度为轴。由于优化要求为成本最小、平均满意度最大，所以pareto前沿应趋于左上角。从图6中可以看出，ISSA的优化结果pareto前沿相较于SSA更趋于左上角，所以ISSA结果整体优于SSA。ISSA、SSA对应的实验路径优化结果分别如图7～8所示。

图4 成本迭代对比

图5 满意度迭代对比

3.3 参数分析

为了验证算法中各参数对算法效用性的影响，需要对不同参数情况下的优化结果进行统计对比。下面主要针对不同种群规模、麻雀发现者比例进行对比分析。

3.3.1 种群规模

实验的种群规模设置如表4所示，最大迭代次数T=800，麻雀发现者比例D=0.2，麻雀侦察者比例D=0.1，预警值T=0.8，每个种群规模进行10次实验，计算每个规模下10次实验结果的均值。

图6 实验pareto前沿

图7 ISSA实验路径

图8 SSA实验路径

由表4可知，在种群规模数量较小的情况下，ISSA不易得到最优结果，且有一定概率出现优化结果不如SSA的情况。这可能是由于种群规模较小时，麻雀种群的多样性较低，算法缺乏局部搜索能力，导致全局搜索能力下降，最后陷入局部最优解。当种群数量在80以上时，ISSA的优化效果较稳定，算法优势也较明显。较大的种群规模增加了种群的多样性。在算法进行局部搜索时，能更好地探索解空间，提高发现全局最优解的机会。

表4 不同种群规模实验结果

Tab.4 Experimental results of different population sizes

注：实验序号2加粗字体表示此次实验的SSA结果优于ISSA。

3.3.2 发现者比例

为了验证麻雀发现者比例对优化结果的影响，实验设置了不同的发现者比例，如表5所示，最大迭代次数T=800，麻雀侦察者比例D=0.1，预警值T=0.8，种群规模为80。每个比例进行10次实验，计算每种发现者比例下的10次实验结果的均值，并记录算法运行时间，如表5所示。

由表5可知，随着发现者比例的增大，ISSA的优化效果明显改善，说明发现者比例的增大可以增强最优个体麻雀的搜索能力，爬山算法的融入改进保证了每次选择的最优个体均不劣于原算法，提升了算法的局部搜索能力，从而提高了全局搜索的效果。SSA的效果相较于ISSA未出现明显变化的趋势，这是由于发现者比例过大时，SSA过分依赖全局搜索，降低了算法在局部搜索空间中的效果，符合SSA优化效果分析得出的存在不稳定性的结论。2种算法在发现者比例增大时都在一定程度上出现了运算时间增加的情况，由于ISSA在每次算法流程中增加了局部搜索操作，所以相较于SSA，其花费的时间更长，但相较于优化效果，认为这个延长的时间在可接受范围内。

3.4 算法效用性分析

为了进一步分析ISSA的效用性，将ISSA与SSA、改进鲸鱼优化算法（Improved Whale Optimization Algorithm，IWOA）[23]、改进粒子群算法（Improved Particle Swarm Optimization，IPSO）[24]的实验结果进行对比。试验迭代次数均为800，种群大小均为80，其余参数设置均为对应算法的初始值。每个算法进行20次实验，实验数据如表6。

表5 不同发现者比例实验结果

Tab.5 Experimental results of the proportion of different discoverers

表6 算法实验结果分析

Tab.6 Algorithm experiment result analysis

从表6可以看出，ISSA的成本和满意度均值均高于其他3种算法，优化效果最好；ISSA的标准差相对较小，算法的优化效果较稳定；SSA的优化效果最差，标准差最大，优化稳定性较差；虽然IPSO的标准差比ISSA的标准差小，但是算法的运行效率和优化效果均不如ISSA，其稳定性差距可以接受；IWOA的优化效果和算法运行效率接近于ISSA，但是其标准差较大、优化稳定性较差。为了更直观地对比算法，取其中一次实验的pareto前沿图，如图9所示。

由图9可知，ISSA的pareto前沿更加趋向于左上角，说明其优化结果更好，在相同成本的情况下可以得到更高的客户满意度。IWOA的pareto前沿有部分解跟ISSA的优化效果近似，但是ISSA整体的pareto前沿分布相对于IWOA更稳定。IPSO的pareto前沿分布较稳定，且部分结果优于IWOA，但是在成本升高时不能带来较大满意度的提升。SSA相较于其他3种算法，其优化效果较差。

图9 4种算法实验的pareto前沿

3.5 模型低碳效用性分析

为了验证低碳模型能够有效降低冷链物流配送的碳排放，并对整个配送网络具有良好的优化作用，将上述算例按照参考文献[25]的方法进行实验对比分析，将不考虑碳排放的成本结果记为s。将计算出的路径带入低碳优化模型中，将结果记为s，以20次实验为1组，进行5组实验，取每组实验结果的均值，再按照式（20）计算s。s通过计算计入碳税前后的成本差占初始成本的结果比重来反映碳成本所带来的影响，比值越大，说明其影响越大，低碳模型的效用性越佳。

实验结果如表7所示，可以看出，无论采用ISSA还是SSA求解成本目标函数，s结果平均值都达到5%以上，说明考虑碳排放成本对ISSA和SSA优化结果都有显著影响，ISSA的s、s的均值均低于SSA，说明ISSA对模型求解的效果更好；ISSA的s均值比SSA更高，说明其模型低碳效应性更好。

表7 低碳效用结果分析

Tab.7 Low carbon utility results analysis

4 结语

针对冷链物流的路径问题，结合低碳排放目标，建立了考虑碳排放的模型，并基于传统SSA对其进行了改进，提出了结合爬山算法局部搜索的ISSA，使得算法在原来的基础上具有更好的个体最优搜索能力，有效避免了算法陷入局部最优的情况发生。通过ISSA、SSA、 IWOA、IPSO对实际应用案例进行求解，并对比分析结果，进一步验证改进算法的有效性和构建模型的合理性。

实验对比结果表明，ISSA的优化效果明显优于SSA，且改进算法后运行得更稳定。虽然算法的改进效果明显，但是需要更长的运行时间，复杂度随之略有增加。如何使算法在相同甚至更少的时间内得到稳定且有效的优化还有待改进。改进算法使得每次迭代的麻雀最优个体的适应度更好，但如何针对麻雀整个种群进行优化，并应用于离散优化问题求解，还有待研究。针对碳排放问题建立模型，并用实际算例证明模型可以有效降低碳排放和整个配送路径成本，未来可以进一步将算法应用于有特殊配送需求的VRP模型中进行目标优化计算。

[1] KUEI C. Supply Chain – Logistics Management[J]. International Journal of Quality & Reliability Management, 2002, 19: 802-803.

[2] KUO J C, CHEN M C. Developing an Advanced Multi-Temperature Joint Distribution System for the Food Cold Chain[J]. Food Control, 2010, 21(4): 559-566.

[3] 丁艳. 多温共配冷链物流车辆配送路径优化仿真[J]. 沈阳工业大学学报, 2021, 43(3): 311-316.

DING Y. Simulation of Vehicle Distribution Path Optimization for Multi-Temperature Co-Distribution Cold Chain Logistics[J]. Journal of Shenyang University of Technology, 2021, 43(3): 311-316.

[4] 李四兰, 宋孟珂, 郭伟钰. 基于低碳排放的冷链物流多温共配路径优化研究[J]. 物流科技, 2021, 44(8): 152-156.

LI S L, SONG M K, GUO W Y. Study on Optimization of Multi-Temperature Co-Distribution Path of Cold Chain Logistics Based on Low Carbon Emissions[J]. Logistics Sci-Tech, 2021, 44(8): 152-156.

[5] 王淑云, 孙虹, 牟进进. 随机需求下蓄冷式多温共配优化模型[J]. 系统管理学报, 2018, 27(4): 712-721.

WANG S Y, SUN H, MOU J J. Optimization of Cold-Storage Multi-Temperature Joint Distribution Based on Stochastic Demands[J]. Journal of Systems & Management, 2018, 27(4): 712-721.

[6] KIM G, ONG Y S, HENG C K, et al. City Vehicle Routing Problem (City VRP): A Review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1654-1666.

[7] POTVIN J Y, BENGIO S. The Vehicle Routing Problem with Time Windows Part Ⅱ: Genetic Search[J]. INFORMS Journal on Computing, 1996, 8(2): 165-172.

[8] Bräysy O, Gendreau M. Metaheuristics for the vehicle routing problem with time windows[J]. Report STF42 A, 2001, 1025: 3-38

[9] CORDEAU J F, LAPORTE G, MERCIER A. A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows[J]. Journal of the Operational Research Society, 2001, 52(8): 928-936.

[10] XUE J K, SHEN B. A Novel Swarm Intelligence Optimization Approach: Sparrow Search Algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.

[11] 楚哲宇, 刘丹, 张蓉波, 等. 麻雀搜索算法与0-1规划在生鲜仓储选址问题中的应用[J]. 自动化应用, 2021(9): 56-59.

CHU Z Y, LIU D, ZHANG R B, et al. Application of Sparrow Search Algorithm and 0-1 Planning in the Location of Fresh Food Storage[J]. Automation Application, 2021(9): 56-59.

[12] 阮信波, 刘丽华, 陈丽瑾. 麻雀搜索算法在物流配送中心选址的应用[J]. 物流技术, 2021, 40(12): 40-43.

RUAN X B, LIU L H, CHEN L J. Application of Sparrow Search Algorithm in Location Selection of Logistics Distribution Center[J]. Logistics Technology, 2021, 40(12): 40-43.

[13] 冯增喜, 李诗妍, 赵锦彤, 等. 基于精英反向学习策略的麻雀搜索算法[J]. 计算机仿真, 2023, 40(1): 378-381.

FENG Z X, LI S Y, ZHAO J T, et al. Sparrow Search Algorithm Based on Elite Reverse Learning Strategy[J]. Computer Simulation, 2023, 40(1): 378-381.

[14] 苏莹莹, 王升旭. 自适应混合策略麻雀搜索算法[J]. 计算机工程与应用, 2023, 59(9): 75-85.

SU Y Y, WANG S X. Adaptive Hybrid Strategy Sparrow Search Algorithm[J]. Computer Engineering and Applications, 2023, 59(9): 75-85.

[15] 陈登旭, 刘吉, 武锦辉, 等. 基于自阈值粒子群算法和爬山算法的DIC形变分析[J]. 国外电子测量技术, 2020, 39(5): 11-16.

CHEN D X, LIU J, WU J H, et al. DIC Deformation Analysis Based on Self-Threshold Particle Swarm Optimization and Hill Climbing Algorithm[J]. Foreign Electronic Measurement Technology, 2020, 39(5): 11-16.

[16] OUYANG C T, ZHU D L, WANG F Q. A Learning Sparrow Search Algorithm[J]. Computational Intelligence and Neuroscience, 2021, 2021: 3946958.

[17] 张天瑞, 刘海波. 碳税政策下基于BFA-ACO的冷链物流路径优化[J]. 沈阳大学学报(自然科学版), 2022, 34(5): 363-372.

ZHANG T R, LIU H B. Cold Chain Logistics Path Optimization Based on BFA-ACO under Carbon Tax Policy[J]. Journal of Shenyang University (Natural Science), 2022, 34(5): 363-372.

[18] 曾敏刚, 王秀慧, 黎建宇. 考虑节点中断与碳排放的冷链物流网络规划研究[J]. 华南理工大学学报(社会科学版), 2021, 23(4): 55-66.

ZENG M G, WANG X H, LI J Y. Cold Chain Logistics Network Planning Considering Node Interruption and Carbon Emissions[J]. Journal of South China University of Technology (Social Science Edition), 2021, 23(4): 55-66.

[19] 周鲜成, 蒋涛营, 贺彩虹, 等. 冷链物流配送的绿色车辆路径模型及其求解算法[J]. 中国管理科学,2023,31(12):203-214.

ZHOU X C, JIANG T Y, HE C H, et alGreen vehicle path model for cold chain logistics distribution and its solution algorithm[J]. Chinese Journal of Management Science:1-11.

[20] MOGHADDAM A A, SEIFI A, NIKNAM T. Multi-Operation Management of a Typical Micro-Grids Using Particle Swarm Optimization: A Comparative Study[J]. Renewable and Sustainable Energy Reviews, 2012, 16(2): 1268-1281.

[21] XI B W, LIU Z, RAGHAVACHARI M, et al. A Smart Hill-Climbing Algorithm for Application Server Configuration[C]// Proceedings of the 13th International Conference on World Wide Web, 2004: 287–296.

[22] GAO B W, SHEN W, GUAN H, et al. Research on Multistrategy Improved Evolutionary Sparrow Search Algorithm and Its Application[J]. IEEE Access, 1809, 10: 62520-62534.

[23] 陈暄, 蔡文雅. 双目标的冷链物流车辆规划路径的研究[J]. 现代信息科技, 2022, 6(23): 125-128.

CHEN X, CAI W Y. Research on the Planning Path of Cold Chain Logistics Vehicles with Dual Objectives[J]. Modern Information Technology, 2022, 6(23): 125-128.

[24] 陈智勇. 基于IPSO算法的多目标车辆配送路径规划研究[J]. 山东农业大学学报(自然科学版), 2017, 48(2): 255-258.

CHEN Z Y. Research on Multi-Objective Vehicle Route Program Based on IPSO Algorithm[J]. Journal of Shandong Agricultural University (Natural Science Edition), 2017, 48(2): 255-258.

[25] 张坤, 张惠珍, 马良, 等. 分布估计灰狼算法求解低碳选址路径问题[J]. 系统管理学报, 2023, 32(4): 701-711.

ZHANG K, ZHANG H Z, MA L, et al. Grey Wolf Optimizer with Distribution Estimation for Low Carbon Location Routing Problem[J]. Journal of Systems & Management, 2023, 32(4): 701-711.

Improved Sparrow Search Algorithm to Solve the Routing Problem of Multi-objective Low-carbon Cold Chain Logistics Vehicle

YANG Chao, ZHANG Huizhen*,QIAN Longjun

(Business School, University of Shanghai for Science and Technology, Shanghai 200093, China)

The work aims to minimize the route cost and maximize the customer satisfaction under limited resources by considering the carbon emissions generated during service nodes and vehicle transportation as well as the customer satisfaction on the basis of the traditional cold chain logistics vehicle routing problem model. A multi-objective low-carbon cold chain logistics vehicle routing problem model was constructed, and the local search idea of mountain climbing algorithm was applied to the sparrow search algorithm to form an improved sparrow search algorithm. Then, the improved algorithm was used to solve the cold chain logistics distribution path optimization problem in a certain area of Shanghai. The results were compared with the results of the other two intelligent optimization algorithms before the improvement: the improved sparrow search algorithm had faster optimization speed and better optimization ability, and the improved algorithm had higher efficiency on carbon emission of the model. Based on the national low-carbon policy, a low-carbon cold chain logistics transport model that is in line with the current situation is designed, and the transport scheme is solved by improving the optimization algorithm, which verifies the effectiveness of the local search idea of the mountain climbing algorithm on the sparrow search algorithm and the rationality of the low-carbon cold chain logistics vehicle routing model constructed.

vehicle routing problem; multi-objective;low-carbon; mountain climbing algorithm;local search; sparrow search algorithm

TP302

A

1001-3563(2024)03-0251-11

10.19554/j.cnki.1001-3563.2024.03.029

2023-04-12

国家自然科学基金（72101149）；教育部人文社会科学基金（21YJC630087）