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

大规模多配送中心车辆路径问题研究

作　者: 崔文
导　师: 吴耀华
学　校: 山东大学
专　业: 控制科学与工程
关键词: 车辆路径问题多配送中心节约算法 Lin-Kernighan算法遗传算法
分类号: F252
类　型: 硕士论文
年　份: 2012年
下　载: 236次
引　用: 0次
阅　读: 论文下载

内容摘要

物流配送是现代化物流系统的一个重要环节,它是指按用户的订货要求,在配送中心进行分货、配货,并将配好的货物及时送交收货人。在配送业务中,存在许多优化决策问题,其中配送车辆调度问题对配送企业加快配送速度、提高服务质量、降低配送成本及增加经济效益影响较大。根据配送中心数目的多少,物流配送车辆调度问题有单配送中心车辆调度问题和多配送中心车辆调度问题之分。在城市物流体系中,往往存在多个配送中心。因此,对多配送中心车辆调度问题的研究具有重要的现实意义。对于多配送中心车辆路径问题,目前的研究尚不够深入,实际的车辆路径问题往往规模较大,这就需要一种耗费时间较少、求解质量较优的算法来满足工作需要。本文针对这一要求,提出了“合并后求解,求解后再优化”的聚合优化算法。第一阶段,借助距离因素对客户点进行合并划分,将多配送中心车辆路径问题转化为单配送中心车辆路径问题；第二阶段,利用基于邻域选择策略的改进节约算法对单配送中心车辆路径问题进行求解,将客户点划分至单一配送中心,完成单车路径的构造；第三阶段,对路径进行二次优化,包括两部分,一是对载重量较少的路径进行合并,提高车辆利用率,二是利用遗传算法对边缘点进行调整,更改不合理客户点的划分,降低行驶距离。同时,本文利用改进的Lin-Kernighan算法对求解得到的单车路径进行了深度优化,进一步提高优化效果,由于Lin-Kernighan算法的复杂度较高,此部分作为可选模块,针对实际问题的具体需求选择性使用。为了验证本文算法的可行性和有效性,文章进行了大量的仿真实验,在章节内对节约算法和Lin-Kernighan算法的性能特点分别进行了测试比较,验证了本文改进算法的有效性,在文章最后一章对整体算法进行了仿真实验,实验包括三个部分：一是利用标准的MDVRP算例对本文算法的可行性进行了研究；二是利用其它文献内构造的小规模MDVRP算法对本文算法的有效性进行了测试,三是对大规模MDVRP问题进行了仿真实验。实验结果表明,本文提到的聚合优化算法大大提高了算法的计算效率,能够在合理的时间内得到较优解,更新了文献中小规模MDVRP的最优解,针对大规模MDVRP同样能够在较短时间内完成优化求解,利用Lin-Kernighan算法改进后,大幅度降低了行驶距离。

全文目录

摘要  8-10
ABSTRACT  10-12
第一章绪论  12-18
  1.1 研究背景及意义  12-13
  1.2 研究现状  13-15
    1.2.1 国外研究现状  13-14
    1.2.2 国内研究现状  14-15
  1.3 论文主要研究工作及组织安排  15-18
第二章多配送中心车辆路径问题  18-26
  2.1 车辆路径问题概述  18-22
    2.1.1 车辆路径问题的定义  18-19
    2.1.2 车辆路径问题的分类  19
    2.1.3 车辆路径问题的求解方法  19-22
  2.2 多配送中心车辆路径问题概述  22-24
    2.2.1 多配送中心车辆路径问题的描述  22-24
    2.2.2 多配送中心车辆路径问题的数学模型  24
  2.3 本章小结  24-26
第三章求解MDVRP的聚合优化算法  26-44
  3.1 聚合优化算法概述  26
  3.2 聚合优化算法的客户点合并策略  26-29
  3.3 改进节约算法求解SDVRP  29-38
    3.3.1 节约算法  29-31
    3.3.2 节约算法的自适应邻域选择策略  31-34
    3.3.3 节约算法性能测试  34-38
  3.4 路径二次分配及优化  38-43
    3.4.1 轻路径合并  38-39
    3.4.2 利用改进遗传算法进行边缘点调整  39-43
  3.5 本章小结  43-44
第四章优化单车路径的改进Lin-Kernighan算法  44-56
  4.1 Lin-Kernighan算法  44-46
  4.2 启发式构造算法  46-50
    4.2.1 启发式构造算法  46-49
    4.2.2 启发式构造算法性能测试  49-50
  4.3 改进Lin-Kernighan算法  50-54
    4.3.1 Lin-Kernighan算法初始解构造策略  50-52
    4.3.2 Lin-Kernighan算法性能测试  52-54
  4.4 本章小结  54-56
第五章仿真及分析  56-62
  5.1 标准MDVRP算例测试  56-58
  5.2 小规模MDVRP仿真对比  58-60
  5.3 大规模MDVRP求解测试  60-61
  5.4 本章小结  61-62
第六章总结与展望  62-64
附录  64-78
  附录一改进节约算法的核心代码  64-68
  附录二改进Lin-Kernighan算法的核心代码  68-78
参考文献  78-84
致谢  84-86
作者攻读硕士学位期间发表的论文  86-88
学位论文评阅及答辩情况表  88

大规模多配送中心车辆路径问题研究

内容摘要

全文目录

相似论文