基于改进遗传算法的弹药运输车辆调度问题研究

陈立云, 卢 昱, 晏 杰, 刘云龙

(1.军械工程学院信息工程系,河北石家庄050003; 2.军械工程学院,河北石家庄050003)

基于改进遗传算法的弹药运输车辆调度问题研究

陈立云1, 卢 昱2, 晏 杰1, 刘云龙1

(1.军械工程学院信息工程系,河北石家庄050003; 2.军械工程学院,河北石家庄050003)

建立了弹药运输车辆调度问题的数学模型,针对传统遗传算法求解该问题具有收敛速度慢、易陷入局部极小的缺点,提出了一种改进的遗传算法予以求解。在改进算法中引入一种基于信息素的遗传交叉算子,该算子能利用以信息素形式保存的全局信息,从而提高收敛速度;算法中的变异算子采用Relocation、Exchange、2-opt*及2-opt 4种启发式搜索算法,尽可能扩大搜索范围。算例分析表明了所提改进遗传算法求解弹药运输车辆调度问题的有效性和可行性。

弹药运输;车辆调度;遗传算法;信息素;交叉算子

战时弹药供应,是装备物资供应的重要组成部分,是装备部门最主要的保障任务。在确定好弹药分配后,运输车辆的优化调度就成了缩短弹药供应时间、提高弹药供应效率的重要方法。弹药运输车辆调度问题指的是对弹药运输车辆确定适当的行车路线,使它们有序地通过弹药仓库及其保障的阵地,在满足一定的约束条件下(如各个阵地的弹药需求量、车辆容量限制、行驶单程限制、时间限制等),达到一定的目标(如路程最短、时间尽量少等)。对于规模较大的弹药运输车辆调度问题,精确求解变得非常困难,所以有必要寻求高效近似的优化算法[1]。本文借鉴蚁群算法[2]中采用信息正反馈的机制,在遗传算法[3]中引入一种新的基于信息素的遗传交叉算子[4]1185,同时,变异算子采用了Relocation、Exchange、2-opt*及2-opt 4种启发式搜索算法。实验表明所提改进遗传算法求解弹药运输车辆调度问题的有效性和可行性。

1 弹药运输车辆调度的问题描述与建模

弹药运输车辆调度的问题可描述如下：假设在装备保障地域有1个弹药仓库,仓库共有K辆运输车,向附近的n个阵地供应弹药,每个阵地的弹药需求量为di(i=1,2,…,n),阵地所需的弹药全部都来自弹药仓库。每辆运输车的最大装载量均为q(q＞di,i=1,2,…,n),能行驶的最大路程为D。每个阵地只让1辆运输车对其运输弹药。如何确定各个车辆的行驶路线,使得仓库向各个阵地完成一次弹药配送的时间最短,即目标为使一次配送中时间消耗最大的行驶路线达到耗时尽可能小。

根据以上的问题描述,建立数学模型如下：设节点集合U={u0}表示仓库,V={vj|j=1,2,…, n}表示阵地,W=U∪V={wm,m=0,1,2,…,n}表示仓库和所有阵地,则边(弧)集A={(wi,wj)| wi,wj∈W,且i≠j}表示车辆在仓库及其保障的阵地之间可能走过的路径的集合,每条边(wi, wj)的距离为cij,车辆在边(wi,wj)上行驶的速度为sij。设决策变量为

式(1)为目标函数,即使一次配送中时间消耗最大的行驶路线达到耗时尽可能小;式(2)确保每个阵地只有1辆车运输弹药;式(3)保证到达和离开某阵地的车为同一辆;式(4)规定了每条线路能使用车辆的最大数目为1;式(5)是车辆的最大行驶距离约束;式(6)保证车辆没有超载;式(7)定义了决策变量的取值范围。

2 改进遗传算法求解弹药运输车辆调度问题

本文对遗传算法的改进主要是2个方面：一是引入了一种基于信息素的遗传交叉算子;二是变异算子采用了Relocation、Exchange、2-opt*及2-opt 4种启发式搜索算法,采用该改进遗传算法求解弹药运输车辆调度问题的过程如下。

2.1 染色体表示及适应度评价

