基于交叉粒子群算法的飛機(jī)指派問(wèn)題研究

賈寶惠，逯艷華，李耀華

（中國(guó)民航大學(xué)航空工程學(xué)院，天津 300300）

基于交叉粒子群算法的飛機(jī)指派問(wèn)題研究

賈寶惠，逯艷華，李耀華

（中國(guó)民航大學(xué)航空工程學(xué)院，天津 300300）

針對(duì)飛機(jī)指派優(yōu)化問(wèn)題進(jìn)行研究，建立了以成本最小化為目標(biāo)函數(shù)的飛機(jī)指派模型，模型以成本作為主要優(yōu)化目標(biāo)，綜合考慮了指派問(wèn)題中的約束條件。引入交叉粒子群算法對(duì)模型進(jìn)行求解，在迭代的過(guò)程中，粒子通過(guò)交叉得到新粒子；為避免粒子陷入局部最優(yōu)，引入了粒子位置變異機(jī)制。在用Delphi7.0編程實(shí)現(xiàn)算法時(shí)，根據(jù)交叉粒子群算法的特點(diǎn)，首先編譯了交叉、位置變異等函數(shù)，增加了程序的可讀性。然后采用航空公司的實(shí)際數(shù)據(jù)進(jìn)行仿真，仿真結(jié)果表明與傳統(tǒng)的以人工決策為主的排班方式相比，本研究提出的模型和算法縮短了工作時(shí)間，降低了指派成本。

飛機(jī)指派；優(yōu)化算法；交叉粒子群

飛機(jī)排班問(wèn)題的研究是航空公司在生產(chǎn)計(jì)劃方面的重要課題，也是航空公司運(yùn)行控制工作的主要內(nèi)容之一。國(guó)內(nèi)民航業(yè)的快速發(fā)展使得航空公司規(guī)?？焖贁U(kuò)大，航班數(shù)量和機(jī)隊(duì)規(guī)模都在成倍增長(zhǎng)。目前以人工決策為主的排班方式存在工作量大、合理性低、靈活性差等缺點(diǎn)，已無(wú)法滿(mǎn)足航空公司的排班需求。

飛機(jī)指派問(wèn)題作為飛機(jī)排班中的一個(gè)主要問(wèn)題，一直是一個(gè)研究熱點(diǎn)，國(guó)外在這方面的研究起步較早，Hanif[1]提出了綜合排班模型和動(dòng)態(tài)排班機(jī)制。Nikolaos[2]建立了航班計(jì)劃的多個(gè)綜合優(yōu)化模型，并將改進(jìn)的Benders分解算法與加速列生成算法相結(jié)合應(yīng)用于模型的求解。Sami[3]等人采用混合列生成和限制規(guī)劃算法對(duì)飛機(jī)指派模型進(jìn)行求解。國(guó)外在這方面的研究比較成熟，但國(guó)外的研究不能貼合國(guó)內(nèi)航空公司的運(yùn)營(yíng)模式。國(guó)內(nèi)在這方面的研究工作起步較晚，目前已有的成熟研究成果很少。高強(qiáng)、朱星輝等[4]將機(jī)型指派、路線(xiàn)問(wèn)題和飛機(jī)指派綜合成一個(gè)問(wèn)題進(jìn)行研究，研究雖然涉及飛機(jī)指派，但并沒(méi)有就指派問(wèn)題的特點(diǎn)進(jìn)行深入研究，也沒(méi)有提出適合指派問(wèn)題的算法。鄭蕓等[5]將螞蟻算法用于飛機(jī)排班問(wèn)題的求解，飛機(jī)排班問(wèn)題是路線(xiàn)問(wèn)題和飛機(jī)指派問(wèn)題的綜合，螞蟻算法是求解TSP問(wèn)題的經(jīng)典算法，其更適用于求解路線(xiàn)問(wèn)題而非指派問(wèn)題。于海波等[6]將離散型粒子群算法用于飛機(jī)排班問(wèn)題的求解，但基本離散型粒子群算法存在著速度難以表達(dá)和容易陷入局部最優(yōu)的缺點(diǎn)。文獻(xiàn)[7]提出的交叉粒子群算法，粒子通過(guò)交叉得到新粒子，克服了難以表達(dá)速度的缺點(diǎn)；引入粒子位置變異機(jī)制，避免粒子陷入局部最優(yōu)。

