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

基于混合遗传算法的有时间窗车辆路径问题研究

作　者: 林清国
导　师: 张强
学　校: 山东大学
专　业: 车辆工程
关键词: 有时间窗车辆路径问题遗传算法模拟退火算法禁忌搜索算法混合遗传算法
分类号: U116.2
类　型: 硕士论文
年　份: 2007年
下　载: 459次
引　用: 13次
阅　读: 论文下载

内容摘要

车辆路径问题(Vehicle Routing Problem,VRP)是对一系列己知需求量的客户,组织适当的行车线路进行服务,在不违反约束条件下,优化路线使总成本最小。有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)因其重要的现实意义备受关注,所谓时间窗即客户接受服务的时间范围。由于车辆路径问题是典型的NP难题,传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向。本文重点研究了基于混合遗传算法求解有时间窗车辆路径问题。详细分析了VRPTW的特点,界定了所研究VRPTW的基本条件,建立了相应的数学模型。根据特定的时间窗、车辆容量等条件约束,设计了VRPTW的遗传算法(Genetic Algorithm,GA)。通过对遗传算法、禁忌搜索算法(Tabu Search,TS)及模拟退火算法(Simulated Annealing,SA)的分析比较,以遗传算法为框架,融合其它两者,提出了用于VRPTW的混合遗传模拟退火算法(Genetic-SimulatedAnnealing Algorithm,GSA)及混合遗传禁忌搜索模拟退火算法(Genetic-TabuSearch-Simulated Annealing Algorithm,GTSA)。在GSA中,将模拟退火算法的Metropolis规则应用到GA的交叉操作中,让GA能够同时接收较优解和劣解,使得父代个体也参加竞争,这样不但避免了GA陷入局部最优,同时又消除了基本遗传算法由于无选择的接收新解而可能会出现的随机搜索现象;在GTSA中,把TS引入到GA的复制操作中产生新的个体,使得遗传算法中每代个体具有尽可能的多样性,从而避免了GA陷入局部最优而出现“早熟”现象,在遗传操作产生新的种群后,对新种群使用SA,以大大增加接受较优解的概率,进而提高GA的收敛性能,加速了算法的收敛。通过实例,用MATLAB编程实现了所提出的GA、GSA、GTSA三种算法,并对三者性能作了比较。可以得出,所设计的混合遗传模拟退火算法和混合遗传禁忌搜索模拟退火算法具有良好的搜索能力及计算效率,算法性能稳定、可靠。

全文目录

中文摘要  9-10
ABSTRACT  10-12
第1章绪论  12-18
  1.1 课题提出的背景及意义  12-13
  1.2 有时间窗车辆路径问题研究现状  13-17
  1.3 论文的研究内容  17-18
第2章有时间窗车辆路径问题的建模  18-26
  2.1 车辆路径问题概述  18-21
    2.1.1 车辆路径问题定义  18
    2.1.2 车辆路径问题组成  18-19
    2.1.3 车辆路径问题主要类型  19-21
  2.2 有时间窗车辆路径问题的模型  21-25
    2.2.1 时间窗问题描述  21-22
    2.2.2 有时间窗车辆路径问题的约束条件  22-23
    2.2.3 有时间窗车辆路径问题的模型  23-25
  2.3 本章小节  25-26
第3章遗传算法及其在VRPTW中的应用  26-44
  3.1 启发式算法  26-30
    3.1.1 启发式算法特点  26
    3.1.2 启发式算法的求解过程  26-27
    3.1.3 主要启发式算法  27-30
  3.2 遗传算法  30-37
    3.2.1 遗传算法基本原理  30
    3.2.2 遗传算法相关概念  30-36
    3.2.3 遗传算法基本步骤  36
    3.2.4 遗传算法基本特点  36-37
  3.3 遗传算法在VRPTW中的应用  37-42
    3.3.1 VRPTW算例  37-38
    3.3.2 VRPTW的遗传算法设计  38-40
    3.3.3 算例计算和结果分析  40-42
  3.4 本章小节  42-44
第4章混和遗传模拟退火算法及其在VRPTW中的应用  44-56
  4.1 混合遗传算法  44-46
    4.1.1 混合遗传算法基本思想  44
    4.1.2 混合遗传算法设计原则  44-45
    4.1.3 混合遗传算法基本特点  45-46
  4.2 模拟退火算法  46-51
    4.2.1 模拟退火算法概要  46-48
    4.2.2 模拟退火算法基本步骤  48-50
    4.2.3 模拟退火算法基本特点  50-51
  4.3 混和遗传模拟退火算法  51-53
  4.4 混和遗传模拟退火算法在VRPTW中的应用  53-55
  4.5 本章小节  55-56
第5章混和遗传禁忌搜索模拟退火算法及其在VRPTW中的应用  56-68
  5.1 禁忌搜索算法  56-60
    5.1.1 禁忌搜索算法基本原理  56
    5.1.2 禁忌搜索算法基本概念  56-58
    5.1.3 禁忌搜索算法运算过程  58-59
    5.1.4 禁忌搜索算法基本特点  59-60
  5.2 混和遗传禁忌搜索模拟退火算法  60-62
    5.2.1 混合遗传禁忌搜索模拟退火算法的基本思想  60-61
    5.2.2 混和遗传禁忌搜索模拟退火算法的运算过程  61-62
  5.3 混合遗传禁忌搜索模拟退火算法在VRPTW中的应用  62-64
    5.3.1 混合遗传禁忌搜索模拟退火算法设计  62-63
    5.3.2 混合遗传禁忌搜索模拟退火算法对算例的优化分析  63-64
  5.4 基于VRPTW算例的三种算法比较分析  64-66
  5.5 本章小节  66-68
总结与展望  68-70
附录  70-88
参考文献  88-92
致谢  92-94
攻读硕士学位期间发表的论文  94-95
学位论文评阅及答辩情况表  95

基于混合遗传算法的有时间窗车辆路径问题研究

内容摘要

全文目录

相似论文