离散粒子群算法在车辆路径问题中的应用毕业设计(论文)

1、计算机科学与技术学院毕业设计(论文)论文题目离散粒子群算法在车辆路径问题中的应用 指导教师职 称讲师学生姓名学 号专 业班 级系 主 任院 长起止时间目录摘要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.1 算法引入102.2.2 算法原理112.2.3 算法应用122.2.4 本节小结15第三章 车辆路径问

2、题分析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算法与遗传算法的比较284.6 本章小结29第五章 结论和展望30参考文献31谢辞34离散粒子群算法在车辆路径问题中的

3、应用摘要：在这个高速发展的经济社会，各行各业对科学技术的革新的要求愈发的强烈，同时对人们的日常生活产生愈来愈广的影响。其中物流企业也逐渐凸显期重要性，然而物流配送则是物流企业日常生产中一个最为重要的环节，物流配送效率的高低直接将会影响到整个物流企业的运作效益，同时对于电子商务活动物流配送也必不可少。物流配送中亟待解决的问题是怎样得到一条费用最小的车辆路径并将货物配送给每个客户，即车辆路径问题(vrp)33。优化车辆路径问题(vrp)则需要优化配送速度、服务质量、配送成本等决定性因素，因此在这些问题中涉及到多种多样优化方案。应用离散粒子群算法(dpso)22这种群体智能算法能更好更快地解决这些多

4、样化的问题，该算法以快速收敛性而获取最佳是通过模拟鸟群觅食得到的。应用于车辆路径问题中的离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，具有记忆和学习能力，克服其他算法的众多参数的问题。因此离散粒子群算法适合应用在车辆路径问题。关键词：粒子群算法、离散粒子群算法、车辆路径问题、物流配送、路径优化问题、免疫算法discrete particle swarm optimization for vehicle routing problemabstract:

5、 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 highlights the importance is the logistics and distribution

6、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 logistics and distribution also essential.logistics and di

7、stribution 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 delivery, quality of service, distribution costs and other

8、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 acquire the best is obtained by simulating the foraging b

9、irds.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 complexity and the algorithm has the general characterist

10、ics 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. therefore discrete particle swarm algorithm suitable for ap

11、plications in vehicle routing problem.keywords: particle swarm optimization; discrete particle swarm optimization; vehicle routing problem; logistics problem; path optimization problem第一章 绪论1.1 课题背景根据中国入世承诺，使得物流行业和服务行业成为中国最早的开放的行业其中之一。从而在经济全球化的趋势下，我国的经济得到了迅猛的发展，在高水平经济的平台上科学技术同时也得到了进步。因此物流产业也得到了发展并成为

12、了国家经济发展中一个重要的行业，同时在全球飞速发展延伸，成为象征一个国家综合国力的标志之一,并在我国开始慢慢成为国家经济的基础产业和主力军。对于物流产业而言，物流配送是其中重要的环节，然而在这个环节中车辆路径的选择则会起着关键性的作用。现实生活的交通中，对于车辆的行驶会有着各种的影响因素，比如天气的变化、突发的交通事故、交通流量等等各种的非主观的因素，因此配送的时间也会相应的被改变，于是研究在诸多的不确定的因素下得出一条最优的或者最优的路径是非常具有意义的。该问题自1959年被首先提出，到现在目前已经有将近五十多年的的研究历史，它已经是组合优化问题领域和运筹学研究的热点和重点。在互联网和电子商

13、务发展的带动下，物流产业得到了飞速的发展，vrp问题模型已经建立在现实生活和生产的各个方面，比如水运的船舶、公共汽车、火车和飞机等的调度问题以及邮政投递的问题，还有电力的调度问题也同样能抽象为车辆路径问题。简而言之，深入对车辆路径问题的研究，很具有工程和科学的应用价值。1.2 课题意义随着物流产业的发展，产业中同时也产生了诸多的问题引人注目，其中运输配送的成本占物流配送总成本中的60%，所以对于物流行业最急需解决的问题便是运输配送的成本的问题。然而影响运输配送的成本的最主要的问题便是车辆路径问题(vrp)，以现代的物流产业的发展的重要性可见的车辆路径问题的显著，因此成功地合理地规划处理车辆路径

14、问题会带来可喜可赞的经济的效益和科学的效益。车辆路径问题(vrp)属于一个np难题，离散粒子算法能较好的解决这一类问题，特别地适合于应用在处理那些复杂的和线性的传统的搜索方法却又很难以解决的疑难问题上，pso算法（粒子群优化算法）1可以提高配送中的物流配送的效率质量等关键问题。应用于车辆路径问题中离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，具有记忆和学习能力，克服其他算法的众多参数的问题，因此离散粒子群算法适合应用在车辆路径问题。1.3 国内外研究

