资源描述：
《带多时间窗的实时车辆路径优化问题的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、带多时间窗的实时车辆路径优化问题的研究【摘要】考虑客户的多时间窗需求，建立RTVRPMTW问题模型。充分利用ACO和GA的优势，并采用了3-opt搜索、车场交换及协同机制等策略进行改进，构造了HACO。对实例进行仿真表明该算法在收敛速度和寻优结果两方面都优于另外三种算法，而且稳定性较好。【关键词】多时间窗；实时车辆路径优化;蚁群优化算法;协同机制ResearchonrealtimevehicleroutingproblemwithmultipietimewindowsLIUZhi-yong,CAIYan-guang(
2、SchoolofAutomation,GuangdongUniversityofTechnology,Guangzhou510006,China)Abstract：Consideringthemultipletimewindows,establishingrealtimevehicleroutingproblemwithmultipletimewindowsmodel.Makingfulluseoftheadvantagesofantcolonyoptimizationandgeneticalgorithm,3~op
3、tlocalsearch,depotexchangeandcollaborativemechanismwereintroducedtoimprovedthealgorithm?sperformance,thenthehybridantcolonyoptimizationwasconstrueted.Experimentsshowthatthealgorithmisbetter.Keywords：multipletimewindows；realtimevehicleroutingproblem；ACO；collabor
4、ativemechanism引言带时间窗的车辆路径优化问题(vehicleroutingproblemwithtimewindows,VRPTW)属于车辆路径问题(vehicleroutingproblem,VRP)的范畴，也属于NP~h问题，近年来，有不少学者［1-3］对VRPTW进行了深入研究,该问题一直是运筹学与组合优化领域的前沿和热点问题，且在现实生产生活中有着相当广泛的应用，因而研究该问题具有现实意义。目前，国内外对于多时间窗VRP的研究文献不少，但是考虑多时间窗的实时VRP(realtimevehicle
5、routingproblemwithmultipletimewindows,RTVRPMTW)的研究文献还相当有限，本文通过提出的混合蚁群优化算法求解该问题模型。1・问题描述及数学模型客户i(i=l,2,…，1)的需求量为gi,客户时间窗的个数，，客户要求送货的时间窗为［,］,等待费用为si,延迟费用为s2,车场个数为n(n=l,2,…，N),车辆类型为h(h=l,2,H),车辆载重为qhgi<；qh,每种类型的车辆数量为Knh,车辆到达i的时间为Ti,车辆在i服务的时间为si,客户i与j之间的距离为dij,单位
6、运价为CS,车辆启用成本为cnh,行驶时间限制为Tlimit,车辆从i到j的行驶时间为t(i,j),车辆的最长行驶时间为eval(Xs),司机工资w,路段i与j的速度为vij,车场n的路径总数为mr,路径r服务的顾客数为mp,最长驾驶时间为Tmr,车场的位置为p(0),第s个顾客被服务的位置为p(s),车场n中h类型的车辆k从i到j的运输成本为。车场编号：1+1,1+2,…，1+No决策变量如下：(1)(2)(3)目标函数：(4)约束条件：(5)(6)(7)(8)(9)(10)(13)(14)2•混合蚁群算法求解流程
7、混合蚁群算法的求解流程框图如图1所示。图1混合蚁群算法的求解流程框图3.算例仿真某企业有两车场，车场A(40,30),两种类型车辆各3辆，载重分别为35和25,固定成本分别为8和5,运输成本为1和0.&车场B(80,45),三种类型车辆各3辆，载重分别为35、20和25,固定成本分别为8、4和5,运输成本分别为1、0.6和0.8。客户信息如表1。最早和最晚发车时间分别为480和600个时间单位。司机工资为10个单位,里程约束为150个单位，车辆最大行驶时间为210个时间单位。服务时间为10个时间单位，早到和迟到惩罚系
8、数分别为1和4。v=50千米/时。表1客户信息在Intel(R)Core?i5CPU3.0GHz、内存为8.0G、win7的PC机上采用MatlabR2010b编程实现。针对RTVRPMTW模型，分别采用GA、TS、ACO和HACO进行仿真，各运行20次。GA参数设计：初始化种群N=20,最大迭代次数为800,交叉概率pc=0.9,变异概率pm
