装甲装备机动抢修路线决策方法

王少华,董原生,吕会强,刘宏祥,彭正军

(1.装甲兵学院 a装备保障与再制造系； b.科研学术处， 北京 100072；2.中国人民解放军77626部队， 拉萨 850000)

在信息化战争中，武器装备的威力和命中精度将大大提高，作为陆军主战力量，装甲装备的损伤机率将随之提高。作为部队补充和恢复战斗力的主要手段，战场抢修能否成功组织实施将极大程度地影响成败。战场抢修力量前出到阵地现场或损伤点附近的掩蔽处实施抢修，能够最大程度地缩短抢修时间、提高抢修的时效性[1]。

在快节奏的战场上，允许战场抢修的时间是有限的，有限的战场抢修力量常常需要在短时间内前出抢修多台损伤装备，因此承担机动抢修任务的抢修组常常需要按照一定的顺序抢修损伤装备，抢修顺序极大地影响着抢修任务完成的时效性甚至成败，必须对其进行科学决策。机动抢修顺序的决策受到决策目标、机动量和机动难度、机动安全性、抢修任务量、抢修工期等诸多因素的影响，必须采用客观决策方法决策，尽量降低主观决策容易带来的潜在风险[2-5]。

目前，研究者已经针对不同类型装备提出了不少相关的战场抢修决策优化方法。田冕[2]采用层次分析法、刘利[3]采用贝叶斯网络理论、何晓晖[4]采用模糊理论提出了相应的多装备抢修顺序决策方法。王雷在考虑抢修时限的条件下提出了抢修顺序决策方法，但该模型未从指挥角度区分装备抢修时限的个体差异性，影响了决策的合理性。针对这一不足，本研究考虑单装抢修时限因素，对抢修顺序决策优化模型进行研究。

1 战场机动抢修决策问题分析

1.1 问题描述

假设机动抢修组预先编成并作为一个整体序贯地抢修损伤装备。因此从理论上可以将机动抢修决策问题视为路径寻优问题，典型的旅行商问题以路径最短为目标进行路径决策，而战场抢修决策影响因素不仅包括抢修组与各损伤装备以及损伤装备之间距离的影响，而且与路线受威胁程度、任务量、器材备件满足程度以及抢修时限等因素紧密相关，因此决策模型也较复杂[5]。

问题描述：假设1个抢修组由其所属位置出发，在战场进行巡回抢修，假设战场共有包含抢修组出发位置的n个抢修点，以1,2,…,n来表示，其中1为出发点，其他为抢修点。定义机动抢修顶点向量V，V=(v1,v2,…,vi,…,vn)，其中，vi为机动抢修路线上的第i个抢修点。定义机动时间矩阵Y，Y={yij|vi,vj∈V}，其中i，j分别为机动路线的起止点。定义抢修时间向量P=(p1,p2,…,pi,…,pn)，其中pn是第n个抢修点的抢修耗时，假设每个抢修点对应确定的抢修任务，每个抢修点所需的抢修资源以及抢修时间是确定的，即P为常值向量。定义抢修时限向量D=(d1,d2,…,di,…,dn)，其中di是第i个抢修点的抢修任务时限，即该抢修点允许的最晚修竣时间。

定义E={(vi,vj)|vi,vj∈V，i≠j}，E为连接各顶点边的集合，表示抢修点间的机动巡回路线。机动抢修的巡回路线为一条起止均为v1的闭合回路，v1为机动抢修组的出发点，抢修组在遍历抢修点之后重新返回出发点v1。

1.2 决策目标

机动抢修决策的目标主要是满足作战需求，即尽量降低对作战时间的影响，常用的目标有：抢修总耗时最短或维修点的待修延误时间最短。如果决策目标不考虑维修时限对抢修行动的影响，仅考虑抢修总耗时最短，由于各抢修点抢修耗时为确定值，所以抢修总耗时最短问题，即等价为抢修巡回路线最短问题，即在网络图G中寻找一条路径，该路径经过每个顶点且只经过一次，目标是使该路径上的机动时间之和最小。这是一个典型的旅行商问题(Traveling salesman problem，TSP)，在图论中属于Hamilton圈问题，是一种NP完全的组合优化问题，可用分枝定界、0-1规划、蚁群算法或遗传算法等解析或智能算法进行求解。但是由于需要考虑抢修时限的影响，即单纯以抢修总耗时最小并非决策者的唯一关注点，以恢复战斗力为目标的战场抢修，必须在战术允许的时间内修竣损伤装备，即抢修时限是不可忽视的决策影响因素。为此在决策目标中引入抢修时限因素[6]。

