柏明国[1]2003年在《CVRP和分配网络流算法研究》文中提出车辆路径问题和网络流问题都是非常着名的网络优化问题。车辆路径问题可以看作是旅行售货员问题的推广，它是NP-完备的问题。它要求对停在中心车站的一队车辆做出安排去服务于一些顾客，并且要求路径最优。网络流问题主要以流网络为研究对象，要求求出流网络中的最大流或最小费用流。 本文对对称的容量固定的车辆路径问题的几种主要的精确算法以及启发式算法作了总结，并且给出了两种新的启发式算法。第一种算法是将非对称情形的算法加以推广所得到。第二种算法则是基于拉格朗日松弛技巧的新算法。对分配网络流做了介绍，通过将网络单纯形算法加以推广，得到了一类特殊分配网络流的最小费用流的一种算法。
张远福[2]2003年在《VRP和制造网络流算法的研究》文中指出VRP问题是为固定的车辆集，设计一些起始于中心站的路径，要求在顾客的需求已知，且每一个顾客最多被服务一次，车的装载量不允许超过车辆容量的情况下，使总费用最小。VRP在大规模物资调运、劳务人员的任务分配等方面具有重要的使用价值。当VRP的一些量为随机变量时，车辆路径问题就转化为随机车辆路径问题(SVRP)。如需求、时间是随机变量，或者每一个顾客以一个概率p_i出现等。在SVRP模型中我们希望车辆旅行的期望费用值(期望路径总长度)最小。制造网络流问题用于解决水源的调度及工厂的产品运输、分配、合成等问题。 本文首先提出一个新的VRP模型及其启发式算法。并证明了在距离约束的VRP情形下对于目标函数MV(车辆数最小)，其任一有多项式时间的启发式算法H得到的车辆数目K~H和最优车辆数目K~V满足关系K~H／K~V≥2，我们还给出了MD(总距离最小)的一个动态规划算法。对随机车辆路径问题，本文给出了一个基于随机需求的SVRP的禁忌算法，并提出了基于这种模型的车辆旅行的最佳方案。最后，本文提出一个制造网络流的最大流算法。
参考文献：
[1]. CVRP和分配网络流算法研究[D]. 柏明国. 山东科技大学. 2003
[2]. VRP和制造网络流算法的研究[D]. 张远福. 山东科技大学. 2003