多约束条件车辆路径问题的二阶段遗传退火算法

《多约束条件车辆路径问题的二阶段遗传退火算法》由会员分享，可在线阅读，更多相关《多约束条件车辆路径问题的二阶段遗传退火算法（11页珍藏版）》请在装配图网上搜索。

1、多约束条件车辆路径问题的二阶段遗传退火算法第39卷第12期2005年12月西安交通大学JOURNALOFXIANJIAOTONGUNIVERSITYVo1.3912Dec.2005多约束条件车辆路径问题的二阶段遗传退火算法吕军,冯博琴,李波(西安交通大学电子与信息工程学院,710049,西安)摘要:针对多约束条件的多配送中心有时间窗车辆路径问题,提出了一种二阶段遗传退火算法.在第1阶段,使用遗传算法对客户按供应量和路径长度进行模糊分区;在第2阶段,采用二维变长染色体编码及相应的遗传算子进行混合遗传算法的全局优化.在初始种群生成和交叉,变异算子中采用了随机贪心算法以避免无效解,并利用退火选择来提

2、高种群的多样性.实验结果表明,二阶段遗传退火算法可加速收敛,提高搜索效率,在模糊分区上的搜索速度较之标准遗传算法提高了3410倍.关键词:车辆路径;遗传退火算法;贪心算法中图分类号:TP18;Ul16文献标识码:A文章编号:0253987X(2005)12129904Two-PhaseGenetic-AnnealingAlgorithmforVehicleRoutingProblemwithMultipleConstraintsL/Jun,FengBoqin,LiBo(SchoolofElectronicsandInformationEngineering,XianJiaotongUniver

3、sity,Xian710049,China)Abstract:Anoveltwophasegenetic-annealingalgorithmisproposedtosolvethevehicleroutingproblemwithtimewindow(MDVRPTW)andmulticonstraintinmultipledispatchingcenters.Inthefirstphase,usersarepartitionedintofuzzyregionsaccordingtoquantitysuppliedandthelengthofpathsusinggeneticalgorithm

4、;inthesecondphasetheglobaloptimizationiscarriedoutbythehybridgeneticalgorithmwith2Dvariable-lengthchromosomesandcorrespondinggeneticoperators.Therandomgreedyalgorithmisusedingeneratingofinitialpopulationandcrossoverandmutationoperatortoavoidinvalidsolution.thenthesimulatedannealingalgorithmisemploye

5、dtoenhancethediversityofpopulation.Theexperimentalresuitsshowthatcomparedwiththetraditionalgeneticalgorithmthesearchspeedoftheproposedalgorithmis3410timesfaster,theconvergenceisspeedup,andsearchefficiencyisincreased.Keywords:vehiclerouting;gP以Pc口72以P口Z以galgorithm;greedyalgorithm车辆路径问题(VehicleRouting

6、Problem,VRP)是一类经典的NP难问题_1,目标函数通常为车辆数和运输成本最小化.随着约束条件的不同,VRP演化出许多模型,如非对称VRP(AVRP),带时间窗的VRP(VRPTW)及多配送中心的VRP(MDVRP)等,而现实环境中的问题往往是以上模型的混合.VRP的求解算法主要有精确算法和启发式算法.对大规模的VRP问题,启发式算法能在较短的时间内获得满意的近似最优解,这种算法主要指构造型算法,改进型算法,导向邻域搜索算法l2,也有许多研究是这些算法的某种混合算法.对于复杂约束VRP问题的遗传算法,其简单的编码必然损失解的大量信息,所以需要设计合适的编码方案.另外,由于约束的增加,会

7、造成整个搜索空间不连续,使邻域搜索更加困难.一般的遗传算子易导致大量的解因违背约束条件而成为无效解,必须针对问题的特殊性设计相关的交叉,变异算子.收稿日期:20050408.作者简介:吕军(1968),男,在职博士生,高工;冯博琴(联系人),男,教授,博士生导师.基金项目:国家高技术研究发展计划资助项目(2003AA001048).1300西安交通大学第39卷本文提出的二阶段遗传退火算法采用二维变长编码保存合法解的各种约束条件,并在初始种群生成和交叉,变异算子中采用随机贪心算法以避免出现无效解.为了缓解种群的多样性损失,在种群竞争中还引入了模拟退火选择机制.算法在第1阶段对客户按供应量和路径长

8、度进行模糊分区,以减少多配送中心的搜索空间.1问题描述实际的多约束条件,多配送中心带时间窗VRP(MDVRPTW)的配送环境可用度量空间M和个要货任务来描述,要货任务中包括g种不同的商品,由k个车辆从个配送中心装载,配送.用一个加权图G(V,E)来表示M,其中为结点集合,包括个配送中心位置,个要货点位置和k个车辆的初始停放点位置;用d.表示结点间链路Z(i,J)E的权值(路径距离);用D三表示配送中心d可供应第t种商品的数量.对于车辆(,=1,),记,为车辆的最小,最大装载量,记,为车辆的固定成本和每公里成本,记为车辆的运行速度,记.,为车辆的工作时间.对于要货任务r,记R为要货数量,记R,R

