【作者】 丑英哲；

【导师】 林丹；

【作者基本信息】 天津大学 ， 运筹学与控制论， 2007， 硕士

【摘要】 车辆路径问题产生于现实生活中的交通运输,自1959年被提出后,就成为运筹学与组合优化领域的研究热点问题。在遗传算法应用到这一问题之前,已产生了许多求解方法,这些传统算法在处理大规模客户问题上存在运算时间较长的不足。而遗传算法作为一种进化算法,可以很好的兼顾运算时间和效率这两方面的要求,在解决车辆路径问题这个NP-困难问题方面,具有很好的发展前途。本文在广泛深入地查阅国内外文献的基础上,对遗传算法的基础理论和方法进行了深入的理论研究,并应用遗传算法对单目标和双目标车辆路径问题进行了实验分析,主要内容如下:1.系统、详尽的介绍了遗传算法的一般流程和基本理论、方法,以及面向多目标优化问题的遗传算法的基本理论方法。对几种常用的多目标遗传算法进行了分析和比较,指出了各自的应用范围和不足之处。2.简要介绍了车辆路径问题的起源和发展历史,归纳总结了其求解方法。提出了一种新的遗传算法来解决以车辆运输成本为目标的单目标车辆路径问题。新算法在基于自然数编码的基础上,采用了改进的最大保留交叉技术。通过对多个实例的计算证明了该算法具有更好的效果。3.提出了一种新的多目标遗传算法,来解决以运输成本最小和所有车辆中最长运行时间最短为目标的双目标车辆路径问题。新算法中采用了NSGA-II技术和改进的最大保留交叉算子进行遗传操作,并使用了两种方法:(1)局部搜索、(2)λ-interchange局部搜索方法来实现解的优化。文中的一系列算例结果说明了该算法的可行性和有效性。更多还原

【Abstract】 Vehicle Routing Problem gives birth to the transportation in the real life. Since it was put forward in 1959, it has been a hotspot in the area of operational research and combination optimization. There are many traditional methods to solve VRP, but they all need long runtime in solving large number problems. Genetic Algorithm is an evolutionary algorithm, it acts well in both runtime and efficiency. Using GA solving the NP-hard problem VRP is a excellent method, and it has developing future. We have read many literature related overseas and domestic broadly, and in this paper, we first analyze the basic theory and method in GA, then using the GA to solve one-objective VRP and multi-objective VRP. The main content from three parts as follows:1. We introduce related biology knowledge and give a brief review of the development history of GA. Then we conclude the main characters of GA and sum up the present situation of the theories and applications of GA. Through comparing and analyzing several multi-objective GAs now in use, this paper indicates their excellence and deficiency.2. We give a brief review on the origin and development of VRP and sum up the solving methods. Then this paper provides a new GA to solve the one-objective VRP. The new GA is coded in natural number, introduces improving PMX.3. This paper introduces a new multi-objective GA to solve the bi-objective VRP. The two objectives and minimize the transport cost and longest transport time in all vehicles. The new GA introduces NSGA-II and improved PMX to put up genetic operation, and it uses two method—local search andλ-interchange local search method to optimize the value. The examples in our paper show the efficiency of the algorithm.更多还原