改进麻雀算法求解带模糊需求的低碳路径优化

黄琴，张惠珍，魏欣，邓歆乐

改进麻雀算法求解带模糊需求的低碳路径优化

黄琴，张惠珍*，魏欣，邓歆乐

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

针对低碳背景下带模糊需求的低碳多式联运规划问题（Low-carbon Multimodal Transportation Planning Problem with Fuzzy Demand, LCMTPP-FD），以成本最小化构建数学模型。同时，结合现有的强制碳排放、碳税、碳交易和碳补偿等政策对LCMTPP-FD进行模型转换，研究不同低碳政策对物流成本和碳排放量的影响。主要根据模型的特征，设计一种分布麻雀搜索算法，对不同低碳政策下的模型进行求解，将迭代次数作为分布的自由度来提高麻雀算法的性能。将改进算法及多个模型应用于实际运输案例中，改进的麻雀算法能在较短时间内获得最优解，并且在强制碳排放下碳排放量最少为9 522.28，在碳交易和碳补偿政策下成本分别降低了11.41%、17.24%。改进的麻雀搜索算法具有较好的收敛性和搜索能力。强制碳排放能有效地降低碳排放量，碳交易和碳补偿能有效降低企业成本，适合于低碳运输的推广。

低碳多式联运；模糊需求；麻雀搜索算法；自适应分布

近年来全球气候变暖，低碳物流已成为运筹优化和物流领域的研究热点之一[1]。国家倡导调整运输结构，推动多式联运，构建低碳、经济和循环发展的运输体系。由此，低碳多式联运规划问题（Low-carbon Multimodal Transportation Planning Problem, LCMTPP）成为物流企业和学术界关注的重点。低碳多式联运指利用不同运输方式的优点将产品从运输起点，途经若干个中转节点，运往目的地的过程[2]。低碳多式联运利用不同运输方式的特点进行组合，实现能源充分利用的低碳运输。邓红星等[3]考虑了联运和中转过程中的成本和时间的影响，构建了以成本、碳排放量和运输时间等目标最小化的低碳多式联运规划模型，并采用NSGA-Ⅱ进行求解。程兴群等[4]分别构建了在强制碳排放、碳交易、碳税和碳中和等政策下考虑道路拥堵情况的多式联运模型，并基于保优策略和移民策略的遗传算法对该问题进行求解[4]。刘杰等[5]构建了总成本和碳排放最小化的多目标0-1规划模型，并采用改进的带精英策略的NSGA-Ⅱ对模型进行求解。

为了将低碳运输推广至各个运输企业中，国家制定了诸多政策来减少碳排放，实现绿色运输，如强制碳排放、碳税、碳交易和碳补偿等[6]。对于不同的低碳政策，企业会选择不同的运输方案[7]。现有文献中对在不同碳政策下带不确定性条件的低碳多式联运问题鲜有研究，交通拥堵[4]、天气和季节性需求[8]等都会增加运输的不确定性。王慧等[8]建立了需求模糊且采用集装箱进行运输的多式联运路径优化模型，并采用粒子群算法和蚁群算法求解该问题。为了使企业更好地响应低碳运输的号召和应对环境变化的不确定性，文中对带模糊需求的低碳多式联运规划问题（Low-carbon Multimodal Transportation Planning Problem with Fuzzy Demand, LCMTPP-FD）展开研究。该问题结合现有主流研究的强制碳排放、碳税、碳交易和碳补偿等低碳政策进行模型转换，制定不同低碳政策下的最佳运输方案。

