【作者】 邱平；

【导师】 李延珩；

【作者基本信息】 大连海事大学 ， 管理科学与工程， 2007， 硕士

【摘要】 随着电子商务的飞速发展，物流产业也发生了新的变革。配送是物流系统中一个直接与消费者相连的重要环节。运输费用在物流总费用中的比例约50％，因此降低物流配送的运输成本成为首要考虑的问题。运输线路是否合理对配送的速度、成本、效益有着直接影响。合适的运输路线，可以加快对客户需求的响应速度，提高服务质量，增强客户满意度，降低运营成本。本文针对配送中的核心问题—车辆路径问题(Vehicle Routing Problem VRP)，采用遗传算法进行了研究。这对物流配送企业实现配送路径优化、降低成本和提高物流经营管理水平、更快的响应顾客，最终增加企业的竞争力具有一定的参考价值。 本文从旅行商问题出发，介绍了车辆路径问题的一般描述及特点；详细介绍了遗传算法的基本概念，基本原理及流程，遗传算法的应用。将遗传算法的基本操作用图例表示，使其变得简单易懂；通过遗传算法的基本操作及改进策略相关详述，为以后算法的改进打下了理论基础。 本文在认真分析国内外对VRP研究的基础上，运用改进遗传算子策略，对遗传算法进行了一系列的改进，如采用自然数编码、引入罚函数对约束进行处理、在遗传算子中选用轮盘赌选择法；PMX方法进行交叉操作；逆转变异算子。对交叉算子和变异算子操作产生的不合法个体进行相应改进操作，直到得到合法的子代个体方可进行下一次迭代。通过MATLAB实现该算法，并通过实例证明了该算法是求解VRP的一个很好方案。更多还原

【Abstract】 With the rapid development of e-commerce, logistic industry has also experienced a new reform. Distribution is an important link in logistics, which is joined to consumers directly, and the cost of transportation occupies 50% of that in whole logistics. So, reducing the cost of logistics begins with reducing that of transportation of logistics distribution. In the problem, whether the transportation route is rational will affect the speed, cost and benefit of distribution. Selecting rational vehicles’ route can help to achieve quicker response speed to customers, improve the quality of service, increase customers’ satisfaction to logistics system and reduce operational cost of service merchants. This paper has studied the core problem of the distribution-VRP by using genetic algorithms (GA). So, it has some value to logistic enterprises to decrease the cost, to improve the level of logistics management, to response customers more quickly and to improve the rivalship power of the enterpriseThe essay, beginning with the general account of TSP, introduces VRP general description and feature; explains the basic concept, principle and procedure of the genetic algorithm. It also display some major process in tables ways, making the genetic algorithm comprehensive. Through the genetic algorithm basic operation and improvement, the essay laid method foundation for the later improvement of algorithm.This paper puts forward an improved genetic algorithm on the base of analysing the research on VRP in China and abroad. The improved genetic algorithm uses natural coding, penalty function to solve constraints, improves crossover operators and mutation operators and uses some operations to deal with illegal individuals until they are legal. At last we realizes the improved genetic algorithm by MATLAB. The algorithm given in this paper can obtain an optimized solution effectively and has been proved to be a good scheme to solve VRP.更多还原