![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于聚类的LNS算法求解异构VRP问题.pdf
《基于聚类的LNS算法求解异构VRP问题.pdf》由会员分享,可在线阅读,更多相关《基于聚类的LNS算法求解异构VRP问题.pdf(7页珍藏版)》请在咨信网上搜索。
1、该文研究了异构车辆路径问题(heterogeneous fleet vehicle routing problem,HVRP),在经典 HVRP 模型的基础上,设计了结合均值漂移聚类算法及大邻域搜索算法的混合求解算法(mean shift-large neighborhood search,MS-LNS)。该算法通过均值漂移聚类算法对客户集进行分类,达到减少计算量、加快算法收敛速度的效果。算法使用单链设计,结合 swap 邻域变换及 insert 邻域变换产生新式邻域变换方法,使邻域变换方法可以随机处理路径间与路径内变换。新增 redistribution邻域变换,在变换后对新解检测是否存在不
2、满足车辆载重利用率的子路径,并将其删除,达到提高车辆利用率的目的。3组仿真实验使用 9 组算例:实验一比较了异构与同构车辆的配送效果,验证结果表明异构车辆配送方案成本较低;实验二验证了聚类算法在不同规模客户数据中的有效性;实验三使用 MD-LNS 算法计算了 4 组算例,并与 4 种算法的结果进行比较,验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间。仿真实验结果验证了模型的合理性及算法的有效性。关键词:异构车辆路径问题;均值漂移聚类算法;大邻域搜索算法;单链设计;redistribution 邻域变换中图分类号:TP301.6摇 摇 摇 摇摇摇 文献标识码:A摇 摇 摇 摇
3、摇 摇 文章编号:1673-629X(2023)09-0098-07doi:10.3969/j.issn.1673-629X.2023.09.015LNS Algorithm Based on Clustering for Solving HVRPZHAO Xiong,LI Lin(School of Science,Shenyang Aerospace University,Shenyang 110136,China)Abstract:We mainly study the heterogeneous fleet vehicle routing problem(HVRP).Based on
4、the classical HVRP model,a mean shiftlarge neighborhood search(MS-LNS)algorithm,which combined with the mean shift clustering algorithm and large neighborhoodsearch algorithm,was proposed.The customer data was divided by classifying the customer set,so as to reduce the amount of calculationand accel
5、erate the convergence speed of the algorithm.The use of single chain design,combined with the swap and insert neighborhoodsearch,the new neighborhood search was produced,which can randomly handle the neighborhood search between paths and one path.Inaddition,a new neighborhood search named redistribu
6、tion was used to detect whether there is a sub path that does not meet the vehicleload utilization rate for the new solution after the neighborhood search,and delete it to improve the vehicle utilization rate.Ninenumerical examples were used to set up three groups of experiments.Experiment one compa
7、res the distribution effects of heterogeneousand homogeneous vehicles,and the verification results show that the cost of heterogeneous vehicle distribution scheme is low.Experimenttwo verifies the effectiveness of clustering algorithm in different scales of customer data.Experiment three uses MD-LNS
8、 to calculatefour examples and compare with the four algorithms.It is verified that the algorithm proposed can reduce the overall running time on thepremise of obtaining similar optimal solutions.Simulation results verify the rationality of the model and the effectiveness of the algo鄄rithm.Key words
9、:HVRP;mean-shift clustering algorithm;large neighborhood search algorithm;single chain design;redistributionneighborhood search0摇 引摇 言车辆 路 径 规 划 问 题(vehicle routing problem,VRP)是规定一组车辆在一组客户集合间运输货物,并使车辆路径满足相应目标函数要求的研究,是物流运输行业中十分重要的一个研究命题,是优化物资分配,调度运输的方法之一。VRP 自 1959 年被提出后便得到了学者们的关注,形成以 VRP 为基础的各项分支研究
10、。HVRP 便是其中之一,主要研究不同车辆在运输第 33 卷摇 第 9 期2023 年 9 月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇计 算 机 技 术 与 发 展COMPUTER TECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇 摇Vol.33摇 No.9Sep.摇 2023调度中的物资分配问题,其中车辆以车辆归属、车辆属性等进行区分。在 HVRP 下存在不同的研究方向,比如带时间 窗的 HVRP 问题1-3(heterogeneous fixedfleetvehicleroutingproblemwithtimewindows,HVRPTW)、带取送货的
11、 HVRP 问题4-5(heterogeneousfixed fleet vehicle routing problem simultaneous pickupand delivery,HVRPSPD)等。VRP 已知是 NP 难问题,可知 HVRP 也是 NP 难问题。精确方法求解问题具有一定难度,为能快速求解问题,部分学者通过模拟自然演变,采用元启发式方法进行求解,并取得了不错的成果。Wu6在求解车辆数量限制下的 VRP 时,使用自适应大邻域搜索算法,并将算法的消除与添加两个变换步骤加以改进,将客户运用聚类方法分类,并在消除变换过程按照聚类结果消除,避免单客户消除方法中客户返回原位置这种算
12、力上的浪费。Molina7在求解 HVRPTW 时设计了一种具有局部搜索的混合蚁群算法(ant colony system,ACS),称为 memetic-ACS 算法,并在其实验中得到了新的最优解。鲁建厦8研究了不同初始解对算法的影响,并证明使用聚类算法生成的初始解能使算法收敛速度有较大改进。Meliani9和 Wei10在其研究中就用 C-W 节约算法来求解模型的初始解。Jin11使用多启动策略来增加每次迭代的初始解的多样性,以此加大产生当前最优解的可能性。闫军12通过将客户集合分成不同的子群,简化数据复杂度然后再进行求解。为提高初始解效率,该文通过均值漂移聚类算法将客户分成多个子类,在初
13、始化时优化每条路径对客户个体的选择,从而优化算法初始解。而后通过单链设计优化邻域变换方法,加快 LNS 算法的收敛速度,并通过三组实验验证了 MS-LNS 算法的合理性及有效性。1摇 问题描述与数学模型HVRP 包括车辆数量限制下(heterogeneous fleetvehicle routing problem)的 HFVRP 和无车辆数量限制(fleet size and mix vehicle routing problem)的 FSMVRP两类13。HFVRP 主要求解在现有资源下如何优化分配,而 FSMVRP 则更侧重于市场需求的最优调度方案。该文研究了 FSMVRP。1.1摇 问
14、题描述该模型以最小化总成本为目标函数值。共有 N个客户需要服务,每个客户的需求量为 qi。车场标记为 0 点。运输车辆数量为 K,共有 M 种车辆。异构车辆按照最大载荷量区分,第 k 种车辆的载荷为 Qk,启动成本为 Ck,单位行驶成本为 Cu。车辆从车场出发服务客户,服务完后回到车场。dij表示客户 i 到 j 的距离。1.2摇 数学模型min:F=移Ni=0移Nj=0移Kk=1Cuxijkdij+移Nj=1移Kk=1Ckx0jk(1)s.t.移j沂Nx0jk=移j沂Nxj0k=1摇(2)移i沂N移k沂Kxijk=移i沂N移k沂Kxjik=1,坌j 沂 N(3)移i沂N移j沂Nqjxijk臆
15、 Qk,坌k 沂 K(4)其中,式(1)F 为目标函数,最小化车辆总成本;式(2)保证每辆车必经过0 点,即车辆必从0 点出发且回到0点;式(3)保证每个客户只有一辆车服务,且只服务一次(此条件可以消除子路径的可能性);式(4)保证车辆不会超载。xijk为 0-1 变量,当车辆 k 经过弧 ij 时为1,否则为 0。2摇 基于均值漂移聚类的 LNS 算法在求解 HVRP 问题时常使用随机算法或贪心算法生成初始解。相较于随机算法,贪心算法获取的初始解距最优解更近,能加快算法前期收敛进度,但由于贪婪算法的最近邻选择机制减弱了初始解群的多样性,使算法容易出现早熟现象。为找到更合适的初始解,加快算法收
16、敛,该文提出使用均值漂移聚类算法区分客户子集,依照客户子集初始化客户列表。2.1摇 编摇 码总路径 赘 采用单链编码方式。客户从 1 开始编号 V=1,2,N。车辆依照类型从客户集后一位开始编号 M=N+1,N+2,N+L,其中任意一个元素表示一类车辆。每辆车的子路径 赘k表示为(N+1,3,5,9,12,4,7),其中起始点为车辆类别,其后所有点为子路径中的客户点。总路径表示为 赘=赘1,赘2,赘K。2.2摇 均值漂移聚类算法初始化均值漂移聚类的主要方法是在客户区域内设置 M个移动点粒子 Xm,在每次迭代过程中移动点粒子搜索扫描半径内的所有客户点,依照公式(5)(其中 Sm为 fm限制条件)
17、生成移动向量来更新移动点坐标(6),当某些移动点十分接近的时候将这些移动点合并,直到所有移动点不再变化时停止迭代。此时剩余移动点的个数就代表客户点聚类的个数,而每个移动点扫描过的客户就属于此类别的客户子集。fm=1Sm(xi-Xm),坌m 沂 MSm=xi|椰xi-Xm椰2 maxQk,坌k 沂 K 则转到步骤 4;若 Qk Qd hQk,埚k 沂 K 则转到步骤 5;若 Qd minhQk,坌k 沂 K 则转到步骤 6;Step4:选择载荷量最大的车辆 k沂K,按照总路径初始化的方式生成需求量 qd刚好大于 hQk的子路径,其子路径包含的客户集为 vl,则剩余客户集合 Vl=Vl-vl,剩余
18、客户需求量 Qd=Qd-qd。返回到步骤3继续判断;Step5:选择对应车辆 k,按照总路径初始化方式生成子路径;Step6:配置车辆 s=argminQk,坌k 沂 K 先将 Vl按回路总成本最小排成路径 赘s,再从已服务客户集合Vl=V-Vl 中,按照最小目标函数值增量方式提取路径 赘l中客户点 i 到路径 赘s,并保证客户 i 提取后 赘l满足车辆 l 的载重下限要求,直到 赘s满足步骤3 为止。2.4摇 变换后解的接受准则该文采用模拟退火算法的接受准则判断每次变换后的路径能否替换当前解。当前解的目标函数值高于当前个体最优解时,通过计算公式(7)得到接受概率,再通过轮盘赌形式决定是否接受
19、当前解。其优点在于前期温度值 T 较高时使粒子具有较大的容错能力,可以让粒子在邻域内快速移动;而后期 T 值减小使粒子容错能力减弱,增强了粒子邻域搜索能力,加快收敛进程。每当接受准则成功执行时需要更新温度值 T=籽T。其中 籽 为温度变化率。P=e(F(Papb)-F(赘)/T摇(7)算法流程见图 3。FPapbPagbPagbredistribution图 3摇 MS-LNS 算法流程先使用聚类算法将客户分为多个子群,而后对每个子群使用贪婪算法,这样既能兼顾贪婪算法对初始解群的优化,也能保证初始种群的多样性。该文通过单链编码方式改进变换方法使得每次变换的空间更大,搜索速度更快。对于使用率较差
20、的车辆使用redistribution 变换重排。以此三种方式对 LNS 算法进行改进,加快 LNS 求解速度。3摇 仿真实验3.1摇 实验数据使用 Golden14及 Penna15提供的 13-17、20 号算001摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷例和对应车辆数据(表 1 中共有六种不同的运输车辆Ver.A-Ver.F),以及 Solomon16中 c201、r201、rc201算例进行实验。Solomon 算例使用 20 号算例中车辆数据
21、进行实验。表 1 中 Q 为车辆载荷,C 为车辆固定成本。表 1摇 车辆数据No摇 摇 摇 Ver.A摇 摇 摇摇 摇 摇 Ver.B摇 摇 摇摇 摇 摇 Ver.C摇 摇 摇摇 摇 摇 Ver.D摇 摇 摇摇 摇 摇 Ver.E摇 摇 摇摇 摇 摇 Ver.F摇 摇 摇QCCuQCCuQCCuQCCuQCCuQCCu132020130351.140501.2701201.71202252.52004003.2141201 00011601 500 1.13003 500 1.4155010011002501.6160450216401001802001.61404002.1175025112
22、0801.22001501.53503201.8206010011403001.720050023.2 摇 参数设计为保证算法的收敛速度与跳出局部最优的能力,需要优化现有的算法参数。文中算法涉及两个参数,即聚类算法扫描半径 r 和模拟退火温度变化量 籽。分别通过以下两种方式计算适合文中算法的参数值:3.2.1摇 聚类算法扫描半径 r为保证使用均值漂移聚类时不会出现过多孤立点,保证客户集合分类符合实际,采用箱型图检测客户点距离并尝试 1/4 位数,中位数,3/4 位数做扫描半径的效果。15、16 号算例为 50 个客户点(图 4(a),17号算例为 75 个客户点(图 4(b),20 号算例为
23、100 个客户点(图 4(c)。图 4摇 四组数据在 1/4 位数时的客户分类四组客户数据在取中位数作为扫描半径时都无法对客户集合进行分类,取 1/4 位数时每组的分类情况如图 4 所示。在 1/4 位数周围取值进行验证时发现,相较于 rc201,15 号及 17 号客户数据的分类对扫描半径的取值十分敏感,令 15 号数据的扫描半径 r=20.7时,分类个数缩减到 3 个。令 r=19 时分类的数据较r=20.2 时有比较明显的变化,而 r=17 时 15 号客户数据则被分为六类。为保证分类质量,在 3.2 节计算当中使用 1/4 位数进行计算求解。3.2.2摇 模拟退火温度变化率 籽采用多组
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 LNS 算法 求解 VRP 问题
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。