有容约束的混合中国邮递员问题及其遗传算法

发布时间：2017-05-19 10:05

  本文关键词：有容约束的混合中国邮递员问题及其遗传算法，由笔耕文化传播整理发布。

【摘要】：随着信息化的不断发展,人们对网购的依赖性越来越强。同时,都市化进程的加快与城市机动车辆的增多,使得货物的派发效率成为销售商、物流公司、顾客强烈关注的问题,也是吸引研究者们的课题之一,因此中国邮递员问题应运而生。本文从实际问题出发并结合遗传算法,研究有容约束的混合中国邮递员问题。首先,从图的定义、分类、矩阵表示等方面阐述了网络的基本知识；概述了中国邮递员问题研究现状；从染色体的编码、解码、遗传操作等方面阐述了遗传算法的基本思想,并给出了算法的基本步骤与程序流程图。其次,给出了基于邮递员的最大工作时间约束和运载车辆的载重约束的中国邮递员问题的数学模型；分析了前人利用遗传算法求解中国邮递员问题的局限性,采用一种新的染色体优先权编码方案和基于“边走边服务”策略的解码方案,克服了遗传算法求解有容约束的混合中国邮递员问题的局限性。其三,从网络拓扑结构和边权两个属性出发,对动态网络进行了分类,基于网络分类提出了两种动态混合中国邮递员问题,针对拓扑结构动态混合中国邮递员问题,设计了网络拓扑结构的依概率动态化算法；针对边权动态混合中国邮递员问题的求解需要,对工作时段内的网络边权属性进行分类,提出了一种使用惩罚因子的网络边权动态化策略。其四,由于边权动态混合中国邮递员问题的时变性和复杂性,设计了一种基于“服务优先策略”的动态边权下路由的工作时间解码算法,克服了边权动态混合网络上弧路由时间的计算复杂性。最后,通过实例验证了上述算法的可行性和有效性。
【关键词】：中国邮递员问题 遗传算法 动态网络 网络拓扑 网络边权 有容约束 混合网络
【学位授予单位】：西北师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP18
【目录】：

• 摘要9-10
• Abstract10-12
• 第1章 绪论12-30
• 1.1 网络的有关知识12-18
• 1.2 路由问题概述18-19
• 1.3 中国邮递员问题概述19-23
• 1.4 遗传算法理论研究23-28
• 1.5 本文主要工作28-30
• 第2章 基于可行路径的最短路径算法30-36
• 2.1 最短路径算法概述30
• 2.2 基于可行路径的最短路径算法30-32
• 2.3 实例分析32-34
• 2.4 结论34-36
• 第3章 有容约束的静态混合中国邮递员问题36-52
• 3.1 问题描述及其假设36-38
• 3.2 数学模型及其意义38-40
• 3.3 网络结构分析40-42
• 3.4 遗传算法设计42-46
• 3.5 实例分析46-50
• 3.6 结论50-52
• 第4章 拓扑结构动态的混合中国邮递员问题52-66
• 4.1 动态网络概述52
• 4.2 拓扑结构动态的混合中国邮递员问题52-55
• 4.3 网络拓扑结构动态化算法设计55-58
• 4.4 遗传算法设计58
• 4.5 实证分析58-64
• 4.6 结论64-66
• 第5章 边权动态的混合中国邮递员问题66-80
• 5.1 网络边权依赖时间的动态化策略66-67
• 5.2 边权动态的混合中国邮递员问题67-70
• 5.3 算法设计70-74
• 5.4 实例分析74-78
• 5.5 结论78-80
• 第6章 总结80-82
• 参考文献82-88
• 攻读硕士学位期间发表的论文88-90
• 致谢90

【相似文献】

中国期刊全文数据库 前10条

1 吴杰;;求解中国邮递员问题的一种思路[J];科技资讯;2007年14期

2 高敬振;高勃;;中国邮递员问题50年[J];运筹学学报;2013年01期

3 忻展红;大城市邮政投递问题及其算法探讨[J];北京邮电大学学报;1994年03期

4 冯俊文;;中国邮递员问题的整数规划模型[J];系统管理学报;2010年06期

5 汪海森;林耿;卓彩娥;;中国邮递员问题的匹配算法[J];长江大学学报(自科版);2013年25期

6 汤泽滢,谢政;水灾地区邮递员问题[J];应用数学与计算数学学报;2000年01期

7 杨万钟;李丹;;关于邮路选择问题[J];辽宁师范大学学报(自然科学版);1986年01期

8 覃太贵,杨磊;混合中国邮递员问题的扰动恢复讨论及其一种启发式算法[J];湖北师范学院学报(自然科学版);2005年02期

9 汤泽滢,卢汉清;战争地区邮递员问题[J];应用数学与计算数学学报;2002年01期

10 李念祖;;关于中国邮递员问题的最优完全子图算法[J];上海师范大学学报(自然科学版);2006年04期

中国硕士学位论文全文数据库 前1条

1 田贵龙;有容约束的混合中国邮递员问题及其遗传算法[D];西北师范大学;2015年

  本文关键词：有容约束的混合中国邮递员问题及其遗传算法，，由笔耕文化传播整理发布。

本文编号：378373