遗传算法求解VRP问题的技术报告.doc
《遗传算法求解VRP问题的技术报告.doc》由会员分享,可在线阅读,更多相关《遗传算法求解VRP问题的技术报告.doc(8页珍藏版)》请在咨信网上搜索。
1、遗传算法求解VRP问题的技术报告摘要:本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法,通过种群初始化,选择,交叉,变异等操作最终得到车辆配送的最短路径。通过MATLAB仿真结果可知,通过遗传算法配送的路径为61.5000km,比随机配送路径67km缩短了5.5km。此结果表明遗传算法可以有效的求解VRP问题。一、 问题描述1.问题描述车辆调度问题(Vehicle Scheduling/Routing Problem,VSP/VRP)的一般定义为1:对一系列送货点和/或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量
2、,送发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。问题描述如下2:有一个或几个配送中心,每个配送中心有种不同类型的车型,每种车型有辆车。有一批配送业务,已知每个配送业务需求量和位置或要求在一定的时间范围内完成,求在满足不超过配送车辆载重等的约束条件下,安排配送车辆在合适的时间、最优路线使用成本最小。2.数学模型设配送中心有K台车,每台车的载重量为,其一次配送的最大行驶距离为,需要向个客户送货,每个客户的货物需求量为,客户到j的运距为,配送中心到各个客户的距离为,再设为第K台车配送的客户数(=0表示未使用第K台车),
3、用集合表示第k条路径,其中表示客户在路径 k 中的顺序为 (不包括配送中心),令 表示配送中心,若以配送总里程最短为目标函数,则可建立如下数学模型: (1) (2) (3) (4) (5) (6) (7) (8)上述模型中,式(1)为目标函数,即要求配送里程最短;式(2)保证每条路径上各个客户的货物需求量之和不超过配送车的载重;式(3)保证每条配送路径的长度不超过配送车的最大行驶距离;式(4)表明每条路径上的客户数不超过总客户数;式(5)表明每个客户都得到配送服务;式(6)表示每条路径的客户组成;式(7)限制每个客户仅能由一台配送车送货;式(8)表示当第 k 辆车服务的客户数大于等于1时,说明
4、该台车参加了配送,则sign(n)的值取1,否则为0。二、 研究现状车辆调度问题在目标和范围方面有很大差别,主要是研究的目标和限定条件不同。在研究目标方面有的是最短路线,有的是最短时间,有的是客户的方便程度等等。在限定条件方面,有配送中心方面的区别,和有单配送中心的,有多配送中心;有配送车辆的数量、种类方面的区别,如车辆数有限、无限、单一车型和多种车型;在业务种类方面,有的是集货任务,有的是送货业务,有的是集送一体化业务,有的是各种业务混合情况。有时间窗的车辆调度问题是最为普通的问题,以成为研究热点。遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识,并能利用问题固有的知识来缩小搜索空间
5、,自适应地控制搜索过程,动态有效地降低问题的复杂度,从而求得原问题的真正最优解或满意解,因此我来选用遗传算法来求解VSP问题。三、 解决方法遗传算法的流程图如下:基于车辆和客户对应排列编码的遗传算法的基本步骤:(1)编码:采用车辆和客户对应排列的编码方法,其基本思路是:用车辆数间的任意自然数(可重复)的排列表示车辆排列,用客户数间的互不重复的自然数排列表示客户排列,两者相对应,构成一个解,并对应一个配送路径方案。例如:对于一个用3台车向9个客户送货的车辆调度优化问题,设某解为(122131223)(456712398),即车辆排列为122131223,客户排列为456712398,两个排列相对
6、应。(2)适应度函数:直接采用公式(1)作为适应度评估函数。对不可行路径进行权重惩罚。(3)选择策略:采用最佳个体保存与赌轮相结合的选择策略。其具体操作为:将每代群体中的N个个体按适应度由小到达排列,排在首位的个体性能最好,将它直接复制到下一代。下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。(4)交叉操作:在该编码方式下有几种编码方式:仅对车辆编码进行交叉、仅对客户编码进行交叉和同时对客户编码和车辆编码进行交叉。本方法中采用仅对车辆编码的方式来交叉。(5)变异操作:本程序中对于变异操作,采用对客户编码变异的方式。用MATLAB编程,在内存为2G,CPU 2.10GH
7、z的微机上运行。采用运行参数:种群规模为100,交叉概率为0.9,变异概率为0.2,进化代数100。变异仅对客户编码,对不可行路径的惩罚权重去100km,具体程序代码见附录。四、 仿真结果某配送中心有2台车,其载重量均为8t,车辆每次配送的最大行驶距离均为50km,配送中心与8个客户之间及8个客户之间相互距离及货物需求见下表:表1 客户需求表2 点对间距表运行结果如下:五、 结论从以上仿真结果可知,用遗传算法通过选择,交叉,变异等操作最终求得配送车辆物流问题中的最短路径,减少了车辆资源和时间的浪费,缩短了运输成本。同时,在车辆调度问题中,进一步加入时间窗等参数的车辆调度问题的遗传算法的求解,还
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 求解 VRP 问题 技术 报告
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。