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

多车程带时间窗车辆路径问题的模型和算法

作　者: 梁文博
导　师: 王征
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 车辆路径多车程时间窗启发式算法
分类号: O224
类　型: 硕士论文
年　份: 2011年
下　载: 82次
引　用: 0次
阅　读: 论文下载

内容摘要

车辆路径问题是组合优化和运筹学领域研究的重要问题之一,主要研究满足一定约束条件下的最优车辆路线规划和使用方案,由于其重要的理论研究和实际应用价值,直得到人们的广泛关注。近些年来,人们开始逐渐研究从实际生活生产衍生而出的众多车辆路径问题分支,并取得了大量的研究成果和巨大的经济效益。而在大多数的车辆路径问题研究文献中,均假设车辆在一个工作周期内,完成一次运输任务后将不再被使用,显然这在很多实际应用中不能成立。本文所要研究的就是解决此类问题：一家大型物流公司,拥有一个车场停放着固定数量的车辆用于配送；公司的客户对其服务时间有着严格的限制,必须在事先指定的时间范围内(时间窗)得到服务；一辆车在一个工作周期内,可以完成多次运输任务,每次任务行使的时间必须限定在一个固定范围内。这一类问题可以抽象为多车程带时间窗的车辆路径问题。由于多车程和时间窗的双重约束的引进,对此类问题的求解会变的更加困难。本文针对多车程带时间窗的车辆路径问题的模型和求解算法进行了研究,主要研究工作如下：建立多车程带时间窗车辆路径问题的数学模型,并对求解多车程带时间窗车辆路径问题的常用启发式算法进行了介绍。设计并实现了一种求解多车程带时间窗车辆路径问题的基于车程的启发式算法,开发出符合问题特性的车程表现形式和局部搜索算子,实现了随机性的车程生成和有效的车程分配算法。修改了Solomon和Gehring标准算例,并对提出的算法进行了实验分析,求解结果全部优于当前的最优解,并且在求解质量上有了很大的提高。

全文目录

摘要  4-5
Abstract  5-9
1 绪论  9-19
  1.1 问题的提出  9-10
  1.2 国内外相关研究综述  10-14
    1.2.1 VRPM相关文献  10-11
    1.2.2 VRPTW相关文献  11-12
    1.2.3 VRPMTW相关文献  12
    1.2.4 VRPMTW研究总结  12-13
    1.2.5 VRPMTW研究的难度  13-14
  1.3 VRP问题求解算法的研究进展  14-17
  1.4 本文的主要研究工作  17-19
2 VRPMTW问题模型研究  19-29
  2.1 车辆路径问题综述  19-21
    2.1.1 车辆路径问题约束条件  19-20
    2.1.2 车辆路径问题优化目标  20-21
  2.2 VRPMTW问题的数学模型  21-29
    2.2.1 多车程问题概述  21-22
    2.2.2 时间窗问题概述  22-23
    2.2.3 VRPMTW问题描述  23-25
    2.2.4 VRPMTW问题的数学模型  25-29
3 求解VRPMTW问题的基于车程的启发式算法  29-48
  3.1 车程构建过程  30-36
  3.2 车程分配过程  36-39
  3.3 Local Search过程  39-46
  3.4 车程池更新过程  46
  3.5 车程选择过程  46-48
4 算例分析  48-56
  4.1 算例描述  48-49
  4.2 参数设置  49-51
  4.3 实验结果和分析  51-56
结论  56-59
参考文献  59-63
攻读硕士学位期间发表学术论文情况  63-64
致谢  64-65

多车程带时间窗车辆路径问题的模型和算法

内容摘要

全文目录

相似论文