抢修时限因素可以为硬约束或软约束，硬约束即表示不接受抢修完成时间超出抢修时限的事件发生，而软约束则以抢修完成时间超出抢修时限的总延误时间最短，则硬约束可视为软约束的一种特殊情况，若软约束条件下最优决策方案能够满足硬约束，表示硬约束条件下该问题可解，否则表示该问题无解。

定义步时间矩阵S={sij}，其中i，j=1，2，…，n；i≠j；sij=yij+pj，sij表示抢修组从vi出发直接到达vj并完成在vj的抢修任务的“一步”所需要的时间。

对于软约束来说，决策目标是使抢修总耗时和抢修延迟时间都最短，这两个目标值常常无法同时达到最优。为此在目标函数中引入系数，将两个目标值进行线性融合。对于V的一个巡回次序C={c1，c2，…，ci，…，cn}，其中ci∈V(i=1，2，…，n)，则有模型：

(1)

λ1+λ2=1

(2)

式中，λ1和λ2分别表示巡回路线最短和延迟时间最短这两个目标的相对权重，通常由决策者预先给定。

2 决策求解算法

由第1节可知，机动抢修顺序决策问题实际上属于有约束的TSP问题，目标函数不仅考虑步序的问题，而且考虑到了延迟时间最短这一目标，用于解决典型TSP问题的许多模型和方法都不再适用，为此采用智能寻优算法进行路径寻优，本文采用遗传算法求解上述模型[7-8]。

遗传算法(Genetic Algorithm，GA)是模拟生物遗传学中自然选择和迭代进化过程的智能寻优算法，它具有广泛的适应性，对于求解复杂TSP问题有着显著的效果。

1) 编码方案

按巡修路线上的维修点顺序进行编码，即染色体中的每个基因代表一个维修点的编号。由于抢修出发点已经确定，即染色体首位皆为1，因此以实际抢修点编码序列构造染色体，染色体长度为n-1，采用随机排序数列生成函数构造染色体，采用实值编码。

2) 适应度函数

初始种群根据编码规则随机产生一代个体，根据每个染色体的表现计算出目标函数值，将第j个染色体对应目标函数值记为Tj，将个体j的适应度定义为：

(3)

其中，N为遗传种群的规模，即一代染色体的数量。

为了有效地控制求解过程的效率，对染色体适应度值进行过程修正，修正后的适应度表示为f′(j)，则有：

(4)

式中： max(Tj)为本代个体的最大目标函数值；η为适应度系数，η取值越小，淘汰率越高，收敛速度越快，这里采用变适应度系数的策略，从0.95到0.15递减取值，以防止过早收敛，无法求得全局最优解。

3) 选择算子

为确保种群进行全局寻优，采用轮盘赌的方法产生新一代种群，然后进行交叉和变异操作。

4) 杂交算子

杂交算子采用顺序交叉的方法，即随机确定交叉段的起止点位置，对中间段的基因进行交叉操作。为了确保交叉之后的染色体仍然对应可行解，在被交叉的两个染色体中随机选中一段长度随机的基因串，进行交叉操作，对基因串进行检验和调换，交叉操作方法示意图如图1所示。

如图1所示，在染色体b中找到将染色体a中被选中的基因段{6，4，5}的位置，按照{6，4，5}的顺序进行重新排序并插回原染色体，同样，在染色体a中找到染色体b中被选中的基因段，做相同操作，交叉前后的基因段则都能够对应决策可行解。

5) 变异算子

变异算子采用双位变异操作模式，在个体染色体中随机抽取2个基因位进行交换而产生新的个体。

6) 进化策略

考虑到选择算子和交叉算子的迭代择优效率不高，为了保存进化成果，每一代经过选择、交叉和变异操作后都保留当代最优个体，剔除最差个体，以保证算法具有全局收敛性。

