《粒子群算法在物流路径优化中的应用 毕业论文.doc》由会员分享，可在线阅读，更多相关《粒子群算法在物流路径优化中的应用 毕业论文.doc（22页珍藏版）》请在三一文库上搜索。
1、 泰山医学院毕业设计（论文） 题目：粒子群算法在物流路径优化中的应用 院（部）系信息工程学院所 学 专 业计算机科学与技术年级、班级2006级本科1班完成人姓名 指导教师姓名专业技术职称 2010 年 6 月 10 日论文原创性保证书我保证所提交的论文都是自己独立完成，如有抄袭、剽窃、雷同等现象，愿承担相应后果，接受学校的处理。专业：班级：签名： 年 月 日泰山医学院本科毕业设计（论文）摘 要随着我国经济社会的飞速发展，各行各业对技术革新的要求愈发强烈，物流行业更是如此。常见表现在物流配送中，物流配送是指按照顾客的要求在物流配送中心进行分货、配货，并将配好的货物及时送交收货人。本设计讨论的物流
2、路径优化问题正是加速配送速度、提高服务质量、降低配送成本的关键。本设计采用粒子群算法求解在需求点和路段较少时的精确解，应用matlab进行开发和研究解决路径优化问题，较为直接的呈现问题解决的界面。基于PSO的参数，对车辆路径问题进行优化，以缩短物流配送供应过程中的供应时间，提高工作效率，降低物流行业的生产成本，提高企业竞争力。本设计仅是基于基础粒子群算法在物流路径的应用，算法原理较为简单，没有对算法进行更进一层的改进。改进方面国内外发展较为迅速，由于个人能力所限，没有对算法进行改进，但粒子群算法在现实应用中还是受到广大学者的喜爱。关键词：粒子群算法；路径优化；物流I AbstractWith
3、the rapid economic and social development of the requirements of various industries on the technological innovation increasingly strong, especially in the logistics industry. Common expression in the logistics, the logistics and distribution is in accordance with the requirements of customers in the
4、 logistics center for value, picking, and timely delivery of goods, the consignee with good. Designed to discuss the logistics of this routing problem is the speed to accelerate delivery, improve service quality and reduce the cost of key distribution. This design uses a particle swarm algorithm in
5、demand when there are fewer points and sections of exact solutions, application development and research matlab to solve the routing problem, a more direct presentation of problem-solving interface. PSO-based parameter optimization for vehicle routing problem is to reduce the supply of logistics and
6、 distribution process of the supply time and increase efficiency, reduce production costs of the logistics industry to enhance the competitiveness of enterprises. This design is only based on particle swarm optimization based on the path of the application in the logistics, the algorithm relatively
7、simple principle, there is no improvement on the algorithm one step further. Improvements and abroad to develop a more rapid, as the limited personal ability, the algorithm does not improve, but the particle swarm algorithm in real-life application or by the majority of scholars likeKeywords: Partic
8、le Swarm Optimization;Path Optimization; LogisticsII第页 共18前言目 录第一章绪论11.课题的研究背景12.课题的研究目的和意义1第二章 粒子群算法31.算法引入32.算法简介33.算法应用34.算法原理4第三章 粒子群算法在物流路径优化中的应用71.车辆路径问题72.车辆路径优化模型73.基于PSO算法的车辆路径问题74. 算法的实现过程84.1实现步骤84.2程序设计94.3结果显示125.粒子群算法和其他算法的比较13结论14参考文献15致谢16III第5页 共19页第一章 绪论第一章绪论随着我国经济社会的发展，我国物流业也去得了很大
9、的进步。而伴随着物流业的日新月异的发展，物流业中存在的问题也越来越凸出并引起物流业及人们的重视，其中物流配送中的车辆路径优化问题便是其中难题之一。物流业都希望通过最小的总耗费代价来完成高质量的服务，他们寻求各种各样的方法用以解决问题，像诸如基于梯度的优化算法，进化算法，蚁群算法等，而此设计是采用的粒子群算法优于其他算法，弥补了其他算法的缺陷，最优的用来帮助物流业可靠，快速，有效的解决配送车辆路径优化问题，降低了物流业的成本，提高了企业的竞争力，具有一定的意义。1.课题的研究背景在过去及现在的物流配送车辆路径的选择及优化中，以及选择最优路径过程和各种算法中，存在着各种各样的问题：首先，物流业选择
10、以低代价完成高质量服务即选择最优路径时，由于涉及算法、方法、设计等的复杂性及多样性存在着一定的困难。其次，有些用于处理路径优化的算法存在着一定的缺点。像遗传算法，虽然属于进化算法（Evolutionary Algorithms）的一种，它通过模仿自然界中选择与遗传的机理来寻找最优解，但是遗传算法的编程实现比较复杂，遗传算法包括：选择、交叉和变异三个算子。首先需要对具体问题进行编码，找到最优解后还要对问题进行解码，另外三个算法的实现也有许多参数，如交叉率和变异率，而且这些参数的选取都影响解的品质，这些参数的取得大部分是依靠经验。基于上述存在的问题，此设计研究粒子群算法在物流配送车辆路径优化问题中
11、的应用。弥补了其他问题的缺陷，综合了优点，达到了很好的效果，具有很强的实用性及意义。2.课题的研究目的和意义 物流配送路径的优化对加快配送速度、提高服务质量、降低配送成本、增加企业竞争力及增加经济效益都有较大的影响。物流配送路径优化问题是一个NP难题，粒子群算法能较好的解决这一问题，特别是适用于处理传统搜索方法难于解决的复杂和非线性问题，粒子群算法能提高物流配送的质量和效率，为企业增加更多的效益。 随着世界经济的快速发展和现代科学技术的进步，物流产业作为国民经济中一个新兴的服务部门，正在全球范围内迅速发展。在国际上，物流产业被认为是国民经济发展的动脉和基础产业，其发展程度成为衡量一国现代化程度
12、和综合国力的重要标志之一，被喻为促进经济发展的“加速器”。 物流的主要特征包括：1、物流的核心目的是向客户提供“准时、保质、保量、低成本”的综合服务。2、以降低服务对象的流通成本为目标，是“第三方利润来源”。3、物流过程实质上是“物流、资金流和信息流”的“三流一体化”过程。 针对以上物流特征，研究物流配送最优路径具有重要意义。而本设计即粒子群算法的物流配送车辆路径优化的开发，具有很多优点，不同于基于梯度的优化算法和蚁群算法等，粒子群算法没有中心控制约束，个别个体的障碍不影响整个问题的求解，即算法变更具有鲁棒性；采用非直接的信息共享方式实现和做，算法具有扩充性；该算法对于复杂的，特别是多峰高维的
13、优化计算问题具有很强的优越性。此外粒子群算法受所求问题维数的影响较小，原理简单，所需要的代码和参数较少。同时，粒子群算法业具有像蚁群算法一样的相似的特点：都是一类不确定的算法；都是一类概率性的全局优化算法；都不依赖于优化问题本身的严格数学性质；都是一种基于多个智能体的仿生优化算法；都具有本质并行性；都具有稳健性和自组织、进化型等等。粒子群算法作为新型群体智能算法的代表，自提出之后，因其概念简明、实现方便，在短期内就得到了国际演化计算研究领域的广泛认可，并在在解决复杂的组合优化类问题中体现其优越性能，被广泛的应用在工程设计及优化、电力系统、机器人控制以及生物医学和电磁学领域。总之，本粒子群算法基
14、于matlab语言的关于物流配送中车辆路径优化的设计与开发具有很强的实用性和实际意义。2第二章 粒子群算法第二章 粒子群算法1.算法引入本设计是为物流业中的配送过程中的车辆路径优化问题而开发研究的。系统为物流业的配送分析服务，使其以最小的总耗费代价完成服务。也就是平常所说的要求以最少的车辆数、最小的车辆总行程来完成货物的派送任务，即车辆路径问题（vehicle routing problem,VRP）,有时也称为“车辆计划”、“货车派遣”等。而设计的总耗费最小的路线集，必须满足一下条件:每个城市或客户只被一辆车访问一次，所有车辆从起点出发再回到起点，某些约束被满足。解决路径优化的方法很多而粒子
15、群算法是解决车辆路径问题的最有效的方法。主要特点有实现容易、精度高、收敛快等。2.算法简介 粒子群算法是群体智能算法（swarm colony algorithm）的一种,群体智能算法也属于启发式算法。从20世纪90年代初，已存在模拟自然界生物的群行为来为构造随机优化算法的思想。典型的方法有Dorigo提出的蚁群算法和Eberhart与Kennedy提出的粒子群算法。 粒子群算法最早是由Eberhart和Kennedy于1995年共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，他们的模型及仿真算法主要是利用生物学家Hepper的模型。在Hepper的仿真模型
16、中，鸟类在一块栖息地附近聚群，这块栖息地吸引着鸟，直到它们降落到这块地上。Hepper的模型中鸟知道栖息地的位置，但是实际情况中，鸟类在刚开始是不知道食物的所在地的。所以Kennedy等认为鸟之间存在着某种交换信息，于是他们在仿真中加入一些内容：每个个体能够通过一定规则估计自身位置的适应值；每个个体能够记住当前所有找到的最好位置，称为“局部最优pbest”；此外还要记得群体中所有鸟中找到的最好位置，称为“全局最优gbest”。这两个最优变量使得鸟在某种程度上朝这些方向靠近。他们综合了这些内容，提出了实际鸟群的简化模型，即我们所说的粒子群算法。Eberhart和Kennedy把此算法应用到神经网
17、络权重的训练中，并且用其来求解一些基准测试函数，从而证实此算法的实用性。3.算法应用PSO是非线性连续优化问题、组合问题和混合整数非线性优化问题的有效优化。工具粒子群算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，并且不需要梯度信息。目前已经广泛应用于函数优化、神经网络训练、模糊系统控制及其他遗传算法的应用领域。Parsopoulos等将PSO用于解决多目标优化问题、最小最大化问题、整数规划问题和定位所有全局极值等问题。其中具体应用实例有：模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测和时频分析等。4.算法原理粒子群算法的理论研究包括微观和宏观两个层面的分析。微观上
18、是对单个粒子在解空间飞行轨迹作为参考，单个粒子的行为过程在一定程度上反映了群体的变化趋势。宏观上则是整个群体的行为作研究，分析群体一般性的搜索过程，建立合理的数学模型，讨论算法的收敛性。粒子群算法原理简单。在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表着一个潜在的解。例如，在一个D维的目标搜索空间中，每个粒子看成空间内的一个点。设群体由m个粒子构成。m也称是群体的规模，过大的m会影响算法的运算速度和收敛性。设Zi=（Zi1，Zi2，ZiD）为第i个粒子（i=1,2,，m）的D维位置矢量，根据事先设定的是一个适应值函数(与要解决的问题有关）计算Zi当前的适应值，即可衡量粒子位置的优劣
19、；Vi=（Vi1，Vi2，Vid，ViD）为粒子i的飞行速度，即粒子移动的距离；Pi=（Pi1，Pi2，Pid，PiD）为粒子迄今为止搜索到的最优位置；Pg=（Pg1，Pg2，Pgd，PgD）为整个粒子群迄今为止搜索到的最优位置。在每次迭代中，粒子根据一下式子更新速度和位置：Vidk+1=Vidk+c1r1（Pid-Zidk）+c2r2（Pgd- Zidk） （2-1）Zidk+1= Zidk + Vidk+1 （2-2）其中，i=1,2,，m，d=1,2,D,k是迭代次数，r1和r2为0,1之间的随机数，用这连个参数来保持群体的多样性。c1和c2为学习因子，也称为加速因子，使粒子具有自我总结
20、并向群体中优秀的个体学习的能力，从为使自己从局部最优“pbest”向全局最优“gbest”靠近，从而达到群体内历史最优点。这两个参数对粒子群算法的收敛起的作用不是很大，但是如果适当的调整这两个参数，可以减少局部最小值的困扰，当然也会使收敛速度变快。由于粒子群算法中没有实际的机制来控制粒子速度，所以没有必要对速度进行最大值的限制，当速度超过这个阈值时，设其为Vmax，这个参数被证明是非常重要的，因为值太大会跳过最好解，但是如果值太小又会导致对搜索空间的不充分搜索。所以速度的最小值Vmin,位置Zi的取值范围为ZminZmax。公式（2-1）的第二项是“认知”部分（cognition part），
21、代表粒子对自身的学习。而第三项是“社会”部分（social part）,代表粒子之间的协作。公式（2-1）正是粒子根据它上一次迭代速度、当前位置和自身最好经验与群体最好经验之间的距离来确定更新速度，然后根据公式（2-2）飞向新的位置。粒子群算法主要遵循五个基本原则，定义为： （1）邻近原则（proximity）：粒子群必须能够进行简单的时间和空间计算； （2）品质原则（quality）：粒子群必须能对周围环境的品质因素有多反应（变量局部最优pbset和全局最优gbest隐含着这一原则）； （3）定性原则（stability）：粒子群不应该在每次环境改变时都改变自身的行为； （4）多样性反应原则
22、（diverse response）：粒子群不应该在过于狭窄的环境中活动； （5）适应性原则（adaptability）：在能够接受的计算量下，粒子群能够在适当的时候改变它们的行为。5. 算法流程 根据算法原理，算法实现的NS图可设计如下表2-1所示： 开始 选择阈值和最大迭代次数：Nmax 初始粒子的位置Zi(0)=(zi1,zi2,ziD),i=1,2，m 初始每个粒子的速度Vi(0)=(vi1,vi2,viD) 测量每个粒子的适应值Zi(0),表示为Di(0)(设此处解为最小化的目标函数) Pi(0)=Zi(0) 根据D（0）=minD1(0),D2(0),Dm(0)找出全局最优Pg(0
23、) K=0步骤一 KK+1 根据公式一更新Vi(k) 根据公式二更新Zi(k)步骤二测量Zi的适应值，表示为Di(k),D（k）=minD1(k),D2(k),，Dm(k) 更新Pi（k）和Pg(k) 如果（D（k-1）-D(k)）/D(k) 且k);disp( );disp(1. Particle Swarm Optimization);disp(2. Standard Backprop);meth=input( Pick training method );disp( );disp(-);disp( );% XOR function test set P=0,0;0,1;1,0;1,1;
24、T=1;0;0;1; minmax=0,1;0,1; l1=0; l2=1; tr(1)=99; % arbitrary choice of initial error just used to update # of neurons%判断选择结果，运行相关子函数if arch=3 w1,b1=initff(minmax,1,tansig); if meth=1 w1,b1,te,tr=trainpso(w1,b1,tansig,P,T,TP); elseif meth=2 w1,b1,te,tr=trainbp(w1,b1,tansig,P,T); end elseif arch=1 whi
25、le tr(end)reqerr l1=l1+1; w1,b1,w2,b2=initff(minmax,l1,tansig,1,purelin); if meth=1 w1,b1,w2,b2,te,tr=trainpso(w1,b1,tansig,w2,b2,purelin,P,T,TP); elseif meth=2 w1,b1,w2,b2,te,tr=trainbp(w1,b1,tansig,w2,b2,purelin,P,T); end if l1maxneur break end endelseif arch=2 while tr(end)reqerr if l1l2 l2=l2+1;
26、 else l1=l1+1; end w1,b1,w2,b2,w3,b3=initff(minmax,l2,tansig,l1,logsig,1,purelin); if meth=1w1,b1,w2,b2,w3,b3,te,tr=trainpso(w1,b1,tansig,w2,b2,logsig,w3,b3,purelin,P,T,TP); elseif meth=2 w1,b1,w2,b2,w3,b3,te,tr=trainbp(w1,b1,tansig,w2,b2,logsig,w3,b3,purelin,P,T); end if l1maxneur break end endend4
27、.3结果显示 运行以上程序，经过几次运行，得到如图4-1所示结果：图4-1算法运行结果图5.粒子群算法和其他算法的比较1、粒子群算法与最小生成树的比较 假设要在物流的n个客户点建立发货网，则连通n个客户点只需要n-1条线路。可以用连通网来表示n个客户点及n个客户点间可能设置的连通线路，其中网的顶点表示客户点，边表示两客户点之间的线路，赋予边的权值表示相应的路程。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个发货网。 这个问题就是构造连通网的最小代价生成树（简称最小生成树）的问题。生成树算法有两种分别是普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。其中Prim
28、算法结果是唯一的，但是它的时间复杂度是O（n2），n代表节点数；而Kruskal算法结果并不唯一，时间复杂度是O（e),e代表边数。所以在实际应用中客户点数比较多时，生成树算法的缺点就显示出来了，运算时间长且算法结果不定。2、粒子群算法与遗传算法的比较 文献1比较了遗传算法和粒子群算法在车辆路径优化问题上的应用。所采用的平台是windows 2000，MATLAB6.1，其中遗传算法采用文献2中的染色体编码方式和相关参数；粒子群算法参数采用满足文献8中约束条件的参数。具体参数设置如下：GA参数：群体规模n=40，交叉概率Pc=0.6；变异概率Pm=0.2；轮盘赌法选择子代，最大迭代次数为200
29、。PSO参数：粒子数n=40，邻居群采用环形（Ring）拓扑结构，邻居子群规模为3；w=0.729；c1=c2=1.49445；最大迭代次数为200。文献1对GA和PSO算法分别运行50次，统计结果如下表3-1所示：表3-1算法比较 方法 达到最优路 未达到最优 达到最优路径时 达到最优路径时 径次数 路径次数 平均迭代数% 平均时间S GA 32 18 53.9 32.3 PSO 50 0 28.36 3.04实验结果表明，PSO方法对该问题的搜索成功率100%，远远高于GA方法的64%，而且达到最优路径的速度比GA方法提高10倍左右。说明在该问题上粒子群算法（PSO）效果高于遗传算法（GA
30、）。结论结论在调查研究准备后，经过一个多月的精心设计与制作，粒子群算法的物流配送过程中的车辆路径优化的设计开发研究已经基本完成。该设计主要实现设计一个总耗费最小的路线集，用最少的车辆数、最小的车辆总行程来完成货物的派送任务。从而提高了物流企业的效益以及市场的竞争力，具有一定的实际意义。本设计采用了粒子群算法和MATLAB编程，简单易懂。但由于时间仓促，考虑的可能不是很周到，问题处理的不是非常的完美，只能做到小型的一个物流配送车辆路径的优化。设计的功能不够全面，规模不够强大。因此，本设计有待进一步的改进和提高，使本设计功能和规模趋于完善。 粒子群算法较生成树算法和遗传算法而言都有比较明显的优势，
31、在实际应用中能提高计算的时间，较好的选择出较优路径，算法理解容易，实现速度快并有较强的收敛性，被广泛的应用到其他研究领域。 17泰山医学院本科毕业设计（论文）参考文献1 Salmen A,Ahmad I,AI-Madani B. Particle swarm optimization for task assignment problemJ. Microprocessors and Mierosystems,2002,26:363-371.2 李宁,邹彤,孙德宝.车辆路径问题的粒子群算法研究J.系统工程学报, 2004,41（23）：43-46.3 Shi Y,Eberhart R C.Emp
32、irical study of particle swarm optimizationC. Processdings of the 1999 Congress on Evolutionary Computation. Piscataway :IEEE Service Center,1999:1945-1950.4 Maurice C,Kennedy J.The particle swarm-explosion , stability ,and convergence in a multidimensional complex spaceJ. IEEE Transactions on Evolu
33、tionary Computation,2002,6(1):58-73.5 肖键梅,李军军,王锡淮. 求解车辆路径问题的改进微粒子群优化算法J. 计算机集成制造系统,2005,11（4）:577-581.6 陈曦,蒋加权.带变异粒子群算法在车辆路径问题中的应用J.计算机与数字工程,2005,34（9）:19-21.7 李宁.邹彤.孙德宝. 带时间窗车辆路径问题的粒子群算法J. 系统工程理论与实践,2004,（4）:130-135.8 李军,郭耀煌. 物流配送车辆优化调度理论与方法M.北京:中国物流出版社,2001.9 陈容秋,广东省现代物流业发展的制约因素及对策建议P.2003,（2）:394
34、1.10 Kennedy, J. and Eberhart, R. C. Particle swarm optimizationC. Proc. IEEE intl conf. on neural networks Vol. IV, pp. 1942-1948. IEEE service center, Piscataway, NJ, 1995. 11 Eberhart, R. C. and Shi, Y. Comparison between genetic algorithms and particle swarm optimizationC. Evolutionary programming vii: proc. 7th ann. conf. on evolutionary conf., Springer-Verlag, Berlin, San Diego, CA., 1998.