使用长度为n+K+1的整数串表示染色体,其中n为阵地数,K为线路(车辆)数量。在染色体中,n个阵地分别用[1,n]的整数表示,0表示仓库,并用于将各线路分开[5]。例如1个染色体为0→2→5→7→0→6→4→1→9→0→8→3→0,它表示第1辆车依次向阵地2、5、7运送弹药,第2辆车依次向阵地6、4、1、9运送弹药,第3辆车类似。

种群中个体的适应度采用基于排序的适应度评价方法进行计算。计算适应度时,首先将种群中的所有个体按其中的单条线路消耗时间最大值由小到大进行排序,时间最短的路线得到序号1,其余依次类推。则序号为i的个体的适应度为

其中,Gpop_size为种群规模,FfitMax为适应度的最大值,FfitMin为适应度的最小值。本文中,FfitMax和FfitMin分别设置为1.2和0.8。

2.2 初始种群的生成

按照染色体表示规则,先采用最近邻居的原则生成每一辆车的运输路线,再将几辆车的运输路线连接起来就构成了1个个体。令r(i)表示车辆供给的第i个阵地。每一辆车的运输路线构造过程如下：① 将仓库作为起始点,即每辆车路线的第一位为“0”,h=1,随机选择1个阵地作为r(h),h=h+1;②从未被供给过的阵地中选择距离阵地r(h-1)最近的阵地w作为路线中的第h个阵地r(h);③检查车辆为前h个阵地运输弹药是否满足车辆的载容量约束条件,若不满足,则将阵地w放回到当前未被供给过弹药的阵地集合中,该辆车的路线构造完毕,即为0→r(1)→r(2)→…→r(h-1),否则令h=h+1,返回②。最后,将这几辆车的运输路线连接起来就构成1个个体,如果构造了Kx(Kx＜K)辆车的运输路线后,所有阵地就已经可以被供给弹药了,那么就需要在Kx辆车的运输路线连接起来后,在其尾部补K-Kx+1个0,一方面统一染色体长度,另一方面方便下一步对染色体进行变异操作,为没有安排运输路线的车辆安排运输补给任务,从而寻找问题的优化解。

2.3 选择算子

这里采用轮盘赌选择策略从种群中选择个体进行交叉。种群中个体的被选择概率采用按比例的适应度分配方法,即适应度为fi的个体fi,其被选择的概率为

2.4 交叉算子

早期的遗传交叉算子在生成子个体时,通常只考虑各阵地的位置或它们之间的顺序,这类算子可以看作是“盲目”交叉。另外一些交叉算子在构造子个体时只能利用一些局部信息,如边的长度、邻接关系,而很少利用可能会有助于产生较优个体的全局信息。这里引入基于信息素[6]的遗传交叉算子,该算子在构造子个体时不仅能利用局部信息,还可以利用以信息素形式保存的全局信息。

交叉时,基于信息素的交叉算子首先随机选择1个阵地i作为子个体中的第一个阵地,然后在其2个父代个体中搜索阵地i,以获取其前后的阵地(称之为邻居)。显然,邻居最多包含4个阵地。交叉算子将从邻居中未被供给过的阵地中,选取距离阵地i运输时间最短的一个作为子个体的下一个阵地[4,7]。如果邻居中的阵地都已经被访问过,算子将按照下述伪随机比例的原则选择下一个阵地j[4,8]。

式中：S为未被供给过的阵地集合;τij(t)表示第t代个体的边(wi,wj)上的信息素值;ηij=sij/cij为从阵地i到阵地j的可见度,即车辆在2个阵地间运输时间的倒数;α是调节信息素值和可见度之间相对重要性的参数;q为随机生成的小数,q0(0≤q0≤1)为一参数;随机变量J服从下面的概率分布[4]1185

选择完阵地j后,检查该车辆为当前选择的几个阵地运输弹药是否满足车辆的载容量约束条件,若满足,则继续按照前述的交叉方法构造子个体;若不满足,则将子个体染色体中阵地j的位置放入“0”,并在“0”的后面从未被补给过弹药的阵地中随机选择1个作为子个体中的下一个阵地,然后继续按照前述的交叉方法构造子个体。上述过程重复进行,直至所有阵地都被供给一次,这样一个子个体构造完毕。按照上述规则,基于信息素的交叉算子将以q0的概率选择“最合适”的阵地作为子个体中的下一个阵地,而以(1-q0)的概率按照式(11)所定义的概率分布进行随机选择。

