基于双层遗传算法的MDARP研究

论文摘要

多车场车辆弧路径问题(MDARP:Multiple Depot Arc Routing Problem)与我们熟悉的车辆路径问题(VRP)的最大区别就在于:VRP中的需要进行服务的是一系列点,而MDARP中需要进行服务的则是一系列边,且有数个车场,车辆可以从每个车场出发最终返回到原车场。目前,对车辆路径问题的研究主要是针对VRP,对于多车场的VRP(Multiple Depot Vehicle Routing Problem:MDVRP)的研究也取得了一定的成果,但是对于大规模的MDARP研究,据所查文献资料来看,目前采用进化计算方法对大规模的MDARP研究还没有相关报导,而只有少量文献对ARP的研究。MDARP在我们的日常生活中也有一些应用的实例,如道路清洁,垃圾回收,输电线路检测等,我们可以借鉴ARP和MDVRP的研究方法对MDARP的进行研究,以解决一些实际问题。对于MDARP问题的研究,本文做的主要工作和获得的研究成果如下:①本文采用双层遗传算法对MDARP进行求解,利用了遗传算法的生物进化机制,对问题的解进行全局搜索,从而寻求满意解。生物学已经证明,“近亲繁殖”不利于群体的健康发展,在同一种群的不同群体之间,交换越深入,后代会越优秀。因此,在双层遗传算法中,除了各子种群内部个体(内层遗传算子)之间进行遗传操作外,我们在各个父种群间(外层遗传算子)也进行类似的遗传操作,以加强群体间的信息交换,改善寻优能力。②对MDARP的数学模型进行探讨,借鉴MDVRP的数学模型构造了MDARP的数学模型,并在模型计算的基础上,针对传统遗传算法编码表达能力不够直观的缺点,本文对染色体编码机制和种群结构进行了改进,设计出了既反映多车场服务组合关系又能反映路径信息的新的编码方式——“双层整数编码方式”,其中外层遗传算法用来确定车场与服务弧的优化组合,内层遗传算法用来最终求解所有的车辆路径,不仅提高了编码方式的表达能力,而且编码码串长度显著下降,避免二进制编码产生的不可行解,提高了选择计算能力。③借鉴整数编码遗传交叉算子在函数求极值进化算子设计方面的经验,结合本文的遗传算子特点,在内层遗传算子进化过程中引入了初始种群生成策略和多样性染色体交叉、增强型染色体邻域搜索等遗传算子进化策略,克服了由于传统遗传算法的随机性所带来的早熟收敛、稳定性差等缺点,使算法达到了良好的收敛性与稳定性。④针对MDARP问题,结合本文提出的双层遗传算法,以某城区洒水车行驶路线为原型,对不同车场数目、不同服务边数量的几种情形进行实验测试,得到了合理的科学的车辆安排方案,比现行的车辆安排方案节省总路程20%以上,并提高了安排效率,验证了本文提出的双层遗传算法的正确性与合理性。基于双层遗传算法的MDARP的研究综合了车辆路径优化领域与遗传算法领域的研究成果,提出具有可扩展性、实时性、稳定性特点的路径优化机制,解决了车场数量和服务对象数量变化车辆安排困难的矛盾,开辟了MDARP的研究新途径。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景及意义
• 1.2 研究内容及技术路线
• 1.3 论文的创新点
• 1.4 论文的内容与结构
• 2 MDARP 相关研究背景
• 2.1 VRP 和ARP 介绍
• 2.2 MDVRP 和MDARP 的研究现状
• 2.2.1 VRP 的研究现状
• 2.2.2 MDVRP 的研究现状
• 2.2.3 MDARP 的研究现状
• 2.3 研究中存在的问题
• 2.4 本章小结
• 3 MDARP 的数学模型及解决思路
• 3.1 MDARP 的描述与数学模型
• 3.2 MDARP 的解决思路
• 3.3 双层遗传算法概述
• 3.3.1 遗传算法简介
• 3.3.2 双层遗传算法介绍
• 3.4 本章小结
• 4 MDARP 的双层遗传算法设计
• 4.1 染色体编码及结构
• 4.2 外层染色体进化过程
• 4.3 内层染色体进化过程
• 4.3.1 内层染色体初始化
• 4.3.2 基于多样性方法的染色体交叉
• 4.3.3 基于邻域搜索的染色体自然选择
• 4.3.4 参数设置及终止条件
• 4.4 双层遗传算法的流程与步骤
• 4.5 本章小结
• 5 算法实验测试
• 5.1 实验及结果分析
• 5.2 扩展实验
• 5.3 本章小结
• 6 总结与展望
• 6.1 研究总结
• 6.2 研究展望
• 致谢
• 参考文献
• 附录