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

遗传算法在物流系统优化中的应用研究

作　者: 姜昌华
导　师: 胡幼华
学　校: 华东师范大学
专　业: 系统分析与集成
关键词: 遗传算法仿真优化候选解收集器旅行商问题 K近邻点集车辆路径问题双层染色体编码方案子路径交换算法
分类号: TP18
类　型: 博士论文
年　份: 2007年
下　载: 2179次
引　用: 15次
阅　读: 论文下载

内容摘要

物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热点。库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。本文的主要研究工作及贡献可归纳如下:(1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产生的Pareto解;提出了M精英选择算子,用于保护潜在的最优个体,使它们在交叉、变异算子中不被破坏。针对两种常用的库存控制策略进行了仿真优化的实验,结果表明本文提出的仿真优化方法是有效的。(2)旅行商问题(TSP)是车辆路径问题的子问题。为了求解TSP问题,研究了常用于TSP问题的三种交叉算子的优化效果,提出了一种求解TSP问题的高效混合遗传算法HGA-TSP。在该算法中以变形的OX算子作为交叉算子,以2-opt算法作为遗传算法的变异算子;提出了K近邻点集的概念以缩减搜索空间并提高算法的时间效率。(3)将单配送中心,多辆运输车且无约束的车辆路径问题建模成具有总路径长度最短、子路径长度均衡性好这两个目标的双目标多旅行商问题(MTSP),并基于HGA-TSP算法,研究了三种求解上述问题的解决方案。(4)对于带能力约束的车辆路径问题(CVRP),提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小,从而提高搜索效率并降低计算时间。子路径交换算法可以有效提高遗传算法的求解精度。基于上述双层染色体编码方案和子路径交换算法,设计了两种求解CVRP问题的混合遗传算法,分别是HGA-CVRP算法和HGA-SE-CVRP算法。(5)对于带时间窗约束的车辆路径问题(VRPTW,首先改进了双层染色体编码方案,以便在编程实现时更方便地进行子路径的处理。然后研究了遗传算法与邻域搜索算法的结合方式,在遗传算法中引入了带克隆操作的邻域搜索算子。最后提出了一种求解VRPTW问题的新型混合遗传算法HGA-VRPTW。(6)综合应用了面向对象分析与设计、多线程、UML等先进的软件开发方法与技术,设计并开发了VRP仿真实验室,这是一个用于研究车辆路径问题的软件包,具有使用简便、界面美观的特点。VRP仿真实验室在本文的研究中发挥了重要的作用,是研究车辆路径问题的有力工具。本文对大量的基准测试实例(Benchmark)进行了仿真计算,计算结果表明,本文所提出的一系列算法能有效求解物流系统中的库存优化问题与车辆路径问题。

全文目录

论文摘要  6-8
Abstract  8-14
第1章绪论  14-22
  1.1 本文的研究背景及意义  14-17
    1.1.1 物流系统及其优化  14-15
    1.1.2 优化问题  15-16
    1.1.3 研究意义  16-17
  1.2 国内外研究现状  17-18
  1.3 本文的研究工作  18-20
    1.3.1 本文的研究内容  18-19
    1.3.2 研究思路与方法  19
    1.3.3 本文的主要贡献  19-20
  1.4 论文的组织  20-22
第2章智能优化算法概述  22-36
  2.1 智能优化算法  22-25
    2.1.1 优化算法  22-23
    2.1.2 智能优化算法简介  23-25
    2.1.3 智能优化算法的特点  25
  2.2 遗传算法  25-35
    2.2.1 遗传算法中的概念  26-29
    2.2.2 遗传算法的基本思想  29
    2.2.3 基本遗传算法描述  29-30
    2.2.4 应用遗传算法求解问题的步骤  30-32
    2.2.5 模式定理与积木块假设  32-34
    2.2.6 遗传算法的优缺点  34-35
  2.3 小结  35-36
第3章库存系统仿真及优化  36-54
  3.1 引言  36-37
  3.2 离散事件系统仿真优化  37-40
    3.2.1 离散事件系统  37-39
    3.2.2 离散事件系统仿真的优化  39-40
  3.3 随机(s，S)库存系统仿真优化  40-47
    3.3.1 随机(s，S)库存系统描述  40-41
    3.3.2 随机(s，S)库存系统的仿真模型  41-42
    3.3.3 仿真优化算法设计  42-45
    3.3.4 仿真计算与分析  45-47
  3.4 随机(Q，r)库存系统仿真优化  47-52
    3.4.1 随机(Q，r)库存系统描述  48-49
    3.4.2 随机(Q，r)库存系统的仿真模型  49
    3.4.3 仿真优化算法设计  49-51
    3.4.4 仿真计算与分析  51-52
  3.5 小结  52-54
第4章求解TSP问题的混合遗传算法  54-66
  4.1 引言  54-55
  4.2 问题描述与数学模型  55
  4.3 求解TSP问题的常用交叉算子  55-58
  4.4 2-OPT算法  58
  4.5 求解TSP问题的HGA-TSP算法  58-60
    4.5.1 HGA-TSP的计算步骤  59
    4.5.2 提高算法时间效率的改进方法  59-60
  4.6 仿真计算与分析  60-65
    4.6.1 三种交叉算子的比较  61-62
    4.6.2 K近邻点集对算法时间效率的影响  62
    4.6.3 HGA-TSP算法的优化效果  62-64
    4.6.4 HGA-TSP算法与问题规模的关系  64-65
  4.7 小结  65-66
第5章双目标MTSP问题的模型与算法  66-74
  5.1 引言  66
  5.2 数学模型  66-67
  5.3 道路网络预处理  67-70
    5.3.1 Dijkstra算法  67-68
    5.3.2 Floyd算法  68-70
  5.4 双目标MTSP的解决方案  70
  5.5 仿真计算与分析  70-73
    5.5.1 本文三种解决方案的对比  71-73
    5.5.2 本文解决方案与其它文献的对比  73
  5.6 小结  73-74
第6章求解CVRP问题的混合遗传算法  74-94
  6.1 引言  74-76
  6.2 问题描述与数学模型  76-77
  6.3 求解CVRP问题的HGA-CVRP算法  77-84
    6.3.1 HGA-CVRP算法  77
    6.3.2 双层染色体编码方案  77-79
    6.3.3 选择算子  79
    6.3.4 交叉算子  79-80
    6.3.5 2-OPT变异算子  80
    6.3.6 HGA-CVRP的计算步骤  80
    6.3.7 仿真计算与分析  80-84
  6.4 求解CVRP问题的HGA-SEA-CVRP算法  84-93
    6.4.1 子路径交换算法SEA的原理  85-87
    6.4.2 HGA-SEA-CVRP的计算步骤  87-88
    6.4.3 仿真计算与分析  88-93
  6.5 小结  93-94
第7章求解VRPTW问题的混合遗传算法  94-117
  7.1 引言  94-95
  7.2 问题描述与数学模型  95-96
  7.3 求解VRPTW问题的HGA-VRPTW算法  96-103
    7.3.1 改进的双层染色体编码方案  96-97
    7.3.2 选择算子  97
    7.3.3 交叉算子  97-98
    7.3.4 变异算子  98
    7.3.5 邻域变异算子  98-99
    7.3.6 克隆算子  99-100
    7.3.7 邻域搜索算子  100-102
    7.3.8 HGA-VRPTW的计算步骤  102-103
  7.4 仿真计算与分析  103-116
    7.4.1 Solomon 50仿真计算与分析  103-111
    7.4.2 Solomon 100仿真计算与分析  111-116
  7.5 小结  116-117
第8章 VRP仿真实验室的设计与实现  117-128
  8.1 引言  117-118
  8.2 VRP仿真实验室的设计  118-121
    8.2.1 设计目标  118
    8.2.2 体系结构与类的设计  118-121
  8.3 VRP仿真实验室的实现  121-127
  8.4 小结  127-128
第9章总结与展望  128-131
  9.1 本文的主要工作及研究结论  128-130
  9.2 展望  130-131
附录1: 56个SOLOMON 50问题的详细解  131-138
附录2: 9个SOLOMON 100问题的详细解  138-141
参考文献  141-149
攻读博士学位期间发表论文及科研情况  149-150
致谢  150

遗传算法在物流系统优化中的应用研究

内容摘要

全文目录

相似论文