15、现状1.3.1国外的研究现状1959年的时候有学者dantzig与ramser二人第一次提出了车辆问题(vechicle routing problem，vrp)33,当时提出该问题的背景是运输汽油，然后给出了出数学模型和求解的具体方法。到目前为止已经提出了很多的只能算法和启发式算法应用在辆路径问题中,从提出到现在vrp的研究经过了近50年的发展，在此过程中已经出现众多的模型和求解算法。从提出的改进版的模拟的退火算法到动态的蚁群算法再到改进的粒子群算法等算法来解决车辆路径问题。由于研究重点的不同模型存在不同的方式。标准的车辆路径问题其实是指带装载限制的车辆路径问题(capacitatied v

16、rp，cvrp)，其他的各类型的问题都是从此问题延伸展开。一个典型的vrp的基本特征包括：目标、派送点、用户点、道路和车辆。同时vrp也可以如此分类：在研究目标方面，可以最小化总的运输成本；可以将顾客的等待时间最小化；可以最小化行驶的路程和将服务的效率最大化等。在限定的条件方面，单一的配送点；多个配送点；带有时间窗口的和没有时间窗口的；开放型的和封闭型的；单一车型配送的和多个车型配送的等。按任务的性质，有确定信息的和不确定的；需求的动态性和静态性等等。随着生活和生产不断地在进步和发展，为了满足这其中的各种的需求，车辆路径问题(vrp)需要不断地进行扩展和完善。通过调整标准的vrp的不同的建设条

