基于Hadoop求解大规模VRPTW问题的并行遗传算法

发布时间：2023-09-02 13:16

　　车辆路径问题广泛应用于各个领域,不论是机器人自主无碰运动、服务网络规划等学术研究领域,还是数字地图导航、仓库AGV无导引小车运作等工业生产环境,甚至是与人们生活息息相关的快递配送业,都要用到车辆路径问题的优化理论。车辆路径问题的研究,不仅具有重要的学术研究意义,而且有重要的生产实用价值。带有时间窗的车辆路径问题在车辆路径问题的基础上考虑了时间成本的影响,更加符合实际需求。针对带有时间窗的车辆路径问题的研究已经比较成熟,包括精确算法、启发式算法、元启发式算法等,但这些算法基本都是串行的集中式算法,大都只能求解中小规模的车辆路径问题,然而现在的车辆路径问题动辄就是上千个节点的规模,加上时间窗的约束,传统串行算法求解效率比较低,短时间内很难求解出可接受解。当今大数据、云计算等计算机技术的蓬勃发展,为并行计算提供了技术支持,也为并行化解决大规模带有时间窗的车辆路径问题提供了新的思路。针对集群式并行计算具有高容错性、高扩展性、高可用性和廉价性等方面的优势,本研究选用了经典的集群分布式并行计算平台----Hadoop作为并行计算的基础架构,基于此使用MapReduce并行框架进行分布式并行算法的设...

【文章页数】：67 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 引言
    1.1 课题背景和研究意义
        1.1.1 课题背景
        1.1.2 研究意义
    1.2 论文主要内容
    1.3 论文组织结构
第2章 文献综述
    2.1 车辆路径问题
    2.2 车辆路径问题的求解方法
        2.2.1 精确算法
        2.2.2 启发式算法
        2.2.3 元启发式算法
        2.2.4 人工智能方法
    2.3 遗传算法求解车辆路径问题
    2.4 MapReduce与 Hadoop的应用
    2.5 遗传算法与MapReduce的结合应用
    2.6 本章小结
第3章 Hadoop平台的搭建
    3.1 Hadoop平台简介与准备工作
    3.2 Hadoop平台的搭建与调试
    3.3 本章小结
第四章 算法设计
    4.1 问题描述
    4.2 遗传算法求解VRPTW
        4.2.1 基因编码
        4.2.2 初始化种群
        4.2.3 适应度评价
        4.2.4 选择精英解
        4.2.5 选择交叉父体
        4.2.6 交叉操作
        4.2.7 变异操作
        4.2.8 选择幸存解
        4.2.9 算法影响因素
    4.3 遗传算法并行模型
    4.4 MapReduce框架
        4.4.1 Mapper的设计
        4.4.2 Reducer的设计
    4.5 基于Hadoop的并行遗传算法的流程控制
        4.5.1 Hadoop系统基础架构分析
        4.5.2 算法整体流程的设计与控制
    4.6 算法回顾
    4.7 本章小结
第5章 数值实验
    5.1 参数设置
        5.1.1 Hadoop集群参数配置与调优
        5.1.2 初始解参数的设置
        5.1.3 遗传操作参数的设置
    5.2 算例结果及分析
        5.2.1 算法有效性的数值验证
        5.2.2 串行算法与并行算法的对比
        5.2.3 处理器数量对计算时间的影响
        5.2.4 处理器配置对计算时间的影响
    5.3 本章小结
第6章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
个人简历、在学期间发表的学术论文与研究成果



本文编号：3845268