信息素按照“最大-最小蚂蚁系统”中的机制进行初始化和更新。在算法的起始阶段,各边的信息素值均被初始化为τmax,并在整个运算过程中,信息素值被限制在区间[τmin,τmax]之间。τmax和τmin定义如下[4]1185：

式中：常数ρ(0＜ρ＜1)为信息素的持久度;f(sgb)为全体父代个体中的最优路线sgb的消耗时间;n为阵地总数。

在遗传算法每代运算结束后,各边的信息素值将按式(14)进行更新：

可见,只有包含在全体父代个体中的最优路线中的边上的信息素才会得到加强。

2.5 变异算子

为提高算法的性能,用局部搜索模块代替简单的变异算子。本算法的局部搜索模块包括4种启发式搜索算法：Relocation、Exchange、2-opt*以及2-opt。Relocation操作将1个阵地从其所在的路线中删除,并将之插入另外一条路线, Exchange操作交换位于不同路线中的2个阵地, 2-opt*操作交换2条路线的后段部分,2-opt操作替换当前路线中的2条不相邻的边以找出更好的路线[9-10]。前3种方法用于路线间的操作,最后一种方法用于路线内的改进。变异算子的局部搜索模块依次执行Relocation、Exchange、2-opt*和2-opt 4种操作,尝试所有可能的交换,从而发现更好的线路。

综合以上描述,本文提出的改进遗传算法求解弹药运输车辆调度问题的流程,如图1所示。

图1 改进遗传算法的流程图

3 算例与分析

假设有一个弹药仓库部署在配置地域,负责向附近的20处阵地供应弹药,这20处阵地的编号依次为1～20,它们对弹药的需求量组成的向量为(0.8,1.2,1.5,0.9,0.7,1.05,0.7,2.1,1.7, 0.6,0.8,2.1,1.1,0.6,1.3,1.5,2.3,0.9,1.9, 1.4)(单位：t),仓库和阵地之间的距离组成的向量为(2,3,1.5,5,6,5.5,10.8,6.1,5.6,6.4,7, 2.5,5.3,7.3,6.2,1.6,7.5,8.2,5.8,7.4)(单位：km),阵地与阵地之间的距离组成的矩阵为C20×20=(cij)20×20,cij表示阵地i与阵地j之间的距离,单位为km,C20×20为对角线元素为0的对称矩阵。

仓库有5辆运输车,每辆车的载重为8 t,车辆在仓库与阵地之间平均行驶速度组成的向量为(37,44,43,35,40,38,42,38,35,40,38,42,40, 35,40,38,42,35,37,40)(单位：km/h),车辆在阵地与阵地之间的各段路径上的平均行驶速度组成的矩阵为S20×20=(sij)20×20,sij表示车辆在阵地i与阵地j之间的路径上的平均行驶速度,单位为km/h,S20×20为对角线元素为0的对称矩阵。下面给出C20×20与S20×20。

算法用matlab 7.0实现,在Intel Pentium Dual-Core E5200 2.5GHz CPU、4G内存的台式机、Windows XP SP3环境上运行。参数设置如下：种群规模Gpop_size=30;变异概率Pm=0.2;算法迭代100代终止,基于信息素的遗传交叉算子中的各参数分别设置为：q0=0.9、ρ=0.95、α=2。计算得到的最后一代的最优个体如表1所示,可知向各个阵地完成一次弹药运输的时间为19 min。

表1 计算结果

现比较相同参数设置下本文的改进遗传算法与文献[5]的遗传算法的求解效果。2种算法程序分别重复运算20次,其结果如表2所示。

表2 2种算法的20次试验对比数据

