构造算法最早提出来解决旅行商问题，这些方法一般速度快，也
很灵活，但这类方法有时找到的解离最优解差得很远。
两阶段法(Two-phase Algorithm)
第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持
解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解
以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目
一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合
涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严
谨启发式方法、人工智能方法等。
综合过去有关VRP的求解方法，可以将其分为精确算法（exact
algorithm）与启发式算法（heuristics），其中精确算法有分支界
限法、分支切割法、集合涵盖法等；启发式算法有节约法、模拟退火 法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算
(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法
(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral
Networks)、粒子群算法（Particle Swarm Optimization,PSO）方
法等。
5.车辆路径问题的研究现状
分重要，采用不同的估价可以有不同的效果。目前已提出的启发式算
法较多，分类也相当多，主要的启发式算法有以下几类：构造算法、
两阶段法、智能化算法。
构造算法(Constructive Algorithm)
这类方法的基本思想是：根据一些准则，每一次将一个不在线路
上的点增加进线路，直到所有点都被安排进线路为止。
标函数值为止。。
智能化算法(Intelligent Algorithm)
这类算法以启发式准则来代替精确算法中的决策准则，以缩小解
搜索的空间。 总体来看，尽管启发式算法能够在有限的时间内求出
质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法
达到预期的要求。
20世纪90年代以来，由于人工智能方法在解决组合优化问题中的
VRP-ppt
3
3.车辆路径问题的概念
车辆路径问题(Vehicle Routing Problem,VRP)车辆路线问题
(VRP)最早是由Dantzig和Ramser于1959年首次提出。是指对一系列
装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在
满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容
研究意义
1.能有效的降低能耗，减少对环境影响
自工业革命以来，人类向大气中排放的二氧化碳逐年增加， “温室效应”也随之而来。2013年，我国大范围的雾霾天气，让我们 出门也不再只看晴雨，考虑是否带伞，还要关注一下空气质量，带上 口罩。VRP的研究能有效地减少车辆的汽油消耗，降低二氧化碳级二 氧化硫等气体的排放。
量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路
程最短、费用最少、时间尽量少、使用车辆数尽量少等)。
车辆路径问题的概念
设有一场站，共有M 辆货车，车辆容量为Q，有N位顾客，每位 顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场 站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车 辆容量的限制，目的是所有车辆路线的总距离最小。
法。
关于车辆路线问题之学术研究文献众多，也提出了相当多的求解策略 与方法，Bodin and Golden（1981）将众多之求解方法归纳成以下 七种：
数学解析法（Exact Procedure）； 人机互动法（Interactive Optimization）； 先分群再排路线（Cluster First–Route Second）； 先排路线再分群（Route First–Cluster Second）； 节省法或插入法（Saving or Insertion）； 改善或交换法（Improvement or Exchanges）； 数学规划近似法（Mathematical programming）。
在基本车辆路线问题（VRP）的基础上，车辆路线问题在学 术研究和实际应用上产生了许多不同的延伸和变化型态，包括时 窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW）、追求最佳服务时间的车辆路线问（VRPDT） 、多车种车辆路线问题（fleet size and mix vehicle routing problems，FSVRP）、车辆多次使用的车辆路线问题（vehicle routingproblems with multiple use of vehicle，VRPM）、考 虑收集的车辆路线问题（vehicle routingproblems with backhauls，VRPB）、随机需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）等。
强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并
构造了大量的基于人工智能的启发式算法(智能化启发式算法)。智能
化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一初
始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达
到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法
车辆路线的实际问题包括配送中心配送、公共汽车路线制定、 信件和报纸投递、航空和铁路时间表安排、工业废品收集等sher曾将求解车辆路线问题的算法分成三个阶段。
第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局
部改善启发式算法和贪婪法等；第二阶段是从1970年到1980年，属于
由于VRP是NP-hard（非确定性多项式）问题，难以用精确算发
求解，启发式算法是求解车辆运输问题的主要方法，为此专家主要把
精力花在构造高质量的启发式算法上。启发式算法是在状态空间中的
改进搜索算法，它对每一个搜索的位置进行评价，得到最好的位置，
再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价十