9、WC为要货时间窗,记DGTf1,如果商品类型为t一0,否则为要货的商品类型(r一1,;t一1,g).在配送方案中,定义如下变量,即fl,如果车辆从配送中心d装载l0,否则f1,如果要货r由车辆完成一10,否则f1,如果车辆经过弧ijl0,否则变量中,弧ij包括从车辆停放点到配送中心,配送中心到要货点及要货点之间的路径,并记s为车辆对要货r的卸货量.配送成本主要是车辆的使用成本,车辆的使用成本包括固定成本c及运行成本c,其中一(r一1,V),一s?d,(i,J一1,聍2+kV).由于有时间窗限制,还会产生惩罚成本,若车辆超时返回,则产生额外费用C.因此,多配送中心车辆配送的优化目标可表示为rai

10、nC一(,+)+c1.t,>(上)一1,k:r:1,J并满足约束条件EsS,1r:1.VJ广厶,ssRD,r>(3)=1,是ir一1,Vd,tJs,=1,kVr(4)2二阶段遗传退火算法本文提出的算法分为2个阶段,第1阶段仅考虑不同商品的供,需情况及路径长度,而忽略车辆,时间窗等其他因素,对要货点进行模糊分区;第2阶段综合全部约束条件,搜索满意配送方案.第1阶段使用遗传算法,并在进化过程中使用修补算子;第2阶段则结合了贪心算法,模拟退火算法和遗传算法.2.1模糊分区阶段第1阶段的目标是对各要货点进行模糊分区,以降低第2阶段的计算量.这一阶段采用带修补算子和局部优化的遗传算法.编码采

11、用多代理TSP常见编码(代理/结点混合编码),选择采用锦标赛法,交叉算子采用两点随机交叉,变异算子采用两点随机交换.由于初始种群是随机产生的,且交叉,变异算子并未考虑商品的供应情况,所以需对个体按供应量进行修补.对所有分组,分商品计算总要货量,而对于总要货量大于配送中心供货量的,应将选取满足供应且移动后路径长度增加最少的要货移到另一分组.进化结束后选取最优的p个个体,从中提取各要货可用的配送中心集合供第2阶段使用.2.2整体优化阶段整体优化过程描述如下.(1)编码设计采用二维结构,由于要货数量可能大于最大车辆装载量,某些要货可能会被分批次送货,所以应以车辆的要货分配为基因,并在基因片断中反映本

12、车辆在要货点的卸货量.车辆的基因格式为vjD,(R1,R2,R)(L1,L2,L),其中D,为车辆装货的配送中心;R(i一1,2)k)为要货点,为本车总服务数,其顺序表示车辆运行路线;L为本车辆在要货点的卸货量.经多轮次分派后会第l2期吕军.等:多约束条件车辆路径问题的二阶段遗传退火算法产生虚拟车辆,虚拟车辆的初始有效时间可在算法搜索过程中得以修正,其余参数如同正常车辆.染色体由各个车辆(含虚拟车辆)的基因片断构成.可以看出,染色体为二维结构,其基因片断和基因个数均是变长的.(2)算法的控制参数包括群体规模N,交叉概率P,变异概率P等,初始种群由以下随机贪心算法生成:S.一全部要货;while

13、(S.!=)从S.中随机选取要货;Lf的要货量;while(L!:0)对从其模糊分组中选取所有配送中心,可用车辆计算最优插入车辆,;将按近邻插入法插入,;L,=LMin(L,剩余容量);SoSo一;.退火算法的初始化参数包括初温Tk(设置为初始种群适应值的均方差),退火条件,退火速率等.(3)个体适应值用式(1)生成,对所有个体按适应值排序后,应用式P:C(1一c)决定个体的选择概率,其中表示个体在种群中的序号,表示适应值最高的个体选择概率,C也是算法的参数之一.(4)染色体中的模式可理解为基因片断(即车辆分配向量)在交叉中应尽量保持优良分配信息:用选择算子选出2个父代个体P,P:;从P中随机

14、选择S个基因片断,O%s%m,并将整个分组复制到一个子代个体上;从Pz中选择剩余基因片断,删除其中已经出现在中的要货并进行复制;使用随机贪心算法把O中没有分配的要货,加入到P复制的某个片断中;对P,P2反向执行上述过程生成子代个体.(5)随机选择一个基因片断,删除其全部要货分配,并使用随机贪心算法重新分配.(6)采用了2种策略进行局部优化,一是搜索虚拟车辆(多轮次分派,故出发时间较晚)中超过时间窗的要货和在第1轮次分派车辆中满足约束,时间窗较晚的要货,并进行交换;二是对各车辆中要货按2-opt法进行路径优化.(7)子代接受条件使用退火策略,如果子代个体优于父代,则直接替换;否则,以概率minl

