![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于多目标混合粒子群算法的车辆路径优化.pdf
《基于多目标混合粒子群算法的车辆路径优化.pdf》由会员分享,可在线阅读,更多相关《基于多目标混合粒子群算法的车辆路径优化.pdf(6页珍藏版)》请在咨信网上搜索。
1、第 卷第 期太原科技大学学报 年 月 文章编号:()收稿日期:基金项目:山西省自然科学基金()作者简介:李琦翔(),女,硕士研究生,主要研究方向为车辆路径优化的理论及应用研究;通信作者:栗振锋教授,:基于多目标混合粒子群算法的车辆路径优化李琦翔,栗振锋,李兴莉(太原科技大学 交通与物流学院,太原 ;太原科技大学 应用科学学院,太原 )摘要:针对车辆路径优化问题中的现实因素,考虑了时间窗约束和时变车速的情况,构建了以配送总成本最低和客户平均满意度最高为目标的数学优化模型。为了提高基本粒子群算法的搜索精度和搜索能力,将遗传算法中的交叉和变异操作引入到基本粒子群算法中,设计了一种多目标混合粒子群算法
2、。选取 条实例在 软件上进行实验仿真,并与基本粒子群算法的优化结果进行对比。算例结果表明,相较于基本粒子群算法的优化结果,多目标混合粒子群算法减少了 的平均配送总成本,提高了 的客户平均满意度,其中平均配送车辆数量、平均行驶总路径长度、每辆车平均配送量的计算结果也都得到了优化。为多目标混合粒子群算法求解车辆路径优化问题提供了较好的理论依据。关键词:时间窗;车辆路径优化;粒子群算法;配送总成本;客户满意度中图分类号:文献标识码:车辆路径问题(,)于 年由 和 首次提出,可描述为:已知一个配送中心和一定数量的客户点及其地理位置、所需货物需求量等信息,在满足一定约束条件(如车辆数最少、路径最短、花费
3、时间最少,成本最低等)的前提下,规划出一条或多条路径来满足客户的需求。证明带时间窗的车辆路径问题是一个 问题,在 的基础上,考虑时间窗限制,这类组合优化问题难以在合理的时间内得到最优解,因此学者们尝试采用智能优化算法求解该问题,如遗传算法 、禁忌搜索算法 、模拟退火算法 等,并得到了不错的效果。粒子群算法(,)由 和 于 年提出的一种新的进化算法,粒子群算法模拟了鸟类种群觅食的行为,它以操作简单、收敛速度快等优点被人们广泛应用于各类实际问题中。遗传算法由 教授 于 年首次提出,是借鉴了生物进化规律,随之衍生出的智能优化算法。因其具有良好的全局寻优能力、便于求解离散问题等特点,使得该方法得以广泛
4、应用。由于单个智能优化算法解决实际问题存在一定缺陷,例如:收敛速度过快、易于陷入局部最优等,因此学者们将两种或多种算法相融合,设计出新的混合智能优化算法求解各类组合优化问题,比如廖良才等 将遗传算法和节约算法融合,提出一种混合遗传算法解决车辆调度优化问题;徐杰等 提出一种混合粒子群优化算法处理多目标离散问题;罗耀 将细菌觅食优化算法与粒子群算法结合,提出一种改进的粒子群算法用于求解车辆路径优化问题;熊昕霞等 提出一种混合粒子群优化算法解决移动机器人的路径规划问题。目前单目标车辆路径优化问题的研究较为成熟,但已有的大部分多目标优化问题研究都是基于理想的状态下,例如:车辆行驶速度一直处于匀速状态、
5、车辆行驶总成本未考虑司机所服务的客户点数量不同等,这在实际应用中会产生较大的误差。针对现有研究存在的一些不足,本文考虑了在实际配送过程中,随着车辆服务的客户点数量的不同,其所产生的固定成本也产生一定的变化,以此构建了以车辆配送总成本和客户平均满意度为目标的多目标数学优化模型,在文献 的基础上考虑了配送过程中车辆速度随路况变化的因素,在不同的时间段,车辆的行驶速度不同,对于车辆配送总成本和客户满意度的计算更加贴合实际;将遗传算法中的交叉和变异思想引入到基本粒子群算法中,使得粒子可以有效跳出局部最优从而快速寻求全局最优解,设计出一种多目标混合粒子群算法求解物流配送中的多目标路径优化问题。针对 条实
6、际案例进行实验仿真并对结果进行对比分析,验证了该算法的有效性,具有很强的实际意义。车辆路径优化问题模型构建 问题描述已知一个配送中心和若干个客户点,在配送中心和各个客户点之间的位置坐标及所需货物数量等信息已知的情况下,配送中心接收到客户点下达的订单数量,安排车辆从配送中心出发,向各个客户点配送货物,在满足车辆装载能力、客户服务时间限制等约束的前提下,设计合理的路线以达到降低配送总成本和提高客户平均满意度两个目标。模型假设()物流配送中心数量单一,且配送中心的货物数量足够,不存在缺货现象;()物流配送中心具有一定数量的同种类型车辆;()各个客户点的地理位置、所需货物数量、时间窗限制等基本信息已知
7、;()配送车辆只负责将货物送至给顾客,不提供换货及退货服务;()配送车辆的速度随路况的变化而变化。模型符号说明(,):为无向图,其中 表示所有节点的集合,表示边集,表示配送中心,用表示,表示客户点集合,则 ,;(,),(,)为客户节点 的位置坐标;以下列出建立模型所需要的数学符号。:配送车辆的总数,车辆 (,):客户点 到客户点 之间的距离:客户点 的货物需求量:配送车辆的最大装载量:配送车辆的单位距离行驶成本:单个车辆的指派成本:点位费:车辆 到达客户 的时间:车辆 在客户 的等待时间:车辆 在客户点 的服务时间:早到的惩罚成本系数:晚到的惩罚成本系数:车辆 在 、两个客户点之间的行驶速度
8、:车辆 在 、两个客户点之间的行驶时间,:客户点 要求服务的时间窗,:客户点 可以接受服务的最早和最晚时间窗 模型建立综合考虑配送总成本最低和客户平均满意度最大的双目标优化模型,其中配送总成本由运输成本、固定成本及惩罚成本组成,运输成本需要根据车辆的行驶距离来确定;固定成本由车辆指派成本和运输车辆行驶的多点位费组成;且车辆提前或延迟到达客户点会产生一定的惩罚。如图 所示,在,中车辆到达客户点,不会产生惩罚,在其余时间内送达会产生相应的惩罚。FJMJ图 惩罚区间图 在车辆配送的过程中,由于道路拥挤、突发情况等诸多因素导致车辆无法在顾客所期待的时间内到达,就会降低客户满意度,客户满意度与车辆到达时
9、间关系如图 所示。运输成本 为 ()固定成本 为 ()()惩罚成本 为第 卷第 期李琦翔,等:基于多目标混合粒子群算法的车辆路径优化 IEJeJlJLJ图 客户满意度与时间关系图 ,()顾客满意度函数为(),()综上所述,建立配送总成本最小和客户满意度最大的多目标数学模型如下:()()()约束条件:,(),(),(),且 (),()()()(),(),()其中,式()表示车辆 所装载的一条路线上的客户总需求量不得超过车辆的最大载重量;式()表示配送车辆从配送中心出发,在完成配送任务后返回配送中心;式()表示到达和离开客户点的配送车辆是同一辆;式()表示保证每个客户点都被服务到且仅有一辆车为其提
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 多目标 混合 粒子 算法 车辆 路径 优化
![提示](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。