考虑同时取送和时间窗的车辆路径及求解算法.pdf

近年来，随着“一带一路”和“自贸区”战略的实施与完善，数字经济和电商模式的发展，极大推动了我国物流行业的迅速发展，物流服务从基本的收寄需求，逐步发展到无人配送、上门揽件、准时到达等多元化需求1。当前，国家大力发展绿色经济，提出碳达峰、碳中和，提倡产品生命周期结束后可回收再利用，注重环境保护、考虑同时取送和时间窗的车辆路径及求解算法刘建胜，蔡祥，黄纪绘，熊君星南昌大学 先进制造学院，南昌 330047摘要：针对带时间窗的同时取送货车辆路径问题（vehicle routing problem with simultaneous pickup-deliveryand time windows，VRPSPDTW），构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型，提出自适应头脑风暴算法（adaptive brain storm optimization，ABSO）进行求解。全局搜索阶段，采用多项惩罚方式扩大搜索区域，并使用聚类及三种路径搜索策略进行全局搜索；局部搜索阶段，将六种破坏-修复算子作为备选集合，进而设计自适应动态选择邻域搜索机制，增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试，实验结果表明针对小规模标准算例，所提算法全部取得了当前已知最优解；对于大规模标准算例，通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比，所提算法实验计算结果有7.52%12.03%的提升；对于实际案例，所提算法在收敛速度和寻优能力方面均展示出优越性，充分验证了所提算法对解决VRPSPDTW问题的有效性。关键词：车辆路径问题；同时取送货；时间窗；头脑风暴算法；自适应大邻域搜索文献标志码：A中图分类号：TP181doi：10.3778/j.issn.1002-8331.2205-0405Solution Algorithm for Vehicle Routing Problem Considering Simultaneous Pickup-Deliveryand Time WindowsLIU Jiansheng,CAI Xiang,HUANG Jihui,XIONG JunxingCollege of Advanced Manufacturing,Nanchang University,Nanchang 330047,ChinaAbstract：This paper proposes an adaptive brain storm optimization（ABSO）for the vehicle routing problem with simul-taneous pickup-delivery and time windows（VRPSPDTW）,a path optimization mathematical model is constructed to min-imize the total expenditure of vehicle use cost and vehicle travel distance cost.In the global search stage,expand thesearch area with multiple penalties,as well as use clustering and three path search strategies for global search.In the localsearch stage,ues six kinds of damage-repair operators as candidate sets,and then design an adaptive dynamic selectionneighborhood search mechanism to enhance local search efficiency.Based on the standard test data set and practical cases,the experimental results show the ABSO algorithm can obtain all the currently known optimal solution for the small-scalestandard test example.For the large-scale standard test example,compared with the genetic algorithm,parallel-simulatedannealing algorithm,and discrete cuckoo search,the experimental calculation results of the algorithm in this paper havean improvement of 7.52%-12.03%.For practical cases,the proposed algorithm shows its superiority in terms of conver-gence speed and optimization ability.The experimental calculation results verify the effectiveness of the proposed ABSOalgorithm to solve the VRPSPDTW.Key words：vehicle routing problem;simultaneous pickup-delivery;time windows;brain storm optimization;adaptivelarge neighborhood search基金项目：国家自然科学基金（51565036）。作者简介：刘建胜（1978），通信作者，男，教授，博士生导师，研究方向为数字化与智能制造、智能优化算法、制造技术与装备，E-mail：；蔡祥（1997），男，硕士研究生，研究方向为智能优化算法、车辆路径优化；黄纪绘（1993），男，博士，讲师，研究方向为微细成形、机械设计与智能制造；熊君星（1981），男，副教授，研究方向为数字化与智能制造、制造技术与装备。收稿日期：2022-05-20修回日期：2022-07-12文章编号：1002-8331（2023）16-0295-10Computer Engineering and Applications计算机工程与应用295Computer Engineering and Applications计算机工程与应用2023，59（16）回收利用等绿色物流的发展2。因此带时间窗的同时取送货车辆路径问题（vehicle routing problem with simul-taneous pickup-delivery and time windows，VRPSPDTW）受到越来越多学者的关注和研究。VRPSPDTW是经典VRP（vehicle routing problem）问题的重要扩展。自1959年提出VRP问题以来，不断取得研究成果和实际应用3。VRPSPDTW是在VRP的基础上扩展了同时取送货（simultaneous pickup-delivery）以及时间窗约束（time windows），要求车辆在规定的时间内同时完成客户的取送货需求。VRPSPDTW最早由Angelelli等4于2002年提出，并设计了一种分支-定界法精确求解该问题。但是随着客户规模的增加，VRPSPDTW的求解变得愈发困难，已被证明为NP-hard问题，精确求解在理论上可行，在现实中由于计算时间及难度变得不切实际，众多学者开始寻找不同的启发式算法来解决该问题。文献5提出一种基于最小插入成本的协同遗传算法解决该问题，并设计了65组针对VRPSPDTW问题的国际标准测试算例。文献6提出包含 RCRS（residualcapacity and radial surcharge）的并行模拟退火算法对该问题进行求解。文献7应用离散布谷鸟算法对该问题进行深入研究，并根据其飞行机制进行有效的全局搜索。文献8和文献9分别采用粒子群优化算法和混合遗传算法对VRPSPDTW进行求解。文献10利用化学反应优化算法对多目标VRPSPDTW进行了研究。文献11和文献12分别采用禁忌搜索算法和分支定界法对需求可拆分的 VRPSPD进行求解。文献13利用多目标变邻域搜索算法对二级配送网络的VRPSPDTW进行了研究。文献14应用禁忌搜索算法对带时间窗的同时取送家庭医疗调度问题进行求解。文献15对多配送中心VRPSPDTW进行研究，并采用3D聚类算法进行求解。通过以上文献梳理可知，尽管国内外关于VRPSPDTW有一定的相关研究，但是该领域仍然有两点不足：（1）在算法的性能方面，大部分文献均采用算法原有搜索机制，未考虑通过多个算法相结合来增强算法的寻优能力；（2）在算法的局部搜索方面，大部分算法仍采用单一的交叉变换，导致生成的解之间多样性有限，难以实现优质解空间的深入搜索。因此，对于考虑多个算法相结合来增强寻优能力，获取高质量解的有效算法需要进一步深入研究。头脑风暴算法（brain storm optimization，BSO）16是一种新兴的受人类行为启发的群智优化算法，具有参数设置简单、易实现和寻优能力强的特点，已经在车间调度、工程通信、图像处理等17-19方面取得了应用，但目前使用BSO算法求解VRP问题较为有限。文献20采用改进的BSO算法对VRPTW进行求解，通过设计新的编码解码方法增加全局搜索范围，实验结果表明求解效果优良。文献21为解决VRPTW问题，提出一种混合的BSO算法，首先通过蚁群系统寻找全局搜索方向，然后通过邻域搜索（local search）进行局部搜索，极大增加了算法的寻优性能。针对VRPSPDTW问题，目前尚未有BSO求解的报道，故十分有必要展开相关研究。综上所述，本文以VRPSPDTW问题为研究对象，建立以车辆使用成本、车辆行驶距离成本总成本最少为优化目标的数学模型，提出一种自适应头脑风暴算法（adaptive brain storm optimization，ABSO）进行求解。本文通过算法相结合来合理引导搜索方向，将 ALNS（adaptive large neighborhood search）算法融入 BSO局部搜索策略中，进行两阶段搜索。全局搜索阶段，执行BSO算法；局部搜索阶段执行ALNS算法。其中BSO采用多项惩罚方式扩大搜索区域，并使用聚类及三种路径搜索策略尽快搜寻到优质解空间；ALNS通过自适应动态选择邻域搜索机制和多种破坏-修复算子集合，对优质解空间进行有效的邻域搜索，进一步加大算法在短时间内寻优的几率。最后，通过对不同规模测试算例和算法比较，验证了ABSO算法的有效性。本文对VRP-SPDTW的研究，不仅进一步扩展了VRP问题的理论研究，也为制定合理科学的车辆调度计划提供决策参考，具有重要的理论和工程实践应用价值。1问题分析1.1问题描述VRPSPDTW 问题示例如图 1所示，存在给定的一个配送中心、一组地理位置不同的客户和一组运输车辆，要求在满足约束的前提下求得一组合理的配送路线，并最小化车辆使用数以及车辆行驶距离。与传统的VRP问题相比，VRPSPDTW问题不仅按照客户规定的时间窗进行服务，进一步提高客户的满意9：009：508：008：3011：0011：409：109：4010：2011：00取货量送货量配送车辆时间窗客户配送中心图1VRPSPDTW问题示例Fig.1VRPSPDTW problem example2962023，59（16）程度，增加企业的核心竞争力，而且还考虑客户的取货需求，更加符合当今物流行业绿色、环保、高效的发展趋势，进一步降低了车辆的空载率，节约企业成本。本文研究的VRPSPDTW问题描述为：（1）若干运输车辆从配送中心出发为客户取送货并最终返回配送中心，每位客户仅可由一辆车服务一次，车辆在配送过程中任何时刻都不能超载。（2）车辆到达客户处为客户送货的同时从客户处取走回收的货物，每位顾客均有取货和送货需求。（3）配送中心和客户的位置、时间窗、客户取送货需求量、服务时间需求，以及配送中心和各个客户之间的距离、车辆行驶速度均已知。（4）允许车辆在客户最早开始服务时间之前到达，不允许车辆在客户最晚开始服务时间之后到达；车辆要在配送中心最早开始时间之后为客户服务，在配送中心最晚截止时间之前返回配送中心。本文将物流网络抽象为一连通图：假设各节点之间相互联通；两点之间的距离对称，即dij=dji；任意3个节点之间距离满足dik+dkjdij；忽略道路、天气及交通堵塞等其他因素。1.2模型建立根据以上问题描述和假设，为方便VRPSPDTW数学模型的建立，本文使用的参数和变量符号说明如下：（1）集合V：顶点集，V=0,1,n；V：客户集，V=V/0=1,2,n；K：车辆集，K=1,2,m。（2）参数：目标权重分派参数，0,1；f：单车使用成本；c：车辆单位距离行驶成本；dij：客户i到客户j的欧氏距离，i,jV；Di：客户i的送货需求量，iV；Pi：客户i的取货需求量，iV；W：车辆最大载重量；M：足够大的正数；ai：节点i左时间窗，其中a0为配送中心，iV；bi：节点i右时间窗，其中b0为配送中心，iV；S0k：车辆k离开配送中心开始配送的时间；R0k：车辆k结束配送返回配送中心的时间；tij：客户点i到客户点j的行驶时间，i,jV；si：客户点i的服务时间，iV。（3）变量wik：车辆k对客户i的开始服务时间，iV，kK；Ljk：车辆服务完客户j后的载重量，jV。L0jk：车辆k离开配送中心的载重量，kK；Li0k：车辆k返回配送中心的载重量，kK。xijk：车辆k是否由节点i前往节点j，如果是xijk=1，否则为0。基于上述参数和决策变量，建立VRPSPDTW车辆路径优化数学模型，优化目标为总配送成本最小。为实现这一目标，本文通过对物流公司实地调研和参考文献22，采用线性加权法设定转化系数，具体优化模型如下：min Z=fkKiVxi0k+()1-ckKiVjVxijkdij（1）s.t.kKiVxijk=1，jV（2）iVxi0km，kK（3）iVxijk=hVxjhk，jV，kK（4）jVx0jk=1，kK（5）jVx0jk=iVxi0k，kK（6）iVxi0k=1，kK（7）L0jk=iVjVDjxijk，jV，kK（8）0L0jkW，jV，kK（9）Li0k=iVjVPixijk，iV，kK（10）0Li0kW，iV，kK（11）L0jk+Pj-Dj-M()1-x0jkLj，jV，kK（12）Lik+Pj-Dj-M1-kKxijkLj，()i,j V，ij（13）LjkW+M1-iVxijk，jV，kK（14）wik+si+tij-wjk 1-kKxijkM，iV，jV（15）aiwikbi，iV，kK（16）a0S0k，kK（17）R0kb0，kK（18）xijk0,1，()i,j V，kK（19）式（1）以车辆使用成本、车辆行驶成本的总配送成本最小为目标；式（2）确保每个客户只由一辆车服务一次；式（3）为限制车辆使用数不超过车辆总数；式（4）为流量守恒式，即到达和离开每个客户的车辆数相同；式（5）（7）确保每辆车从配送中心出发，最终返回配送中心；式（8）、（9）为车辆从配送中心出发时的装载量及其约束；式（10）、（11）为车辆返回配送中心的装载量及其约束；式（12）、（13）分别为车辆服务完第一个客户后载重量公式和车辆配送途中的载重量公式；式（14）为车刘建胜，等：考虑同时取送和时间窗的车辆路径及求解算法297Computer Engineering and Applications计算机工程与应用2023，59（16）辆载重量约束；式（15）、（16）为客户的时间窗约束；式（17）、（18）为配送中心时间窗约束；式（19）为决策变量约束。本文模型与既有模型相比所用参数和变量较少，并具有较强的通用性，通过参数与约束条件的变换则可以变为不同的车辆路径问题优化模型。例如去掉约束（15）、（16）、（17）、（18）后变成了同时取送货车辆路径问题；去掉约束（10）并且令Pi=0则变为带时间窗的车辆路径问题（VRP with time windows）。2算法设计头脑风暴算法作为一种新型的智能优化算法，相比较于其他元启发式搜索算法而言具有较高的求解精度和效率，但该算法同其他常见的智能优化算法类似，在迭代后期存在收敛速度慢、容易陷入局部最优等问题。基于此，本文将 BSO 算法与 ALNS 算法相结合，提出ABSO算法。考虑到该问题模型中存在大量约束，在全局搜索阶段，通过BSO算法对不满足车辆载重约束或时间窗约束的配送方案进行惩罚，降低其适应度值，扩大种群搜索范围，快速找到优质解区域；在局部搜索阶段，通过ALNS算法对不满足载重量及时间窗要求的配送方案进行剔除，保证配送方案的可行性，继而对优质解区域进行深度搜索，增强算法寻优性能。2.1编码解码与种群初始化本文算法采用整数编码的方式，确保每个客户只能由一辆车服务一次，并通过编码的长度来限制车辆使用数目不超过车辆总数，以满足模型约束。假设所研究的配送网络中共有N个客户，配送中心最多可使用m辆车，则个体的解可以表示为1()N+m-1随机排列。如图2所示，该个体表示服务6个客户，最多使用3辆车的一个解。配送中心表示0；客户集1,2,3,4,5,6；车辆集7,8。具体解码为：首先找到车辆节点7、8的位置；提取节点2、5、7；在个体中删除提取节点，在所提取节点中删除车辆节点并在首尾加上配送中心，生成子路径0250；重复操作生成子路径0310；最后提取剩余节点生成子路径0460。初始解的质量对算法的求解速度和求解质量影响较大。例如，周蓉等23通过大部分初始种群个体随机生成和部分优良个体采用改进节约算法的方式生成初始种群。Xia等24采用随机方式生成初始解，并通过设计邻域搜索机制来降低算法对初始解的依赖性。本文选择随机方式生成初始解，并通过对违反载重量、时间窗的惩罚机制接受不可行解，增大搜索范围以及提高算法跳出局部最优的能力，使算法在迭代寻优中找到更优质的解。2.2计算适应度值解码出的配送方案并不一定都是可行的，首先通过式（21）、（22）分别计算当前配送方案违反载重量约束及违反时间窗约束之和，然后通过式（20）对违反载重量和时间窗约束的配送方案进行惩罚，保证算法能找到更优质的解。因此，在评价一个配送方案时需要将成本函数分为三部分进行计算：车辆总的行驶距离成本、配送车辆使用成本和惩罚成本。配送方案总成本的计算公式如下：G()x=fK()x+cC()x+L()x+T()x（20）L()x=kKmax()L0jk-W,0+jVmaxLj-W-M1-iVxijk,0（21）T()x=iVmax()li-bi,0（22）式中，G()x为当前配送方案的总成本，即目标函数；K()x为车辆使用数目；C()x为车辆总行驶距离；L()x为各条配送路径违反的载重量约束之和；T()x为所有客户违反的时间窗约束之和；为违反载重量约束的惩罚因子；为违反时间窗约束的惩罚因子；li为货车到达客户i的时间。2.3聚类及替换（1）计算每个个体的适应度函数值，采用k-means聚类方法把n个个体分成m个类，并将各类个体进行排序，其中最佳个体作为聚类中心。（2）随机产生一个0,1之间的数r1，若r1小于给定的参数p0（替换概率），则进入（3），否则进入生成新个体操作。（3）在m个聚类中随机选择一个聚类的聚类中心，生成一新个体，然后用新个体替换选中的聚类中心。2.4更新种群更新种群的主要方法是生成新的个体，而生成新个体的方式有两种：（1）选出某一个聚类中的个体进行2-insert和2-opt操作；（2）选出某两个聚类中心的个体进行顺序交叉操作。（1）2-insert：如图3（a）所示，节点5、7插入到节点8后。（2）2-opt：如图3（b）所示，节点7保持不变，节点3、1、8逆序。25731846257318460460车辆节点客户节点车辆1车辆2车辆302500310图2个体解码示意图Fig.2Individual decoding diagram2982023，59（16）（3）顺序交叉（sequential cross）：顺序交叉如图3（c）所示，首先找到个体xi第一部分（选中的两个客户节点之间的部分），然后将xj放到xi第一部分之后，最后依次删除重复个体，xj同理。生成新个体的部分参数为：r2、r3、r4，0,1之间的随机数；p1，选择一个聚类的概率；p2，选择一个聚类中聚类中心的概率；p3，选择两个聚类中聚类中心的概率；Ci()i=1,2,m，第i个聚类的聚类中心；x1，从聚类中选出的第一个个体；x2，从聚类中选出的第二个个体；obj()xi()i=1,2,n，个体xi的目标函数值。假设种群（population）数目为n，聚类数目为m()m2，更新种群的伪代码如下所示。输入：当前种群及算法参数。输出：更新后的新种群。初始化种群参数fori=1:nif随机数选择1个聚类中心概率随机选择1个聚类if随机数选择1个聚类中聚类中心概率选择该聚类中心x1=Cix2=Cielsex1=从该聚类中随机选择1个体x2=x1xnew1=2-insert x1xnew2=2-opt x2else随机选择2个聚类if随机数选择2个聚类中心概率选择聚类中心x1=Cix2=Cjelsex1=从聚类1中随机选择1个体x2=从聚类2中随机选择1个体xnew1xnew2=sequential crossx1x2endxnew=minobjxnew1,xnew2ifobj()xnewobj()population()ipopulation()i=xnewend2.5局部搜索策略本文的目标函数成本主要与行驶距离、时间窗、车辆指派数相关，而车辆指派数又与取送货需求量相关，因此本文设计的大邻域搜索算子主要与上述四点相关，破坏操作结束后输出被移除的节点集合R，以及被破坏的个体Sdestory；修复操作结束后输出修复后的个体Srepair。本文共设计了6种“破坏”与“修复”算子。2.5.1破坏算子（1）路径随机破坏：随机选择种群中一个个体xi，然后再随机选择一个节点放入被移除的节点集合R，同时更新xi，重复操作，直到r个节点被移除。（2）相似度破坏：该算子分别从行驶距离、时间窗、送取货需求量，以及是否同一路径四方面考虑两个节点的相似度。两节点间的相似度由R()i,j表示，其表达式如下：R()i,j=11Cij+2Dij+3Tij+4（23）Cij=cijmax()cij（24）Dij=()|Di-Dj+|Pi-Pjmax()()|Di-Dj+|Pi-Pj（25）Tij=()|ai-aj+|bi-bjmax()()|ai-aj+|bi-bj（26）其中，R()i,j越大表示节点i、j相似度越大，而被移除的所有节点要尽可能保证相似度低。1、2、3、4分别为行驶距离、时间窗、送取货需求量以及是否同一路径权重系数；若节点i和节点j在同一路径上4为0，否则为1。（3）目标最差破坏：该算子主要目标是移除对目标成本影响最大的节点，包括考虑距离、时间窗两方面，从而直观地改善总的运输成本。2.5.2修复算子（1）贪婪修复算子：在满足所有约束的基础上从被移除的节点集合R中随机选择一个节点，找到该节点2573146231885746257314623781346825731463864271588642573173186425个体xi个体xj个体xnew1个体xnew2（a）2-insert示意图（b）2-opt示意图（c）sequential cross示意图图3生成新个体示意图Fig.3Diagram of generating new individual刘建胜，等：考虑同时取送和时间窗的车辆路径及求解算法299Computer Engineering and Applications计算机工程与应用2023，59（16）可插入的位置，计算该点插入某一位置后的插入成本（将R中的某个节点插入Sdestory的某个位置后，此时修复后的总成本减去修复前的总成本即为“插入成本”），选择插入成本增加最少的位置进行插入，重复操作直到R为空集。（2）遗憾值修复：在满足约束的基础上，R中节点i在Sdestory若有l个可插入位置，则对应产生l个插入成本。将l个插入成本从小到大排序，排在第二位的插入成本减去排在第一位的插入成本即为节点i插回Sdestory的遗憾值。（3）最短距离修复：在满足约束的基础上从R中随机选择一个节点k，计算k各个插入位置的节约值，如将节点k插入节点i、j之间，则节约值d()i,k,j=dik+dkj-dij。选择节约值最小的位置进行插入并更新R，重复操作直到R为空集。2.6自适应机制为增强算法的自适应调整能力，本文为每种破坏和修复算子分配了权重。基于轮盘赌的思想，在迭代过程中，根据每种算子被分配的权重在所有算子权重中所占的比例i，首先自适应选择其中一种破坏算子对当前个体x进行破坏，然后同样以自适应的方式选择修复算子进行修复操作。每种算子权重占比i计算公式为：i=ij=1j（27）可以看出i越大，选中的几率越大。在计算开始时，每种算子都有相同的权重和分值，并且初始分值0，根据算子在迭代计算中的表现给予不同的分值，得分越高表明该组算子性能越好，具体得分规则为：（1）Srepair被接受作为下一次邻域搜索的出发解且是全局最优解，得10分；（2）Srepair被接受作为下一次邻域搜索的出发解，得5分；（3）Srepair未被接受作为下一次邻域搜索的出发解，得0分。为避免算子收敛速度过快容易陷入局部最优，在算子权重更新计算中添加了算子权重更新系数，增加算子搜索过程的多样性和跳出局部最优的能力。算子权重更新公式如下：i=i,fi=0()si/fi+()1-i,fi0（28）其中，i为算子权重，si为累计得分，fi为累计使用次数。2.7迭代终止条件ABSO有两种迭代的终止条件，只要满足条件之一便使算法终止迭代：（1）当种群中的最优解连续不变的迭代次数达到预设的阈值maxremain；（2）当实际总迭代次数达到预设的最大迭代次数maxgen。终止迭代后，选取全局最优解作为最终解输出。2.8ABSO算法流程ABSO算法引入ALNS算法局部搜索机制，进行有效的邻域搜索，并通过惩罚机制在一定情况下接受不可行解，加深种群搜索，通过聚类及替换操作增加种群的多样性，避免算法陷入局部最优，以更大几率找到优质解，算法具体流程如下所示。输入：算法参数、客户信息、车辆信息、迭代次数等。输出：VRPSPDTW问题车辆配送方案。1.提取数据信息，初始化算法参数2.种群初始化：生成初始种群3.初始化全局最优，保留每次迭代全局最优4.开始迭代循环whilegenMaxgendo计算个体适应度值obj()i=objfunction()population()i聚类操作：将n个个体分为m个聚类每个聚类中最优个体作为聚类中心替换操作if随机数替换概率随机生成个体替换随机选中聚类中心end更新种群2-insert、2-opt、sequential cross选择种群中适应度值排名前50%个体局部搜索操作Whilei选中的局部搜索个体数 do依据自适应评分机制随机选择破坏算子选择修复算子对个体修复ifobj()new obj()population()ipopulation1()i=new更新评分机制end局部搜索后种群与原种群前50%合并计算合并后个体适应度值ifobj（当前最优解）bj（全局最优解）bestpopulation=当前个体endend输出全局最优解：bestpopulation3算例实验与分析为验证模型和算法的有效性，本文进行3组实验。实验1验证本文算法在小规模标准算例方面的有效性，分别对10、25、50个客户数量的小规模标准算例进行实验。实验2验证本文算法对大规模标准算例的性能，针3002023，59（16）对6组不同类型大规模标准算例，每组随机抽选3个，共选取18个算例进行实验，每个算例包含100个客户。实验3引入具体问题案例对算法性能进行测试，验证算法实际应用价值。本文算法由 Matlab-2018a 编程实现，在 CPU 为AMD Ryzen 5 2500U，2.00 GHz，内存为 8.00 GB 的Windows10操作系统的计算机上运行。算法参数设置如下：最大迭代次数Maxgen=400；种群规模Popsize=50100，种群的规模与客户点规模n有关，n越小种群规模越小。考虑测试算例车辆数目，选取聚类数目为8个；p_replace调整算法局部与全局的关系，将该参数设置为0.3；参数p_one与算法搜索邻域大小成反比，将该参数设置为0.4；p_one_center、p_two_center主要考虑局部最优与随机个体的关系，为防止陷入局部最优并且加大算法搜索效率，将上述参数分别设置为0.3、0.2。算法参数根据控制变量法实验得出，每次调整只变动某一个参数进行反复实验，确定了合适的参数值，具体参数设置如表1所示。3.1小规模标准算例分析实验1 采用文献8的9个小规模标准算例进行实验，9个小规模标准算例包括3个10个客户规模，3个25个客户规模，3个50个客户规模。将实验结果与文献8（GA）算法、文献9（p-SA）算法和文献10（DCS）算法对比，所对比文献的主要目标函数均为最小化车辆使用数（number vehicle，NV），次要目标函数为最小化行驶距离（travel distance，TD），本文也采用相同的目标函数。实验对比结果如表2所示，表3给出了算例Rcdp2504的车辆配送路线。不难看出，本文设计的算法可以全部求得小规模标准算例已知的最优解，验证了本文算法对VRPSPDTW小规模标准算例求解的有效性。3.2大规模标准算例分析实验2 为验证本文算法对大规模算例的有效性，选用文献8设计的大规模标准算例进行实验。为保证实验的准确性，针对6组实验数据，随机选择每组的3个算例进行实验，每个算例包含100个客户。在同时满足载重量和时间窗约束的条件下进行实验，将实验结果与文献8（GA）算法、文献9（p-SA）算法和文献10（DCS）算法进行对比。同样的本文主要目标函数为最小化车辆使用数（NV），次要目标函数为最小化行驶距离（TD）。实验对比结果如表4所示。可以看出，在求解质量方面，本文提出的算法在随机选择的18个标准算例中有13个算例更新了最优解，4个算例取得与当前最优解相同的结果。其中算例Rcdp202与GA算法相比提升了算法参数聚类数目cluster_num用随机解替换一个聚类中心的概率p_replace选择一个聚类的概率p_one选择一个聚类中聚类中心的概率p_one_center选择两个聚类中聚类中心的概率p_two_center取值80.30.40.30.2表1算法参数设置Table 1Algorithm parameter settings算例/客户数Rcdp1001/10Rcdp1004/10Rcdp1007/10Rcdp2501/25Rcdp2504/25Rcdp2507/25Rcdp5001/50Rcdp5004/50Rcdp5007/50GANV322545967TD349.98216.69310.81551.05473.46540.87994.18725.59809.72p-SANV322545967TD349.98216.69310.81552.21473.46540.87994.70725.90810.04DCSNV322545967TD349.98216.69310.81551.05473.46540.87994.18725.59809.72ABSONV322545967TD349.98216.69310.81551.05473.46540.87994.18725.59809.72表2小规模客户算例实验结果对比Table 2Comparison of experimental results of small-scalecustomer examples车辆配送路线配送路线1：01822241215645230配送路线2：013252016320配送路线3：02110171119140配送路线4：078190车辆总行驶距离473.46表3Rcdp2504配送路线Table 3Rcdp2504 delivery route算例Rdp101Rdp103Rdp108Rdp201Rdp204Rdp211Cdp101Cdp104Cdp106Cdp201Cdp205Cdp207Rcdp101Rcdp104Rcdp106Rcdp201Rcdp202Rcdp204GANV191410433111011333151113443TD1 653.531 216.16967.491 280.44775.23839.611 001.97878.93878.29591.56588.88588.291 652.901 188.491 422.871 587.921 211.12822.02p-SANV191410433111011333151013443TD1 660.981 226.77962.481 286.55848.01812.44992.88944.73878.29591.56588.88588.291 659.591 268.431 418.161 513.721 273.26897.14DCSNV191410433111011333151013443TD1 658.651 228.48964.381 281.63776.00819.88998.29931.26878.29591.56588.88588.291 654.321 269.311 419.261 520.561 242.92822.02ABSONV191410433111011333151013443TD1 651.101 216.05959.731 264.02757.14801.23986.22890.82878.29591.56588.88588.291 651.361 183.231 393.611 493.141 120.03801.90表4大规模客户算例实验结果对比Table 4Comparison of experimental results of large-scalecustomer examples刘建胜，等：考虑同时取送和时间窗的车辆路径及求解算法301Computer Engineering and Applications计算机工程与应用2023，59（16）7.52%，与 p-SA、DCS 算法相比分别提升了 12.03%、9.89%。在求解速度方面，如图4所示，本文算法可以在较少的迭代次数内快速收敛，当算法陷入局部最优解时，可快速跳出局部最优，具有较好的寻优性能。为更直观地展示本文实验结果，图5给出了算例Rcdp106的配送路线图。综合随机选取的 18 个标准算例实验数据，本文算法更新或达到最优的算例占测试算例的94.45%，其中72.22%的算例更新了最优解，充分说明了本文提出的模型和算法在解决大规模标准算例方面的有效性。3.3应用案例分析实验3 为验证本文算法在实际物流案例中的有效性，本文获取了某物流快递公司在一定区域内的数据信息，包括1个中转物流中心，20个门店的送货量、取货量以及服务时间要求。为进一步提高算法的可靠性及实际案例的应用价值，本文在考虑道路通畅信息的情况下导出配送中心与各个门店之间距离矩阵。此外，通过实地调研的方式获取各个门店的取送货量需求以及服务时间需求，保证数据的准确性。为计算方便，对中转配送中心和各个门店进行编号，