麻雀搜索算法（Sparrow Search Algorithm, SSA）是由Xue等[9]于2020年首次提出的一种新颖的群集智能优化算法。该算法具有收敛速度快、易实现和参数少等优点，已成功应用于设施选址问题[10]、三维路径规划[11]、车间调度[12]和无人机航迹规划[13]等领域，但在多式联运方向鲜有应用。这里根据构建的模型，将分布模型[14]应用于SSA的搜索过程，设计了求解不同低碳政策下的LCMTPP-FD的自适应分布麻雀搜索算法（Sparrow Search Algorithm with AdaptiveDistribution, ATDSSA）。该算法将迭代次数作为分布的自由度进行变异搜索，该操作不仅避免了SSA易陷入局部最优，还弥补了该算法易过早收敛的缺陷。最后，在实际案例中，将原算法和改进算法在实际运输中不同低碳政策下的LCMTPP-FD进行求解，以验证模型和改进算法的可行性和有效性。

1 带模糊需求的低碳多式联运模型

1.1 模糊机会约束规划

图1 梯形模糊变量隶属度函数

Fig.1 Membership function of trapezoidal fuzzy variable

1.2 LCMTPP-FD模型

在某物流企业的由若干中转节点和多种运输方式组成的交通系统中，将需求量不确定的货物从运输起点，途经若干中转节点，运至目的地。同时，为了响应国家低碳运输的号召，企业需在不同碳政策下制定出相应的方案进行运输。为了便于构建模型，给出如下假设：货物在运输途中不可拆分；在2个中转节点间至多选择1种模式运输；每个中转节点至多进行1次模式转换；在运输过程中需考虑各路段和节点的容量限制；不考虑运输过程中天气、货损和设备故障等因素。

s. t.

1.3 不同碳政策下的LCMTPP-FD模型

现有的文献中对于多式联运的研究大多数在确定的环境中进行，但是交通运输系统中包含多种不确定因素，需在需求不确定环境下进行运输任务的安排。LCMTPP-FD考虑了运输需求的不确定性，并结合了当前多种低碳政策，符合实际运输。LCMTPP-FD模型分别与强制碳排放、碳税、碳交易和碳补偿等4种政策相结合，其对应政策下的转换模型依次记为模型Ⅰ、模型Ⅱ、模型Ⅲ、模型Ⅳ，分述如下。

1.3.1 强制碳排放政策下的模型——模型Ⅰ

在强制碳排放政策下，物流运输需严格按照政府的碳排放限制进行。由此，约束式（9）应满足该政策下的碳排放额度限制，构建模型Ⅰ，见式（14）。

约束式（14）表示运输碳排放量必须小于政府规定的碳排放量。同时，式（3）—（13）成立。

1.3.2 碳税政策下的模型——模型Ⅱ

1.3.3 碳交易政策下的模型——模型Ⅲ

碳交易指企业有一定量的碳排放额度，企业可根据实际运输情况从外购买或者出售碳排放额度，在运输完成的同时尽可能降低成本，模型Ⅲ的构建见式（16）。目标函数式（16）表示最小化总物流成本，它包括运输路径成本、模式中转成本和碳交易成本；式（17）表示碳交易量与实际排放量之间的关系；约束式（18）确保碳交易量不低于0，符合实际情况。同时，约束式（4）—（13）成立。

s. t.

trading+emission=T(17)

T≥0(18)

1.3.4 碳补偿政策下的模型——模型Ⅳ

根据碳补偿政策的规定，如果企业的碳排放量额度不能满足实际运输时，则可从外购买，以保证货物的成功运输。如果企业完成运输后有剩余的额度，则不可对外进行售卖。LCMTPP-FD在碳补偿政策下转换为模型Ⅳ，具体见式（19）—（20）。

s. t.

目标函数式（19）表示包含碳补偿成本的最小系统总成本，式（20）表示碳补偿量由实际碳排放量和碳补偿下配额量之间的关系决定。同时，约束式（4）—（13）成立。

2 求解LCMTPP-FD的ATDSSA

2.1 麻雀搜索算法

SSA通过模拟麻雀的觅食行为对解空间进行探索，根据适应度的优劣程度将适应度较优的麻雀作为发现者，负责整个种群食物的搜索，指引雀群的搜索方向。适应度较差的个体为加入者，相较于发现者，其搜索范围有限。如果麻雀察觉到危险，则会通过更新位置进行反扑行为。文献[9]表明，麻雀能够在发现者与加入者之间转换。在SSA中，发现者和加入者的搜索策略分别如式（21）—（22）所示。