17、件，从而来扩宽vrp的研究。当前最普遍的车辆路径问题是带有时间窗的静态车辆问题，世界各国的研究学者通过对基本的vrp的研究得出了基本的模型，使用得出的基本的模型做出各种类型的题库，比如fisher题库等。将不同的扩宽元素再与标准的vrp相结合,然后可以构造出不同的车辆路径问题,比如：有能力约束的vrp(cvr)、有时间窗的约束的vrp(vrptw)、带取送货的vrp(vrppd)、周期性的vrp(pvrp)、分散配送vrp(sdvri)和带回程载货的vrp(vrpb)等3-16。同时针对不同的主要的约束条件，针对不同实际公司和企业中的不通风情况又能衍生出一些衍生模型：多仓库型的车辆路径问题(m

18、vrp)、多车型的车辆路径问题（hvrp)、随机的车辆路径问题(svrp）、模糊的车辆路径问题(fvrp)。总结得出vrp扩展问题及关系图如图1.1所示。图 1.1 vrp扩展问题以及关系1.3.2国外的研究现状从上个世纪的90年代开始，国内也开始对vrp进行研究。到目前为止，可以在国内的各大期刊网站上都能搜索到有关vrp的研究成果近千篇，同时着也说明了vrp这个问题的研究价值和重要性，同时还说明了国内学者对不同类型的vrp的研究做出了不可磨灭的贡献。其中这些研究主要有取送货问题17，多需求点调度问题18，装卸一体化问题19等。同时为了解决vrp的各种确定性问题用了各类型的不同算法，如遗传算法

19、20、混合算法21等。对vrp的研究国内已经达到了相当的规模，虽然如此，但是vrp仍然存在很多的问题值得我们进一步的研究，同时对于vrp的复杂性和解决工具还需要更进一步的完善。主要的问题有如下：、首先vrp的问题是一个np的难题。因此在求解的过程中如何优化计算时间和结果的精确性是解决问题的重点同时也是难点。于是对vrp的求解研究快速的高效的智能算法是一个很有价值的研究方向。、其次vrp的信息存在不确定性。因此必须对不确定的信息进行预先的处理，于是每次使用的智能算法都需要根据具体的问题进行变化。分析和优化不确定因素的解决策略也是vrp的另一研究方面。、还有用于求解动态的vrp的仿真环境仍然需要开

20、发研究。仿真环境中关于如何产生一条符合实际情况的的路径，以及计算机模拟等问题都需要我们继续不断的努力。、最后在实际的物流配送任务中，对于城市的道路的同行状况的了解和掌握，因此我们可以考虑在vrp的框架下更进一步的研究。1.4 论文的结构为了便于阅读，本论文的章节是这样安排的。首先，在本论文的第一章，对本课题的研究背景、目前国内外的研究动态进行简要地概述。第二章，介绍本课题研究设计所需的基础算法粒子群算法的理论知识，介绍离散粒子群算法，其中包括离散粒子群算法的基本原理以及离散粒子群算法在各个领域中的广泛应用。第三章，介绍物流配送，由物流配送引入车辆路径问题，深入地剖析车辆路径问题。第四章，介绍基

21、于离散粒子群算法的车辆路径问题的建模和总体的算法思路，并且对算法的实现做了详细的设计，展示设计结果。第五章，对本论文的工作做了回顾和总结，归纳出了本论文的主要工作、取得的成果以及不足，并对本研究课题做了分析以及对今后的进一步研究工作做了展望。第二章 离散粒子群算法2.1粒子群优化算法2.1.1算法介绍 粒子群优化算法(particle swarm optimization , pso)算法是1995年提出来的，由kennedy和eberhart二人提出的1，算法的起源灵感是来源于对鸟类等其他各类生物的饮食习惯观察、研究并将其简化而产生所得。自然界中各种各类的生物体基本上都会有着一定的群体的行为

22、，因此为人类生命的研究的领域的讨论群体生物行为所产生的生物学的特性提供了立体的直观的模型，同时为在计算机上建立和模拟群体概念提供了模型。其中包括近邻的速度匹配、多维的搜索以及加速距离的概念，从而形成了关于pso的初始的版本。在此之后引进了shi这个概念到惯性权重的算法中来平衡开发和挖掘的能力，才形成目前标准的版本。由于粒子群算法（pso）的计算较简单、速度快的收敛性等优点使得算法在近十年内得到了较快的发展，并在很多领域得到了广泛的应用，成为了智能计算领域的宠儿。粒子群优化算法作为启发式的全局搜索的算法与此同时也是一个新的建立在群体基础上的智能算法，只需要用过粒子群中的粒子在相互之间进行相互地竞

23、争和相互的合作，这样便能达到优化的效果，并较快速地在一未知或特定的空间中寻找到最优的一点从而达到空间全局最优。粒子群算法和其他的进化算法大体上是相同的，都是在进化和种群的基础概念之上的，然后使得群体中的个体之间竞争和合作配合相结合实现在复杂环境下最优的搜索。pso算法（粒子群优化算法）作为新的智能的优化技术，它是来自于人工的生命与演化计算的理论知识：对群体中的每一个都进行一次初始化，初始化后的粒子都将作为一个可能存在的解或预备方案，然后不断地更新搜索迭代出空间里最优的解空间。首先pso算法（粒子群优化算法）会对随机的一群粒子进行初始化，再利用获得的最优解进行迭代在找到解的空间的一过程中追踪两个

24、所谓的极值个别的极端、全局的极值以此来不断地更新自己的位置和速度等。2.1.2 算法原理在pso算法（粒子群优化算法）当中，存在的每种需要优化的问题都对应着在搜索空间里存在的鸟，而在dspo（离散粒子群算法）中这些优化问题被称作粒子。这些粒子全部是需要被函数所确定的适应值，并且会存在一个各自的速度来计算他们运动的距离和方向。由此便会产生一个最优粒子，然后群体中的粒子们便会依据此最优粒子开始在解空间里搜索最优。于是每次的计算迭代，粒子都会依据来个极值来使自己的值保持最新状态。首先pso算法（粒子群算法）会对随机的一群粒子进行初始化，再利用获得的最优解进行迭代在找到解的空间的一过程中追踪两个所谓的

25、极值个别的极端、全局的极值以此来不断地更新自己的位置和速度等。由于这样粒子在整个的更新过程不会总得出比较好的值，于是很好的解决了某些问题。以上便是pso（粒子群算法）的原理内容。以上对pso（粒子群算法）的原理分析，下面就pso（粒子群算法）的原理阐述pso（粒子群算法）具体的算法过程：首先，需要对群体中的所有的粒子进行一个随机的初始化，初始化他们的位置和他们的速度，这样便能使群体均匀地分布在解空间当中。分别使用和来描述群体中的i粒子在解空间中的速度与位置。然后再通过上述的迭代方法得出得出最优的解再利用这个最优的解来得出新的关于速度与位置的值。在这个迭代的过程产生的个体极值用来表示。然后通过粒

26、子间的领域得出另一个全局极值，即为整个群体中的一个最优的粒子用来表示。最后粒子根据以下的两个计算公式得到最后具体的关于粒子的速度与位置。 上述的公式中的c1和c2是用来表示加速度的常数，这两个参数可以用来调整在全局中最优的粒子与个体中最优的粒子的步长。这两个常数不能太小也不能太大，如果它们的值太小则会使得粒子们远离我们的目标区域，但是如果太大便会使得粒子突然就向目标的区域飞过去或者甚至可能使得粒子飞出我们的目标区域。因此只有选择两个适当的值赋予c1和c2，适当的c1和c2能够加快整个算法的收敛速度并且也只有这样才能使得算法得出的最优解释一个局部的最优解。rand()函数能产生01的随机数。但是

27、粒子的速度不能超过算法在每一维中设定的最大的速度vmax。算法设置这样的一个vmax的值的目的在于这样能确保粒子在群体中能达到的全局的搜索能力，在算法的整个运算的过程中若将vmax的值设置的越小就会越增加粒子在算法中的局部的搜索的能力。由于pso算法（粒子群算法）的思想是来自于鸟群的觅食，在对算法的使用过程中，众多的学者们发现很多的时候使用动物或者是生物的认知来展示算法的原理这样会显得更加的具体和完善，并且更容易让人理解和应用。由之前提到的更新速度的公式可将其大致地分为三个部分，首先一部分是关于vi一种粒子会按照原来的方向和形同的速度完成搜索过程的趋势，而这可以转换为用人的认知习惯来解释这一原

28、理。其次一部分为，这一部分的内容可以解释为粒子在过去寻找到的最优解中继续搜索的趋势，同样这也可以用人在认知的过程使用中所积累的经验来解释。最后一部分为，而这一部分可以表示为粒子能在整个空间中的领域中以前遇到到过的那些最优的解中再次进行搜索的可能方向，这个有可以类比于人类可以通过从他人的所学会的知识中而获得一些经验。综上所述，pso实质上就是通过人或者动物的学习和认知的习惯过程总结出寻找到最优的解。 通过上述对pso（粒子群算法）原理的分析和概述因而可以总结出ps的几大显著的优点：、由于pso算法的来源贴近人的惯性思维所以pso是较容易便能进行描述的；、因为pso原理和内容是简洁易懂的所以将其实

29、现的过程也是较为轻松的。、在利用pso来计算时用到的参数的数量也是较少的，并且这些参数都为常数，所以基本上不需要费太多的心思在调整参数上。、在算法应用的整个过程中由于群体的规模相比较而言稍微小一点，并且较少次数的利用到评估的函数，由此一来收敛速度便快了。、在该过程中由于用到的计算较少因此对设备的cpu与内存的要求也不那么严格。由以上的优点可以显然地得出目前解决全局的优化的问题pso是很有效果的。2.1.3 算法流程 算法的流程：首先，需要对群体中的所有的粒子进行一个随机的初始化，初始化他们的位置和他们的速度，这样便能使群体均匀地分布在解空间当中。然后再通过上述的迭代方法得出得出最优的解再利用这

30、个最优的解来得出新的关于速度与位置的值。最后粒子根据以下的两个计算公式得到最后具体的关于粒子的速度与位置（如图2-1所示）。图2-1粒子群算流程图2.1.4 本节小结 本章对pso算法(粒子群优化算法)进行了深入浅出的介绍，首先大概介绍了pso算法的来源、形成和发展。然后展开对pso算法详细描述，对pso算法原理进行深刻的剖析和认识，同时对pso算法应用的优点进行了具体的阐述。最后为了能更好的对pso算的理解，画出了pso算法直观的流程图，使得算法便于理解和后面的实现。2.2 离散粒子群算法2.2.1 算法引入pso算法开始只是用于处理一些连续性的问题，然而随着近些年的发展，此算法被越来越广泛

31、地使用在处理和完善离散问题中,从而逐渐地频繁地出现在人们的视线中并开始得到关注，因此在离散问题中衍生出来的pso算法被称为离散粒子群算法(discrete pso, dpso)22。在关注dpso这个过程中，人们对dpso这个算法的了解也愈深刻，尤其是在我们中国有一些研究者对dpso的研究特别重视。该课题先描述了pso算法的原理和内容，然后在基于离散化的情况对pso算法进行进一步的说明和阐述并基于离散映射不同的方法pso算法，将dpso算法的离散空间进行划分，再将衍生出来的dpso算法应用到vrp问题中，最后就该课题现状的客观分析以及讨论发展趋势和在该领域内的前景展望。 在dpso的问题中逐渐

32、出现两条主要的技术方法：一种方法是依据以往经典的连续的pso算法，然后再将这个连续运动的粒子映射到离散空间中并适当修改算法使之适应能够解决离散问题。另一种方法是离散优化问题，用pso为基础来更新各种新信息，用经典的算法的思想和框架重新定义dpso中的粒子的表达和求解方式。利用离散空间上的位操作的独特载体，以取代传统的矢量的计算，从信息的流动的机制的角度上来计算，依然保存着pso的具体的信息交换伴随流动的机制。而这两种方式的差别在于：第一种是在以连续空间的基础上的dpso，而第二种则是在以离散空间为基础的dpso。根据现实生活中遇到的各类型的问题而言，以上的两种方法可以分别应用于在生活中的不同领

33、域。就连续空间上研究的dpso形成了二进制的pso主要被应用在规划类型的问题中，除此之外还建立了专属于改算法的新的计算的模型还包括了些可能会被常用到的关于离散化的研究方法策略。 但是现实生活中的问题不全是都能在连续型的模型上建立起来并得到解决，因此bpso在一些离散化的情况中将不再是那么适用。虽然现在急于离散化的pso的研究还是不多的，但是仍然存在着一些这样的算法应用与离散化的相关的问题中。例如旅行商问题（tsp），在以离散空间为基础的前提下dspo通过利用位运算，这样虽然可能会增加一些计算的时间，但是这样便不会产生多余的搜索的问题，这样还能自然地描述离散的问题，并能和其他的演化算法紧密地结合

34、起来，如此使得其有更好的发展前景。但是由于研究还是不是特别的多，因此缺乏一个通用的、统一的和标准的模型。2.2.2 算法原理 二进制pso利用粒子的速度作为粒子的位置的变化的概率，这个观点由kennedy和eberhart两位博士首次提出的，专门用于解决01类型的规划的问题，在这个算法中，仅仅就是使用二进制的量来代表每个粒子并且利用二进制空间来代替超立方的空间，然后用二进制的量之间的转化来使得粒子在超空间中移动。于是得出更新速度的公式为：公式中的vid为粒子的位置的变化的概率；xid代表了当前粒子的确切的位置的值；则为常数因子，即为该粒子的学习因子；公式中的pid和pgd则分别代表了在空间中的

35、粒子的局部的最优的位置和全局的最优的位置。由于此算法为二进制的空间中的算法因此以上的参数中的xid、pid和pgd的值都只能为0或者是1。于是根据速度的变化的公式可以得到粒子的位置的公式为：其中. 在上述公式中的sig(vid)表示的是用于限制转换的函数，目的是为让vid的值始终能保持在0-1之间的一个随机的数。其中vid的值的选着直接关系到xid的确切的值的大小，若vid的值偏大，粒子的xid则为1的概率非常的大，反之，粒子的xid则为0的概率非常大。随着dpso在各个领域的广泛的应用，算法的不足之处也慢慢的不断的涌现出来，比如在组合式的优化问题当中表现的更为的突出，于是研究学家们便直接对连

36、续的pso离散化，将粒子的非整的位置近似的等于整数，其余的部分保持和连续的pso中一致。虽然在算法中出现了近似的取整的情况，并利用这些近似的解得可行的解，但是得到的可行解在高维的规划问题中仍能式算法具有较高的稳定性，并使得算法不会轻易地陷入停止的搜索状态。因此可得离散粒子群算法（dpso）的流程图如图3-1所示。图3-1 离散粒子群算法流程图2.2.3 算法应用由于pso的众多的优点，目前它已经应用在生活、工业和科学等的各个领域中，并且成为了解决实际的工程与科学问题热门算法。同时dpso也得到了广泛的研究应用，比如在组合性的优化难题上，超大规模的集成电路上，电力系统上，无线的传感器的网络中和用

37、于挖掘数据等等。通过不断的研究和应用，算法将会被更加广泛的应用，给我们的生活、工业和科学带来更多的便利和突破。以下我们对常见的dpso的应用简单的分析与介绍： 、典型性的组合型的优化问题该问题属于运筹学的一个重要的部分，其中主要包括了tsp的问题、0-1背包的问题、工作的排序问题还有最小生成树的问题等。用重新总结定义的pso来操作算式的方法得出了一种tsp-dpso的算法，于是根据这一改进和突破，更多的学者以典型性的组合型的优化问题为基础提出了解决tsp的问题23-24、0-1背包的问题25-26、工作的排序问题还有最小生成树的问题等一系列的的算法。 、电力体统在该领域中，需要解决的是在最低成

38、本的情况下进行发电扩张的问题，利用dpso能很有效的处理该种有强约束力的组合型的优化问题。由于近几年来dpso算法得到了有力地发展，解决这一问题的方法也随之越来越多，比如可以使用改进的bps来恢复配电网出现的故障；或者可以根据配输电网的扩展规划的问题与电网的重构问题来设计适合的dpso；又或者可以用dpso处理电力系统中满足发电机的约束的经济的调度问题；亦或是就给出的电力市场中盈利区间内的约束问题改进我们的dpso；亦或者是关于热备、停开机等约束的机组的调度问题与组合机组的等问题利用dpso可以很好地将其解决。 、vlsivlsi的设计中的布置线路、布值全局与布置图形是整个vlsi设计的最重要

39、的环节同时也是整个设计的核心关键所在。然而其中的布置线路、布值全局与布置图形又是整个设计中最为复杂最为困难的，该问题也以被证实为np的难题。如若使用传统的算法来优化这个问题要么会因为爆炸量的计算要么就会因为得出的结果是局部性的而非全局的，很显然传统的算法已经是不能很好解决这些棘手的问题了。于是为了解决这一抽象性的难题研究学者们想到了在集成的电路中间使用启发式的算法来进行优化。但是pso拥有更容易被实现的优点和更厉害的全局性的优化能力，学者们转而开始在vlsi的设计中使用pso，于是辨得出了更多有效的关于解决布置线路27-28、布值全局29-30与布置图形问题的dpso。 、wsnwsn作为新的

40、网络出现，它不需要事先配置那些基础的网络的设施便能实现传感器之间节点的自由组网间的通信，还拥有应用空间的广阔性。虽然wsn拥有很多的优点，但是它同时也存在着不足之处，比如它自身带有的电能是有限的，它的的通讯能力也存在很大的局限性，在节点之间的计算能力也略显不足和它的存储能力也十分的有限。以上wsn这些不足会使得无线的传感器网络之间的游泳资源相对的缺乏例如，因此要解决这些问题就显得有些迫不及待了。这几年来，表示已经有一些研究学者对wsn的各种问题展开了研究并且已经抽离出了它的数学模型来进行优化了，同时还建立了对应的pso。很多的文献都已分别提出了pso在wsn领域中的应用。还有一些学者将会深入的

41、进一步在wsn中的任务的调度中与wsn的容错拓扑的控制中应用pso来求解并得到最优的结果。 、数据挖掘它的属性的选择使用了bpso得到了解决；并已有文献提出在dpso基础之上的特征子集的选择方法；还有文献为传统的特征的选择的不足引入了粗超的简约的模型，同时还给了结合了pso和领域粗超集的模型得出新的一种新的特征的选择的算法。 、图像处理有文献提出将pso与模糊的理论相结合得出图像匹配、识别的混合算法；有文献提出使用混合的pso与局部的搜索相结合可以对生物学中的图像进行标准匹配；有文献利用了混沌的优化的搜索得出以混沌搜索为基础的pso，而且使的它与图像匹配的问题有较好的求解效果；还有文献表示可以

42、在使用pso的基础上利用红外的图像的分割的技术得到另一种快速的二维的熵算法。 、vrp虽然vrp是tsp的一种拓展的问题，但是在利用pso求解释vrp时用到了全不一样的的技术。现有文献提出了可以通过将连续空间里的粒子进行仅是的离散化然后再加粒子的位置映射到离散的排序空间中，这样便能得到粒子在离散状态下的变化情况。与其他的遗传的算法相比较，在搜索的时候rpso拥有更高的成功率，更高的最优解的质量与更优的时间复杂度。 、job2shop该问题一直都是调度和柔韧性制造的系统中人们时刻关注的一个问题之一。其用意在于利用现在拥有的资源来达到满足任务需要的约束，并且使得所有的人物能尽量在规定的时间之内较好

43、的完成。cagnina等研究学者曾在使用pso处理单机的调度问题时，边用到了随机的键来显示粒子的具体的位置。然后再利用粒子的键值对作业排序，这需要先将粒子的具体位置影射到一种合法的调度上，只有这样才能更为便捷地使用连续pso来计算出粒子具体的速度和具体的位置。在各个领域还广泛的存在很多关于pso在job2shop的应用。、其他领域综合以上所叙述的关于dpso的应用，此外，dpso在神经元的网络训练、一些有关机械的设计、通讯、化工业和经济生活等领域中都有获得许多的研究性的成果。2.2.4 本节小结 本章对dpso算法(离散粒子群算法)进行了深入浅出的介绍，首先大概介绍了dpso算法的来源、形成和

44、发展。然后展开对dpso算法详细描述，对dpso算法原理进行深刻的剖析和认识，最后为了能更好的对dpso算的理解，详细的例举了dpso在各个领域的应用。第三章 车辆路径问题分析3.1 物流配送由于互联的发展和电子商务的迅猛的发展，因而触发了物流产业的蓬勃发展，形成了物流热效应，于是对于物流管理技术的需求也日趋提高，传统的物流管理的方法已经不能满足发展的要求，因此急需对这些传统的方法进行改进，在这个改进的环节中，物流配送中问题显得尤为的重要。物流中一个重要的直接与消费者相连的环节便是物流配送。所谓的配送则是货物从物流节点送达到收货人的这一过程。配送路线的合理与否将直接影响到配送的速度、配送的成本

45、和配送最后的效益，当配送的过程是一个多用户的配送时，一条合理的配送路线将会更加的重要和必要。因此我们需要采用十分科学和有效地方法来优化配送的路线问题。随着物流产业一体化的发展，经常会将配送中的各种问题结合起来一起考虑，核心部分为配送车辆的集中货物、货物的装配与送货路线的优化。于是对配送系统优化的其实就是对车辆路径的优化。由现在的物流配送的流程图（图3.1）显然可知，配送环节成为了整个物流配送中最重要的，而存储环节则相对显得不再那么重要且趋于弱化。有数据显示在各不相同的行业中，在物流运输的全过程中用于运输的成本费用竟都已超过了50%，有的甚至到了70%以上。由此可见，对物流配送优化的过程最重要就

46、是对配送时车辆调度的优化，这其中又包括了运货路线的优化，装配货物的优化以及送货到用户的线路的优化。图3.1 物流配送流程图3.2 车辆路径问题的概述在物流的配送的供应中，经常会存在一个这样的问题：目前有着一批顾客，当前我们是知道它们的具体的位置的坐标还知道关于货物的具体的需求量，表示供应商目前拥有者许多两的车可以供派送使用，但是这些车辆具体的运载能力是确定的，要求每一辆车都必须是从起点出发的，然后需要完成若干的客户的点再回到起点的位置。现在供应商要求使用最少的车辆和最小的行程完成整个配送的任务。上面所叙述的便是该课题所需研究的vrp，也就是配送中最为关键性的问题之一，同时还被称作为车辆计划或货

47、车派送问题等。vrp因此在一般的情况下可以被描述为：在一定问题的约束的条件下，我们可以设计不同或者是相同的出发点，然后从这些出发点出发到多个不同的客户目的点的最优的送货的巡回的路径。即设计出一个消耗最小的路径集，这些最优的路径集需要满足一下几个条件：首先是每个客户目的点都只能被我们的车辆访问一次；其次我们配送的称量斗必须是从出发点出发然后访问完所有的客户目的点之后才能回到最初的出发点；最后还需要满足具体情况下的一些具体的要求。3.3 车辆路径问题的分析3.3.1 vrp的研究要素关于vrp的分析如下：将服务的抽象对象具体成一位客户，将满足客户需求表示为供应点；相反的客户所在地点则表示为需求点；

48、连接供应点和需求点并提供配送服务的车辆表示配送车辆，配送中心则为配送车辆出发的地点。现在是在一定的约束条件下，比如配货司机连续的行车时间、货物的需求量、配送的时间以及载重的限制等,然后使用已有的配送车辆，并按照由不同需求确定的顺序准时地将物品配送至需求点，同时最达到满足一个配送车辆使用最优和车辆路径最优的状态,使得配送的整个过程的运输成本能够达到最低。(如图3.2所示)图3.2 vrp示意图由以上的分析可得到关于vrp的核心问题在于配送中心的选择，其他的影响的因素有：有关相关函数的选择；不确定的约束条件；配送的车辆、配送地点、配送的时间限制和道路情况等。3.3.2 vrp的优化目标为了解决现实

49、生活中对于vrp的不同的要求，归纳总结有以下几点：、最短的总行驶路径最小化总的行驶路径能在很大程度上避免一些不可预知的道路问题。同时能减少车辆在途中的各种成本消耗。在物流配送中最常用的一种计量单位是吨位公里，其计算方法是：车辆所运输货物的吨位量乘以行驶路径的公里数。因此需要优化总的行驶路径。、最少的配送车辆最少化配送车辆数能减小车辆的各种损耗比如油耗车辆的关卡费。所以最少化车辆数根本上就是减少总的成本输出。主要包括：车辆的折损费、油耗、过路费和人工成本等。所以再一定的目标下，竟可能地减少车辆的使用，可以为企业节约成本。、最少的用时在服务性的行业中，时间往往会骑着决定的作用，因此可以说时间便是金

50、钱。同时时间减少了，可以减少车辆的空载率，从而可以有效地降低运输的成本。服务一方面体现在人员的素质上面，另一方面时间越少，显示出企业的实力和管理水平越高。设计合理的行车路线可以减少车辆的空载率，从而有效的降低运营的成本。、最大的客户满意度只有最高效的将货物送至各户手中才能得到更多的客户的信赖的和肯定，从而提高企业的形象，以此来获得更高的客户，给企业带来更多的利润的。顾客就是上帝，企业所做的一切商务活动，都是围绕着顾客进行的，特别对于一些保存时间短的货物，更是要求及时送达，以免给顾客造成一些不必要的损失，同时也损害了企业的形象。3.3.3 vrp的实现算法 前面以提到说明vrp属于np的难题，所

51、以问题的复杂度会随着客户的增加而呈现指数式的增长。因此解决vrp这类问题常用的算法有启发式，粒子群算法，还有包括本文介绍的dspo(离散粒子群算法)，能更有效的解决vrp中存在的多目标性。3.4 本章小结 本章对vrp(车辆路径问题)进行了深入浅出的介绍，首先大概介绍了物流配送形成和发展。然后展开对vrp详细描述，对vrp原理进行深刻的剖析和认识，同时对vrp的模型进行了具体的描述。第四章 车辆路径问题的建模与实现4.1 车辆路径问题的建模vrp因此在一般的情况下可以被描述为：在一定问题的约束的条件下，我们可以设计不同或者是相同的出发点，然后从这些出发点出发到多个不同的客户目的点的最优的送货的

52、巡回的路径。即设计出一个消耗最小的路径集，这些最优的路径集需要满足一下几个条件：、首先必须满足的是每一条配送路线上所有的客户目的点的总的需求量的和是不得超过每一台车辆的运载的能力，目前现在拥有k辆车，它们的运载量应该为。、其次每一个客户的目的点有且只能被访问一次，假设现在有l个客户的目的点的运输任务需呀完成，用1-l表示，其中第i个的发货点运载量为，并且；、最后每个运输车辆总的行驶的路程不能超过配送一次的最大的行驶的路程。求解满足以上要求的运输的最短的车辆行驶的路径。此模型明确的要求每一个客户的目的点都必须要得到配送的服务，在此过程中还需要不断的限制每一个客户的目的点的需求量只一车辆来完成；在

53、确保每一条的路径上的各个客户的目的点的需求不能超过了这一条路径上车辆的总的配送的需求量。如若在所有的车辆路径的中和达到了最小，便属于了对该问题的优化了。4.2 算法实现要是的问题解决的关键还是必须找到复合算法的表达式，然后再是的粒子与其相对应。有众多的文献所给的思路，在根据实际的问题产生的具体的实现步骤如下：第一步：我们首先需要对粒子群进行初始化、开始我们需要得到两个相互重叠的粒子群，所以我们需要将整个粒子群进行划分；、对每个粒子的具体的位置和具体的速度进行离散化的映射，是的它们的值都能分别属于0k和0l之间的的整数；、利用评价性的函数eval对所有的粒子进行一个评估；、将中得到的初始化的值作

54、为一个个体的历史性的最优的解pi，然后在找到子群中的最优的解pi和总的群体中的最优的解pg第二步：、根据dpso中速度、位置的更新公式进行迭代，如若超出范围的值按边界的值进行取舍。、利用评价性的函数eval对所有的粒子进行一个评估；、如若此时得到的评估值优于其之前所有历史中的任何一个评估值，便将该评估值记录为当前的历史最优的值，并同时记录下它的历史最优的位置。、重复以上步骤，直到找到满足条件的最优的解或者达到了要求的最大的迭代的次数。其中评估函数eval的主要任务为： 、函数将所得到的xr按照小到大的顺序再次进行排列得到一个新的规范的整数序列，利于以后计算行驶的距离和后面的迭代的计算。、计算每

55、一个粒子所代表的方案的距离总和。假设在某一条路径上的配送任务的总的需求超过的要求而使得方案不可行时，则函数便会将评估的值置为最大而不可达。4.3 实现代码根据以上的实现步骤的详细分析,因此可以如下设计程序： % 首先进行初始化nntwarn offcpdt=25;maxcp=1000;reqerr=0.02;maxneur=30;popsz=20;maxvel= 4;acnst1=2;acnst2=2;inwtl=9;inwt2=0.2;endepoch=1500；maxwt=0.05；cnt=0；%counter for neuron architccture%training paramc

56、ters, change these to experiment with dpso performance%type help traindpso to find out what they dotp=cpdt,maxep,reqerr,popsz,maxvel,acnst2,inwt2,endepoch,maxwt,2,1e-9,200; %选择优化方案disp(-);disp(）；disp（1.1 hiddden layer）；disp（2.2 hiddden layer）；disp（3. no hiddden layer）；arch=input(pick a necural net architecture