基于改进型遗传算法的多目标配送线路优化仿真.pdf
《基于改进型遗传算法的多目标配送线路优化仿真.pdf》由会员分享,可在线阅读,更多相关《基于改进型遗传算法的多目标配送线路优化仿真.pdf(6页珍藏版)》请在咨信网上搜索。
1、 年第 卷第 期总第 期物流工程与管理 物流技术:./.基于改进型遗传算法的多目标配送线路优化仿真 张杨阳张革伕贺 娜梁腾飞(.南华大学 经济管理与法学学院湖南 衡阳.南华大学 计算机科学与技术学院湖南 衡阳)【收稿日期】基金项目:大学生创新课题项目:叫驴子(编号:)【作者简介】张杨阳女硕士研究生研究方向:物流与供应链管理张革伕男博士副教授硕士研究生导师研究方向:物流与供应链管理人工智能贺 娜女本科研究方向:工商管理 【摘 要】优化配送路径对节约物流成本、提高服务水平具有重大意义 文中构建了一个物流中心和 个配送节点应用场景以配送线路总长度最短为目标提出了一个改进型多种群竞争遗传算法模型 通过
2、随机聚类来形成比较稳定的初始代使用“最优 最劣”“次优 次劣”的选择交叉繁殖策略以及引入基于邻接点的自我繁殖可改善陷入局部过早收敛情况多种群竞争模式能提高随机向优的命中率 基于 的仿真实验表明改进后的遗传算法结果更优、更可靠稳定性更好对于生产实践极具指导价值【关键词】遗传算法旅行商问题物流配送【中图分类号】【文献标识码】【文章编号】()(.)【】.“.”“.”.【】引言随着新营销渠道电子商务的不断发展物流专业化技术水平也不断提高但多目标物流配送作为现代化物流系统的重要一环仍存在很多问题并有待优化 多目标配送是指按用户的订货要求在配送中心进行分货、配货并将配好的货物及时送交多个不同位置收货人的活
3、动 采取合适的配送策略选择合适的配送路线对提高物流公司的服务水平降低运货费用和增加经济效益都具有重要意义 目前多目标配送线路的选择与规划大多由配送员的经验决定多目标配送路径规划属于组合优化问题可以将其抽象为典型的组合优化问题 旅行商问题()来研究 最早提出解决 问题的方法是穷举法列举问题的可能解再计算寻找最优但是在需求点和路段较多的情况下使用穷举法不仅效率低还会出现解的遗漏计算量巨大很难精准地获得最优解 当前随着人工智能的发展有许多全局的启发式智能优化算法被用于解决 问题 例如郑娟毅等提出了一种改进的蚁群算法改进信息素浓度的设定加强了算法的全局搜索性可以求解不同规模的旅行商问题 张海南等用动态
4、进化与交互学习机制融合改进蚁群算法采用多组不同规模的 进行仿真得出物流工程与管理第 卷最优解 石红国等利用 神经网络()与归约法相结合的方法求解大规模的旅行商问题 蒋冬梅用粒子群优化算法()求解 问题并在 平台下实现 虽然这些算法为解决 给出了多种有效途径但是仍然存在一定的问题 比如改进后的蚁群算法应用在大规模的 问题上的精确度明显降低对模型参数和初始条件具有很强的依赖性求解的结论稳健性较低而 研究处于初期还有很多问题值得研究如算法的收敛性、理论依据等 使用遗传算法来求解也很常见但其过早收敛和随机性对其应用存在不少问题传统 模型求解算法前提假设是两个节点之间车辆来回配送的距离一样 但现实中受道
5、路结构与河流桥梁布局的影响两个节点之间车辆来程与去程的距离可能完全不一样这给多目标配送路线规划求解带来了困扰实验表明用常见算法模型解决此类问题通常难以奏效 构造运行性能更好、结果更稳健的算法对多目标配送路径的选择优化有重要的实践价值 研究综述遗传算法最早是在二十世纪六十年代由美国的.教授提出的它是一类借鉴生物界的适者生存、优胜劣汰遗传机制演化而来的随机化搜索方法 它将一个问题的候选解抽象为染色体通过选择、交叉、变异等遗传操作向更好的解进化得出问题的最优解 遗传算法主要被用于解决标准搜索方法难以解决的复杂和非线性的问题 等使用轮盘赌法和混合交叉对遗传算子进行改进找到了更短的最优车辆路线 等提出了
6、一种新的交叉算子方式 两部分染色体交叉()在最小化问题搜索空间大小的改进上又增强了遗传算法的搜索能力提高了遗传算法解的质量 等针对遗传算法在求解旅行商问题()时存在收敛速度慢、解质量低、易陷入局部最优等问题提出了一种带跳跃基因和启发式算子的遗传算法()并设计了一种改进的组合适应度函数的轮盘赌选择和双向启发式交叉()算子以保持种群多样性增强开发能力 针对共享单车的逆向物流问题应用帕累托原理的财富分配不平衡理论来改进遗传算法的选择算子提高了算法的全局搜索能力和收敛速度多数学者针对标准的遗传算法“早熟”即过早收敛和易陷入局部最优等问题提出对算法的三个遗传算子:选择、交叉和变异进行改进保证寻优时种群中
7、个体的多样性避免陷入局部最优 本文提出了一种在遗传操作后再通过搜索基因近邻点位的方法来产生优质遗传基因组在进化中不断增加个体适应度并进行多种群竞争从而获得最优解 物流配送问题场景随着电子商务下沉到农村快递配送的效率效益问题迅速凸显给配送企业带来了困扰 不仅仅在乡村城镇中的冷链配送、连锁配送、快递配送等企业实际都存在配送路线规划不合理高度制约服务成本问题 为了提高效益配送企业都会选择一次性地尽可能多装配包裹通常单次配送达到 个单子收货地址组达到 个 例如下面的仿真实例面向村落递送的班车化服务中物流中心承揽了 个包裹收货地址涉及 个村落分发点(包裹驿站)地名地址信息如表 所示表 地名地址信息序号地
8、名经度纬度序号地名经度纬度配送中心.马 头 村 第 村民小组.石市村第 村民小组.马 头 村 第 村民小组.石市村第 村民小组.马 头 村 第 村民小组.台 凡 村 第 村民小组.石马村第 村民小组.台凡村第 村民小组.石马村第 村民小组.按照约定配送车从配送中心出发最后必须回到配送中心 配送中心到各个节点以及各个节点间的车辆行驶距离可以通过异步调用百度地图 来获得 显然车辆在两个点之间来回的行车距离可能存在较大差异其原因在于存在护栏隔离带或单行线 表 为所构建的两两节点间的车辆行驶距离矩阵(部分数据)序号、等仅代表配送节点非配送顺序 代表配送中心表 配送车辆行驶距离矩阵序号.配送车辆必须每个
9、节点都送到例如 个网点都需要到达所有节点的任意一种排列组合即构成车辆的一条行驶线路 显然车辆的运行成本直接与行走线路的长度直接相关本研究的目的就是要从线路中寻找出最短的一条 改进型遗传算法遗传算法有两个明显的缺陷:一是缺乏有效规避机制进化容易过早陷入局部最优二是过于随机导致结果缺乏稳定性 本研究提出三种策略来改进遗传算法一是聚类分段二是进化启发三是多种群竞争.规划模型上述物流配送路径优化问题可以描述为:已知各个需求点(顾客)的位置信息和需求量由一辆汽车从配送中心向 个需求点(配送节点)配送要求合理规划配送路线使路线的总行车距离最短 存在如下约束每条路线都需要从配送中心出发每个点的需求必须满足(
10、即每个点至少经过 次)车辆必须回到起点配送中心第 期张杨阳等:基于改进型遗传算法的多目标配送线路优化仿真最短路线规划数学模型的定义如式()()()()式中:表示需求点(为配送中心)表示配送顺序表示第 个被配送的需求点()表示需求点 到需求点 之间的距离(可能存在()()从式()可知除配送中心以外的节点每个节点都可被选为下一个达到的点因而至少有 种可能 当 时按选择节点排列的顺序所构成的线路数量为 个数的排列数使用穷举法或贪婪算法上述问题求解在有限时间和有限算力下基本无法完成.线路编码传统的遗传算法是对解空间内个体进行二进制编码以/串来代表个体染色体对染色体基因片段上的 串进行复制、转换操作完成
11、遗传与进化/编码串模式对于连续值类解搜索适应但是对于线路规划这种非连续值不合适本研究采用自然节点号码值序列来表示解空间内的个体基因对于任何一条可能的线路其编码形式为:显然线路规划不能单独对某个节点进行操作必须是两个节点以上对调任何两个节点的顺序都会改变线路的本质形成一条新的线路例如把 和 变换新线路为其中至少有 段路改变包括:、和 对单个节点的改变操作会形成冲突节点重复和节点丢失下面的算法研究就是要通过选择可能的初始线路改变其上的节点位置和顺序形成新线路再测量新线路的长度以寻找最短线路.启发进化法理论上通过随机操作线路上的节点使得新生线路一次比一次短随着线路节点数量的增加困难度呈指数级增加本研
12、究提出了三个进化策略:对所有节点进行聚类按就近原则排序以减小调换搜索空间这点与用聚类来进行车辆调度的目的不一样选择交叉父母代采用“最优 最劣”“次优 次劣”模式对线路上的顺路相邻点进行固化避免因随机调换错开称之为自我繁殖应用上述启发策略形成改良型遗传算法具体算法设计如下.聚类改良初始代在实际中物流配送时就近送是基本原则从配送中心出发按照远近来安排目标点但是远近受到实际道路的连接制约 文献中一般采用的是随机生成配送线路节点号序列串来构成线路这对于目标搜索空间大小没有改变 本研究采用如下聚类算法 随机生成一个线路节点序列串任取 个点作为分组中心点 将所有点逐个与任意中心点 进行连接从行车距离矩阵中
- 配套讲稿:
如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。