2.2 t分布

分布又称学生分布[14]，其自由度参数决定了分布曲线的图像特点和形态，自由度参数越小，其曲线变化越平坦，峰值越低，其概率密度函数根据式（23）计算。

2.3 自适应t分布麻雀搜索算法

ATDSSA在原SSA的基础上将算法的迭代次数作为分布的自由度，对SSA个体的搜索策略进行扰动。在迭代前期，分布趋向于柯西分布变异，其全局搜索能力较强；在迭代后期，近似于高斯分布，具有良好的局部探索能力。分布的自由度随着迭代次数的变化而不断调整，以此平衡局部搜索和全局搜索，加快收敛速度。自适应分布更新见式（24）。

这里用分布对基本的SSA进行改进，首先采用参数调优方法，即在测试1个或1对参数对ATDSSA性能的影响时，其他参数保持不变，比较不同取值下调试参数对实验结果的影响，从而确定算法性能最佳的参数值。根据调试结果，种群规模=30，迭代次数=200，预警值T=0.6，发现者和加入者的比例1∶2=0.3∶0.7，发现危险程度D=0.2。根据设置的参数随机生成初始种群，并计算每只麻雀的适应度值，按升序排列。其次，根据适应度将种群个体分为发现者和加入者，分别对发现者和加入者进行位置更新。最后，当分布的密度函数值大于随机数时对种群进行分布变异操作。当满足最大迭代次数时结束循环，输出最优解。自适应分布麻雀搜索算法具体流程如图2所示。

图2 自适应t分布麻雀搜索算法流程

Fig.2 Process of sparrow search algorithm with adaptive t distribution

2.3.1 解的表示

采用两段式自然数编码方式，每个个体长度为−1。第1段为长度的路径编码，遍历过的节点用其对应的自然数表示，未遍历的节点用0代替。第2段由长度为−1的模式编码，1、2、3分别表示公路、铁路和水路。某10多式联运网络的可行解编码如图3所示，该可行解从运输起点出发，依次经过节点3、6、8，到达目的地，未经过节点2、4、5、7、9。

图3 某个体的表示方式

2.3.2 位置更新过程

原始SSA的更新方式适合于连续优化问题。由于这里涉及的各个节点为离散分布，因此对麻雀中的发现者（加入者）位置更新进行改进，具体步骤如下。

2）从父代从随机选择一个中转节点进行路径（运输模式）交叉。

3）调整交叉节点前后节点的连接关系，使路径可行。

2.3.3分布变异

1）计算出变异节点采用不同运输模式到各个后向节点的局部适应度。

2）选择最小局部适应度对应的后向节点及运输模式作为该变异点的后向局部路径。

3）将选择的后向节点作为新的变异节点，重复步骤1）—3），直至变异节点为终点时，结束循环。

3 算例分析

为了验证改进的算法求解上述模型的有效性，以南宁市到哈尔滨市的实际运输进行计算。实验环境：Windows 11系统下的Matlab 2016a，使用AMD Ryzen 7 5800U with Radeon Graphics、CPU 1.90 GHz、16.0 GB RAM的个人笔记本电脑。

3.1 算例简介

以国内某多式联运网络为例，该运输网络涉及南昌、贵阳、重庆、南昌、长沙、武汉、合肥、上海、徐州、济南、郑州、太原、北京、大连和哈尔滨等15个城市，且分别以、1、2…13和表示。通过轮船票网、火车票网和高德地图获得水路、铁路和公路等运输方式在两两城市间不同运输模式对应的距离，如表1所示。

图4 t分布变异

表1 不同运输方式下两城市间的距离

Tab.1 Distance between two cities under different modes of transportation

表2 不同运输方式的参数

Tab.2 Parameters of different transportation modes

3.2 结果对比分析