本文以當(dāng)前國(guó)內(nèi)航空公司的排班工作為背景，借鑒已有的研究成果，針對(duì)飛機(jī)指派優(yōu)化問(wèn)題進(jìn)行分析和研究，建立了飛機(jī)指派優(yōu)化模型，并將交叉粒子群算法應(yīng)用于飛機(jī)指派問(wèn)題的求解，為飛機(jī)排班問(wèn)題奠定了基礎(chǔ)。

1 飛機(jī)指派模型的建立

1.1 飛機(jī)指派問(wèn)題概述

飛機(jī)排班是依據(jù)航空公司的航班計(jì)劃和飛機(jī)維護(hù)工作安排為每一個(gè)航班指定一架具體執(zhí)行的飛機(jī)，也即給每一個(gè)航班號(hào)分配一個(gè)相應(yīng)的機(jī)尾號(hào)。目前，國(guó)內(nèi)航空公司的飛機(jī)排班流程大致如下：

1）根據(jù)航空公司的航班時(shí)刻表，將航空公司一個(gè)周期內(nèi)所有航班連接成時(shí)間地點(diǎn)前后銜接的航班串。

2）將生成的航班串進(jìn)行篩選，得到覆蓋所有航班而且滿(mǎn)足一定目標(biāo)的部分航班串。這里的“一定目標(biāo)”一般是指航班串?dāng)?shù)最少。航班串?dāng)?shù)越少在隨后的指派過(guò)程中用到的飛機(jī)就越少。

3）為篩選得到的每一個(gè)航班串指派一架具體執(zhí)飛的飛機(jī)。

飛機(jī)排班的過(guò)程中要受到航班飛行區(qū)域、飛機(jī)維修計(jì)劃等諸多因素的制約，本文針對(duì)上述飛機(jī)排班問(wèn)題中的第3個(gè)子問(wèn)題進(jìn)行研究，主要考慮的約束如下：

1）唯一性約束 在同一時(shí)間每架飛機(jī)最多只能執(zhí)行一個(gè)航班，每個(gè)航班只能由一架飛機(jī)執(zhí)行。

2）飛機(jī)總數(shù)約束 任何時(shí)刻在地面機(jī)場(chǎng)的飛機(jī)數(shù)和在空中執(zhí)行航班的飛機(jī)數(shù)之和保持不變。

3）飛機(jī)與航班的匹配性約束 飛機(jī)的大小、可飛行區(qū)域等要與航班要求相一致。

1.2 飛機(jī)指派問(wèn)題優(yōu)化模型

飛機(jī)指派優(yōu)化問(wèn)題涉及問(wèn)題規(guī)模較大，變量眾多，本文基于以上約束，建立了以成本最小化為目標(biāo)函數(shù)的飛機(jī)指派模型。模型符號(hào)和參數(shù)的具體說(shuō)明如下：

式（1）是成本最小化的目標(biāo)函數(shù)；式（2）和式（3）是唯一性約束，式（2）表示排班結(jié)果應(yīng)保證每一個(gè)航班有且只有一架飛機(jī)執(zhí)行，式（3）表示同一時(shí)間每架飛機(jī)最多只能執(zhí)行一個(gè)航班；式（4）和式（5）為飛機(jī)數(shù)量守恒約束，式（4）表示在任意時(shí)刻t，在空中執(zhí)行航班的飛機(jī)數(shù)量與在地面機(jī)場(chǎng)的飛機(jī)數(shù)量之和等于在排班方案中用到的飛機(jī)總數(shù)，式（5）表示機(jī)場(chǎng)飛機(jī)數(shù)量守恒，即對(duì)任一機(jī)場(chǎng)o（o∈S），在任意時(shí)刻t從其他機(jī)場(chǎng)飛抵機(jī)場(chǎng)o的飛機(jī)數(shù)量與從t-到t時(shí)刻一直在機(jī)場(chǎng)o的飛機(jī)數(shù)量之和，等于t時(shí)刻從o機(jī)場(chǎng)飛往其他機(jī)場(chǎng)的飛機(jī)數(shù)量與t到t+留在o機(jī)場(chǎng)的飛機(jī)數(shù)量之和；式（6）為飛機(jī)總數(shù)約束，在排班方案中用到的飛機(jī)總數(shù)不能大于航空公司的可用飛機(jī)總數(shù)；式（7）表示對(duì)于任意時(shí)刻t，機(jī)場(chǎng)o（o∈S）的飛機(jī)數(shù)量不能為負(fù)。

2 交叉粒子群算法求解飛機(jī)指派模型

