基于蚁群算法的舰载直升机维修资源优化调度研究*

李军亮 滕克难 衣冠琛 刘国桓

(1.海军航空工程学院 烟台 264001)(2.92514部队 烟台 264007)

基于蚁群算法的舰载直升机维修资源优化调度研究*

李军亮1滕克难1衣冠琛1刘国桓2

(1.海军航空工程学院 烟台 264001)(2.92514部队 烟台 264007)

针对舰载直升机远航时驻舰周期长、维修任务时间紧、资源有限的特殊性，合理构建舰载直升机驻舰维修模型，建立舰载直升机驻舰维修资源优化调度模型，采用改进蚁群算法进行仿真计算，通过计算验证表明：该算法较好的解决维修过程中出现的资源冲突问题，缩短舰载直升机维修工期。

舰载直升机; 维修保障; 资源调度; 蚁群算法

Class Number V241

1 引言

随着蓝色海军战略转型的不断深入，海军执行远洋任务日益频繁，舰载直升机能够担负侦察、搜救、运输、反潜等多种使命，其作用更加突出。但舰载直升机的使用仍受到多方面因素制约，一方面由于目前舰载直升机驻舰保障仍然沿用岸基“基层级”、“中继级”和“基地级”的三级保障体制，舰船空间有限不能携带较多的航材备件，维修资源相对受限；另外远航时舰载直升机驻舰周期长、气候环境恶劣，执行任务具有突发性和应急性，装备故障率高且故障出现时间具有不确定性[1]。那么如何通过对维修资的源优化调度来解决维修保障过程中出现的维修保障资源分配不均、计划不周、预测不准等问题，充分利用现有维修资源，缩短待修直升机维修周期，提高维修资源利用率，在短时间内恢复战斗力，最大限度地保证直升机完好率，顺利执行各项任务已经成为机务维修人员亟待解决的重大课题。

资源受限项目调度问题(resource-constrained project scheduling problem,RCPSP)，要求在满足项目任务的紧前关系和资源约束的条件下，优化项目的进度安排，从而优化最小项目目标函数。RCPSP算法主要分两种：精确算法和启发式算法。精确算法包括整数规划、分支界定法、动态规划法等。由于RCPSP是NP-hard问题，对于较复杂的项目，在可以接受的时间范围内，精确算法难以得到最优解。相对而言启发式算法不能保证得到最优解，但能够较快地找到较好解。各类启发式算法是近年来的研究热点，目前的研究主要集中于遗传算法、模拟退火、禁忌搜索以及蚁群算法[2～3]。笔者根据舰载直升机有限资源维修问题的特殊性，采取蚁群算法进行优化实现，基于复杂的参数设置，得到较好的结果。

2 舰载直升机驻舰保障维修资源分析

舰载直升机维修资源是指与舰载直升机维修直接关联的维修经费、维修物资器材、维修设施设备、维修人才、维修信息以及维修管理等有形和无形的资源[4]。而在实际工作中只考虑以实物形式存在的舰载直升机维修资源，即维修物资器材、维修设施设备和维修人才。

根据实际工作情况，舰载直升机的驻舰维修是由随舰保障的地勤人员来完成，维修工作按照机械、特设、电子、军械和声纳五个专业进行划分，如果多专业同时进行项目维修，就可能会产生资源冲突，每个维修项目的工作进度都会受到影响，就容易造成整体维修工期拖后的现象，要合理解决资源冲突，有效利用关键资源，有序分散的并行进行维修项目，保证多项目、多工序交叉进行和推进，就势必要对维修资源进行优化调度。

多专业多项目维修工作并行开展时要考虑维修任务中维修项目所需的资源配置，再根据各个专业的分工职能，对所属专业项目的维修资源进行调配。直升机维修工作是一个复杂的系统工程，各专业并行作业时存在制约和关联，各专业内部工序可在满足紧前约束的前提下串联进行。文献[5]在资源受限模型建模时引进维修单元重要度的概念来确定工序前后顺序的优先策略。具体表现为实际维修工作中维修项目的重要性和蚁群算法中信息素的挥发系数联系起来，即维修项目重要度和信息素挥发系数成反比关系，这样的计算结果更贴近实际维修工作。

笔者结合目前舰载直升机驻舰保障的实际情况，对在舰面可完成的实际维修项目进行编码，规则如下：

按照目前的维修方式将直升机维修工作划分为机械专业M1，特设专业M2，军械专业M3，电子专业M4，声纳专业M5，各专业维修项目按照工作顺序编码，各维修项目完成需要的时间用矩阵D表示。

(1)

其中，矩阵中的列分别表示专业，矩阵中的行表示专业的维修项目。dij表示第i个专业的第j个维修项目的工作时间。确定每个项目dij的优先策略时，首先要满足紧前约束，其次参考重要度函数θj，θj如式(2)所示：

(2)

3 舰载直升机维修优化调度模型的建立

由于舰载直升机维修任务比较特殊，不仅具有较高的并发性，还有关键资源的制约。那么一个维修项目可以表示为一个节点式(activity-on-node,AON)有向网络[6]，并存在两类约束：一类是任务之间存在的逻辑约束，用AON网络中的箭头表示；另一类是有限资源造成的资源约束，限定同一时刻各任务对资源的需求不能超过资源的供给。假设项目包含j个任务，需要k种可更新资源,其中第k种资源的供给量为Rk。项目的第j个任务，其工期为Pj，截止日期为dj对第k种资源的需求量为rjk，其所有紧前任务的集合记为Pj，任务的开始时间标记为Sj，结束时间标记为Cj，项目从t=0时刻开始执行,设定最晚完工时间为T=∑Pj；在时间t所有进行中任务的集合标记为It，可以用任务结束时间向量表示一个项目进度计划S=(C1,C2,…,Cj)。因此，RCPSP可以描述为