根据上述数据，采ATDSSA、SSA分别对强制碳排、碳税、碳交易和碳补偿政策下的LCMTPP-FD模型进行求解，如表3所示。ATDSSA和SSA在求解强制碳排放和碳税政策下的LCMTPP-FD均能找到相同的满意解。同时，不同碳政策下的碳排放量结果表明，强制碳排放政策有利于减排，且优于其他3种政策下的减排效果。由此，在环境污染较重时期推行强制碳排放政策有利于减轻环境污染。ATDSSA在求解碳交易和碳补偿时获得的结果中，总成本均为132 946.44，而SSA在碳交易和碳补偿下的总成本分别为148 115.19、155 861.72，其增加的成本主要源于节点3到节点8或节点9的模式转换成本，增加了转运成本，2个政策下成本改进百分比分别为11.41%、17.24%。在这2种低碳政策下，企业运输在满足碳排放约束情况下，为了降低运输成本，会偏向于选择ATDSSA获得的运输方案。由此，在推行低碳初期，碳交易和碳补偿可以在一定程度上降低运输成本，利于低碳运输的推广和实践。其中，多式联运路径中的H、R、S分别表示公路、铁路和水路运输，见表3。

ATDSSA和SSA在不同低碳政策下获得的成本和运输所产生的总碳排放量如图5—6所示，可以发现，在强制碳排放、碳交易和碳补偿等政策下运输成本明显低于在碳税政策下的成本；强制碳排放政策能有效降低碳排放量，利于低碳运输目标的实现。此外，由于这里构建的LCMTPP-FD是在成本最小的前提下降低碳排放量，因而ATDSSA在4种低碳政策下的成本均优于SSA。由图6可知，SSA在碳交易和碳补偿政策下的碳排放量低于ATDSSA，符合需求主体利益。

为了验证ATDSSA算法在求解LCMTPP-FD的有效性，这里将改进的ADTSSA在碳交易政策下的收敛情况与原始的SSA[9]、遗传算法（Genetic Algorithm，GA）[18]和粒子群优化算法（Particle Swarm optimization, PSO）[19]进行比较分析。如图7所示，PSO和SSA的收敛速度较慢，容易陷入局部最优；ATDSSA和GA均能获得较好解，但是ATDSSA的收敛速度和初始解的质量明显优于GA。将4种算法在同一设备上迭代200次，其中，GA、PSO、SSA和ATDSSA的运行时间分别为31.4、17.8、20.67、6.22 s。在1个理想时间内，ATDSSA每次迭代获得的最优解明显优于SSA和PSO，且在保证获得同样优质解的同时，ATDSSA所需的计算时间更少。由此可见，分布变异操作有效，改进算法不仅能节约时间，还可有效提高算法性能。

表3 实验结果

Tab.3 Experimental results

图5 不同低碳政策下的成本

图6 不同低碳政策下的碳排放量

图7 收敛曲线

4 结语

针对不同碳排放政策下带模糊需求的多式联运路径问题，以最小化运输成本、模式转换成本及碳排放成本之和为目标，构建了4种低碳政策下的LCMTPP-FD。构建的数学模型考虑了环境变化和实际情况约束，从而达到了实现经济、低碳运输的目的。根据不同的低碳政策模型获得的结果表明，强制碳排放政策可以有效降低碳排放量，适合在急需减排的情况下推行；碳交易和碳补偿政策对减少碳排放的力度较小，但可降低企业成本，适合于低碳运输初期的推广。LCMTPP-FD为后续的低碳运输和相关部门制定政策提供了理论依据。

通过对SSA算法进行改进，以迭代次数作为分布的自由度，以引导雀群进行变异搜索，平衡了SSA的全局搜索能力和局部搜索能力，弥补了SSA算法易陷入局部最优的缺陷，提高了算法的搜索能力。实验结果表明，在算法的搜索能力和收敛性等方面，ATDSSA与SSA、GA和PSO等智能优化算法相比，它在运行时间和获得的解质量上都具有较强的竞争力。该算法具有较好的性能，可应用于离散或连续的诸多组合优化问题研究中，如车辆路径问题、设施选址问题和选址路径问题等。后续应继续将该算法应用于易腐蚀物品和危险物品等特殊场景的运输。

