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

VRP和制造网络流算法的研究

作　者: 张远福
导　师: 贺国平
学　校: 山东科技大学
专　业: 应用数学
关键词: 车辆路径问题细化贪婪算法分枝定界法禁忌搜索随机车辆路径问题制造网络流问题最大流层数
分类号: O29
类　型: 硕士论文
年　份: 2003年
下　载: 227次
引　用: 1次
阅　读: 论文下载

内容摘要

VRP问题是为固定的车辆集，设计一些起始于中心站的路径，要求在顾客的需求已知，且每一个顾客最多被服务一次，车的装载量不允许超过车辆容量的情况下，使总费用最小。VRP在大规模物资调运、劳务人员的任务分配等方面具有重要的使用价值。当VRP的一些量为随机变量时，车辆路径问题就转化为随机车辆路径问题(SVRP)。如需求、时间是随机变量，或者每一个顾客以一个概率p_i出现等。在SVRP模型中我们希望车辆旅行的期望费用值(期望路径总长度)最小。制造网络流问题用于解决水源的调度及工厂的产品运输、分配、合成等问题。本文首先提出一个新的VRP模型及其启发式算法。并证明了在距离约束的VRP情形下对于目标函数MV(车辆数最小)，其任一有多项式时间的启发式算法H得到的车辆数目K~H和最优车辆数目K~V满足关系K~H／K~V≥2，我们还给出了MD(总距离最小)的一个动态规划算法。对随机车辆路径问题，本文给出了一个基于随机需求的SVRP的禁忌算法，并提出了基于这种模型的车辆旅行的最佳方案。最后，本文提出一个制造网络流的最大流算法。

全文目录

1 前言  23-27
  1.1 对车辆路径问题(VRP)的回顾  23-24
  1.2 VRP的线性规划数学模型及精确算法  24-25
  1.3 VRP的启发式算法的回顾  25-26
  1.4 随机车辆路径问题(SVRP)简介  26
  1.5 制造网络流问题简介  26-27
2 车辆路径问题(VRP)的一个新的模型及其启发式算法  27-33
  2.1 引言  27
  2.2 记号与数学模型  27-28
  2.3 一个启发式算法  28-30
  2.4 关于启发式算法的一个下界  30-31
  2.5 算例  31-33
3 距离约束的车辆路径问题  33-37
  3.1 记号  33-34
  3.2 MD和MV的最优解的关系  34
  3.3 启发式算法分析  34-35
  3.4 MD问题的一个动态规划算法  35
  3.5 算例  35-37
4 随机车辆路径问题(SVRP)的研究  37-48
  4.1 SVRP介绍  37-38
  4.2 SVRP的随机规划方法模型  38-39
  4.3 一个解随机需求的SVRP算法  39-45
    4.3.1 记号和公式定义  41
    4.3.2 二元需求  41-42
    4.3.3 一般需求  42-43
    4.3.4 基于随机需求SVRP模型的近似和界  43-44
    4.3.5 一个解随机需求SVRP模型的禁忌算法  44-45
  4.4 车辆旅行的最佳方案  45-48
5 一个制造网络的最大流算法  48-58
  5.1 点和弧  48-51
  5.2 广义的MNF优化问题  51-52
  5.3 制造网络的一个最大流算法  52-55
  5.4 算例  55-58
6 致谢  58-59
7 主要参考文献  59-61

VRP和制造网络流算法的研究

内容摘要

全文目录

相似论文