从表2可知,改进遗传算法更容易找到最优的弹药运输路线,其得到的解的波动性也较小,这说明了改进遗传算法求解弹药运输车辆调度问题的有效性。但是在算法单次运行的平均耗时上,由于改进遗传算法中变异算子采用了Relocation、Exchange、2-opt*及2-opt 4种启发式搜索算法,因此改进遗传算法要比文献[5]中的遗传算法的平均耗时多2倍以上。在实际应用中,可以根据具体需要选用其中1种算法。

4 结 论

针对弹药运输车辆调度问题,本文建立了其数学模型,并提出了1种改进的遗传算法予以求解。在遗传算法中引入了1种基于信息素的遗传交叉算子,该算子在构造子个体时可以利用以信息素形式保存的全局信息;算法中的变异算子采用了Relocation、Exchange、2-opt*及2-opt 4种启发式搜索算法,尽可能扩大搜索范围。通过一个算例的计算表明,采用本文所提出的改进遗传算法求解弹药运输车辆调度问题得到了更好的解,具有有效性和可行性。

References)

[1]谈晓勇,刘秋菊.应急配送车辆调度优化研究综述与展望[J].计算机应用研究,2012,29(9)：3212-3215,3220.

[2]ELLABIB I,CALAMAI P,BASIR O.Exchange strategiesfor multiple ant colony system[J].Information Sciences, 2007,177(5)：1248-1264.

[3]NGUYEN H D,YOSHIHARA I,YAMAMORI K.Implementation of an effective hybrid GA for large scale traveling salesman problems[J].IEEE Transactions on Systems,Man and Cybernetics,2007,37(1)：92-99.

[4]赵方庚,李苏剑,孙江生,等.求解TSP问题的一种基于信息素的遗传交叉算子[J].北京科技大学学报,2008,30(10)：1184-1187.

[5]钟石泉,王雪莲.多车场集送一体化车辆调度问题及其遗传算法研究[J].西安电子科技大学学报：社会科学版,2009,19 (1)：63-68.

[6]孙晓莹,徐红霞.基于蚁群算法的煤矿运输车辆调度应用研究[J].煤炭技术,2012,31(7)：140-142.

[7]CHEN R,GEN M.Crossover on intensive search and traveling salesman problem[J].Computer&Industrial Engineering,1994,27(1)：485-488.

[8]GAMBARDELLA L M,DORIGO M.Solving symmetric and asymmetric TSPs by ant colonies[C]//Proceedings of IEEE International Conference on Evolutionary Computation. IEEE,1996：622-627.

[9]CHIANG C W,LEE W P,HEH J S.A 2-opt based differential evolution for global optimization[J].Applied Soft Computing,2010,10(4)：1200-1207.

[10]ENGELS C,MANTHEY B.Average-case approximation ratio of the 2-opt algorithm for the TSP[J].Operations Research Letters,2009,37(2)：83-84.

(编辑：李江涛)

Study of Scheduling Problem of Ammunition Transport Vehicles Based on Improved Genetic Algorithm

CHEN Liyun1, LU Yu2, YAN Jie1, LIU Yunlong1

(1.Department of Information Engineering,Ordnance Engineering College,Shijiazhuang Hebei 050003,China; 2.Ordnance Engineering College,Shijiazhuang Hebei 050003,China)

The mathematic model is built for scheduling problem of ammunition transport vehicles,and an improved genetic algorithm is put forward to solve the problem considering the defects of the traditional genetic algorithm in solving the problem which include the slow convergent speed and easy convergence to a local minimum point.A genetic crossover operator based on pheromone is introduced in the improved algorithm,and the operator can utilize the global information saved by the form of pheromone to improve the convergence speed.The mutation operator in the algorithm adopts four heuristic search algorithms to extend the search scope as much as possible which are Relocation,Exchange,2-opt*and 2-opt.The example analysis shows that the proposed and improved genetic algorithm is effective and feasible in solving the scheduling problem of ammunition transport vehicles.

ammunition transport;vehicle scheduling;genetic algorithm;pheromone;crossover operator

E 951.3

2095-3828(2014)02-0106-06

ADOI10.3783/j.issn.2095-3828.2014.02.025

2013-09-26

陈立云(1969-),男,副教授,博士.主要研究方向：装备保障信息化.jack20030552@oec.mtn.