车辆路径问题(vehicle routing problem，VRP)属于组合优化和整数规划中的NP难问题[1]，也是运筹学中重要研究问题之一[2-3]．有容量约束的车辆路径问题(capacitated vehicle routing problem，CVRP)是VRP问题中的一种基本问题，CVRP问题被认为是组合优化领域的一个基本问题，特别是在运输和配送物流中[4-5]，同时也是NP难问题，其约束主要在于满足车辆容量和每辆车可以行驶的最大距离[6]．文献[7]将混合蛙跳算法[8]、极值动力学优化算法[9]两种启发式算法进行融合，当对CVRP问题进行求解时可以提升算法的多样性和随机性．文献[10]提出先路由后分组思想，将问题一分为二，通过灰狼优化算法进行离散化编码，再引入3元素优化操作的劣势点启发邻域搜索策略，改进算法的拓展性．文献[11-12]在局部搜索方面皆引入2元素优化操作进行局部搜索，并利用编解码策略将搜索空间离散化，实现搜索空间与CVRP解空间之间的转换．向子权等[13]也利用离散化处理方法求解连续优化问题．斑点鬣狗优化(spotted hyena optimizer，SHO)算法[14]是一种群智能优化算法，文献[15]用29个著名的基准测试函数进行测试，证实该算法可以解决计算复杂度和收敛性低等问题．文献[16]针对特征选择的方法，设计一种与模拟退火算法相结合的混合模型来解决此问题，在分类精度、空间搜索和特征属性方面都取得很好的效果．CVRP问题研究的现实意义不断增强，高效的求解算法有助于更合理地规划出行路线．现有文献还未有利用SHO算法求解车辆路径问题，基于CVRP问题的特点，本研究提出一种融合多策略改进的斑点鬣狗优化(improved spotted hyena optimizer，ISHO)算法用于求解小规模CVRP问题．首先，通过改进的K-means聚类和贪心选择相结合的初始化方法提高初始解质量；然后，在全局搜索上融合鲸鱼优化算法[17]的螺旋探索模型，并对其进行离散化，同时定义出一种变异算子、两种交叉算子和局部逆操作方法，避免算法早熟陷入局部最优；最后，将本文算法在国际基准算例上进行求解实验，并与另外4种智能优化算法进行对比实验，实验结果表明本文算法用于小规模CVRP问题是有效的．1 CVRP问题已知具体数量的客户点，各客户点有不同的需求量，考虑一个配送中心，安排若干相同型号车辆从配送中心出发，向各客户点提供配送服务．此问题用数学语言描述如下：令G=(N,A)，N=N0⋃Nc，其中：A={(i,j)|i,j∈N}为客户点i到客户点j之间的距离；N0为配送中心；Nc为客户结点的数目．车辆行驶路径和服务客户点的数学表达式为xijv=1    (车辆v由客户点i行驶至客户点 j),0    (其他情况);yiv=1    (客户点i由车辆v服务),0    (其他情况).定义：V为车辆集合；U为车辆载重量(配送车辆型号完全相同)；Qi为客户点i的需求量；Dij为配送车辆从客户点i到客户点j之间的距离；nc为Nc的真子集，nc为集合nc中所含元素的个数，即客户结点数．则CVRP模型为：min  f=∑i∈N ∑j∈N ∑v∈VDijxijv; (1)s.t.∑i∈NQiyiv≤U    (v∈V); (2)∑v∈Vyiv=1    (i∈Nc); (3)∑i∈Ncxijv=yjv    (j∈Nc,v∈V); (4)∑j∈Ncxijv=yiv    (i∈Nc,v∈V); (5)∑i∈Ncx0iv=1    (v∈V); (6)∑i∈Nxi0v=1    (v∈V); (7)∑i,j∈Ncxijv≤nc-1    (∀nc∈Nc,v∈V)．(8)式(1)为目标函数，考虑配送路径最短；式(2)为容量约束限制；式(3)为每个客户仅被一辆车服务；式(4)和(5)表示同一配送路线上的客户仅有一辆车服务且只能访问一次；式(6)和(7)表示配送车辆从配送中心0出发，最后返回配送中心；约束式(8)用于消除子回路．2 标准斑点鬣狗优化算法斑点鬣狗狩猎行为包括包围猎物、追捕猎物、攻击猎物和搜索机制4个过程．2.1　包围猎物对斑点鬣狗社会层次结构分析，定义出当前最优解，其他斑点鬣狗的位置根据最优解进行更新．建立如下数学模型，Dh=BPpt-Pt;P(t+1)=Pp(t)-EDh,式中：Dh为个体与猎物之间的距离；t为当前迭代；P为个体位置；Pp为猎物的位置；B和E分别为摇摆因子和收敛因子，计算公式为B=2r1，E=2hr2-h，h=5-t(5/Z)，其中，h从5线性递减到0，r1和r2为[0，1]内随机数；Z为最大迭代次数．2.2　追捕猎物假设无论哪个个体最优，最佳搜索个体都清楚猎物的位置．其他搜索个体组成一个可信任的集群，向最好搜索个体靠拢，并保存到当前最好方案，更新它们的位置．建立如下数学模型，Dh=BPh-Pk；Pk=Ph-EDh；Ch=Pk+Pk+1+⋯+Pk+S，式中：Ph为斑点鬣狗的第一个最佳位置；Pk为其他斑点鬣狗位置；S为斑点鬣狗数量；Ch为S个最优解集群，S=counto(Ph,Ph+1,Ph+2,…,(Ph+M))，其中，M为[0.5，1]的随机数，o为可行解数量．2.3　攻击猎物斑点鬣狗在猎食的最后阶段开始攻击猎物，攻击猎物的数学模型定义为P(t+1)=Ch/S．2.4　搜索机制通过E的值控制个体位置，当E1时，进行全局搜索．改变B的值是SHO算法的另一种搜索方式，假设B1优先于B1，有助于搜索和避免局部最优，为搜索提供随机值．3 离散型斑点鬣狗优化算法求解CVRP为了将SHO算法应用到CVRP问题中，须对其进行离散化处理．首先，将斑点鬣狗种群和个体作为可行解，对N个节点进行编码和初始化；然后，将鲸鱼算法螺旋攻击模型与SHO算法相结合，同时对该模型进行离散化用于更新；最后，引入交叉算法，实现算法的全局搜索过程．在算法后期迭代过程中，通过对每次迭代过程保存的优秀个体与本次迭代过程中随机选取的个体进行比对，选取最优解，跳出局部最优，完成操作．3.1　CVRP问题解的构造本研究中0表示配送中心，V为车辆数，1~Nc依次对客户点编号，将客户编码和配送中心共同排列的编码方式作为CVRP问题的解．假设V=3，Nc=10，路径编码如图1所示．10.13245/j.hust.240210.F001图1路径编码当构造CVRP的初始解时，首先确定配送中心0的位置和每条长度为Nd+2的车辆配送路径序列，其中Nd为单辆车需要配送的客户数量；根据车辆载重约束U向CVRP序列中逐一添加客户点，直至该路径满足最大容量限制，停止添加．CVRP问题种群节点矩阵为P=P1,1P1,2…P1,Nc+VP2,1P2,2…P2,Nc+V⋮⋮Pi,j⋮PG,1PG,2…PG,Nc+V，式中：Pi,j为第i个斑点鬣狗个体访问第j个节点；G为种群数．3.2　路径初始化将K-means算法中聚类思想和贪心选择思想相结合，有效避免陷入局部最优，保证初始解的个体多样性，提高初始种群质量．算法改进思想如下：距配送中心最近的Np个结点中随机选取V个结点作为聚类中心，根据贪心选择策略，计算出每个客户点到V个聚类中心的距离，将各客户点分配给最近的聚类中心，重复此操作直至客户点全部分配完全，生成V个配送路径；输出路径，算法结束．各个节点和聚类中心点之间的距离d*为d*=abs(xi-nj)    (i∈Nc,j∈V);Np=Nc/2，式中：xi为第i个客户点；nj为第j个聚类中心；为向下取整．3.3　螺旋探索及离散化模拟斑点鬣狗以对数螺旋的方式向猎物移动，改进后的更新斑点鬣狗位置方法为P(t+1)=Ph(t)+Dhdcos m;d=Rekb,式中：随机数m∈[0,2π]；d为每圈的螺旋半径；螺旋形状分别由常数R和b定义(R=b=1)．利用下式求得k值，得到节点Pi,k，      k=Dhe2πcos m+j(2/π)tan(t/Z)+Dhe2πcos m+j(2/π)tan(t/Z)Nc+V-1+1; (9)Pi,j(t+1)=swap(Pi,j(t), Pi,k(t))，(10)选取一个取值范围为[1,Nc+V-1]的随机数j，利用式(10)对二者进行交换，选择最优个体更新当前个体．3.4　变异算子通过模仿差分变异算子设计一种变异操作，拓宽算法搜索区域．首先，随机从全局最优个体(无重复)中选取两个最优个体，同时进行遍历，返回同列不同值的列号将其存储至sel_pos数组中；然后，从数组sel_pos中随机选取两个以上的列号，找到当前个体cur_ind对应位置元素，对其进行随机互换．变异操作详细过程如图2所示．10.13245/j.hust.240210.F002图2变异操作3.5　交叉算子引入两种不同的交叉算子．第一种：在[1,Nc+V-1]中选取一个随机数i，在当前个体cur_ind和全局最优个体best_ind中找到列号为i的对应值，将二者进行比较，若不等，则将i添加至sel_pos数组(生成过程见图3)中，并保存节点值best_ind(i)，在cur_ind中寻找与best_ind(i)相等的节点值，返回列号j并将其存储至sel_pos数组中，同时在best_ind中找出列号为j的节点值，将其与cur_ind(i)进行比较，若相等，则结束循环返回sel_pos数组，将best_ind和cur_ind两个个体中sel_pos位置元素进行交叉互换生成两个新的个体，计算二者种群适应度，取最优；反之，重复此操作．交叉互换过程如图4所示．10.13245/j.hust.240210.F003图3sel_pos数组生成过程10.13245/j.hust.240210.F004图4交叉互换过程第二种：在[1,Nc+V-1]中选取随机数i及一个长度为Nc+V-1的数组，将该数组截取成长度为i的数组并进行升序排列，产生sel_pos1数组；将数组sel_pos1中元素作为列号对当前个体cur_ind进行截取，找出全局最优个体best_ind中与之对应元素，返回列号至数组sel_pos2中进行存储；完成交叉互换，将cur_ind (sel_pos1)节点值与best_ind(sel_pos2)节点值交叉互换．交叉互换操作见图5，图中：cur_ind中灰色部分根据sel_pos1数组中的元素进行选取；best_ind中灰色部分根据sel_pos2选取．二者进行交叉互换，选择最优个体更新种群．10.13245/j.hust.240210.F005图5交叉互换操作3.6　逆转操作随机选择两个位置，对这两个位置间元素进行逆序排列．逆转操作如图6所示．10.13245/j.hust.240210.F006图6逆转操作3.7　ISHO求解CVRP问题算法步骤步骤1 初始化h，B，E等参数，设置种群数G=100、最大迭代次数Z=100、车辆载重量U及客户数目．步骤2 改进的初始化算法生成种群，计算个体适应度，将最优个体单独存储．步骤3 更新E．当E1时，通过式(9)、(10)和第一种交叉算法对个体进行更新；当E1时，通过第二种交叉和变异算子进行更新；进行逆转操作，对比适应度值，选最优个体更新．步骤4 对最优解进行解码，输出车辆路径．4 实验与分析4.1　测试用例与环境选取文献[18]提出的A，B，E和P基准实例．实验环境为MATLAB R2017b，64位Windows 10操作系统，处理器类型为Intel Core(TM) m5-6Y54．4.2　算法性能分析实验1：将标准斑点鬣狗优化(SHO)算法、种群初始化改进后的斑点鬣狗优化(GSHO)算法与ISHO算法进行对比实验．相同的实验环境下进行20次独立实验，设置G=100，Z=100．测试结果如表1所示，表中数值表示完成配送所需最短距离，其中：BKS为已知最优解；运算结果达到最优值的，加粗且加星号表示；运算结果在3以内趋近于最优值的，加粗表示．ISHO算法达到已知最优解占比高达67%，求解精度均明显优于其他两种算法．三种算法求解A-n37-k5算例的迭代过程见图7．10.13245/j.hust.240210.T001表1SHO及其改进算法实验结果对比InstanceBKSSHOGSHOISHOA-n32-k5784833789784*A-n33-k5661731664661*A-n33-k6742806769743A-n34-k5778868809785A-n37-k5669771737669*A-n39-k5822942905833A-n39-k6831936876833A-n46-k79141014991925B-n31-k5672708690672*B-n34-k5788795791788*B-n38-k6805990825807E-n22-k4375411376375*E-n23-k3569637570569*E-n30-k3534556558534*E-n33-k4835930842837P-n16-k8450448/450450*P-n19-k2212229212212*P-n20-k2216240218216*P-n21-k2211238225211*P-n22-k2216218224216*P-n22-k8603621612603*P-n23-k8529566538/529*P-n40-k5458502489459P-n45-k5510574558510*注：/代表违反约束跑出的数据．10.13245/j.hust.240210.F007图7三种算法求解A-n37-k5的迭代过程实验2：从客户点分布、客户需求量及最少车辆数等出发，筛选出标准测试集A，P，B，E中24个具有代表性(客户均匀、随机、密集分布等)的数据集测试，验证算法适用性．选用SA+NN算法[19]、Adaptive Sweep+VTPSO算法[20]、CVRP-FA算法[21]、Firefly算法[22]与本文算法进行对比实验，表2~4为测试结果．10.13245/j.hust.240210.T002表2A数据集实验结果A数据集BKSSA+NNAdaptiveSweep+TPSOCVRP-FAFireflyISHOA-n32-k57841012882796831784*A-n33-k5661847698661*711661*A-n33-k6742919751742*783743A-n34-k5778933785778*827785A-n37-k5669876754669*669*669*A-n39-k58221 147877822*898833A-n39-k68311 065972831*868833A-n46-k79141 071975914*1 04992510.13245/j.hust.240210.T003表3P数据集实验结果P数据集BKSSA+NNAdaptiveSweep+TPSOCVRP-FAFireflyISHOP-n16-k8450546549450*450*450*P-n19-k2212253246212*212*212*P-n20-k2216267249216*216*216*P-n21-k2211288211*211*211*211*P-n22-k2216274216*216*216*216*P-n22-k8603667633603*603*603*P-n23-k8529743634529*529*529*P-n40-k5458563483458*508459P-n45-k5510662524519595510*10.13245/j.hust.240210.T004表4B，E类型数据集实验结果B，E数据集BKSSA+NNAdaptiveSweep+TPSOCVRP-FAFireflyISHOB-n31-k5672713—672*672*672*B-n34-k5788995—788*788*788*B-n38-k6805888—806834807E-n22-k4375375*—375*375*375*E-n23-k3569569*—569*569*569*E-n30-k3534534*—534*534*534*E-n33-k4835835*—835*835*835*注：“—”代表数据缺失．图8为ISHO算法在4种不同客户规模问题上求解的最优路径图，图中(X，Y)表示在此坐标系中的相对位置．ISHO算法获得了16个最佳解决方案，求解精度上整体效果表现不错．10.13245/j.hust.240210.F008图8最优路径图由图8可知：ISHO算法在求解不同规模CVRP时，每条路径上的客户分配合理，未出现集中于某一条路径上的情况，表现了良好的寻优能力．ISHO算法在A-n32-k5，B-n31-k5，E-n30-k3和P-n45-k5数据集上的平均收敛次数分别为22，7，20和23次，均在迭代20次左右开始收敛，在算例B-n31-k5上迭代7次左右就快速收敛．本文算法确保了鲁棒性，提高了找到最佳解决方案的适应性与精确性．5 结语针对CVRP问题的特点，本研究提出了一种融合多策略的斑点鬣狗优化算法．首先，定义出种群初始化算法；然后，通过离散化处理提升全局搜索能力，同时加入不同算子及局部逆操作防止算法陷入局部最优．在24个基准算例上进行仿真实验，将计算结果与其他优化算法进行对比，结果表明，ISHO算法求解小规模CVRP问题时具有较好的求解精度和收敛速度．在未来的工作中，可以将其拓展至大规模车辆路径问题，使算法具有更强的适用性．