基于遺傳算法的飛機(jī)維修計(jì)劃編制優(yōu)化方案

董嘯虎 劉曉東 楊航

摘要

航空公司開(kāi)展飛機(jī)管理工作時(shí)，重要環(huán)節(jié)即為編制維修計(jì)劃，通過(guò)科學(xué)合理的編制，保證飛機(jī)性能正常，預(yù)防安全事故的發(fā)生。針對(duì)飛機(jī)維修計(jì)劃編制工作的重要性，本文在遺傳算法的基礎(chǔ)上提出了維修計(jì)劃編制優(yōu)化方案，結(jié)果表明，該方案的可行性比較強(qiáng)，可在各類型航空公司中應(yīng)用。

【關(guān)鍵詞】遺傳算法 飛機(jī)維修計(jì)劃 編制 優(yōu)化

從本質(zhì)上，飛機(jī)維修計(jì)劃編制優(yōu)化就是優(yōu)化成本，即在規(guī)定時(shí)間內(nèi)將飛機(jī)持續(xù)適航維修任務(wù)完成，保證飛機(jī)的安全性及可靠性，使維修成本降低。通常，維修計(jì)劃包含三種，分別為短期維修計(jì)劃、中期維修計(jì)劃、長(zhǎng)期維修計(jì)劃，計(jì)劃類型不同時(shí)，優(yōu)化目標(biāo)也存在一定的差別，因此，航空公司應(yīng)建立具備通用性的優(yōu)化模型，從而妥善的解決維修計(jì)劃編制中遇到的各種實(shí)際問(wèn)題，實(shí)現(xiàn)優(yōu)化目的。

1 遺傳算法介紹

遺傳算法是一種計(jì)算模型，其通過(guò)對(duì)自然選擇和生物進(jìn)化過(guò)程做出模擬，將最優(yōu)解搜索出來(lái)。由于仿照基因編碼的復(fù)雜性非常高，因而進(jìn)行簡(jiǎn)化處理，如二進(jìn)制編碼，產(chǎn)生初代種群后，按照優(yōu)勝劣汰、適者生存原則，逐代的演化，將越來(lái)越好的近似解產(chǎn)生，末代種群中出現(xiàn)最優(yōu)個(gè)體后，對(duì)其進(jìn)行解碼處理，最優(yōu)解搜索完成。遺傳算法的運(yùn)算過(guò)程通常包含6步：第一步為初始化，進(jìn)化代數(shù)計(jì)數(shù)器t設(shè)置為0，以T作為進(jìn)化代數(shù)最大值，M個(gè)個(gè)體隨機(jī)生成，并將其組成初始群體P（0）;第二步為個(gè)體評(píng)價(jià)，將群體P（t）中每個(gè)個(gè)體的適應(yīng)度計(jì)算出來(lái);第三步為選擇運(yùn)算，在群體內(nèi)發(fā)揮選擇算子的作用，向下一代直接遺傳優(yōu)化的個(gè)體，或向下一代遺傳配對(duì)交叉產(chǎn)生的新個(gè)體;第四步為交叉運(yùn)算，在群體內(nèi)開(kāi)展交叉運(yùn)算，交叉算子在此過(guò)程中發(fā)揮核心作用;第五步為變異運(yùn)算，在群體內(nèi)實(shí)施變異運(yùn)算，使下一代群體產(chǎn)生;第六步為判斷終止條件，如果t與T相等，則計(jì)算終止，獲得最優(yōu)解。

2 基于遺傳算法的飛機(jī)維修計(jì)劃編制優(yōu)化方案

2.1 建立飛機(jī)維修計(jì)劃模型

在飛機(jī)維修計(jì)劃編制優(yōu)化問(wèn)題中，優(yōu)化目標(biāo)、約束條件均包含多個(gè)。一般，表示飛機(jī)維修類別時(shí)，采取的方式為A檢、C檢、D檢等，目標(biāo)為各種經(jīng)濟(jì)性因素，如維修停場(chǎng)損失、維修費(fèi)用、外委維修費(fèi)用等。因此，總體上看，優(yōu)化維修計(jì)劃編制的目標(biāo)為上述三方面因素的和最小。而維修間隔、運(yùn)力需求等作為其約束條件，要將不同機(jī)型維修方案的要求滿足，還要匹配于航班計(jì)劃，并保證飛機(jī)持續(xù)適航。基于此，可定義模型目標(biāo)函數(shù)：

在公式（1）中，N、T、H所表示的含義分別為需維修飛機(jī)數(shù)量、維修計(jì)劃周期時(shí)間跨度、維修基地機(jī)庫(kù)總數(shù)量;t時(shí)間飛機(jī)i開(kāi)展維修后，單位停場(chǎng)損失為P_ij，于h機(jī)庫(kù)中實(shí)施第j次定檢維修時(shí)，M_itjh為其日平均維修費(fèi)用，O_itjh為其日平均外委維修費(fèi)用·

2.2 遺傳算法求解

首先，染色體編碼。遺傳算法表示維修計(jì)劃優(yōu)化參數(shù)時(shí)，要以編碼方式將其視為染色體或個(gè)體，由于優(yōu)化模型具有較多的變量，因而不適合采用傳統(tǒng)的二進(jìn)制編碼，為將求解效率提高，本文利用十進(jìn)制編碼開(kāi)展染色體編碼，把不可行解產(chǎn)生個(gè)數(shù)減少。定義染色體如下：

