论文部分内容阅读
车辆路径问题广泛应用于各个领域,不论是机器人自主无碰运动、服务网络规划等学术研究领域,还是数字地图导航、仓库AGV无导引小车运作等工业生产环境,甚至是与人们生活息息相关的快递配送业,都要用到车辆路径问题的优化理论。车辆路径问题的研究,不仅具有重要的学术研究意义,而且有重要的生产实用价值。带有时间窗的车辆路径问题在车辆路径问题的基础上考虑了时间成本的影响,更加符合实际需求。针对带有时间窗的车辆路径问题的研究已经比较成熟,包括精确算法、启发式算法、元启发式算法等,但这些算法基本都是串行的集中式算法,大都只能求解中小规模的车辆路径问题,然而现在的车辆路径问题动辄就是上千个节点的规模,加上时间窗的约束,传统串行算法求解效率比较低,短时间内很难求解出可接受解。当今大数据、云计算等计算机技术的蓬勃发展,为并行计算提供了技术支持,也为并行化解决大规模带有时间窗的车辆路径问题提供了新的思路。针对集群式并行计算具有高容错性、高扩展性、高可用性和廉价性等方面的优势,本研究选用了经典的集群分布式并行计算平台----Hadoop作为并行计算的基础架构,基于此使用MapReduce并行框架进行分布式并行算法的设计与优化,用以解决大规模带有时间窗的车辆路径问题。本研究在基础算法的设计上,选取了具有天然并行特性的遗传算法。为了最大限度地降低遗传算法的巨大计算开销,本文选择并改进了比较优秀的选择、交叉、变异算子。在MapReduce框架中,map和reduce阶段的设计上,充分考虑了大规模车辆路径问题的遗传基因的长度带来的影响,同时考虑了如何降低集群间信息传输的压力,最终采用粗粒度并行模型----遗传算法岛屿模型嵌入MapReduce框架。在键值对的处理上,利用键值对中“键”的不变性保持遗传算法解个体和适应度值的一致性,并将迁徙操作与shuffle阶段结合起来,保证迁徙过程顺利执行。本文使用带有时间窗的车辆路径问题的大规模标准算例----Gehring&Homberger(1999)算例进行了算法验证,分别从并行算法的有效性、串行和并行算法的对比、集群处理器数量对算法的影响和处理器配置对算法的影响等四个方面进行了数值实验与精确的分析,并论述了本文研究的有效性和重要价值。