[1] 李想, 闵德权, 张祺. 随机需求下半开放式冷链物流车辆路径优化[J]. 包装工程, 2022, 43(7): 160-169.

LI Xiang, MIN De-quan, ZHANG Qi. Routing Optimization of Semi-Open Cold-Chain Logistics Vehicle under Random Demand[J]. Packaging Engineering, 2022, 43(7): 160-169.

[2] ZHU C, ZHU X N. Multi-Objective Path-Decision Model of Multimodal Transport Considering Uncertain Conditions and Carbon Emission Policies[J]. Symmetry, 2022, 14(2): 221.

[3] 邓红星, 宋雅婧. 考虑碳排放的多式联运多目标路径规划[J]. 重庆理工大学学报(自然科学), 2022, 36(11): 219-225.

DENG Hong-xing, SONG Ya-jing. Multi-Objective Route Planning for Multimodal Transportation Considering Carbon Emissions[J]. Journal of Chongqing University of Technology (NaturalScience), 2022 36(11): 219-225.

[4] 程兴群, 金淳. 低碳政策下考虑道路拥堵的多式联运路径选择问题[J]. 运筹与管理, 2019, 28(4): 67-77.

CHENG Xing-qun, JIN Chun. Route Selection Problem in Multimodal Transportation with Traffic Congestion Considered under Low-Carbon Policies[J]. Operations Research and Management Science, 2019, 28(4): 67-77.

[5] 刘杰, 彭其渊, 殷勇. 低碳背景下的多式联运路径规划[J]. 交通运输系统工程与信息, 2018, 18(6): 243-249.

