带时间窗的多中心半开放式VRPSDP问题研究.pdf
《带时间窗的多中心半开放式VRPSDP问题研究.pdf》由会员分享,可在线阅读,更多相关《带时间窗的多中心半开放式VRPSDP问题研究.pdf(12页珍藏版)》请在咨信网上搜索。
1、系统仿真学报系统仿真学报Journal of System Simulation第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023带时间窗的多中心半开放式带时间窗的多中心半开放式VRPSDP问题研究问题研究张颖钰1,吴立云1*,贾胜钛2(1.河南理工大学 工商管理学院,河南 焦作 454003;2.河南理工大学 能源科学与工程学院,河南 焦作 454003)摘要摘要:针对带时间窗的多中心半开放式同时送取货车辆路径问题,构建了配送中心车辆进出平衡且以车辆配送距离最小化为目标的带时间窗的多中心半开放式同时送取货车辆路径问题的数学模型。设计了混沌变异头脑风暴算法求
2、解该问题,采用顺序交叉策略增加种群多样性,设置2种混沌映射进行混沌变异操作,利用混沌变异的多样性、遍历性和随机性,增强算法全局搜索能力。通过多组算例对比,不仅验证所提算法求解多种车辆路径问题的有效性与稳定性,还验证了带时间窗下的多中心半开放同时送取货配送模式优于多中心闭合式同时送取货配送模式。研究成果不仅拓展了车辆路径类的模型,还为相关物流企业提供一种决策参考。关键词关键词:车辆路径问题;多中心;同时送取货;时间窗;混沌变异头脑风暴算法中图分类号:TP391.9;F252 文献标志码:A 文章编号:1004-731X(2023)11-2464-12DOI:10.16182/j.issn1004
3、731x.joss.22-0727引用格式引用格式:张颖钰,吴立云,贾胜钛.带时间窗的多中心半开放式VRPSDP问题研究J.系统仿真学报,2023,35(11):2464-2475.Reference format:Zhang Yingyu,Wu Liyun,Jia Shengtai.Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time WindowsJ.Journal of System Simulation,2023,35(11):2464-2475.Multi-de
4、pot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time WindowsZhang Yingyu1,Wu Liyun1*,Jia Shengtai2(1.School of Business Administration,Henan Polytechnic University,Jiaozuo 454003,China;2.School of Energy Science and Engineering,Henan Polytechnic University,Jiaozuo 454003,
5、China)Abstract:To solve the multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows,this paper builds a mathematical model of a multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows by balancing the vehicle in and ou
6、t of the distribution center and minimizing vehicle delivery distance as the goal.According to the characteristics of the problem,a brain storm algorithm based on chaotic mutation is designed to solve this problem,and the sequential crossover strategy is adopted to increase the population diversity.
7、Meanwhile,the algorithm selects two chaotic maps for chaotic mutation operation,which employs the diversity,ergodicity,and randomness of chaotic mutation to enhance the overall search capability of the algorithm.Multiple numerical example comparison not only verifies the effectiveness and stability
8、of the proposed algorithm for solving various vehicle routing problems but also indicates the distribution mode of multi-depot half-open simultaneous delivery-pickup and time windows is superior to that of multi-depot simultaneous delivery-pickup and time windows.The research results expand the vehi
9、cle routing problem and provide a decision-making reference for related logistics enterprises.收稿日期:2022-06-24 修回日期:2022-08-22基金项目:国家自然科学基金(51874121);NSFC-河南联合基金重点项目(U1904210);河南省高校基本科研业务费专项资金(NSFRF180104)第一作者:张颖钰(1997-),女,硕士生,研究方向为现代物流与供应链管理。E-mail:通讯作者:吴立云(1973-),女,教授,博士,研究方向为现代物流与供应链管理、质量与安全管理等。E-
10、mail:第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-Keywords:vehicle routing problem;multi-depot;simultaneous delivery-pickup;time windows;brain storm optimization algorithm based on chaotic mutation0引言引言近年来电商联盟发展迅速,人们对物流的服务要求逐渐提高,针对电商退换货的逆向物流也随之备受关注。因此国内外众多学者
11、对车辆路径问题展开广泛研究,衍生出了多中心半开放式车辆路径问题(multi-depot half open vehicle routing problem,MDHOVRP)以及同时送取货车辆路径问题(vehicle routing problem with simultaneous delivery and pickup,VRPSDP)等众多 VRP 的拓展问题。为了提升服务质量和客户满意度,物流企业不仅要满足客户需求,还要考虑客户的服务时间窗。因此,本文研究了带时间窗的多中心半开放式同时送取货车辆路径问题(multi-depot half open vehicle routing probl
12、em with simultaneous delivery-pickup and time windows,MDHOVRPSDPTW)。该问题描述的配送网络包括多个配送中心和客户点,每个客户点同时具有送取货需求,所有配送车辆从配送中心出发对客户点执行送取货服务,且必须在客户点要求的访问时间内完成服务。相对于闭合式的配送中心,半开放式配送中心允许车辆完成配送任务后在保持配送中心车辆均衡的原则下可就近返回任意配送中心。MDHOVRPSDPTW问题更加符合现实物流配送的复杂情况,如在一个区域内含有多家配送公司负责多个小区的快递配送及揽收服务,通过配送中心与车辆之间的共享,缩短配送距离、减少用车数量,
13、进而降低配送成本。MDHOVRPSDPTW问题是由带时间窗的同时送取货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSDPTW)和 MDHOVRP 结合而来。目前,针对该问题的研究涉及较少。但其包含的VRPSDPTW,MDHOVRP等问题仍是当前的研究热点。关于VRPSDPTW,MDHOVRP国内外学者都对其模型和求解方法进行了广泛和深入的研究。VRPSDPTW问题由Angelelli等提出,针对该问题设计精确算法进行算例规模为20 的小型算例求解1。但是精确算法会随着客
14、户规模增大导致求解效率变低,故更多学者采用启发式算法对其进行求解。文献2对于VRPSDPTW问题采用协同进化遗传算法求解,并在经典算例Solomon的基础上设计了测试算例。文献3设计离散布谷鸟搜索算法求解VRPSDPTW问题,并与文献2做对比验证且更新了5个国际已知最优解。于次年又设计回溯搜索优化算法有效求解 VRPSDPTW 问题4。文献5为解决VRPSDPTW问题,提出基于模拟退火与自适应大规模邻域搜索结合的混合算法,对 56 个 大 规 模 算 例 进 行 验 证。关 于MDHOVRP问题的研究,文献6提出一种自适应局部搜索的混合遗传算法来求解带时间窗的多中心半 开 放 式 车 辆 路
15、径 问 题(multi-depot half open vehicle routing problem with time windows,MDHOVRPTW)。文献7针对 MDHOVRPTW 问题建立混合整数规划模型,提出一种基于3种有效局部搜索的构造型启发式算法并求得满意解。文 献 8 将 粒 子 群 算 法 与 遗 传 算 法 结 合 求 解MDHOVRP问题。文献9基于生鲜品的物流配送提出MDHOVRPTW配送模式,构建多目标优化模型并设计蚁群算法求解该问题。文献10将多中心联合配送与电动车辆结合,构建带时间窗的多中心半开放式纯电动车辆路径优化模型,并改进蚁 群 算 法 对 其 进 行
16、 求 解。文 献 11 针 对MDHOVRPTW问题,设计了一种三阶段求解算法,并改进多蚁群算法求解该问题。文献12考虑软 时 间 窗 约 束 和 车 辆 速 度 变 化 情 况,针 对MDHOVRP问题,设计了改进粒子群算法和变邻域搜索算法的两阶段求解算法。综 上 所 述,国 内 外 文 献 主 要 集 中 在 对 2465第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-VRPSDPTW问题及MDHOVRP问题分开的研究,将 VRPSDPTW 与 MDHO
17、VRP 问题结合考虑的文献较少。此外在模型构建方面,多中心车辆路径文献中车辆大多数按照就近原则返回配送中心,容易造成配送中心车辆不均衡,甚至导致配送中心无车可用。本文在模型构建中加入车辆进出数量守恒约束,即车辆返回配送中心时应先满足配送中心车辆进出平衡,再实行就近原则。由于MDHOVRPSDPTW问题约束条件复杂,使求解难度进一步增加,为了提升求解效率和解的质量,本文设计了一种针对MDHOVRPSDPTW问题特点的混沌变异头脑风暴算法,采用k-means聚类操作,按照适应度值将相似的个体聚成k类,并引入顺序交叉策略,增强个体之间交流,增加种群的多样性。当算法陷入局部最优时,随机选取混沌映射,利
18、用混沌变异的多样性、遍历性和随机性生成新的解集合,平衡搜索时的收敛和发散操作,进而提高算法跳出局部最优的能力。1MDHOVRPSDPTW数学模型数学模型1.1 问题描述问题描述本文研究的MDHOVRPSDPTW问题可以描述如下:在配送网络中存在多个配送中心和客户点,客户点同时具有送取需求,同一类型的车辆从任意配送中心以负载状态出发,对客户点执行送取任务,在一次服务中完成客户点的所有需求,车辆在配送路径中均满足自身载重约束、客户点与配送中心服务时间窗要求,当车辆完成配送任务后在保证配送中心车辆均衡的情况下就近返回任意配送中心。目标是找到一条满足所有约束条件的配送路径,并使配送距离最小化。模型假设
19、如下:(1)配送中心、客户点的地理信息已知;(2)配送中心、客户点的服务时间窗信息已知;(3)客户点的送取需求已知;(4)同一类型车辆的最大装载已知;(5)车辆对客户点无服务顺序要求;(6)车辆匀速行驶。1.2 模型构建模型构建以配送距离最小化为优化目标,建立如下MDHOVRPSDPTW模型。最小化配送距离:Zmin=iVyVkKcijxijk(1)式中:cij为节点i到节点j的距离,ijV;xijk为车辆k是否从节点i到节点j,如果是,则xijk=1,否则,xijk=0。客户点需求不能被拆分且只能被一辆车服务:s.t.iVkKxijk=1jN(2)式中:N为客户户点合集,N12,n。车辆在路
20、径上货物进出平衡:jVxijk=1kK(3)式 中:k 为 车 辆 标 号(车 辆 型 号 统 一),k12,K;K为车辆总数。iVxijk=iVxjikjNkK(4)车辆k从客户i到客户j的行驶时间等于客户i到客户j之间的距离与车辆行驶速度比值:tij=cijGijV(5)式中:cij为节点i到节点j的距离,ijV;G为车辆行驶速度;V为所有节点合集,V=NM。车辆行驶时间的连续性:wik+si+tij-wjkB(1-xijk)(6)式中:wik为车辆k对节点i开始服务时间,iV;si为客户户i的服务时间,iN;tiy为从节点i到节点j的行驶时间,ijV;B为足够大的正数。保证车辆满足客户点
21、和配送中心的时间窗要求:ai(jVxijk)wikbi(jVxjik)iVkK(7)2466第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023张颖钰,等:带时间窗的多中心半开放式VRPSDP问题研究http:/www.china-式中:ai为节点i的左时间窗,iV;b为节点i的右时间窗,iV。车辆初始装载:L0k=iNdijNxijkkK(8)式中:di为客户户i的送货需求,iN。车辆完成任意客户点后的车辆载重及完成后不超过自身载重:LjLi-di+pj-B(1-kKxijk)iNjN(9)式中:Lj为车辆对客户j服务后的装载量,jN;pj为客户i的取货求量
22、,jN。LjQ+B(1-iVxijk)jNkK(10)式中:Q为车辆最大载重;车辆从任意配送中心出发且仅离开一次,并最终返回任意配送中心:iMjNxijk=iNjMxijk=1kK(11)从配送中心出发的车辆数等于返回该配送中心的车辆数:jNkKxijk=jNkKxjikiM(12)决策变量取值:xijk01i.jVkK(13)2混沌变异头脑风暴算法混沌变异头脑风暴算法MDHOVRPSDPTW问题是NP-Hard问题,其多中心、半开放式以及时间窗等特点增加了求解难度。为了求解该问题,本文将头脑风暴优化(brain storm optimization,BSO)13算法和混沌变异策略14相结合,
23、设计了混沌变异头脑风暴(brain storm optimization based on chaotic mutation,CMBSO)算法。传统头脑风暴算法是模拟人类求解问题集思广益的行为,由量变到质变的过程,其基本流程包含解码、聚类及迭代搜索。本文设计的CMBSO算法采用非0自然数编码,两段式解码,提高可行解的产生。在迭代搜索中采用顺序交叉策略与混沌变异策略,不仅扩大了算法的搜索空间,还增强了算法全局搜索能力,旨在获得高质量的满意解。2.1 编码与解码编码与解码本文采用非0自然数编码,将客户点随机全排列,所有客户点储存在C_Num中,18为客户点,记录服务顺序如图1所示。解码过程分为2个
24、阶段。第1阶段,车辆依照从左到右顺序依次服务客户点,并进行载重、时间窗约束检验。若满足约束,则对客户点分配路径;否则,结束分配,由新派车辆进行服务。第2阶段,对每辆车服务首尾客户点随机分配配送中心,并进行车辆进出平衡约束检验,满足约束再按照就近原则,确定每辆车的始末配送中心。举例对图1进行求解。假设车辆k1在满足载重和时间窗约束下服务客户点4、客户点1,当对客户点3服务时不满足载重约束,则退出路径分配,由车辆k2继续服务客户点3、客户点2、客户点7和客户点6,车辆k2不满足客户点5的时间窗约束退出路径分配,由车辆k3进行余下客户点的服务。当路径分配完毕后,先对车辆服务的初始客户点按照就近原则分
25、配配送中心,满足车辆进出平衡情况下,再对末尾客户点按照就近原则分配配送中心,911为配送中心。求解过程如图2所示。2.2 适应度函数适应度函数解码过程第2阶段确定始末配送中心时不一定满足时间窗需求,为保证解码的配送路径都是可行解,加入违反时间窗惩罚条件,以达到配送路线满足约束,惩罚函数为图1 编码示意图Fig.1 Encoding diagram 2467第 35 卷第 11 期2023 年 11 月Vol.35 No.11Nov.2023系统仿真学报Journal of System Simulationhttp:/www.china-t(s)=i=1nmaxai-bi0(14)式中:ai为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 时间 中心 半开 VRPSDP 问题 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。