学位论文 > 优秀研究生学位论文题录展示

改进蚁群算法对CVRP及机器人路径规划问题的应用研究

作　者: 王沛栋
导　师: 冯祖洪
学　校: 北方民族大学
专　业: 计算机应用技术
关键词: CVRP 路径规划蚁群算法移动机器人栅格法
分类号: TP242
类　型: 硕士论文
年　份: 2009年
下　载: 37次
引　用: 0次
阅　读: 论文下载

内容摘要

带负载的车辆路径问题(CVRP)和机器人路径规划问题都是著名的组合优化问题,现实中的很多问题都可以抽象为这两种问题。对于它们的求解方法有很多,例如:遗传算法、人工神经网络、模拟退火等等,但大都存在着执行时间长,效率不高等问题。蚁群算法自上个世纪90年代提出以来,在许多领域都得到了广泛应用,取得了不错的效果。与其它算法相比,蚁群算法具有更强的正反馈性、强启发性、协调性。本文针对上述两种问题的特点,分别提出两种改进的蚁群算法,并进行了实验仿真。实验结果证明了改进算法的有效性,本文的主要内容如下:针对CVRP问题,设计了一种改进的蚁群算法,其中提出了四点改进策略:1.初始化策略,初始化时,将蚂蚁都放置在配送中心,按照路径选择机制来选择初始点,增加了蚂蚁走出最优路径的可能性。此外,细化了路径上信息素的初始值;2.路径选择策略,使用蚂蚁群系统路径选择机制,以路径上的节约量作为启发信息,并且以小窗口策略来限制每次选取的客户数量,增强了选择的正确性,加快了解的收敛的速度;3.信息素更新策略,使用信息素局部更新与全局更新相结合的方法。在全局更新中提出一种新的动态更新方式,它能够根据蚂蚁构建路径的情况来调配最优路径上信息素值,使算法不致于“停滞”;4.局部搜索策略,除使用2-opt方法对每个车辆构成的路径进行调配处理外,加入客户插入、交换运算,增加了搜索的多样性,进一步加快了解的收敛的速度。针对机器人路径规划问题,提出了一种静态环境下机器人路径规划的改进蚁群算法。该算法使用栅格法对机器人的工作空间进行建模。通过模拟蚂蚁的觅食行为,使蚂蚁在起始点和目标点之间采用折返的方式完成最优路径的搜索,增强了蚂蚁搜索的多样性;搜索过程采用“惯性原则”和最大信息素搜索策略,使蚂蚁对最优路径更为敏感;同时,根据信息素在栅格模型中散播的特点,提出一种新的信息素更新策略和散播方式,加快了解的收敛速度。仿真结果验证了该算法的有效性,即使在障碍物复杂的地理环境下,用该算法也能迅速规划出最优路径。

全文目录

摘要  3-4
ABSTRACT  4-7
第一章绪论  7-10
  1.1 课题背景  7-8
  1.2 研究内容  8
  1.3 课题意义  8-9
  1.4 本文结构  9-10
第二章蚂蚁群算法  10-17
  2.1 蚂蚁群算法的基本原理  10-11
  2.2 蚁群优化算法  11-14
    2.2.1 基本蚁群系统模型（Ant System, AS 算法）  11-12
    2.2.2 蚂蚁群系统模型（Ant Colony System, ACS 算法）  12-13
    2.2.3 基于图搜索的蚂蚁系统模型（Graph-based Ant System, GBAS 算法）  13-14
  2.3 蚁群优化算法参数及意义  14-15
    2.3.1 蚂蚁数目m  14
    2.3.2 信息素蒸发率ρ  14
    2.3.3 启发因子α和β  14-15
  2.4 蚁群优化算法性能与特点  15-16
  2.5 小结  16-17
第三章 CVRP 及机器人路径问题  17-25
  3.1 车辆路由问题  17-20
    3.1.1 车辆路由问题  17
    3.1.2 VRP 问题发展的三个阶段  17-18
    3.1.3 CVRP 问题描述  18
    3.1.4 CVRP 的研究现状  18-20
  3.2 机器人路径规划问题  20-23
    3.2.1 机器人路径规划  20-21
    3.2.2 机器人路径规划的分类  21
    3.2.3 机器人路径路径规划的环境表达  21-22
    3.2.4 机器人路径规划的路径搜索  22-23
  3.3 本文主要解决的问题和任务  23-24
  3.4 小结  24-25
第四章 CVRP 及机器人路径问题的改进蚁群算法  25-43
  4.1 CVRP 问题的数学模型  25-26
  4.2 蚁群算法应用于CVRP 研究现状  26-28
  4.3 CVRP 问题的改进蚂蚁群算法设计  28-34
    4.3.1 算法改进及说明  28-33
    4.3.2 算法步骤  33-34
  4.4 机器人路径规划环境的构建  34
  4.5 机器人路径规划问题的数学模型  34-35
  4.6 蚁群算法对机器人路径规划问题研究现状  35-37
  4.7 机器人路径规划问题的改进蚂蚁群算法设计  37-40
    4.7.1 算法改进及说明  37-39
    4.7.2 算法步骤  39-40
  4.8 改进算法的时间复杂度及收敛性分析  40-42
  4.9 小结  42-43
第五章仿真实验与结果分析  43-61
  5.1 基于CVRP 问题的改进蚂蚁群算法  43-52
    5.1.1 插入、交换运算分析  43-45
    5.1.2 参数设置与分析  45-49
    5.1.3 改进算法仿真实验与性能对比  49-52
  5.2 基于机器人路径规划问题的改进蚂蚁群算法  52-58
    5.2.1 参数设置与分析  52-55
    5.2.2 改进算法仿真实验与性能对比  55-58
  5.3 综合实验与分析  58-60
  5.4 小结  60-61
第六章总结与展望  61-63
  6.1 总结  61
  6.2 进一步的工作  61-63
致谢  63-64
参考文献  64-67
攻读学位期间发表的学术论文  67

改进蚁群算法对CVRP及机器人路径规划问题的应用研究

内容摘要

全文目录

相似论文