公式（2）中，染色體個(gè)數(shù)為K，飛機(jī)i第J次定檢維修從t_kr時(shí)間開(kāi)始，在h_kr機(jī)庫(kù)中進(jìn)行。根據(jù)Z_itjh、X_itjh的數(shù)值均為1，可將i、j、t、h確定，同時(shí)，t與t_kr相等，h與h_kr相等。維修計(jì)劃編制優(yōu)化具體開(kāi)展時(shí)，將相應(yīng)的數(shù)值賦予代表各參數(shù)的染色體，約束條件不滿足情況下，賦值重新進(jìn)行，直到優(yōu)化i、t、j、h獲得。

其次，適應(yīng)值調(diào)整。遺傳算法求解過(guò)程中，遵照的原則為優(yōu)勝劣汰，外部信息基本不需要提供給凈化搜索，個(gè)體優(yōu)劣表示時(shí)采用適應(yīng)度，據(jù)此進(jìn)行遺傳操作。適應(yīng)度函數(shù)具體設(shè)計(jì)時(shí)，要與求解問(wèn)題自身的約束條件相結(jié)合。群體中，區(qū)分個(gè)體時(shí)好時(shí)壞時(shí)，以適應(yīng)值調(diào)整作為度量，因而適應(yīng)值是唯一的自然選擇依據(jù)。本文進(jìn)行適應(yīng)值調(diào)整時(shí)，采取線性調(diào)整法。

最后，控制參數(shù)選擇。遺傳算法中，群體大小K、交叉概率P、最大世代數(shù)Maxgen為主要的需選擇的參數(shù)。為保證參數(shù)值選擇恰當(dāng)，大量學(xué)者開(kāi)展了相應(yīng)的研究，不過(guò)每名學(xué)者提出的建議并不相同，國(guó)外學(xué)者多建議這三個(gè)參數(shù)取值范圍為20～30、0.005～0.01、0.75～0.95，而我國(guó)多數(shù)學(xué)者建議這三個(gè)參數(shù)取值范圍為20～300、0～0.05、0.～1.0。具體選擇控制參數(shù)時(shí)，要以參數(shù)變化為依據(jù)，將平均最優(yōu)值獲得，形成擬合曲線圖，再對(duì)曲線收斂速度和穩(wěn)定性做出對(duì)比、分析，保證參數(shù)值選擇的恰當(dāng)性，防止計(jì)算錯(cuò)誤、結(jié)果不可靠現(xiàn)象的發(fā)生。

2.3 驗(yàn)證優(yōu)化方案

為對(duì)模型及算法的可行性做出驗(yàn)證，維修計(jì)劃編制對(duì)象選擇某航空公司機(jī)對(duì)內(nèi)的7架飛機(jī)，分別編號(hào)為1號(hào)至7號(hào)，1號(hào)、2號(hào)飛機(jī)均在1號(hào)主基地1號(hào)機(jī)庫(kù)中執(zhí)行維修，持續(xù)時(shí)間5d，時(shí)間窗口分[04/03，04/08]、[05/02，05/07];3號(hào)飛機(jī)在3號(hào)主基地5號(hào)機(jī)庫(kù)中維修，持續(xù)10d，時(shí)間窗口[05/18，05/28];4號(hào)飛機(jī)在1號(hào)主基地2號(hào)機(jī)庫(kù)中維修，持續(xù)18d，時(shí)間窗口[06/01，07/01];5號(hào)飛機(jī)在2號(hào)主基地3號(hào)機(jī)庫(kù)中維修，持續(xù)5d，時(shí)間窗口[06/25，07/02];6號(hào)、7號(hào)飛機(jī)均建議外委維修，持續(xù)時(shí)間均為13d，時(shí)間窗口分別為[05/29，05/13]、[06/15，07/01]。優(yōu)化7架飛機(jī)維修計(jì)劃時(shí)，目標(biāo)為飛機(jī)維修停場(chǎng)損失+維修費(fèi)用十外委費(fèi)用最小，維修計(jì)劃周期為年。驗(yàn)證結(jié)果發(fā)現(xiàn)，在旺季時(shí)，停場(chǎng)維修的飛機(jī)并未出現(xiàn)，與設(shè)定條件相符合;定檢起始時(shí)間均未超出時(shí)間窗口，與約束條件相符合。對(duì)優(yōu)化效果進(jìn)一步驗(yàn)證，三個(gè)控制參數(shù)分別設(shè)置為10、50、20，優(yōu)化后，降低目標(biāo)值到179萬(wàn)元，明顯低于未優(yōu)化前的203萬(wàn)元目標(biāo)值，實(shí)現(xiàn)降低維修成本的優(yōu)化目標(biāo)。

3 結(jié)論

本文在遺傳算法基礎(chǔ)上建立的飛機(jī)維修計(jì)劃編制優(yōu)化模型具有較強(qiáng)的可行性，可在航空公司中應(yīng)用，不過(guò)實(shí)際應(yīng)用中由于存在更多的約束條件，且不斷變化條件自身，因而還需要開(kāi)展更為深入的研究。

參考文獻(xiàn)

[1]楊少華，王瑛，劉剛.基于耦合約束的飛機(jī)維修作業(yè)調(diào)度優(yōu)化研究[J].計(jì)算機(jī)工程，2016，42（09）：297-304.

[2]栗中華，陳艷，官頌.不確定作業(yè)的飛機(jī)大修并行拆卻調(diào)度優(yōu)化研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（03）：1097-1101.

[3]王正武，陳世國(guó)，寧順杰.基于GA-RBF網(wǎng)絡(luò)的航空維修資源優(yōu)化配置[J].航空維修與工程，2013（02）：77-78.