15、,exp(-zx/rk)接受子代,其中为新旧代适应值之差,为温度.算法运行代或连续G代无进化则停止,退温函数采用一rk,为退温速率,退火条件为连续G代无进化.3实验分析基于本文算法的系统已在一个省级成品油配送中心投入运行.限于篇幅,此处仅给出模糊分区的效果分析及遗传退火算法的多样性和搜索效率分析.运行数据表明,使用模糊分区可有效降低运行时间的复杂度.在各油库资源充足的情况下(对应于无资源限制的MDVRP模型),50以上的要货点模糊分组的油库个数不会大于2,最大模糊分组的油库数为4.在某种商品资源紧缺的情况下,小分组数要货点的个数明显减少,显示出各要货点竞争资源的特性.为测试模糊分组对整体优化结

16、果的影响,在整体优化时将所有分组初始化为全部油库(即采用单阶段整体优化).多次运行结果表明,运行时间(主要是贪心算法的搜索时间)延长了3410倍,优化结果无明显改善.为了评价随机贪心算法产生初始种群的多样性,要对种群中所有个体提取元组(De,R.,R.,V),该元组元素分别表示油库,出发点(要货点或油库),到达点(要货或油库),车辆种类,它可反映配送中心,车辆及要货点配送的顺序.通过计算所有个体与当代最优个体元组集的差值,可以获得初始种群所有个体的差异(距离)和适应值的分布,如图1所示.图1种群适应值/距离分布从图1中可以看出,随机贪心算法生成的初始种群含有一些优良的个体,并具有较好的多样性.

17、为考察局部优化算法和退火选择的效率,先去掉局部优化,并采用父代和子代择优竞争生存模式西安交通大学第39卷(tg即纯遗传算法),记录进化过程中个体的最差,平均及最优适应值(见图2),再记录混合遗传退火算法进化过程中的相应数据,结果如图3所示.图2纯遗传算法的进化过程图3混合遗传算法的进化过程从图2,图3的对比中可以看出,混合遗传退火算法的初始种群的最差的个体适应值显着优于纯遗传算法,均值及最优个体的适应值也具优势,它显示出局部优化能有效改进个体的适应值.图3的最差个体值进化曲线变化较大,这是退火选择能接受较差个体概率的结果,而最优个体值的进化情况则比图2中的大有改进,进化结束后的最优个体值也具优

18、势.对比分析结果表明,混合遗传退火算法的搜索效率明显高于纯遗传算法.4结论本文针对多约束MDVRPTW的实际工程应用,提出了一种二阶段遗传退火算法,使用遗传算法在第1阶段对要货点进行模糊分区,以缩小优化计算的搜索空间;在第2阶段,设计了能有效保持约束信息的编码方案及相应的遗传算子,以随机贪心算法产生初始种群,并对个体使用局部爬山算法,来提高遗传退火算法的搜索效率.实验结果表明,模糊分区显着降低了计算复杂度,而混合遗传退火算法能有效保持种群的多样性和搜索效率.算法的实现系统已经成功地运用在某省级成品油配送中心,极大地提高了配送效率,降低了配送成本,并对油库资源的平衡摆布优化提供了参考依据.参考文

19、献:1DantzigGB,RamserRH.ThetruckdispatchingproblemJ.ManagementScience,1959,6(1):8O一91.2BrfiysyO,BergerJ,BarkaouiMAnewhybridevolutionaryalgorithmforthevehicleroutingproblemwithtimewindowsA.TheRoute2000Workshop,Skodsborg,Denmark,2000.3ZouT,LiN,SunDB.Geneticalgorithmforvehicleroutingproblemwithtimewindow

20、withuncertainvehiclenumberA.FifthWorldCongressonIntelligentControlandAutomation,Hangzhou,China,2004.4LouisSJ,YinXY,ZhenYY.MultiplevehicleroutingwithtimewindowsusinggeneticalgorithmsA.CongressonEvolutionaryComputation,WashingtonDC,1999.5MakKI,GuoZG.Ageneticalgorithmforvehicleroutingproblemswithstocha

21、sticdemandandsofttimewindowsA.IEEESystemsandInformationEngineeringDesignSymposium,Charlottesville,USA,2004.(编辑苗凌)西安加速器质谱中心完成设备安装由国家科技部,教育部和中国科学院共同出资,西安交大与中科院西安地球环境研究所共建的西安加速器质谱中心,已经完成了所有设备的安装工作.据西安交大科技园相关人士介绍,具有国际一流水平的西安加速器质谱中心,将利用国外引进的先进设备和技术,围绕环境变化这个主题,综合运用地球科学,考古学,生命科学等学科领域的知识,建立分析与共享为一体的大型科学仪器装备实验基地,为在西部形成一个跨部门,跨学科,优势互补,协同攻关,强强联合的国家级综合型科研基地,为我国科学家获得原创性学术成果提供技术保障.(来源:西安日报)