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

遗传算法在VRP中的应用与研究

作　者: 王刚
导　师: 池洁
学　校: 重庆交通大学
专　业: 系统工程
关键词: 遗传算法 VRP 配送成本遗传算子仿真
分类号: TP18
类　型: 硕士论文
年　份: 2011年
下　载: 146次
引　用: 0次
阅　读: 论文下载

内容摘要

在科学技术飞速发展的今天,物流业面临着更多的挑战,要想在挑战中获胜,就要进行变革,而在创新变革的过程中,由于运输成本占物流总成本的50%以上,因此,如何优化配送路径也就成为了物流企业最关心的课题。车辆路径问题(Vehicle Routing Problem,简称VRP)是一个复杂的组合优化问题,针对这一问题的研究已经越来越广泛,运输路径的好坏将严重影响配送的速度、成本和用户满意度等,因此,本文应用遗传算法来优化车辆路径的问题,这对企业实现降低运营成本、增强顾客满意度、提高服务质量等都有很高的参考价值。目前对于车辆路径问题的研究还处于探索阶段,还没有一种万能的方法适合所有的问题模型。在考虑车辆路径问题的约束方面也不够全面,很多研究都仅仅局限于满足车载量约束等初级阶段,没有考虑到时间窗约束、客户满意度约束等。针对问题的最终目标,很多研究仅仅考虑路径最短,而不注重配送车辆数目、客户配送等级等问题,导致总配送成本的提高,本文针对这些问题做了进一步的研究,考虑了时间成本、客户满意度等问题,使总物流成本得到了降低,提高了企业的经济效益。本文主要的研究内容为:首先,系统地介绍了车辆路径问题以及各类算法的相关理论知识,并在此基础上深入分析此问题模型,通过对现有的解决车辆路径问题的方法进行研究,采用局部改进的遗传算法解决车辆路径问题。其次,考虑了车辆路径问题中的车载量约束、时间窗约束、客户满意度约束等,完善了问题模型,并对模型进行了优化,使模型在满足所有条件的前提下更加简化,更容易算法的实现。对遗传算法采用自然数编码策略,使其更容易满足不同模型的需求;通过扫描法生成算法的初始种群,一定程度上避免了纯随机策略导致的初始种群适应值过低的现象,加快了算法的收敛速度;采用排序法进行遗传算子的选择,使适应值高的个体遗传到下一代的概率得到了提高;将逆转算子与变异算子结合,使变异的过程更具规则性,同时降低了优良基因缺失的概率。对于算法的设计,每一个步骤都降低随机性选取的概率,加快算法的收敛速度,降低局部收敛概率,使其更容易寻找到最优解。通过案例验证了算法的优越性,并通过matlab对算法进行模拟仿真,使算法的应用更加直观和清晰。

全文目录

摘要  3-5
ABSTRACT  5-9
第1章绪论  9-16
  1.1 课题背景及意义  9-10
  1.2 国内外研究现状  10-14
    1.2.1 国内研究现状  11-13
    1.2.2 国外研究现状  13-14
  1.3 论文创新点  14
  1.4 论文的主要内容  14-15
  1.5 本章小结  15-16
第2章车辆路径问题介绍  16-21
  2.1 车辆路径问题概述  16-17
  2.2 车辆路径问题的特点  17
  2.3 车辆路径问题的分类  17-19
  2.4 求解车辆路径问题的基本方法  19-20
  2.5 本章小结  20-21
第3章车辆路径问题的算法研究  21-39
  3.1 解决VRP 的精确算法介绍  21-22
    3.1.1 整数规划算法  21-22
    3.1.2 分支定界算法  22
    3.1.3 动态规划算法  22
  3.2 解决VRP 的启发式算法介绍  22-23
  3.3 早期的启发式算法  23-27
    3.3.1 插入算法  23
    3.3.2 节约里程法  23-24
    3.3.3 Petal 算法  24-26
    3.3.4 Sweep 算法  26-27
  3.4 现代的启发式算法  27-37
    3.4.1 禁忌搜索算法  28-30
    3.4.2 模拟退火算法  30-32
    3.4.3 蚁群算法  32-34
    3.4.4 人工免疫算法  34-37
    3.4.5 神经网络算法  37
  3.5 本章小结  37-39
第4章遗传算法解决 VRP 问题  39-64
  4.1 遗传算法的基本概念  39-40
  4.2 遗传算法的基本原理及流程  40-41
  4.3 遗传算法的特点  41-42
  4.4 遗传算法的基本操作  42-51
    4.4.1 遗传编码  42-44
    4.4.2 适应度函数（评价函数）  44-45
    4.4.3 遗传算子  45-47
    4.4.4 交叉  47-48
    4.4.5 逆转算子  48
    4.4.6 变异算子  48-49
    4.4.7 群体的设定  49-50
    4.4.8 初始化群体  50
    4.4.9 算法终止条件  50
    4.4.10 参数的控制和选择  50-51
  4.5 遗传算法的应用  51-54
    4.5.1 遗传算法的关键技术  52
    4.5.2 现行遗传算法的改进策略  52-54
  4.6 VRP 数学模型的建立  54-57
    4.6.1 问题描述  54
    4.6.2 模型假设  54-55
    4.6.3 VRP 模型建立  55-57
  4.7 遗传算法的优化求解设计  57-63
  4.8 本章小结  63-64
第5章遗传算法解决 VRP 的实证分析  64-70
  5.1 实证分析背景及数学模型优化  64-65
  5.2 案例分析  65-69
    5.2.1 案例分析一  65-66
    5.2.2 案例分析二  66-69
  5.3 本章小结  69-70
第6章研究结论及展望  70-72
  6.1 论文研究的主要结论  70
  6.2 需要进一步研究的问题  70-72
参考文献  72-76
致谢  76-77
附录程序清单  77-82
在学期间发表的论著及取得的科研成果  82

遗传算法在VRP中的应用与研究

内容摘要

全文目录

相似论文