3 应用实例

假设在某次联合进攻战役过程中，我数字化合成部队与当面之敌展开攻防作战，在正面作战方向上，数字化合成部队所属两个合成作战营作为第一梯队在炮兵防空兵掩护下，突破敌永久防御攻势向纵深发展，由于受敌地雷和反坦克武器的攻击，第一梯队报告坦克和步兵战车共战损15台，受前方指挥所指示，后方指挥所决定派出一支抢救抢修队立即前出进行战场抢修。

已知各战损装备的待修位置，前方抢修力量已经完成损伤的初步评估，预测得出各单装的现地抢修工时，如表1所示，各抢修点之间的距离换算为时间，如表2所示，为了保证进攻的持续性，前方指挥所对各台装备的修竣时限提出了要求，如表3所示。后方指挥所要为抢救抢修队规划抢修路线，目标是使得战损装备总延误时间最小。

表1 损伤装备现地抢修工时 min

表2 损伤装备之间的距离 min

续表(表2)

表3 损伤装备修竣时限 min

应用Matlab编写遗传算法求解程序，进行决策优化求解，主要计算过程如下：

1) 利用表1～3中的数据得到步时间矩阵和修竣时间矩阵，给定λ1和λ2的值，设定遗传算法参数，随机生成初始种群。

2) 根据式(4)计算初始种群中各个个体的适应度值。

3) 根据设定的种群保留概率随机生成相应数量的子代个体，根据轮盘赌的策略选择父代个体组成新种群。

4) 根据杂交概率进行交叉操作。

5) 根据变异概率进行变异操作。

6) 根据当次种群保留概率用当代最优个体替换最差个体。

7) 更新群体，用新种群替代父代种群，更新种群保留概率。

8) 判断是否达到最大遗传代数或代际适应度最优值变化值低于阈值，则算法终止并输出最优结果；否则转第2)步。

根据案例中决策问题的特点，设定λ1=0.3，λ2=0.7，设定遗传算法参数为：群体规模为50，最大迭代次数为 2 000，适应度系数为0.95，种群初始保留概率为0.95，杂交概率为0.7，变异概率为0.25。

按照上述参数进行决策求解，求解过程如图2所示，由图2可知，在约300次迭代后，最优解即收敛到最优值。

得到最佳的巡修路线为：

{1→9→6→2→3→4→8→12→16→15→11→7→5→10→14→13}

按照该巡修路线实施抢修，本次任务预计耗时 1 184min。但由于作战需求，无法在给定抢修时限内完成全部抢修任务，各抢修任务的修竣时间与修竣时限的对比图如图3所示。

如图3所示，对于个抢修点来说，若修竣时间低于修竣时限，表示及时完成了该任务，此类事件越多，越符合决策者的需求。由图中可知共有5个抢修任务及时完成，分别为任务9、6、2、3、4。由于采用式(1)中的决策目标函数，综合了抢修总时间和抢修延迟时间最短这两类目标，因此该决策解是权衡这两类目标的最优解，与λ1和λ2的取值有关。

当λ1=1，λ2=0时，则决策目标为抢修总时间最短，当λ1=0，λ2=1时，则决策目标为抢修总延误时间最短。

按照上述参数进行求解，可分别得到两种情况下的最优决策解，将图2所示方案标识为方案1，结果如表4所示。

表4 不同条件下巡修路线决策最优解 min

由表4所示数据可知，若仅以抢修总时间最短为目标，则抢修总时间最小可达到1 173 min，若仅以总延误时间最短，该值最小可达到3 576 min，若λ1和λ2取0～1之间数值的话，则这两类指标将得到权衡。

4 结论

在信息化战争条件下，对于有限的战场抢修力量来说，战场机动抢修顺序决策直接关系着抢修人员的安全性和抢修效益。在战术允许的时间内完成抢修，是作战指挥员关注的重点，必须综合考虑总抢修时间与抢修延迟时间，使战场抢修效益最大化。由于抢修行动本身在资源消耗、时间消耗上存在较大的不确定性，本文对其进行了简化处理，在下一步的研究中，有必要针对单装抢修时间与资源的随机特性确定最优的抢修顺序。