考虑同时取送和时间窗的车辆路径及求解算法.pdf
《考虑同时取送和时间窗的车辆路径及求解算法.pdf》由会员分享,可在线阅读,更多相关《考虑同时取送和时间窗的车辆路径及求解算法.pdf(10页珍藏版)》请在咨信网上搜索。
1、近年来,随着“一带一路”和“自贸区”战略的实施与完善,数字经济和电商模式的发展,极大推动了我国物流行业的迅速发展,物流服务从基本的收寄需求,逐步发展到无人配送、上门揽件、准时到达等多元化需求1。当前,国家大力发展绿色经济,提出碳达峰、碳中和,提倡产品生命周期结束后可回收再利用,注重环境保护、考虑同时取送和时间窗的车辆路径及求解算法刘建胜,蔡祥,黄纪绘,熊君星南昌大学 先进制造学院,南昌 330047摘要:针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-deliveryand time windows,VRP
2、SPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%
3、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,X
4、IONG 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 constr
5、ucted 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
6、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 t
7、he 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 case
8、s,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 s
9、torm optimization;adaptivelarge neighborhood search基金项目:国家自然科学基金(51565036)。作者简介:刘建胜(1978),通信作者,男,教授,博士生导师,研究方向为数字化与智能制造、智能优化算法、制造技术与装备,E-mail:;蔡祥(1997),男,硕士研究生,研究方向为智能优化算法、车辆路径优化;黄纪绘(1993),男,博士,讲师,研究方向为微细成形、机械设计与智能制造;熊君星(1981),男,副教授,研究方向为数字化与智能制造、制造技术与装备。收稿日期:2022-05-20修回日期:2022-07-12文章编号:1002-8331(
10、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)问题的重要扩展。自
11、1959年提出VRP问题以来,不断取得研究成果和实际应用3。VRPSPDTW是在VRP的基础上扩展了同时取送货(simultaneous pickup-delivery)以及时间窗约束(time windows),要求车辆在规定的时间内同时完成客户的取送货需求。VRPSPDTW最早由Angelelli等4于2002年提出,并设计了一种分支-定界法精确求解该问题。但是随着客户规模的增加,VRPSPDTW的求解变得愈发困难,已被证明为NP-hard问题,精确求解在理论上可行,在现实中由于计算时间及难度变得不切实际,众多学者开始寻找不同的启发式算法来解决该问题。文献5提出一种基于最小插入成本的协同遗
12、传算法解决该问题,并设计了65组针对VRPSPDTW问题的国际标准测试算例。文献6提出包含 RCRS(residualcapacity and radial surcharge)的并行模拟退火算法对该问题进行求解。文献7应用离散布谷鸟算法对该问题进行深入研究,并根据其飞行机制进行有效的全局搜索。文献8和文献9分别采用粒子群优化算法和混合遗传算法对VRPSPDTW进行求解。文献10利用化学反应优化算法对多目标VRPSPDTW进行了研究。文献11和文献12分别采用禁忌搜索算法和分支定界法对需求可拆分的 VRPSPD进行求解。文献13利用多目标变邻域搜索算法对二级配送网络的VRPSPDTW进行了研究
13、。文献14应用禁忌搜索算法对带时间窗的同时取送家庭医疗调度问题进行求解。文献15对多配送中心VRPSPDTW进行研究,并采用3D聚类算法进行求解。通过以上文献梳理可知,尽管国内外关于VRPSPDTW有一定的相关研究,但是该领域仍然有两点不足:(1)在算法的性能方面,大部分文献均采用算法原有搜索机制,未考虑通过多个算法相结合来增强算法的寻优能力;(2)在算法的局部搜索方面,大部分算法仍采用单一的交叉变换,导致生成的解之间多样性有限,难以实现优质解空间的深入搜索。因此,对于考虑多个算法相结合来增强寻优能力,获取高质量解的有效算法需要进一步深入研究。头脑风暴算法(brain storm optimi
14、zation,BSO)16是一种新兴的受人类行为启发的群智优化算法,具有参数设置简单、易实现和寻优能力强的特点,已经在车间调度、工程通信、图像处理等17-19方面取得了应用,但目前使用BSO算法求解VRP问题较为有限。文献20采用改进的BSO算法对VRPTW进行求解,通过设计新的编码解码方法增加全局搜索范围,实验结果表明求解效果优良。文献21为解决VRPTW问题,提出一种混合的BSO算法,首先通过蚁群系统寻找全局搜索方向,然后通过邻域搜索(local search)进行局部搜索,极大增加了算法的寻优性能。针对VRPSPDTW问题,目前尚未有BSO求解的报道,故十分有必要展开相关研究。综上所述,
15、本文以VRPSPDTW问题为研究对象,建立以车辆使用成本、车辆行驶距离成本总成本最少为优化目标的数学模型,提出一种自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。本文通过算法相结合来合理引导搜索方向,将 ALNS(adaptive large neighborhood search)算法融入 BSO局部搜索策略中,进行两阶段搜索。全局搜索阶段,执行BSO算法;局部搜索阶段执行ALNS算法。其中BSO采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略尽快搜寻到优质解空间;ALNS通过自适应动态选择邻域搜索机制和多种破坏-修复算子
16、集合,对优质解空间进行有效的邻域搜索,进一步加大算法在短时间内寻优的几率。最后,通过对不同规模测试算例和算法比较,验证了ABSO算法的有效性。本文对VRP-SPDTW的研究,不仅进一步扩展了VRP问题的理论研究,也为制定合理科学的车辆调度计划提供决策参考,具有重要的理论和工程实践应用价值。1问题分析1.1问题描述VRPSPDTW 问题示例如图 1所示,存在给定的一个配送中心、一组地理位置不同的客户和一组运输车辆,要求在满足约束的前提下求得一组合理的配送路线,并最小化车辆使用数以及车辆行驶距离。与传统的VRP问题相比,VRPSPDTW问题不仅按照客户规定的时间窗进行服务,进一步提高客户的满意9:
17、009:508:008:3011:0011:409:109:4010:2011:00取货量送货量配送车辆时间窗客户配送中心图1VRPSPDTW问题示例Fig.1VRPSPDTW problem example2962023,59(16)程度,增加企业的核心竞争力,而且还考虑客户的取货需求,更加符合当今物流行业绿色、环保、高效的发展趋势,进一步降低了车辆的空载率,节约企业成本。本文研究的VRPSPDTW问题描述为:(1)若干运输车辆从配送中心出发为客户取送货并最终返回配送中心,每位客户仅可由一辆车服务一次,车辆在配送过程中任何时刻都不能超载。(2)车辆到达客户处为客户送货的同时从客户处取走回收的
18、货物,每位顾客均有取货和送货需求。(3)配送中心和客户的位置、时间窗、客户取送货需求量、服务时间需求,以及配送中心和各个客户之间的距离、车辆行驶速度均已知。(4)允许车辆在客户最早开始服务时间之前到达,不允许车辆在客户最晚开始服务时间之后到达;车辆要在配送中心最早开始时间之后为客户服务,在配送中心最晚截止时间之前返回配送中心。本文将物流网络抽象为一连通图:假设各节点之间相互联通;两点之间的距离对称,即dij=dji;任意3个节点之间距离满足dik+dkjdij;忽略道路、天气及交通堵塞等其他因素。1.2模型建立根据以上问题描述和假设,为方便VRPSPDTW数学模型的建立,本文使用的参数和变量符
19、号说明如下:(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
20、。(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)i
21、Vxijk=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(
22、17)R0kb0,kK(18)xijk0,1,()i,j V,kK(19)式(1)以车辆使用成本、车辆行驶成本的总配送成本最小为目标;式(2)确保每个客户只由一辆车服务一次;式(3)为限制车辆使用数不超过车辆总数;式(4)为流量守恒式,即到达和离开每个客户的车辆数相同;式(5)(7)确保每辆车从配送中心出发,最终返回配送中心;式(8)、(9)为车辆从配送中心出发时的装载量及其约束;式(10)、(11)为车辆返回配送中心的装载量及其约束;式(12)、(13)分别为车辆服务完第一个客户后载重量公式和车辆配送途中的载重量公式;式(14)为车刘建胜,等:考虑同时取送和时间窗的车辆路径及求解算法297C
23、omputer Engineering and Applications计算机工程与应用2023,59(16)辆载重量约束;式(15)、(16)为客户的时间窗约束;式(17)、(18)为配送中心时间窗约束;式(19)为决策变量约束。本文模型与既有模型相比所用参数和变量较少,并具有较强的通用性,通过参数与约束条件的变换则可以变为不同的车辆路径问题优化模型。例如去掉约束(15)、(16)、(17)、(18)后变成了同时取送货车辆路径问题;去掉约束(10)并且令Pi=0则变为带时间窗的车辆路径问题(VRP with time windows)。2算法设计头脑风暴算法作为一种新型的智能优化算法,相比较
24、于其他元启发式搜索算法而言具有较高的求解精度和效率,但该算法同其他常见的智能优化算法类似,在迭代后期存在收敛速度慢、容易陷入局部最优等问题。基于此,本文将 BSO 算法与 ALNS 算法相结合,提出ABSO算法。考虑到该问题模型中存在大量约束,在全局搜索阶段,通过BSO算法对不满足车辆载重约束或时间窗约束的配送方案进行惩罚,降低其适应度值,扩大种群搜索范围,快速找到优质解区域;在局部搜索阶段,通过ALNS算法对不满足载重量及时间窗要求的配送方案进行剔除,保证配送方案的可行性,继而对优质解区域进行深度搜索,增强算法寻优性能。2.1编码解码与种群初始化本文算法采用整数编码的方式,确保每个客户只能由
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考虑 同时 时间 车辆 路径 求解 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。