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

基于磁滞优化的车辆路径问题研究

作　者: 闫晓波
导　师: 吴维敏
学　校: 浙江大学
专　业: 控制理论与控制工程
关键词: 车辆路径问题图模型启发式算法智能优化算法磁滞优化算法
分类号: O224
类　型: 硕士论文
年　份: 2012年
下　载: 29次
引　用: 0次
阅　读: 论文下载

内容摘要

车辆路径问题是物流配送领域涉及到的典型问题,也是组合优化领域最为重要和流行的研究问题之一。本文研究有能力约束车辆路径问题(CVRP)。首先以数学规划模型为基础,针对CVRP分别应用磁滞优化算法(HO)和改进的磁滞优化算法进行了求解,并针对标准的测试问题,进行了实验仿真,并给出了与其它优化算法如粒子群算法(PSO)和遗传算法(GA)相比较的结果。本文首先介绍了CVRP的基本理论。在这个问题中,所有的顾客都有预先决定好的需求,每个车辆都有相同的容量约束,现在有一个从公共车场点出发的一列运输车队来服务这些顾客,最终要决定每辆车所服务的顾客,并且确定其访问顺序,从而使得总花费最小。首先给出了其图模型和数学模型。在详细说明了几种常见的智能优化方法的基本原理以后,分别给出了每种方法应用到CVRP上的过程和算法步骤。包括模拟退火算法、禁忌搜索算法、遗传算法和蚁群算法等。接着,本文首次把磁滞优化算法(HO)应用到有能力约束车辆路径问题中。HO是一种起初针对旋转玻璃模型所提出的物理优化算法,最早由Zarand等人于2002年提出。HO的核心在于利用交流去磁过程达到优化的效果。具体来说,通过在原来模型中引入一个幅值逐步衰减的外部交变磁场,随着外部场强方向的依次交替变化,来优化目标函数,使其逐步趋于最优解。Zarand等人曾把它应用到100个城市规模的旅行商问题(TSP)求解中,并验证了该算法的有效性,本文首次把HO算法应用到有能力约束车辆路径问题中,针对5个标准的问题进行了仿真测试,实验结果表明HO算法能够找到车辆路径问题的次优解,且其解优于其它智能优化算法得到的结果。其次,本文针对有能力约束车辆路径问题提出了改进的磁滞优化算法。由于磁滞优化算法相对于模拟退火算法等其它智能算法设计更为复杂,且对于一般的优化问题来说,定义构象空间距离又相对麻烦,所以本文考虑采用改进的磁滞优化算法来求解车辆路径问题。通过定义泛化的外磁场,并且设定突变的雪崩点,本文进一步改进了基于磁滞优化算法的车辆路径问题的求解,使得算法的求解变得更加通用、简单和快速。最后,本文对全文做了总结,并对未来的研究做了展望。

全文目录

致谢  5-7
摘要  7-9
Abstract  9-13
第1章引言  13-25
  1.1 选题背景及研究意义  13-14
  1.2 车辆路径问题概述  14-17
    1.2.1 车辆路径问题的定义  14-15
    1.2.2 车辆路径问题的分类  15-16
    1.2.3 车辆路径问题与NP-hard问题  16-17
  1.3 车辆路径问题国内外研究综述  17-22
    1.3.1 精确算法  17-18
    1.3.2 启发式算法  18-19
    1.3.3 亚启发式算法  19-22
  1.4 磁滞优化综述  22
  1.5 论文主要内容  22-25
第2章有能力约束车辆路径问题的基本理论  25-39
  2.1 有能力约束车辆路径问题简介  25
  2.2 有能力约束车辆路径问题的模型及特点  25-27
    2.2.1 图模型  25-26
    2.2.2 数学规划模型  26-27
  2.3 有能力约束车辆路径问题的亚启发式算法  27-37
    2.3.1 模拟退火算法  28-30
    2.3.2 禁忌搜索算法  30-32
    2.3.3 遗传算法  32-35
    2.3.4 蚁群算法  35-37
  2.4 小结  37-39
第3章基于磁滞优化算法的车辆路径问题研究  39-63
  3.1 磁滞优化算法  39-47
    3.1.1 交流去磁过程  39-41
    3.1.2 针对自旋玻璃模型的磁滞优化过程  41-44
    3.1.3 磁滞优化算法及其应用  44-47
  3.2 车辆路径问题求解细则  47-50
    3.2.1 初始解构建方法  47-48
    3.2.2 局部邻域搜索算法  48-50
  3.3 应用磁滞优化算法求解有能力约束车辆路径问题  50-55
    3.3.1 求解基本思想  51
    3.3.2 问题的表达、参数选择及定义  51-54
    3.3.3 算法应用流程  54-55
  3.4 实例仿真及分析  55-61
  3.5 小结  61-63
第4章基于改进的磁滞优化算法的车辆路径问题研究  63-73
  4.1 问题的提出  63
  4.2 磁滞优化算法改进的基本思想和方法  63-65
    4.2.1 模拟"淬火"技术  63-64
    4.2.2 泛化外磁场定义  64-65
  4.3 应用改进的磁滞优化算法求解有能力约束车辆路径问题  65-67
    4.3.1 参数选择及定义  65-66
    4.3.2 算法应用流程  66-67
  4.4 实例仿真及分析  67-71
  4.5 小结  71-73
第5章结论与展望  73-75
  5.1 研究结论  73
  5.2 对未来研究的展望  73-75
参考文献  75-85
作者简历  85
攻读硕士学位期间所取得的科研成果  85

基于磁滞优化的车辆路径问题研究

内容摘要

全文目录

相似论文