自Dantzig和Ramser提出了VRP之后，VRP显示了强大的生命力。VRP涉及到组合数学、应用数学、计算机科学、运筹学等数学、计算机、经济领域的理论知识，具有较强的理论研究价值。再加上研究VRP有助于降低社会物流成本、提高社会经济效益，具有较高的实际应用价值。VRP的这两个优点引发了相关领域专家对其研究热情。一些物流企业也将节约物流运输成本作为提高企业利润的出发点，因此不惜投资重金聘请专家研究VRP。

1.1、国外研究历史与成果

从20世界60年代VRP提出后，国外学者与专家进行了几十年的学习与研究，得出了大量的车辆路线问题的研究理论与方法。不过纵观整个VRP的研究历程，对于VRP的求解方法可分为两类：精确算法(ExactAlgorithm)、启发式算法(HeuristicAlgorithm)。其中启发式算法又可分为：传统启发式算法(TraditionalHeuristicAlgorithm)和智能启发式算法(IntelligentHeuristicAlgorithm)。

1、精确算法

精确算法包括割平面法、动态规划法、K-树算法、三下标车辆流、分支定界法。

1962年Balinski对平面进行分割，将所有客户中心划分为几个较小的集合，再分别对各个集合优化求解[1]。1971年Eilon提出了用于精确求解已知车辆数VRP的动态规划法，不过其时间复杂度为指数级。1981年Christofides提出了K-树算法求解经典VRP[2]。1981年Fisher提出了三下标车辆流方程求解带时间窗口的VRP[3]。1981年Laporte采用分支定界法求解VRP[4]。精确算法严格按照问题的约束条件进行求解，各个求解结构清晰，并且结构之间的关系明确，边界范围清楚，可精确求得VRP的最优解。不过，随着VRP规模的扩大，精确算法的时间复杂度呈指数级别骤增。当遇到稍大规模数据量的VRP时，精确算法将不再适用。

2、启发式算法

精确算法可以求得VRP的精确解，不过当遇到大规模的VRP时，其算法耗时往往不能被人接受。不过人们受自然规律和工作经验的启发设计出了可高效求解VRP的一类算法——启发式算法。启发式算法可以在较低的时间复杂度内求得VRP的近似最优解。根据启发式算法的求解效果，可将启发式算法进一步划分为传统启发式算法和智能启发式算法。

①传统启发式算法：节省法、扫描法、最近邻居法等。

1964年Clarke和Wright提出了C-W节省法，解决车辆数不确定的VRP[5]。Solomon提出了最近邻居法，先划分VRP中的节点再求解。Gillett和Miller提出了基于极坐标形式的扫描算法以求解VRP[6]。

传统启发式算法易于实现，容易理解，求解速度较快。不过其只适用于求小规模的VRP，当遇到大规模的VRP时，其求解结果往往与最优解偏差较大。

②智能启发式算法：禁忌搜索算法（TabuSearch,TS）、遗传算法（GeneticAlgorithm,SA）、模拟退火算法（SimulatedAnnealing，SA）、蚁群算法（AntColonyOptimization，ACO）等。

自20世纪90年代以来，智能启发式算法在解决组合优化问题上显示了强大的优势，在诸多领域得到了广泛的应用。不少专家利用智能启发式算法求解车辆路线问题，并取得了良好的成绩。Willard最早将禁忌搜索算法求解VRP。模拟退火算法具有收敛速度快，且能求得全局最优解的特点，Osman研究了模拟退火算法求解VRP。Holland应用遗传算法解决了VRPTW。现在出现了混合式启发式算法，其原理是将2个及以上的智能启发式算法结合起来，融合了各个启发式算法特有的优点，在求解VRP时显示了更好的效果。

1.2、国内研究历史及成果

由于物流行业蓬勃发展并在国民经济中占有越来越大的比重，不少国内专家开始研究车辆路线问题。虽然国内对车辆路线问题的研究较晚，不过也取得了一些可喜的成绩。 VRP车辆路径问题的研究现状与历史:http://www.youerw.com/yanjiu/lunwen_204275.html