带时间窗车辆路径问题的改进粒子群算法研究.pdf

《带时间窗车辆路径问题的改进粒子群算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2302010，46(15)c0唧曲，E，谚船e咖帆dApp趾瓜如m计算机工程与应用带时间窗车辆路径问题的改进粒子群算法研究吴耀华，张念志WUY∞_hua，ZHANGNian—zlli山东大学现代物流研究中心，济南25006l，I．IlebgisticsResearchCenter，ShandongUniVe瑙畸，Jin粕25006l，Chi咖E—mail：Mike．wu@263．netWUY∞一h聃。ZHANGNi粕一zm．ModifiedPa确ckSwamo叫miza6蛆algorithmforvemcIemuti呜problem喇胁缸e喇ndo哪．compll自盯Engin船

2、血gandAppⅡ∞a啷。2010，46(15)：230-234．Abs心an：nispapergivesakalne盯舱i曲bodIoodpanickSw硼OpliIIIi丝tion(PSO)algo甜mmatc髓optimizetIIeu出a-8iblepanicle’spoBition．Bydividingthepanickswa珊intosevemlovedappingsubgmupsand100kingf曲ne盯rIe培hbo礴inv撕一ou8subgmups，mepmposedalgorithmcan胡bctivelyimpmvethele哪ingofparticles

3、andinc他asetlIespeedofp枷cle8tofindneighbo措．Itc棚alsoincre船ethespeedto8朗rchtbe叩timizedresultVia叩timizjllgtheu耐B鹊iblepanicles．％eexperimentre一眦ltsprovetllehighe伍ciencyofthealgorithmtosolvetIlevehicler叫tingpmblem诵thtime而ndows．Keywords：localnear眦ighbor；PaIticleSwa唧0plim妇ion(PS0)；VehicleRoutingPmblem(

4、VRP)摘要：设计了一种引入局部近邻机制并且能够优化不可行解的粒子群算法。该算法将粒子群分成相互重叠的子群，在各个子群内寻找近邻，提高了粒子的学习功能和寻找近邻的速度；同时将产生的不可行解进行局部优化，增强了粒子寻找最优的能力。实验结果表明：该算法可以快速求得带时间窗车辆路径问题的满意解。关键词：局部近邻；粒子群算法；车辆路径问题DoI：10．3778，j．i88n．1002—8331．2010．15．068文章编号：1002—833l(2010)15—0230_05文献标识码：A中图分类号：TP301．6l引言由Dantzig和R且m∞r【-吁1959年首次提出的车辆路径问题(V

5、ehicleRoutingPmblem，VRP)，是—个NP“a一组合优化问题田。它是指对一系列发货(或收货)点，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件(如货物需求量、发送量、交发货时间、车辆容量限制等)的情况下，达到一定的目标(如路径最短、费用最小、耗费时间尽量少等)闭。带时问窗的车辆路径问翘日(VehicIeRoutingPmblem诵thTimeWindows。VRPlw)是在VRP的基础上增加了客户要求访问的时间窗口。在现实生活中许多问题都可以归结为VRP，rW(如邮政投递、火车及公共汽车的调度等)；它是衡量企业服务质量标准之一，所以对它的研究越来越受

6、到人们的重视。vRfyrw也是NP—hard问题f4J，先后出现了一般启发式算法和神经网络、遗传等智能化启发式算法，均取得了一些较好的效果。粒子群优化算法(Paniclesw删optimi豫tion，Ps0)御是通过对鸟群(或鱼群)的研究而得出的一种群体随机优化算法。它具有概念清晰、实现容易、便于应用等优点，在各类多维连续空问优化问题上均取得了较好的效果帅。但是由于PS0算法的寻优能力主要来自于粒子之问的相互作用和相互影响，粒子本身没有变异机制，因而PSo算法容易陷入局部最优。近年来，人们对粒子群算法作了许多改进。Veeramachaneni嘴争人提出的近邻粒子群算法，通过计入来自

7、粒子“近邻”的信息，增加了粒子群体的多样性，并以此改善了算法搜索全局最优解的能力，使算法的鲁棒性得以增强。ven嘴争人使用了不同连接拓扑的Ps0进行实验，结果表明，选择合适的邻近群拓扑，对算法性能有明显的影响。HigaLsh旧等人提出了自己的变异Ps0算法，通过引入变异算子跳出局部极值点，提高算法全局搜索能力。An异eline【il】将选择算子引入Ps0中，选择每次迭代后较好的粒子复制给下一代，以保证每次迭代的粒子群都具有较好的性能。此外，还有一些对PS0的改进，仅仅