基于离散海鸥算法求解循环取货车辆路径问题.pdf

May2023Journal of JilinUniversiti(InformationScienceEdition2023年5 月No.3Vol.41吉林大学（信息科学版）第3期第41卷文章编号：16 7 1-5 8 9 6（2 0 2 3)0 3-0 49 3-10基于离散海鸥算法求解循环取货车辆路径问题张强，韩利婷，姜慧清，朱必磊，魏永和?（1.东北石油大学计算机与信息技术学院，黑龙江大庆16 3318；2.国家电网冀北电力有限公司管理培训中心，北京10 0 0 0 0）摘要：针对如何降低循环取货车辆路径问题（VRP：Ve h i c l e Ro u t i n g Pr o b l e m）中的运输成本，提出一种离散海鸥算法。首先，在海鸥迁移过程中，采用insert、r e v e r s e 操作更新海鸥位置加快算法寻优速度；其次，在海鸥攻击过程中，采用swap、3-o p t 操作更新海鸥位置提升算法局部搜索能力；最后，结合模拟退火算法避免算法在运行过程中陷人局部最优，重新定义了在离散的车辆路径问题下的更新策略。以总成本最低为目标函数，构建相应的数学模型。实验结果表明，该算法具有高效解决循环取货车辆路径问题的能力，寻优效果及求解质量均高于标准海鸥优化算法、粒子群算法、模拟退火算法、灰狼优化算法、鲸鱼算法和飞蛾扑火算法。关键词：离散海鸥算法；循环取货；车辆路径问题；优化算法中图分类号：TP18文献标志码：ASolving Vehicle Routing Problem of Milk-Run Based onDiscrete Seagull AlgorithmZHANG Qiang,HAN Liting,JIANG Huiqing,ZHU Bilei,WEI Yonghe?(1.School of Computer and Information Technology,Northeast Petroleum University,Daqing 163318,China;2.Management Training Center,Chinses Grid Hebei Electric Power Company Limited,Beijing 100000,China)Abstract:To reduce the transportation cost in the VRP（Ve h i c l e Ro u t i n g Pr o b l e m)o f mi l k-r u n,a d i s c r e t eseagull algorithm is proposed.Firstly,in the process of seagull migration,insert and reverse operations are usedto update the seagull position to improve the algorithms search speed.Secondly,swap and 3-opt operations areused to update the seagull position to improve the algorithms local search capability.Finally,combined withsimulated annealing algorithm,the phenomenon of landing on local optimum is prevented during the operation ofthe algorithm,the update strategy is redefined under the discrete vehicle routing problem.With the lowest totalcost as the objective function,the corresponding mathematical model is constructed.Experiment results show thatthe algorithm is able to efficaciously deal with the vehicle routing problem of milk-run,the finding effect andsolution quality are better than the standard seagull optimization algorithm,particle swarm algorithm,simulatedannealing,gray wolf optimization,whale optimization algorithm,and moth-flame optimization.Key words:discrete seagull algorithm;milk-run;vehicle routing problem;optimization algorithm0引言车辆路径问题（VRP：Ve h i c l e Ro u t i n g Pr o b l e m）是一种属于NP-hard的经典组合优化问题，由Dantzig等1I在19 5 9 年提出。循环取货（Milk-run）用于当供应商单个产品的供应量在未达到指定运输车辆的额定容积时，附近还存在其他供应商的情形。规划车辆路径在提高Milk-run的运输效率中起重要作用，收稿日期：2 0 2 2-0 6-0 2基金项目：国家自然科学基金资助项目（6 17 0 2 0 9 3）；黑龙江省自然科学基金资助项目（F2018003）；黑龙江省博士后专项经费资助项目(LBH-Q20077)作者简介：张强（19 8 2 一），男，黑龙江大庆人，东北石油大学教授，博士，主要从事智能进化算法和神经网络研究，（Tel）8 6-13796989561(E-mail)dqpi_。1=494吉林大学报（信息科学版）第41卷因此，循环取货车辆路径优化属于VRP。对循环取货模式下的VRP，人们应用不同的群智能算法寻找近似最优解。陈荣等2 根据鲸鱼优化算法特点，引人了自适应权重并结合模拟退火算法提高了算法的寻优能力。何茵楠等3设计了遗传算法解决考虑碳排放的循环取货路径问题。陈婵娟等4根据多层级循环取货的模型特征，通过模拟蚁群觅食行为设计了蚁群算法。熊天宇5 针对如何进一步挖掘循环取货优化空间问题，设计了一种结合遗传算法和模拟退火特征的混合算法，为求解循环取货的延伸优化提供了一种新的思路。孟佳纯6 在禁忌搜索算法的基础上，设计了新邻域生成策略和解多样性策略求解模型。韩笑7 结合遗传算法和禁忌算法的优缺点求解三维装载约束下的循环取货VRP。李杨8 通过对遗传算法改进求解循环取货车辆的路径问题，结果表明经改进的遗传算法比改进前提高了对此类优化问题的求解效率。王双金9 设计了一种改进蚁群算法，通过对更新和转移规则的优化，提高了算法的搜索效率。陈畴铺等10 设计了一种将禁忌搜索算法融人传统蚁群算法求解循环取货的VRP。吴兵海使用聚类和区分任务等级提高初始种群整体质量的方法，提高了粒子群算法的求解效率。海鸥优化算法（SOA：Se a g u l l O p t i mi z a t i o n A l g o r i t h m）是Dhiman等12 受生物行为启发设计的一种群智能优化算法。该算法通过模拟自然界中海鸥在给定搜索空间寻找最佳地点的迁移和攻击行为，从而建立解决问题的寻优数学模型。由于SOA算法设计思路易于理解，性能优良且容易实现，目前已被应用于工业生产分类问题13。但在传统海鸥优化算法中，海鸥单一的飞行路线和有限的寻优能力导致算法容易出现陷人局部优值的情形。因此，笔者提出一种离散海鸥算法（DSOA：D i s c r e t e Se a g u l l O p t i m i z a t i o nAlgorithm）求解循环取货VRP，通过对当前最优位置进行insert、r e v e r s e 操作，重定义海鸥的迁移行为，寻找更多潜在的优秀解；应用swap、3-o p t 操作实现位置更新，重定义海鸥的攻击行为，扩大局部搜索范围；结合模拟退火算法，利用概率性跳出局部最优的特点，从而接近全局最优。实验结果表明，DSOA可以有效跳出局部最优解，最快达到全局最优解。1问题描述及建模1.1问题描述循环取货VRP可描述为：一组同种车型的车辆从配送中心出发到若干个供应商处取货，每个供应商的供应量是明确的，供应商之间的距离为车辆行驶距离，需要合理规划路径使目标函数最优。对循环取货VRP做如下假设：1）配送中心到各供应商的车辆路径确定后，路径中两点之间的往返距离相同；2）车辆必须以配送中心作为取货路径的起始点和完成取货任务后的返回点；3）每辆车可对多个供应商进行取货，但每个供应商只允许有一辆车向其取货；4）配送中心和供应商之间及供应商之间都是相互连通的道路；5）车辆单车容量相同，各车成本与取货量、行驶里程之间存在可量化规律；6）所有供应商的取货周期是相同的。1.2数学建模在循环取货VRP中，N=1,2，,n为所有供应商节点的集合，即iEn；K=1,2，,m 为配送中心的所有车辆集合；V=O,N)为配送中心和所有供应商集合；9:为供应商节点i的货物供应量；Q为每辆车的容许载重量；T.为车辆k从供应商i取出的货物量；d,为i与j两节点间的距离；x为车辆k由供应商i行驶到供应商j（x=1为从i行驶到j，（x=0 为不行驶）；y为供应商j由车辆k进行取货操作（y=1为从i行驶到j，y 为不行驶）；C,为单个取货车辆的固定费用；C为单位距离的行驶成本；C，为单位距离的运货成本。循环取货VRP具体模型如下。取货成本最小化的目标函数：nnmin M=C,Z N+mZZZd(C,+C,T.)。(1)=i=0i=0每辆车的货物量不允许超出其最大载重量：ZqQ,VkEK。(2)配送中心是每辆车取货路径的起点和终点：性立k=1卖性：张强，等：基于离散海鸥算法求解循环取货车辆路径问题495第3期n=1,VkEK。(3)00操作后再去供应商执行操作，确保取货路径的连车辆对供应商i执行完取货操作后再去供应商，VieV,keK。(4)二i=0=，Vje V,keK。(5)每个供应商只能被一辆车执行取货操作：Zy=1,mVieV,kEK。(6)供应商i的供应量不能超过车辆k的最大载重量：n0ZT.Q,VkEK。(7)决策变量约束条件2离散海鸥算法2.1标准海鸥优化算法x=0,11,Vi,jeV,keK。(8)海鸥优化算法14通过模拟海鸥在特定搜索区域内的迁徙和攻击两种行为获得最佳飞行位置。海鸥是一种分布全球的群居海鸟，为寻觅食物会随着季节的变换在不同地域之间迁徙。海鸥的捕食过程主要包括迁徙阶段和攻击阶段。在迁徙过程中，所有海鸥向食物最丰富的位置飞行时，个体间按照一定的飞行规律保持独立性，以避免发生位置相互碰撞。同时，为获取更多食物，海鸥通常会对其他猎物进行螺旋飞行方式的攻击。2.1.1迁徙海鸥迁徙是个体从一个飞行位置探索至另一个飞行位置的过程。为保持海鸥在迁徙过程的飞行独，引人了变量A更新海鸥位置，以避免海鸥个体间发生碰撞，A的计算如下：A=J.(M)(9)M.teration其中Miteratio为最大迭代次数，f。=2 为控制因子。与其他海鸥无位置冲突的新位置：数，f。=2 为控制因子。突的新位置：C.(t)=AP.(t),(10)其中P（t)为当前海鸥的飞行位置，t为当前迭代的次数。海鸥在保持与其他个体间距的同时，判断出自已与当前最优个体的相对方向，如下：M,(t)=B(Pbs(t)-P(t),(11)B=2Ard,(12)其中M（t)为当前海鸥需要移动的方向，Pbs（t)为所有海鸥中最优个体的位置，ra为一个均匀分布在(0,1)的随机数确定了与最优个体的相对方向后，计算出与最优个体的相对距离，向最佳位置靠近，如下：D,(t)=IC,(t),+M,(t)l,(13)其中D（t)为海鸥迁徙的最终位置。2.1.22攻击海鸥利用翅膀和重量在飞行过程中保持高度。当海鸥发现其他候鸟时，通过改变飞行角度与速度，以螺旋形状发起攻击，模拟三维坐标，y，z 描述该攻击行为的公式为x=rcos(0),(14)y=rsin(),(15)第41卷吉林大学报（信息科学版）496z=rO,(16)u(17)ueP(t)=D(t-1)xyz+Pb(t-1)(18)其中r为螺旋飞行的运动半径，为0,2 区间内的飞行攻击角度，u和为定义螺旋形状的常数，P（t）为海鸥当时的攻击位置。2.2海鸥优化算法离散化标准海鸥优化算法只适用于在连续的解空间中寻优。但车辆路径问题的解空间是离散的，需将标准海鸥优化算法进行离散化，使其适用于求解车辆路径问题2.2.1编码与解码由于配送中心和供应商节点均为离散点，因此采用连续的自然数对各节点编码。根据规则将海鸥位置与取货路径相互对应。配送中心表示为0，供应商节点为1,2，n。车辆首先从配送中心出发，然后对一条取货路径上的所有供应商进行取货操作，执行完取货操作后返回配送中心。例如，由1个配送中心对10 个供应商节点进行取货操作，根据每条路径上车辆的最大装载能力约束可得如10,5,2,10,7,0，1,4,6,0,8,3,9,0的解，表示10 个节点被划分在3条取货路径中，对应的取货路径分别为10,5,2,10,7，0(0,1,4,6,0)0,8,3,9,0 2.2.2初始解的构成车辆路径的初始化是通过对各供应商节点随机组合生成，然后根据一条路径上车辆的最大装载量约束规划每辆车的路径，具体操作如下：Step 1令取货路径起点为配送中心0，未加人取货路径的节点集合为V；Step 2按顺序读取集合中未访问节点以及对应供应商节点的供应量，判断加人该点后是否满足当前路径车辆的最大装载量，若满足，则执行Step3，否则在该路径中加人节点0，重复执行Step2；Step3将节点加入路径中，并把该点设置为已访问状态，继续执行Step2，直到集合中没有待访问的节点。2.2.3位置更新策略标准海鸥优化算法主要解决连续性问题，而在循环取货VRP模型中均是离散的节点编码，因此提出一种离散海鸥算法重新定义海鸥优化算法中的海鸥位置更新策略。1）迁徙行为重定义。海鸥在迁徙过程中忽视了对最优解的邻域进行搜索，然而其周围很大程度存在更多潜在的优秀解。为发掘更多潜在优秀解，利于种群的全局进化方向，设置供应商之间的距离差值不等于0 保证海鸥的飞行独立性，对得到的最优路径方案做insert、r e v e r s e 操作开发最优解的邻域，使海鸥向最优位置的邻域进行迁徙。其中，insert操作（见图1）是在最优路径方案中随机选取两个节点ij，将节点j插人到节点i的位置后，形成一条新的路径。reverse操作（见图2）是在最优路径方案中随机选取两个节点，反转节点i到节点j之间的所有节点，形成一条新的路径。更新前：1510112468793更新前：510112468793一更新后：1510112846793更新后：1510118642793图1insert操作图2reverse操作Fig.1Insert operationFig.2Reverse operation2）攻击行为重定义。海鸥在进攻猎物时，采用螺旋飞行方式进行攻击的方法较为单一。为扩大局部搜索范围，提高发现新路径的能力，在海鸥最终迁徒位置的基础上，对当前路径方案进行swap、3-o p t操作取代海鸥的攻击方式。swap操作（见图3)是在所选路径方案中随机选取两个节点ii，将节点i与节点位置进行交换，形成一条新的路径。3-opt操作（见图4）是从所选路径方案中随机选取3个节点i、设第3期张强，等：基于离散海鸥算法求解循环取货车辆路径问题497j、k，将3个节点的位置顺序依次交换，形成一条新的路径。ijik更新前：1510112468793更新前：1510112468793K更新后：1510118462793更新后：1510118463792图3Swap操作图 43-opt操作Fig.3Swap operationFig.43-opt operation2.3结合模拟退火算法在模拟退火阶段，为避免算法陷人局部最优，概率性选择一些比当前海鸥所处位置适应度低的点置采用较差解的概率为PexpT=0.99T,(19)newT其中fnew为海鸥新的适应度值，fnew-f为海鸥新旧适应度的差值，T为当前温度。2.4算法步骤Step 1夜初始化海鸥种群，初始温度T、当前的选代次数Citealion，截止到当前选代次数的海鸥最优位置Gbest等参数；Step2计算每个海鸥的适应度值，按照式(1)计算出种群中最优的海鸥位置赋值给Fbet，作为下次迭代过程中海鸥种群迁徒的最优位置，并将Fbest赋值给Gbest；Step 3对当前最优路径以轮盘赌的方式做insert、r e v e r s e 操作，使海鸥向最优路径靠近；Step 4海鸥在攻击过程中以轮盘赌的方式选择对当前路径进行swap、3-o p t 操作；Step 5重新计算海鸥的适应度值，如果优于当前Fbest，则取代Fbest，否则利用概率P判断是否取代Fbest;Step 6判断Fbest是否优于Gbest，如果优于Gbest，则取代Gbet;Step 7执行退火操作T=0.99T；Step 8判断Citeraion是否等于预设最高值，若等于最高值则输出Gest，终止算法；否则执行步骤Step3。3实验与分析3.1Solomon数据集测试分析为检验所提优化算法的正确性，使用Solomon数据集15 对标准海鸥优化算法（SOA）、粒子群算法（PSO：Pa r t i c l e Sw a r m O p t i mi z a t i o n）【16、模拟退火算法（SA：Si mu l a t e d A n n e a l i n g）【17、灰狼优化算法（CW O：G r e y W o l f O p t i mi z a t i o n）【18、鲸鱼算法（WOA：W h a l e O p t i mi z a t i o n A l g o r i t h m）【19、飞蛾扑火算法（M FO：M o t h-Fl a me O p t i mi z a t i o n）【2 0 和笔者提出的离散海鸥算法（DSOA）进行对比试验。实验中设置最大迭代次数为30 0，种群数量为30 0。表1为各算法在Solomon部分数据集上独立求解10 次取平均值的总成本对比结果。通过表1可看出，改进后的离散海鸥算法在求解循环取货车辆路径问题时，与标准海鸥优化算法相比结果更优。同时，离散海鸥算法总成本普遍优于PSO、SA、G W O、W O A 和MFO算法。为直观呈现在送代过程中成本的变动情况，下面以Solomon数据集中的C101、C2 0 1、R10 6、R2 0 6、RC10 2、RC2 0 1为例，给出每个算法在算例中总成本迭代过程中的变化，结果如下。其中C101算例的总成本最优解为17 9 0 6 1元，其他几种算法总成本均高于2 0 0 0 0 0 元，证明了离散海鸥算法对C101算例有更好的求解效果；C201算例的总成本最优解为2 13315 元，其他几种算法总成本均高于离散海鸥算法，证明离散海鸥算法对C201算例有更好的求解效果；R106算例的总成本498吉林大学学学报（信息科学版）第41卷最优解为17 7 0 5 7 元，其他几种算法总成本均高于2 0 0 0 0 0 元，证明离散海鸥算法对R106算例有更好的求解效果；R206算例的总成本最优解为18 19 5 8 元，其他几种算法总成本均高于离散海鸥算法，证明离散海鸥算法对R206算例有更好的求解效果；RC102算例的总成本最优解为2 2 46 36 元，其他几种算法总成本均高于30 0 0 0 0 元，证明离散海鸥算法对RC102算例有更好的求解效果；RC201算例的总成本最优解为2 36 9 39 元，其他几种算法总成本均高于离散海鸥算法，证明离散海鸥算法对于RC201算例有更好的求解效果。表1实验结果Tab.1The results of experiment总成本/元算例DSOASOAPSOSAGWOWOAMFOC101179 061243552369360509026495834445291430 198C102196810266 660408052565 789551 759531 806487 762C106194 601275 777408 494566 483560 795530 472477 915C201213315282.980424 497576 355562.909499 316494 362C202225 417279.541419 229583 268565 486532 646507 359C206209.279285582424 087580750564 968473759503 168R101171 420251 432343 195482 453466 249460 294419 476R102180 102255 461342.593474.537465 377404522406 956R106177 057251 743340483477 772471 156440936399 571R201179 269253 073343 093487 312470 419454 657414 690R202179 710254719348 236480.518463 904434350412 831R206181 958247 553342975485.589463531421 817423 176RC101235372313438463537638841635717551911536 651RC102224636322.554465010643016631 229546228546159RC106230773322935473 413641 531622.456607 625554111RC201236939333 263466 662650479620707539 207544705RC202230.971326839466 610640 256629 016550 429528781RC206217 130319 632464 273642.093629 647568021546 173图5 图10 反映了取货成本随着算法迭代次数变化而变动的情况，可看出DSOA有较高求解质量，取得的总成本在迭代次数增加过程中始终低于其他算法的总成本。DSOA与标准SOA相比，在前期送代过程中总成本随迭代次数的增加大幅减少，表明在迁徙过程中对海鸥最优个体位置的邻域进行开发的方式，优于SOA基于最优个体位置确定最终迁徙位置的方式，加快了算法向全局最优解趋近的速度。DSOA的总成本随迭代次数的增加呈现出放缓的趋势，DSOA局部搜索能力发挥了重要作用，其中swap、3-opt操作扩展搜索区域，提高了算法的探索能力，结合模拟退火机制降低了陷入局部优值的概率。实验结果验证了在求解循环取货VRP模型时，DSOA具有较强的全局和局部搜索能力，最终实现效果优于SOA、PSO、SA、G W O、W O A 和MFO6种算法。DSOA-SOA-PSOSA6GWO-WOA-MFO5432051015202530选代次数10图5C101实验结果迭代图Fig.5Iteration chart of result of C101DSOA-SOA-PSOSAGWOWOA.MFO65432051015202530送代次数10图6C201实验结果送代图Fig.6Iteration chart of result of C201第3 期张强，等：基于离散海鸥算法求解循环取货车辆路径问题499DSOA-SOA-PSOSAGWO-WOA-.-MFO52/01x+43211051015202530送代次数10图7R106实验结果迭代图Fig.7Iteration chart of result R106DSOA-SOA-PSOSAGWO-WOA-.MFO6543051015202530送代次数10图9RC102实验结果迭代图Fig.9Iteration chart of result RC1023.2实例验证DSOA-.-SOA-PSOSAGWO-WOA.MFO5432051015202530送代次数10图8R206实验结果迭代图Fig.8Iteration chart of result R206-DSOA-SOA-PSOSA7GWO-WOA-.-MFO6543051015202530选代次数x10图10RC201实验结果迭代图Fig.10Iteration chart of result RC201为进一步验证笔者算法的有效性，以某采油厂捞油工作为研究对象，建立以总成本（固定成本、行驶成本、运油成本）最小为目标函数的数学模型，通过对DSOA和SOA、PSO、SA、G W O、W O A 和MFO算法优化结果的对比，分析DSOA对该采油厂捞油工作规划车辆路径方案的性能。在该采油厂捞油工作的VRP中，N=1,2,N)为所有油井节点的集合，即ieN；K=1,2,m 为采油厂的车辆集合；V=O,N)为采油厂和所有油井集合；s;为油井节点i的储油量；S为车辆的最大容量；T，为车辆k从油井i运出的原油量；d,为节点i到节点j之间的距离；x为车辆k由油井i行驶到油井i（x=1为从i行驶到j，为不行驶)；为油井j由车辆进行运油操作(y=1为从i行驶到j，=0 为不行驶)；C为单个捞油车辆的固定费用；C，为单位距离的行驶成本；C。为单位距离的运油成本。具体模型如下捞油成本最小化的目标函数：nmmin M=CZN+ZZZdgxg(C,+C.T.)。(20)=01=0每辆车装载的原油量不允许超过其最大载重量：s./S,VkEK。(21)i=1油厂车辆从采油厂出发完成捞油任务后必须返回采油厂：nXoi=1,VkEK。=0=0Zx0=Zx=1,VkEK。(22)VVi=0=0乍后再去油井i执行操作：车辆对油井i执行完捞油操作后再去油井i执行操作：Z=,VieV,kEK。(23)1=0之前对油井执行操作：车辆对油井j执行捞油操作之前对油井i执行操作：nK=片，Vj:V,keK一Z=片,VjeV,kEK。(24)每个油井的油可以被多辆车运输：2/1,mVieV,keK。(25)(27)500第41卷吉林大学学报（信息科学版）在油井i点运出的原油量不能超过车辆k的最大载重量：决策变量约束条件：02T.S.VkEK。(26)=1xE(1,2),Vi,jeV,keK。VijeV,kEK。图11是DSOA和其他6 种算法随迭代次数变动的总成本变化情况，图12 为该采油厂捞油工作路线图。由图11可看出，DSOA对该采油厂捞油工作规划的车辆路径方案效果最好。DSOA在迭代初期总成本高于SOA，是因为该算例相比于Solomon数据集规模较小，开发最优路径邻域的优势不明显。但本算法采用swap、3-o p t 操作增强算法的局部搜索能力，提高发现更多新路径的能力；通过与模拟退火算法结合扩大搜索空间，从而避免了算法陷人局部最优，使算法在迭代后期始终优于SOA。实际应用结果表明，DSOA对该采油厂捞油工作规划车辆路径方案时，可得到较优的结果。用DSOA、SO A、W O A 与文献2 的改进鲸鱼算法（WOA1）对Solomon部分算例以及采油厂实例进行求解，结果如表2、图13 图15 所示。2.5-DSOA-.-SOA-PSO.SA21420配送中心GWO-WOA.MFO供应商2.421415/2.3?214102.2214052.12140005101520253045374.5384539454045414542选代次数10Xx103图11捞油工作总成本送代图图12取油最优路径路线图Fig.11Iteration chart of oil recovery costFig.12Optimal route map for oil extractionDSOA-SOADSOA-SOA235DSOA-SOAWOAi-WOAWOAi-WOAWOAiWOA662305522542204321532210105101520 25 30051015202530051015202530送代次数10送代次数10选代次数10图13R206实验结果迭代图图14RC101实验结果选代图图15捞油工作总成本选代图Fig.13Iteration chart of resultFig.14Iteration chart of resultFig.15Iteration chart of oilR206RC101recovery cost表2实验结果Tab.2The results of experiment总成本/元算例DSOASOAWOA1WOAC101207010267 307241.753481 523C206212.666313201215535466 171R101183072277 480183756469 569R206191 625254 123192.272412310RC101251055329692279 127560542RC206216 497302.738248 206590 475某采油厂2062071021 132.07520 839 20722 121 016张强，等：基于离散海鸥算法求解循环取货车辆路径问题第3期501由表2、图13 图15 可见，虽然改进鲸鱼算法（WOA1）的总成本均低于WOA和SOA，寻优效果均强于WOA和SOA，但DSOA寻优能力强于改进鲸鱼算法，由此表明DSOA在规划不同规模的循环取货VRP时均表现出了良好的鲁棒性。4结语笔者对求解循环取货VRP问题，首先构建了以最小总成本为目标的数学模型，随后将标准海鸥优化算法进行离散化，并结合模拟退火算法提出了离散海鸥算法。通过离散海鸥算法求解数据集Solomon和某采油厂捞油工作的实例，并与SOA、PSO、SA、G W O、W O A 和MFO进行对比实验，结果表明笔者提出的离散海鸥算法在求解循环取货VRP问题时优于其他算法，因此更具有参考价值。目前，在车辆路径问题中仍然存在很多不确定因素，下一步将继续研究海鸥优化算法在其他车辆路径问题上的应用。参考文献：1 JDANTZIG G B,RAMSER J H.The Truck Dispatching Problem J.Management Science,1959,6(1):80-91.【2 陈荣，王雯阳，下东东基于鲸鱼算法的循环取货路径优化研究J.物流科技，2 0 2 1，44（10）：2 8-32.CHEN R,WANG W Y,BIAN D D.Research on Cyclic Pickup Path Optimization Based on Whale AlgorithmJJ.LogisticsTechnology,2021,44(10):28-32.【3何茵楠，王帮俊，魏宇茜，等碳减排下的汽车零部件循环取货路径优化研究J重庆工商大学学报（自然科学版),2 0 2 1,38(3)：7 1-7 8.HE Y N,WANG B J,WEI Y X,et al.Study on the Optimization of Circular Pickup Path of Auto Parts under CarbonEmission Reduction J.Journal of Chongqing University of Technology and Industry(Natural Science Edition),2021,38(3):71-78.【4陈婵娟，寇创创，刘利军，等.一种汽车零件人厂物流的多层级循环取货模型研究J.机械设计与制造，2 0 2 1(12）：293-296.CHEN C J,KOU C C,LIU L J,et al.A Multi-Level Circular Pickup Model for Inbound Logistics of Automotive Parts J.Machine Design and Manufacture,2021(12):293-296.【5 熊天宇循环取货延伸模式及其车辆路径问题研究【D重庆：重庆大学机械工程学院，2 0 19.XIONG T Y.Research on Circular Pickup Extension Model and Its Vehicle Path Problem D.Chongqing:College ofMechanical Engineering,Chongqing University,2019.【6 孟佳纯.基于禁忌搜索的电动物流车循环取货路径规划【D大连：大连理工大学交通学院，2 0 19.MENG J C.Circular Pickup Path Planning for Electric Logistics Vehicles Based on Forbidden Search D.Dalian:School ofTransportation,Dalian University of Technology,2019.【7 韩笑。生鲜电商物流取货及配送优化方法研究【D.北京：华北电力大学经济与管理学院，2 0 18.HAN X.Research on Fresh E-Commerce Logistics Pickup and Distribution Optimization Method D.Beijing:School ofEconomics and Management,North China University of Electric Power,2018.【8 李杨汽车零部件人厂物流循环取货车辆路径问题研究【D.沈阳：沈阳工业大学机械工程学院，2 0 17.LI Y.Research on Vehicle Path Problem of Auto Parts Inbound Logistics Cycle Pickup D.Shenyang:College of MechanicalEngineering,Shenyang University of Technology,2017.【9 王双金。汽车零部件入厂物流循环取货路径优化的模型及算法J.物流工程与管理，2 0 16，38（3）：12 2-12 4.WANG S J.Optimization Model and Algorithm of Circular Pick-up Path of Incoming Logistics of Auto Parts J.LogisticsEngineering and Management,2016,38(3):122-124.10陈畴铺，王基于改进的蚁群算法的汽车零部件物流配送路径优化J生产力研究，2 0 17（11）：12 4-12 7,149.CHEN C Y,WANG J.Auto Parts Logistics Distribution Path Optimization Based on Improved Ant Colony Algorithm J.Productivity Research,2017(11):124-127,149.11吴兵海工厂线边接货模式下的车辆运输调度优化研究D上海：上海交通大学船舶海洋与建筑工程学院，2 0 16.WU B H.Research on Vehicle Transportation Scheduling Optimization under