飛機(jī)指派模型的求解屬于NP-hard問(wèn)題，很難采用精確求解方法進(jìn)行求解。近年來(lái)啟發(fā)式算法被廣泛應(yīng)用于優(yōu)化方面的NP-hard問(wèn)題的求解。粒子群算法由于求解簡(jiǎn)單、參數(shù)調(diào)整少等優(yōu)點(diǎn)，成為求解優(yōu)化問(wèn)題的有效算法。

本文采用交叉粒子群算法求解飛機(jī)指派的數(shù)學(xué)模型。交叉粒子群算法是一種改進(jìn)的離散型粒子群算法。對(duì)于指派問(wèn)題，若按基本粒子群算法其速度難以表達(dá)，交叉粒子群算法采用了遺傳算法交叉操作的思想。本文應(yīng)用的交叉粒子群算法的主要改進(jìn)部分和求解流程如下：

1）交叉過(guò)程

交叉粒子群算法通過(guò)離子與個(gè)體極值和全局極值的交叉得到新粒子。以粒子與個(gè)體極值的交叉為例來(lái)說(shuō)明交叉過(guò)程。設(shè)Xi={xi1，xi2，…，xin}是優(yōu)化問(wèn)題的一個(gè)可行解，Pbesti={Pbesti1，Pbesti2，…，Pbestin}是粒子X(jué)i的個(gè)體極值。交叉步驟如下：①隨機(jī)選擇位置點(diǎn)position1，將Xi中的前position1個(gè)元素保留不變記為S1。然后把Pbesti中與S1相同的元素刪除，余下的元素記為S2，S1和S2合在一起構(gòu)成新粒子y1。②將Pbesti中的前position1個(gè)元素保留不變，記為S1。然后把Xi中與S1相同的元素刪除，余下的元素記為S2，S1和S2合在一起構(gòu)成新粒子y2。③計(jì)算y1和y2的適應(yīng)度函數(shù)值，以適應(yīng)度函數(shù)值優(yōu)者作為交叉得到的新粒子。粒子與全局極值的交叉與此類(lèi)似。

2）位置變異

位置變異是粒子自身元素位置的交換。以Xi= {xi1，xi2，…，xin}的一對(duì)位置變異為例來(lái)說(shuō)明位置變異的具體過(guò)程，隨機(jī)選擇兩個(gè)位置點(diǎn)，如2和n，變異之后的粒子為Xi={xi1，xin，…，xi2}。位置變異增加了粒子的多樣性，避免尋優(yōu)時(shí)粒子群陷入局部極值中。圖1為交叉粒子群算法的流程圖。

圖1 交叉粒子群算法流程圖Fig.1 Flow chart of cross particle swarm algorithm

3 仿真試驗(yàn)與效果分析

為了驗(yàn)證飛機(jī)指派模型及交叉粒子群算法，選取某航空公司1天的11個(gè)航班串，合理安排11架飛機(jī)來(lái)執(zhí)行這些航班串，原始數(shù)據(jù)如表1所示。

表1 航班時(shí)刻表Tab.1 Flight schedule

參數(shù)的選擇如下：位置變異對(duì)數(shù)為2對(duì)，設(shè)定粒子種群數(shù)為20，迭代次數(shù)為1 500次。本文根據(jù)交叉粒子群算法的特點(diǎn)，采用Delphi7.0軟件編程實(shí)現(xiàn)算法對(duì)模型的求解。交叉粒子群算法的核心是交叉和位置變異，進(jìn)行交叉和位置變異操作之前要選擇交叉和變異的位置，交叉和位置變異之后要比較得到的新粒子與個(gè)體極值的適應(yīng)度值。在每次迭代過(guò)程中，每個(gè)粒子都要經(jīng)歷2次交叉、1次位置變異、3次隨機(jī)位置選擇和3次適應(yīng)度值比較。為了增加程序的可讀性，也為了減少編程的工作量，在用Delphi7.0軟件編程實(shí)現(xiàn)算法的過(guò)程中，在主程序之前編制了隨機(jī)選擇位置函數(shù)、交叉函數(shù)、位置變異函數(shù)和適應(yīng)度值比較函數(shù)。主程序包含兩層嵌套循環(huán)，外層循環(huán)控制迭代次數(shù)，內(nèi)層循環(huán)通過(guò)調(diào)用以上函數(shù)實(shí)現(xiàn)交叉和位置變異等操作。