minf(s)

(3)

s.t

Sj≥Ch,∀j,h∈Pj

(4)

∑j∈Itrk≤Rk,∀k,t

(5)

式(3)表示项目的目标函数，式(4)表示任务之间的紧前关系，式(5)表示资源约束。对于经典RCPSP问题，目标是最小化项目总工期。

4 蚁群算法设计

蚁群算法是对蚂蚁群体利用信息素进行觅食行为的仿生，已经被广泛应用于各种组合优化问题，以及应用于求解RCPSP[7～8]。一般而言，蚁群算法采用进度生成机制，通过逐步扩展局部进度计划来生成一个完整可行的项目进度计划，并通过反复搜索获得最优解。

(6)

式中：τij为信息素信息，ηij为启发式信息,α和β为控制两类信息权重的参数。启发式信息一般表示蚂蚁在搜索决策中可以利用的直观信息。在RCPSP中，一般用优先规则来构造启发式信息，最常见的是最迟完工(late finish，LF)时间，记任务j的最迟完工时间为Lj，则启发式信息可以表示为

(7)

信息素的更新是蚁群算法的重点，包括信息素的挥发和累积。鉴于舰载直升机维修工作的特殊性，本文将ρ的变化为与重要度函数θj成反比的函数，各条路径信息素更新如式(8)所示：

(8)

Δτij(g)=ρ/f

(9)

式中：ρ为信息素的挥发率，f为蚂蚁在完成一次完整的搜索后得到的目标函数值。当蚂蚁k从第1个任务逐步搜索到第j个任务时，就构成一个完整的任务列。以该任务列的顺序，在满足资源约束的前提下，按照尽早原则逐个安排所有任务的开始时间，就得到一个可行的项目进度计划。

5 算例分析

蚁群算法是一种自适应、正反馈、分布式的模拟优化计算法，它在求解各复杂的组合优化问题上表现出一定优势，较好的α，β有较好的解质量以及好的稳定性，但如果对蚁群参数选择不当，蚁群算法较快收敛到局部最优或较慢的收敛，对算法有极大地影响。文献[9～10]利用大量数据分析了α，β参数不同组合得到的算法性能。在0.1≤α≤0.3，3≤β≤6的些范围内，算法总体上有较好的性能，到达的最优解与全局最优接近，同时，所需的迭代次数也较少，不易陷入局部最优，导致算法停滞。本文算法中控制参数取值如表1所示。

表1 计算参数的选择

假设舰载直升机在执行某次任务后，部分装备受到损伤，再次出动需要对5个专业9个项目维修，如表2所示。

表2 维修项目、时间及保障重要度

根据以上假设和优化目标，采用蚁群算法用Matlab编程计算结果如图1所示。

图1 最佳路径和最短工时

假设条件数据不变，应用其它算法求解本例，得到计算结果如表3所示，可以发现本文所述算法求解结果基本优于其他算法，其求解时间对比显示：本文求解时间小于其它算法，基本适用于应急保障资源调度对决策时间的快速要求。

表3 计算结果的比较

6 结语

该模型可以计算出舰载直升机在有限资源情况下保障维修的最短工时和最优工序，能够提高维修效率，从而提高舰载直升机的完好率。本文在计算维修任务的重要度时只考虑了三个影响因素，为了更切近实际保障工作，可以全面研究各种影响因素，确定更为合理的维修工序。

[1] 张鑫,金超.基于蚁群算法的舰船维修资源优化调度[J].兵工自动化,2011,30(11):1-35.

[2] 寿涌毅,傅奥.多目标资源受限项目调度的多种一群算法[J].浙江大学学报,2010,44(1):51-55.

[3] 崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2008:253-256.

[4] 李耀华,谭娜,郝贵和.飞机维修计划优化模型与算法研究[J].控制工程,2008,15(1):99-102.

[5] 孙宝琛,贾希胜.基于蚁群算法的维修资源应急调度研究[J].研究与设计,2012(6):37-41.

[6] 陈庆华.装备运筹学[M].北京:国防工业出版社,2007:85-89.

[7] Merkle D, Middendorf M, Sch Meck H. Ant colony optimization for resource constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation,2002,6(4):333-346.

[8] Mazzeo S, Loiseau I. An ant colony algorithm for the capacitated vehicle routing[J]. Electronic Notes indiscrete Mathematics,2004(8):181-186.

[9] 蒋玲艳.蚁群算法的参数分析[J].计算机工程与应用,2007(20):31-36.

[10] 黄翰,郝志峰,吴春国.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1344-1353.

Optimal Scheduling of Shipboard Helicopter Maintenance Resource Based on Ant Colony Algorithm

LI Junliang1TENG Ke’nan1YI Guanchen1LIU Guohuan2

(1. Naval Aeronautical Engineering Institute, Yantai 264001)(2. No. 92514 Troops of PLA, Yantai 264007)

According to the particularity of the maintenance of shipboard helicopter with constrained resource and time limited, the optimized scheduling model of shipboard helicopter maintenance resource is put forward. By using the ant colony algorithm, the simulating calculation proves that the method uses the pheromone update to enhance search capability of ants to the optimal path, which solves the resource shortage problem well and reduces the maintenance cycle.

shipboard helicopter maintenance, resource constraint, optimized resources, shortest time, ant-colony-algorithm

2014年5月10日,

2014年6月23日 作者简介:李军亮,男,博士研究生,研究方向:飞行器动力学和航空装备保障。滕克难,男,博士,教授,博士生导师,研究方向:武器装备发展论证。衣冠琛,男,硕士,研究方向:航空装备保障。刘国桓,男,工程师,研究方向:航空装备保障。

V241

10.3969/j.issn1672-9730.2014.11.035