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

物流车辆路径问题算法研究

作　者: 欧阳涛
导　师: 李雄飞
学　校: 吉林大学
专　业: 软件工程
关键词: 车辆路径算法蜂群算法人工蜂群算法蜂群优化算法层次分析法
分类号: F252
类　型: 硕士论文
年　份: 2011年
下　载: 308次
引　用: 0次
阅　读: 论文下载

内容摘要

被誉为现在企业的“第三利润源泉”的物流业在世界经济的发展带动下,在现代经济中占据了重要的地位,在社会发展和国民经济中也发挥着重要的作用。但是因为物流业处于一个初步阶段,从现有的各种统计数据中我们不难发现,我国的物流业中的成本费用太高。因此,减少物流业的成本费用也就显得极其重要。要降低物流费用的成本,从物流费用的核心—物流配送费用入手显然是一个很好的途径。需要减少物流配送的费用,优化物流配送路径则是重中之重。物流配送路径的问题,简单来说就是车辆路径问题(Vehicle Routing Problem, VRP)。VRP问题自从Danting和Ramse与1959年提出(Danting&Ramse,1959)后,就受到国内外相关学者的高度关注,他们进行了大量的理论研究,并且提出了各种行之有效的解决方案;如精确类的算法:分支界定法(Branch and Bound Approach),K-度中心树法(K-degree center tree and a related algorithm)等;经典的启发式算法:节约法(Saving Heuristic),扫描算法(Sweep Alogorithm)等;现代的启发式算法:模拟退火算法(Simulated Annealing),禁忌表算法(Taboo search),遗传算法(Genetic Algorithm),蚁群算法(AOC)等。在此同时,基于蜂群采蜜的行为而发展起来的各种蜂群智能算法,目前也成为了优化领域的研究热点。其中D T Pham的蜂群算法(Bee Algorithm,BA),Dervis Karaboga的人工蜂群算法(Aritificial Bee Colony,ABC),Dusan Teodorovic和Mauro Dell’Orco的蜂群优化算法(Bee Colony Optimization Metaheuristic ,BCO)都具有很强的代表性。本文通过对这三种算法的分析与研究,给出了算法BA、ABC,BCO详细的描述以及算法解决问题的基本框架与相应的伪代码。同时在ABC、BCO这两种算法的基础上,借鉴了其他的解决VRP问题算法的思想,如禁忌表算法、节约算法、2-opt技术等,很好的解决了带时间窗的车辆路径问题(VRPTW)。并且对VRPTW问题进行了仿真,与其他算法的解决方案相比较,在比较中发现,ABC、BCO算法在最终的结果的优化方面有了显著提高。这也说明了将蜂群智能算法运用在解决VRP问题上是可行的,并且是行之有效的。在利用这两种分别解决VRP问题的过程中,发现了两种算法对VRP的不同适应的能力,进而提出了联合ABC、BCO两种算法的综合求解方案,给出了算法流程图,为下一步研究做好了基础。在确定路径的最终方案时候需要考虑到VRP问题中的目标函数中所包含的影响因素。在文章的最后,本文为了更好的解决VRP问题,确定目标函数中各个影响因素的权重,以及ABC、BCO算法中的一些参数的设定问题,提出了层次分析法(AHP),将各个影响因素之间的一些定性的表达转化了定量的数据,也就使得VRP的目标函数更加的多目标化、更精确;同时使得两种算法在求解过程让参数的作用发挥起来,让算法的结果更加的优化。

全文目录

摘要  4-6
Abstract  6-10
第1章绪论  10-13
  1.1 课题背景与研究意义  10-12
  1.2 本文研究框架  12
  1.3 研究方法  12-13
第2章车辆路径问题研究  13-23
  2.1 车辆路径问题的概述  13-15
  2.2 车辆路径问题的分类  15-18
  2.3 车辆路径问题的数学描述  18-19
  2.4 求解VRP 算法的基本分析  19-23
第3章蜂群算法理论及研究  23-36
  3.1 蜂群算法的生物模型  23-25
  3.2 蜂群算法研究  25-29
  3.3 人工蜂群算法研究  29-34
  3.4 蜂群优化算法研究  34-36
第4章蜂群智能算法在VRPTW 问题上的应用  36-50
  4.1 VRPTW 的数学模型  36-38
  4.2 基于ABC 求解VRPTW 问题  38-44
    4.2.1 禁忌搜索在ABC 算法中的应用  38-39
    4.2.2 ABC 求解 VRPTW 的实现  39-44
  4.3 基于BCO 求解VRPTW 问题  44-46
    4.3.1 BCO 算法与 VRPTW 模型的映射  44-46
    4.3.2 BCO 求解 VRPTW 的实现  46
  4.4 实例求解与性能分析  46-48
  4.5 ABC/BCO 联合求解 VRPTW 问题设计  48-50
第5章层次分析决策模型在VRP 问题上的应用  50-56
  5.1 层次分析法的简单介绍与实现  50-54
  5.2 层次分析法决策分析法在VRP 问题上的应用  54-56
第6章总结和展望  56-58
  6.1 工作总结  56-57
  6.2 研究展望  57-58
参考文献  58-60
致谢  60

物流车辆路径问题算法研究

内容摘要

全文目录

相似论文