表1和表2分別為仿真的航班信息和飛機(jī)信息，根據(jù)表1的航班信息生成了11個(gè)航班串，如表3所示。表3第1列是航班串的序號(hào)，第2列是由表1中的航班序號(hào)組成的航班串，第3列是航空公司原本的指派結(jié)果，即航空公司有經(jīng)驗(yàn)的工作人員為每個(gè)航班串選定的飛機(jī)編號(hào)，第4列是模型和算法為航班串選定的執(zhí)行飛機(jī)的編號(hào)。

表2 飛機(jī)信息表Tab.2 Aircraft information

表3 排班結(jié)果Tab.3 Assignment result

圖2為用交叉粒子群算法求解模型的適應(yīng)度值跟蹤圖。算法在800次左右開(kāi)始進(jìn)入收斂。整個(gè)計(jì)算過(guò)程不到15 s，而依靠工作人員手工完成這項(xiàng)工作至少需要2天的時(shí)間。在不考慮人工成本的條件下，模型和算法求得的指派結(jié)果與人工指派結(jié)果相比，成本降低了1.15%，如果考慮人工成本，總成本降低的比例會(huì)更大。

圖2 交叉粒子群算法求解模型的適應(yīng)度值跟蹤圖Fig.2 Adaptive value trace of cross particle swarm algorithm

4 結(jié)語(yǔ)

飛機(jī)指派問(wèn)題是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題，本文建立了以成本最小化為目標(biāo)函數(shù)的飛機(jī)指派模型。首次將交叉粒子群算法引入指派模型的求解。結(jié)合交叉粒子群算法的特點(diǎn)，采用Delphi7.0軟件編程實(shí)現(xiàn)算法對(duì)模型的求解。最后，采用航空公司的實(shí)際數(shù)據(jù)進(jìn)行仿真，結(jié)果表明本文針對(duì)指派問(wèn)題提出的模型和算法既能節(jié)約成本又能提高工作效率。

[1]HANIF D SHERALI，EBRU K BISH，ZHU XIAOMEI.Airline fleet assignment concepts，models，and algorithms[J].Science Direct，2006（172）：1-30.

[2]NIKOLAOS PAPADAKOS.Integrated airline scheduling[J].Computers &Operations Research，2009，36（1）：176-195.

[3]SAMI GABTENI，MATTIAS GRONKVIST.Combining column generation and constraint programming to solve the tail assignment problem[J]. Annals of Operations Research，2009，171（1）：61-76.

[4]高 強(qiáng)，朱星輝，李 云，等.飛機(jī)排班一體化模型與算法研究[J].武漢理工大學(xué)學(xué)報(bào)，2012，36（2）：153-157.

[5]鄭 蕓，王錦彪，王元崑.螞蟻算法在民航飛機(jī)排班問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程，2005，31（S）：7-9.

[6]于海波，夏洪山，朱 鋒.離散型粒子群算法求解民航飛機(jī)排班問(wèn)題[J].江蘇航空，2006（4）：18-19.

[7]孫曉雅，林 焰.一種新的離散粒子群算法在指派問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2009，26（11）：4091-4097.

（責(zé)任編輯：楊媛媛）

Research on aircraft assignment based on cross particle swarm algorithm

JIA Bao-hui，LU Yan-hua，LI Yao-hua
（College of Aeronautical Engineering，CAUC，Tianjin 300300，China）

Aircraft assignment is studied and a mathematical model of aircraft assignment is established，whose objective function is cost-minimization.Cost is the main optimization objective of the model and assignment constraints are considered.Cross particle swarm algorithm is proposed to solve the mathematical model of aircraft assignment. During the process of iteration，new particles are obtained by crossing.In order to avoid local optimum，an updating scheme of particle position is introduced.The Delphi 7.0 is used to implement cross particle swarm algorithm，helping to solve the assignment model.Based on the characteristics of cross particle swarm algorithm，the cross function and position updating function are compiled firstly to increase the readability of the program. The actual data of the airline is used to simulate.Simulation result shows that the proposed model and algorithm shorten the working time and reduce the cost of assignment compared with traditional manual decision-based scheduling methods.

aircraft assignment；optimization algorithm；cross particle swarm

F560

：A

：1674-5590（2015）04-0006-04

2014-09-12；

：2014-11-10

國(guó)家自然科學(xué)基金項(xiàng)目（U1233107）；中原高校基金預(yù)研重大維修工程分析關(guān)鍵技術(shù)研究（3122014P002）

賈寶惠（1971—），女，山西運(yùn)城人，教授，碩士，研究方向?yàn)轱w機(jī)維修工程、適航管理、飛機(jī)機(jī)電系統(tǒng)等.