LIU Jie, PENG Qi-yuan, YIN Yong. Multimodal Transportation Route Planning under Low Carbon Emissions Background[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(6): 243-249.

[6] 杨珺, 卢巍. 低碳政策下多容量等级选址与配送问题研究[J]. 中国管理科学, 2014, 22(5): 51-60.

YANG Jun, LU Wei. A Location and Distribution Model with Hierarchical Capacities under Different Carbon Emission Policies[J]. Chinese Journal of Management Science, 2014, 22(5): 51-60.

[7] HOEN K M R, TAN T, FRANSOO J C, et al. Effect of Carbon Emission Regulations on Transport Mode Selection under Stochastic Demand[J]. Flexible Services and Manufacturing Journal, 2014, 26(1): 170-195.

[8] 王慧, 汪传旭. 模糊需求环境下集装箱多式联运箱型和运输方式的选择[J]. 公路交通科技, 2012, 29(4): 153-158.

WANG Hui, WANG Chuan-xu. Selection of Container Types and Transport Modes for Container Multi-Modal Transport with Fuzzy Demand[J]. Journal of Highway and Transportation Research and Development, 2012, 29(4): 153-158.

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

[10] 罗晴川. 基于改进麻雀搜索算法的电动汽车充电站选址定容在规划区的应用[D]. 大庆: 东北石油大学, 2022: 1-64.

LUO Qing-chuan. Application of Location and Capacity Determination of Electric Vehicle Charging Station Based on Improved Sparrow Search Algorithm in Planning Area[D]. Daqing: Northeast Petroleum University, 2022: 1-64.

[11] 白文杰, 贾新春, 吕腾. 改进麻雀搜索算法在三维路径规划中的应用[J]. 控制工程, 2022, 29(10): 1800-1809.

BAI Wen-jie, JIA Xin-chun, LYU Teng. Application of Improved Sparrow Search Algorithm in 3D Path Planning[J]. Control Engineering of China, 2022, 29(10): 1800-1809.

[12] LUAN F, LI R T, LIU S Q, et al. An Improved Sparrow Search Algorithm for Solving the Energy-Saving Flexible Job Shop Scheduling Problem[J]. Machines, 2022, 10(10): 847.

[13] 李楠, 薛建凯, 舒慧生. 基于自适应t分布变异麻雀搜索算法的无人机航迹规划[J]. 东华大学学报(自然科学版), 2022, 48(3): 69-74.

LI Nan, XUE Jian-kai, SHU Hui-sheng. A Sparrow Search Algorithm with Adaptive t Distribution Mutation-Based Path Planning of Unmanned Aerial Vehicles[J]. Journal of Donghua University (Natural Science), 2022, 48(3): 69-74.

[14] 周方俊, 王向军, 张民. 基于t分布变异的进化规划[J]. 电子学报, 2008, 36(4): 667-671.

ZHOU Fang-jun, WANG Xiang-jun, ZHANG Min. Evolutionary Programming Using Mutations Based on the t Probability Distribution[J]. Acta Electronica Sinica, 2008, 36(4): 667-671.

[15] LIU B D. Fuzzy Random Chance-Constrained Programming[J]. IEEE Transactions on Fuzzy Systems, 2001, 9(5): 713-720.

[16] SUN Y, ZHANG G J, HONG Z J, et al. How Uncertain Information on Service Capacity Influences the Intermodal Routing Decision: A Fuzzy Programming Perspective[J]. Information, 2018, 9(1): 24.

[17] 袁旭梅, 降亚迪, 张旭. 低碳政策下基于区间的模糊多式联运路径鲁棒优化研究[J]. 工业工程与管理, 2021, 26(4): 134-141.

YUAN Xu-mei, JIANG Ya-di, ZHANG Xu. Research on Robust Optimization of Interval-Based Fuzzy Multimodal Transport Paths under Low-Carbon Policies[J]. Industrial Engineering and Management, 2021, 26(4): 134-141.

[18] HOSAGE C M, GOODCHILD M F. Discrete Space Location-Allocation Solutions from Genetic Algorithms[J]. Annals of Operations Research, 1986, 6(2): 35-46.

[19] KANNAN S, SLOCHANAL S M R, SUBBARAJ P, et al. Application of Particle Swarm Optimization Technique and Its Variants to Generation Expansion Planning Problem[J]. Electric Power Systems Research, 2004, 70(3): 203-210.

Improved Sparrow Algorithm for Low-carbon Routing Optimization with Fuzzy Demand

HUANG Qin, ZHANG Hui-zhen*,WEI Xin,DENG Xin-le

(School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China)

For low-carbon multimodal transportation planning problem with fuzzy demand (LCMTPP-FD) under the low-carbon background, the work aims to construct a mathematical model to minimize the cost, and transform the LCMTPP-FD by combining existing policies, such as mandatory carbon emission, carbon tax, carbon trading and carbon offset, so as to study the impact of different low-carbon policies on logistics costs and carbon emissions. According to the characteristics of the model, a sparrow search algorithm withdistribution was designed to solve the model under different low-carbon policies, and the number of iterations was taken as the degree of freedom ofdistribution to improve the performance of the sparrow algorithm. The improved algorithm and several models were applied to a real transportation case. The improved sparrow algorithm could obtain the optimal solution in a short time, and the minimum carbon emission under the mandatory carbon emission was 9 522.28. The costs under the carbon trading and carbon offset policies were reduced by 11.41% and 17.24%, respectively. The experimental results show that the improved sparrow search algorithm has high convergence and search ability. Moreover, mandatory carbon emission can effectively reduce carbon emissions. Carbon trading and carbon offset can reduce the total costs, which are suitable for the promotion phase of low-carbon transportation.

low-carbon multimodal transportation; fuzzy demand; sparrow search algorithm; adaptivedistribution

TP301.6

A

1001-3563(2023)17-0220-09

10.19554/j.cnki.1001-3563.2023.17.027

2023-01-16

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

责任编辑：彭颋