为了提高车辆调度优化效率，提出一种病毒进化遗传算法的车辆调度优化模型。建立车辆调度的数学模型，采用遗传算法对模型进行求解，并采用病毒群体感染主群体，主群体在历代个体间纵向传递信息以利于全局优化，病毒群体通过感染操作在同代个体间横向传递信息利于局部搜索，进行仿真对比实验。结果表明，病毒进化遗传算法较好地解决了标准遗传算法存在的不足，加快了车辆调度优化问题的求解效率，获得了更优的车辆调度方案，具有较高的应用价值。
242 015,51(15) Computer Engineering and Applications计算机工程与应用 0.8 遗传算法 病毒进化遗传算法 遗传算法 0.6 病毒进化遗传算法 倒 0.4 10 200 20 进化代数 进化代数 (a) Sphere函数的适应度对比 (b) Rosenbrock函数的适应度对比 遺传算法 遗传算法 坦001 病寺进化贵传算法 病毒进化遗传算法 150 150 200 进化代数 进化代数 (c) Griewank两数的适应度对比 (d) Rastrigin函数的适应度对比 图2遗传算法和病毒进化遗传算法的性能对比 (5)病毒感染的生命力计算,执行病毒感染、进化 fx)=2400-1c0)+1 (9)操作。 (4) Rastrigin函数,多峰,最优值为0。 (6)病毒生命力计算,病毒个体更新。 f(x)=∑[x2-10c0s(2x)+10 (10) (7)评价主群体,并将最优秀的0.1×n个体行采取 精英保留策略 标准遗传算法和病青进化遗传算法的仿直结果如 8)如果达到终止条件,输出最优车辆调度方案。 表1所示,收敛曲线如图2所示。从图2可知,标准遗传 算法明显出现早熟收敛现象,而病毒进化遗传算法的收5仿真实验 敛速度和收敛精度明显更优。对比结果表明病毒进化5.1仿真环境 遗传算法能够有效地抑制早熟收敛问题,验证了本文改 为了测试病毒进化遗传算法的有效性,在酷睿双核 进的有效性。 35GHz,8GDDR, Windows7操作系统的计算机上,采川 表1遗传算法和病毒进化遗传算法结果对比 VC-+编程进行仿真实验。仿真对象来白文献[5],其 遗传算法 病毒进化遗传算法 函数名 最优值平均值最优值平均值 包括3个仓库点:c1c2,c3,目标地为:e2ey,e4,配送 Sphere 0.12 0.40 0.04 0.25 物资分为3类:w,w2w3,其地理位置如图3所示,距离 Rosenbrock 64.54 27.15 2722 关系和需求量分别如表2、表3所示。选择遗传算法与 Griewank 0.01 0.0 文献[15]算法进行对比测试,依据对比结果对两种算法 strigil62072581504158性能优劣进行分析。 4病毒进化遗传算法的车辆调度问题求解 320km (1)设置相应的参数,主要包括:交义概率P,变异 e2}180km 概率Pn,种群数m,最大迭代次数7,概率Piet, P。和P,生命力衰减率0等。 C1 200 km- b (2)初始化种群。将每一辆车的调度任务序列设为 个染色体 (3)个体的适应度评价。采用调度方案的完成时间 与该方案的奖惩值之和的倒数作为适应度函数 (4)依据遗传算法对主群体进行选择、交叉和变异 等還传操作。 图3各仓库点、的地之间路径关系 童立君:病毒进化遗传算法的车辆调度优化模型 2015,51(15)243 表2各仑库点、目的地的运输路径距离km 6结束语 为∫提高配送车辆调度的效率和效果,针对遗传算 330 法冇在的不足,提出病毒进化遗传算法的车辆调度模 320 280 型,并采用仿真实验测试本文算法的性能,仿真结果表 表3各仓库点、目的地的物资存储量和需求量 明,本文算法不仅获得了更优的车辆调度方案,而且提 高了求解效率,可以有效降低应急物资调度成忪,为其 4 他多目标、多约束的优化问题提供了一种新的研究思想 25 15 02565 参考文献: 5.2结果分析 [1Ozdamar L, Ekinci E Emergency logistic planning in nat 5.2.1最优方案求解对比 ural disasters[J.Annals of Operations Research, 2004 遗传算法、病毒进化遗传算法和文献[l5]算法的车 217-245 辆调度最优方案收敛变化曲线情况如图4所示,从图4[2] Sheu J B. Special issue on emergency logistics management 可以清楚看出,相对于对比算法,病毒进化遺传算法的 ransportation research part E: logistics and transporta- 收敛比较快,很快就逼近车辆调度最优方案,而且获得 tion revicw[J]. Transportation Rcscarch Part E, 2005(1) 了更优的车牺调度最优方案。 3 Beradi P, Bruni M Ea probabilistic model applied to 100 emergency service vehicle location [J]. European Journal —病毒进化遗传算法 文献[15算法 of Operational Research, 2009, 196(1): 323-331 遗传算法 [4 Nanry w P, Barnes J w.solving the pickup and delivery problem with time windows using reactive tabu search[J] Transportation Research Part B: Methodological, 2000, 34 60 [5]李波,邱红艳基于双层模糊聚类的多车场车辆路径遗传 算法[J计算机工程与应用,2014,50(5):261-264. 8001000 [6 Dondo R, Mendez C A, Cerda JOptimal management of 进化代数 图4不同算法的车辆调度最优方案收敛变化曲线 logisticactivitiesinmulti-siteenvironments[j.comput ers Chemical Engineering, 2008,32(11) 522不同算法的求解效率对比 刁]黄震混合量子粒子群算法求解车辆路径问题[计算机工 为∫测试不同算法的车辆调度问题求解效率,采川 程与应用,2013,49(24):219-223 仿真实验对它们的求解时间进行测试,共进行5次实8王仁民,闭应洲改进变邻域搜素算法求解动态车辆路径 验,找到最优解的时间如图5所示。从图5可知,相对于 问题[计算机工程与应用,2014,50(2):237-24 对比算法,病毒进化遗传算法的运行时间最短,而且求 [9 Wei Yi, Kumar AAnt colony optimization for disaste 解时间比较稳定,而对比算法运行时间大幅度延长,而 licf opcrations[J]. Transportation Rcscarch Part E, 2007 且变化范围比较大,这主要是由于病毒遗传算法采用病 43:660-672 毒群体感染主群体,主样体在历代个体间纵向传递信[10]王晓博,李一军多车场多车型装卸合车辆路径问题研 息,病毒群体通过感染操作在同代个体间横向传递信 究[控制与决策,2009,24(12):1769-1714 息,加快了算法的求解收敛效率,可以满足大规模的车[11陈迎欣基于收进蚁群算法的车辆路径优化问题研究[ 辆调度优化问题求解。 计算机应用研究,2012,29(6):2031-2034. 口病毒进化遗传算法 [12 Fukasawa R, Longo H, Lysgaard J, et al. Robust branch □遗传算法 and-cut-and-price for the capacitated vehicle routing prob 口文献「51算法 lcm[J].Mathcmatical Programming, 2006, 106(3): 491-511 1]3]工君,李波带模糊预约时间的车辆路径问题的多目标禁 忌搜索算法[J计算机集成制造系统,2011,17(4):858-866. 「14]宋远清,李永生,梁慎清,等需求随机应急物配送车辆调 度问题的遗传算法饼究[计算机技术与发展,2009,19 2 仿真次数 15]邬开俊,铁君基于改进差分进化的车辆路径优化算 图5不同算法的运行时间对比 法[J计算机工程与应用,2013,49(13):17-20