《本科毕业论文-—离散粒子群算法在车辆路径问题中的应用.doc》由会员分享，可在线阅读，更多相关《本科毕业论文-—离散粒子群算法在车辆路径问题中的应用.doc（40页珍藏版）》请在金锄头文库上搜索。
1、南华大学计算机科学与技术学院毕业设计（论文）计算机科学与技术学院毕业设计(论文)论文题目离散粒子群算法在车辆路径问题中的应用 指导教师职 称讲师学生姓名学 号专 业班 级系 主 任院 长起止时间2013年10月11日至2014年5月23日2014年5月23日目录摘要iAbstract.ii第一章 绪论11.1 课题背景11.2 课题意义11.3 国内外研究现状21.3.1国外的研究现状21.3.2国外的研究现状31.4 论文的结构4第二章 离散粒子群算法62.1粒子群优化算法62.1.1算法介绍62.1.2 算法原理62.1.3 算法流程82.1.4 本节小结92.2 离散粒子群算法102.2
2、.1 算法引入102.2.2 算法原理112.2.3 算法应用122.2.4 本节小结15第三章 车辆路径问题分析163.1 物流配送163.2 车辆路径问题的概述173.3 车辆路径问题的分析173.3.1 VRP的研究要素183.3.2 VRP的优化目标183.3.3 VRP的实现算法193.4 本章小结19第四章 车辆路径问题的建模与实现214.1 车辆路径问题的建模214.2 算法实现214.3 实现代码224.4 演示结果254.5 DPSO算法与其他算法的比较254.5.1 DPSO算法与免疫算法的比较254.5.2 DPSO算法与最小生成树的比较284.5.3 DPSO算法与遗传
3、算法的比较284.6 本章小结29第五章 结论和展望30参考文献31谢辞34离散粒子群算法在车辆路径问题中的应用摘要：在这个高速发展的经济社会，各行各业对科学技术的革新的要求愈发的强烈，同时对人们的日常生活产生愈来愈广的影响。其中物流企业也逐渐凸显期重要性，然而物流配送则是物流企业日常生产中一个最为重要的环节，物流配送效率的高低直接将会影响到整个物流企业的运作效益，同时对于电子商务活动物流配送也必不可少。物流配送中亟待解决的问题是怎样得到一条费用最小的车辆路径并将货物配送给每个客户，即车辆路径问题(VRP)33。优化车辆路径问题(VRP)则需要优化配送速度、服务质量、配送成本等决定性因素，因此
4、在这些问题中涉及到多种多样优化方案。应用离散粒子群算法(DPSO)22这种群体智能算法能更好更快地解决这些多样化的问题，该算法以快速收敛性而获取最佳是通过模拟鸟群觅食得到的。应用于车辆路径问题中的离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，具有记忆和学习能力，克服其他算法的众多参数的问题。因此离散粒子群算法适合应用在车辆路径问题。关键词：粒子群算法、离散粒子群算法、车辆路径问题、物流配送、路径优化问题、免疫算法Discrete Particle S
5、warm Optimization for Vehicle Routing ProblemAbstract: In this high-speed economic and social development, science and technology sectors of innovation requires increasingly strong, while producing increasingly broad impact on peoples daily lives. Which of logistics enterprises have gradually highli
6、ghts the importance is the logistics and distribution logistics companies daily production one of the most important aspects, however the level will directly affect the efficiency of logistics and distribution to the operational efficiency of the entire logistics enterprises, but for e-commerce logi
7、stics and distribution also essential.Logistics and distribution problems to be solved is how to get a minimum cost of vehicle routing and distribution of goods to each customer, namely vehicle routing problem (VRP). Optimizing vehicle routing problem (VRP) is required to optimize the speed of deliv
8、ery, quality of service, distribution costs and other decisive factors, involved in these issues to a wide variety optimization. Discrete Particle Swarm Optimization (PSO) algorithm which swarm intelligence to better address these diverse problems faster, rapid convergence of the algorithm is to acq
9、uire the best is obtained by simulating the foraging birds.Applied to the vehicle routing problem discrete particle swarm algorithm also overcomes the deficiencies and shortcomings of other algorithms, discrete particle swarm algorithm coded genetic algorithm is relatively simple to overcome the com
10、plexity and the algorithm has the general characteristics for the vast majority of objective optimization problem. And groups of particles based on their own experience to optimize the update, with memory and learning ability, to overcome the problems of many other parameters of the algorithm. There
11、fore discrete particle swarm algorithm suitable for applications in vehicle routing problem.Keywords: Particle Swarm Optimization; Discrete Particle Swarm Optimization; Vehicle Routing Problem; Logistics Problem; Path Optimization Problem1第一章 绪论1.1 课题背景根据中国入世承诺，使得物流行业和服务行业成为中国最早的开放的行业其中之一。从而在经济全球化的趋
12、势下，我国的经济得到了迅猛的发展，在高水平经济的平台上科学技术同时也得到了进步。因此物流产业也得到了发展并成为了国家经济发展中一个重要的行业，同时在全球飞速发展延伸，成为象征一个国家综合国力的标志之一,并在我国开始慢慢成为国家经济的基础产业和主力军。对于物流产业而言，物流配送是其中重要的环节，然而在这个环节中车辆路径的选择则会起着关键性的作用。现实生活的交通中，对于车辆的行驶会有着各种的影响因素，比如天气的变化、突发的交通事故、交通流量等等各种的非主观的因素，因此配送的时间也会相应的被改变，于是研究在诸多的不确定的因素下得出一条最优的或者最优的路径是非常具有意义的。该问题自1959年被首先提出
13、，到现在目前已经有将近五十多年的的研究历史，它已经是组合优化问题领域和运筹学研究的热点和重点。在互联网和电子商务发展的带动下，物流产业得到了飞速的发展，VRP问题模型已经建立在现实生活和生产的各个方面，比如水运的船舶、公共汽车、火车和飞机等的调度问题以及邮政投递的问题，还有电力的调度问题也同样能抽象为车辆路径问题。简而言之，深入对车辆路径问题的研究，很具有工程和科学的应用价值。1.2 课题意义随着物流产业的发展，产业中同时也产生了诸多的问题引人注目，其中运输配送的成本占物流配送总成本中的60%，所以对于物流行业最急需解决的问题便是运输配送的成本的问题。然而影响运输配送的成本的最主要的问题便是车
14、辆路径问题(VRP)，以现代的物流产业的发展的重要性可见的车辆路径问题的显著，因此成功地合理地规划处理车辆路径问题会带来可喜可赞的经济的效益和科学的效益。车辆路径问题(VRP)属于一个NP难题，离散粒子算法能较好的解决这一类问题，特别地适合于应用在处理那些复杂的和线性的传统的搜索方法却又很难以解决的疑难问题上，PSO算法（粒子群优化算法）1可以提高配送中的物流配送的效率质量等关键问题。应用于车辆路径问题中离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，
15、具有记忆和学习能力，克服其他算法的众多参数的问题，因此离散粒子群算法适合应用在车辆路径问题。1.3 国内外研究现状1.3.1国外的研究现状1959年的时候有学者Dantzig与Ramser二人第一次提出了车辆问题(Vechicle Routing Problem，VRP)33,当时提出该问题的背景是运输汽油，然后给出了出数学模型和求解的具体方法。到目前为止已经提出了很多的只能算法和启发式算法应用在辆路径问题中,从提出到现在VRP的研究经过了近50年的发展，在此过程中已经出现众多的模型和求解算法。从提出的改进版的模拟的退火算法到动态的蚁群算法再到改进的粒子群算法等算法来解决车辆路径问题。由于研究重点的不同模型存在不同的方式。标准的车辆路径问题其实是指带装载限制的车辆路径问题(Capacitatied VRP，CVRP)，其他的各类型的问题都是从此问题延伸展开。一个典型的VRP的基本特征包括：目标、派送点、用户点、道路和车辆。同时VRP也可以如此分类：在研究目标方面，可以最小化总的运输成本；可以将顾客的等待时间最小化；可以最小化行驶的路程和将服务的效率最大化等。在限定的条件
