帶時間窗的飛機(jī)排班問題優(yōu)化摘要：為提高飛機(jī)排班質(zhì)量，在以航空公司成本最小化為目標(biāo)的基礎(chǔ)上，兼顧顧客的滿意度(航班準(zhǔn)時性)和飛機(jī)使用數(shù)目最小化目標(biāo)，建立優(yōu)化的多目標(biāo)帶有時間窗的飛機(jī)排班問題(Aircraft-arrangementProblemwithTimeWindows,APTW)模型。引用算例，對3個目標(biāo)函數(shù)都進(jìn)行處理后，運(yùn)用離散量子粒子群算法進(jìn)行求解，最終得出模型解的運(yùn)算結(jié)果和時間都在理想范圍之內(nèi)，表明新模型是有效可行的。該模型的建立有助于有效地解決帶有時間窗的飛機(jī)排班問題，提高了排班工作效率。關(guān)鍵詞：飛機(jī)排班；離散量子粒子群算法；時間窗；多目標(biāo)模型Aircraft-arrangementProblemoptimizationwithtimewindowsAbstract:Inordertoimproveaircraft-arrangementquality,amulti-objectivemodelofAircraft-arrangementProblemwithTimeWindows(APTW)whichcoverstwotargets(thedegreeofcustoms’satisfactionandplane’sminimumnumber)arebuiltbasedonthetraditionaltargetofminimumcost.Afterdealingwiththreetargetfunctionsbyprocess,theQuantumdiscretePSOisemployedtosolvethemodelwhichcitesdatafromtheinternationallyrecognizedquestiondatabaseofaircraft-arrangementproblem.Finally,bothresultofthemodelandthetimethatsolvethemo-delbelongtotheidealrange,whichindicatesthatthenewmodelisfeasible.Thebuildingofthemodelwhichishelpfultooptimizeaircraft-arrangementproblemwithtimewindowscanimprovelogisticefficiencyeffectively.Keywords:Aircraft-arrangementProblem;QuantumdiscretePSO;Timewindows;Multi-objectivemodel近年來，隨著我國航空運(yùn)輸業(yè)快速發(fā)展，低成本航空的興起，航空運(yùn)輸業(yè)的市場化程度也越來越明顯，對飛機(jī)的調(diào)度使用安排就越來越重要。飛機(jī)排班是航空公司對飛機(jī)的調(diào)度，也就是對飛機(jī)和航班的優(yōu)化配置過程。在我國，航空公司的航班主要圍繞一個基地機(jī)場安排,飛機(jī)所在的基地機(jī)場保持不變,各類飛機(jī)遣派不僅要考慮飛機(jī)維護(hù)計劃的需要,還要滿足各類控制要求的規(guī)定。隨著航空公司機(jī)隊的不斷壯大,航班數(shù)量的不斷增多,完全依靠人工完成該項工作的難度越來越大,因此利用計算機(jī)輔助完成飛機(jī)排班工作已成為飛機(jī)遣派人員的需求。本文在系統(tǒng)分析國內(nèi)航空公司的航線結(jié)構(gòu)及運(yùn)行管理方式的基礎(chǔ)上，建立了一種兼顧顧客的滿意度和飛機(jī)使用數(shù)目最小化目標(biāo)描述飛機(jī)排班問題的APTW模型，并運(yùn)用離散量子粒子群算法對模型求解。１問題的數(shù)學(xué)模型帶有時間窗的飛機(jī)排班問題[1](Aircraft-arrangementProblemwithTimeWindows,APTW)是指假設(shè)有f個等待排航班、出發(fā)機(jī)場a和機(jī)型為K的飛機(jī)，已知每個航班和出發(fā)機(jī)場的位置坐標(biāo)、乘客數(shù)量，每架飛機(jī)的容量和允許服務(wù)的時間窗口,要求設(shè)計飛機(jī)的航行路線并滿足一系列約束條件。有效地解決帶有時間窗的飛機(jī)排班問題，使得運(yùn)輸費(fèi)用最低、需要的運(yùn)輸飛機(jī)數(shù)最少、運(yùn)輸總時間最短等。不僅可以提高運(yùn)輸工作效率，而且能有效的節(jié)約航空公司運(yùn)營成本。本文建立新的多目標(biāo)APTW模型，在基本的以飛機(jī)運(yùn)行成本最小化為目標(biāo)的模型基礎(chǔ)上，兼顧顧客的滿意度和飛機(jī)使用數(shù)最小化為目標(biāo)，要達(dá)到提高客戶滿意度即航班延誤減少，本文主要通過航班時效性標(biāo)準(zhǔn)衡量客戶滿意度。并要滿足以下約束[2]：1)同一時間內(nèi),一架飛機(jī)最多只能執(zhí)行一個航班。2)每個航班應(yīng)當(dāng)且只能由一架飛機(jī)執(zhí)行，即所有航班都有飛機(jī)執(zhí)飛。3)飛機(jī)與指派的航班任務(wù)應(yīng)相互匹配。4)最少需用飛機(jī)數(shù)要求。5)滿足最短過站時間要求（飛機(jī)有足夠的時間裝卸客貨、加油等必要的活動），一般為45min。根據(jù)以上所述，得到帶時間窗飛機(jī)排班模型[3][4][5][6]如下：首先定義K為所有待排機(jī)型集合；F為待排航班數(shù)；ckf為機(jī)型為k的飛機(jī)飛航班f的單位航程所耗運(yùn)行成本；Xkf為決策變量，Xkf＝1表示用機(jī)型k的飛機(jī)飛航班f；否則Xkf＝０；Z為機(jī)場集合；N為航線網(wǎng)絡(luò)中某個時刻的點(diǎn)集合，{k,a,t}表示；NUMk為機(jī)型為k的飛機(jī)的數(shù)量；CL(k)表示使用k機(jī)型所飛航段的集合。d(Zij)為機(jī)場i到機(jī)場j的航程，ei為到達(dá)機(jī)場i的實(shí)際時間，tif為航班f到達(dá)機(jī)場i的預(yù)定時刻。Nk,a,t為t時刻之前在機(jī)場z的機(jī)型為k的飛機(jī)數(shù)量。建立如下數(shù)學(xué)模型：QUOTEminA=i=0Fj=0Fk=1Kckfd(Aij)X(2)QUOTEminC=j=1Fk=1KX0jks.tQUOTEf∈Fxｋf(4)(5)(6)(7)上述模型中式（1）為目標(biāo)函數(shù)，即要求使用全部航班的總飛行成本最低；式（2）表示飛機(jī)延遲的時間最短，保證準(zhǔn)時到達(dá)，確保消費(fèi)者滿意；式（3）表示應(yīng)用的飛機(jī)數(shù)量最少；式（4）是滿足所有航班都被覆蓋，且只被一架飛機(jī)執(zhí)飛；式（5）保證了在同一時間內(nèi)每一個航班號最多只能由一架飛機(jī)執(zhí)行；式（6）保證了正在執(zhí)行航班的某種機(jī)型的飛機(jī)和在機(jī)場的該機(jī)型的飛機(jī)的數(shù)量總和不超過公司所有的這種機(jī)型的飛機(jī)數(shù)量。式（7）保證飛機(jī)k從機(jī)場z出發(fā)，并最終回到機(jī)場z。2粒子群算法的設(shè)計2.1粒子群算法原理粒子群優(yōu)化（PSO）算法是美國的Kennedy和Eberhar受鳥群覓食行為的啟發(fā),于1995年提出的[7][8]。其他進(jìn)化算法一樣，也是基于“種群”和“進(jìn)化”的概念，通過個體間的協(xié)作與競爭，實(shí)現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時，PSO又不像其他進(jìn)化算法那樣對個體進(jìn)行交叉、變異、選擇等進(jìn)化算子操作，而是將群體(swarm)中的個體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個粒子以一定的速度在解空間運(yùn)動，并向自身歷史最佳位置pbest和鄰域歷史最佳位置gbest聚集，實(shí)現(xiàn)對候選解的進(jìn)化。初始化為一群隨機(jī)粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。設(shè)一個粒子種群共有m個粒子，每個粒子處于n維的Rn空間，具有vi的飛行速度，并且是根據(jù)自己以前最優(yōu)解得解pbesti和整個種群中最優(yōu)的解gbesti進(jìn)行動態(tài)調(diào)整[9]。速度更新時通過粒子的當(dāng)前速度和位置的線性組合來計算的。所有的粒子運(yùn)動服從下面方程：QUOTEνit+1=ωνit+c1r1pbestiQUOTEpit+1=νit+1+pit式中，ω為慣性加權(quán)系數(shù)，用來控制歷史速度對當(dāng)前速度的影響程度，一般在［0.1,0.9］之間取值。通常cl，c2在[0，4]之間，一般取c1=c2=2。r1，r2是均勻分布于[0，11]之間的兩個隨機(jī)數(shù)。式(9)主要通過三部分來計算粒子i新的速度:粒子i前一時刻的速度，粒子i當(dāng)前位置與自己最好位置之間的距離，粒子i當(dāng)前位置與群體最好位置之間的距離。粒子i通過公式(10)計算新位置的坐標(biāo)。通過式(9)和(10)決定粒子下一步的運(yùn)動位置。由于基本粒子群算法存在許多不足，因此常常會因?yàn)閜best和gbest的原因而不能達(dá)到最優(yōu)區(qū)域，使算法早熟收斂。據(jù)此，學(xué)者們在基本粒子群算法的基礎(chǔ)上又提出了離散量子粒子群優(yōu)化算法這種改進(jìn)算法。算法將量子粒子群算法中的粒子離散化，成為離散的粒子矢量[10]。離散量子粒子群算法的粒子群表述為：X=[X1，X2，…XM]，X=[QUOTEχi，1χi，2…，χi，Ν其中，M為粒子群的群體規(guī)模，N為粒子離散化后的位數(shù)。離散粒子每一位QUOTEχij只可取0或者1.離散量子粒子群的粒子更新公式為：(11)(12)(13)QUOTEVgbestκ=αχgbest(14)其中，為分布在[0,1]范圍內(nèi)的隨機(jī)數(shù)。0<,<1為控制參數(shù)，代表了算法對速度的控制度。慣性系數(shù)、社會系數(shù)和認(rèn)知系數(shù)滿足0<<1，2.2算法設(shè)計2.2.1粒子表粒示粒子采用自然數(shù)編碼。飛機(jī)航線可形成一個長度為n+1維(n為航班數(shù))的粒子,其中第n+1維為存放：最優(yōu)評估值位置：例如n=8時，粒子為(3，8，7，5，4，2，1，6，x)。粒子的編碼表示可理解為飛機(jī)從機(jī)場0出發(fā)，執(zhí)行航班任務(wù)3，8，7，5，4，2，1，6后,回到機(jī)場0，形成一條回路。2.2.2計算評價函數(shù)對于某個粒子所對應(yīng)的航線方案，要判定其優(yōu)劣，一是要看其是否滿足航班的約束條件；二是要計算其目標(biāo)函數(shù)值。根據(jù)飛機(jī)排班優(yōu)化問題的特色所確定的編碼方法，隱含能夠滿足每個航班都得到執(zhí)行及每個航班僅由一架飛機(jī)執(zhí)行的約束條件，但不能保證滿足到達(dá)每個機(jī)場時間都滿足時間窗的約束條件（即后一航班的起飛時間必須在前一航班到達(dá)時間之后，其時間間隔不得少于完成一次過站作業(yè)如客貨的裝卸，飛機(jī)加油等所需的最短時間要求，即45min）。為此，對每個粒子所對應(yīng)的航班方案要逐一進(jìn)行判斷，看其是否滿足上述約束條件，若不滿足，則將不能由該粒子執(zhí)行。最后計算目標(biāo)函數(shù)值。對于某個粒子，目標(biāo)函數(shù)為=A+B+C，設(shè)其對應(yīng)航班方案的不可行數(shù)為(=0表示該抗體對應(yīng)一個可行解)，評價函數(shù)值為，QUOTEEi=1Zj+R*Mj2.2.3實(shí)現(xiàn)步驟通過飛機(jī)排班問題的離散量子粒子群算法設(shè)計以及對算法策略的描述可以得到采用離散量子粒子群算法進(jìn)行飛機(jī)排班的程序流程圖，如下圖1所示：初始粒子初始粒子計算粒子適應(yīng)度是否滿足結(jié)束條件定義新的gbest,pbest和H是否產(chǎn)生新的gbest調(diào)整ω值更新速度V和位置P結(jié)束Gbest周圍重新初始化YesYes圖1流程圖Fig.1FlowChartNONO （1）初始化設(shè)置粒子個數(shù)N、慣性權(quán)值、壓縮因子、加速系數(shù)、最大允許迭代次數(shù)或適應(yīng)值誤差限、各粒子的初始位置和初始速度等。（2）按目標(biāo)函數(shù)Ei評價各粒子的初始適應(yīng)值,并保存各粒子初始?xì)v史最優(yōu)位置和初始個體歷史最優(yōu)適應(yīng)值。（3）第i子相粒子進(jìn)行優(yōu)化。（4）i是否超過粒子群所分的相數(shù)?如果沒超過，則i=i+1,且轉(zhuǎn)至步驟(3);否則,i=0,轉(zhuǎn)至步驟(5)。（5）若滿足停止條件(適應(yīng)值誤差達(dá)到設(shè)定的適應(yīng)值誤差限或整個算法迭代次數(shù)超過最大允許迭代次數(shù))，搜索停止，輸出全局歷史最優(yōu)位置和全局歷史最優(yōu)適應(yīng)值為所求結(jié)果;否則，返回步驟(3)進(jìn)行滾動優(yōu)化。3算例分析本文采用文獻(xiàn)[3]的實(shí)例。來比較基本排班模型與本文多目標(biāo)排班模型的排班結(jié)果。表1某航空公司機(jī)型數(shù)據(jù)表Table2Fleetdatasheetofanairline機(jī)型座位數(shù)（個）架次（架）運(yùn)行成本（元）M1248540000M21881835500M31682030000M41482627500M5120322500以某航空公司一周的國內(nèi)航線為例，來比較文獻(xiàn)[3]與本文APTW模型的排班結(jié)果。某航空公司有5種機(jī)型，72架飛機(jī)，5個基地。執(zhí)行48個機(jī)場，1星期的1750個航班。各機(jī)型數(shù)據(jù)如表1所示。根據(jù)飛機(jī)排班問題的特點(diǎn)，在用離散量子粒子群算法初始參數(shù)：最大進(jìn)化代數(shù)G=1000，編碼長度f=20，種群規(guī)模N=20，c1=c2=2，慣性權(quán)重=0.6，=0.1，=0.3，=0.6。對不可行路徑的懲罰權(quán)重R=500。求解10次，得到的結(jié)果見表2。由于數(shù)據(jù)較多，本文就列舉了其中30次航班的排班結(jié)果。表2某航空公司航班時刻表及排班結(jié)果Table2Flightscheduleandarrangementresultofanairline起飛機(jī)場到達(dá)機(jī)場起飛時刻到港時刻班期基本模型排班結(jié)果APTW模型排班結(jié)果PEKSHA093011302M2M1PEKKWE082511101234567M3M4PEKTNA094010301234567M1M1PEKHGH080009501234567M3M3NKGFOC094010551234567M3M1HKGHGH080010101234567M3M3PEKSHA153017253M1M1SHAPEK184020353M5M5PEKSHA093011303M4M5CTUPEK162018301234567M4M4……PEKCTU193022001234567M5M4PEKCTU193022051234567M4M4CTUPEK100011552M1M1CTUPEK10001210136M3M4CTUPEK10001155457M4M4PEKCTU140016251234567M4M4LXACTU154017201234567M3M4LXAPEK154020301234567M4M4CTUPEK182020301234567M4M4PEKPVG074509406M2M2……PEKPVG074509406M2M2PEKPVG0745094013M5M5PEKPVG0745094013M2M5PEKSHA0800100036M4M5PVGPEK143016254M5M5SHAPEK143016254M3M5PVGPEK1430162527M5M5SHAPEK1430162527M5M5SYXCKG230500402357M1M1運(yùn)行結(jié)果顯示的排班方式見表2，表中的排班結(jié)果是進(jìn)行手工調(diào)整后的結(jié)果，表中只列出了排班的機(jī)型選擇結(jié)果，從中可以看出，執(zhí)行APTW模型后的排班結(jié)果不僅將這72個航班均給予了適當(dāng)?shù)陌才?，而且與文獻(xiàn)[3]的結(jié)果相比，增加了需要多飛的M3機(jī)型的飛行時間，減少了需要少飛的M1機(jī)型的飛行時間，飛機(jī)利用率提高了7.58%，確保使用飛機(jī)數(shù)最少這一目標(biāo)；本文排班結(jié)果的成本為3226090元，比文獻(xiàn)[3]排班結(jié)果少了538910元。仿真結(jié)果證明，應(yīng)用本文模型和離散量子粒子群算法等到的排班結(jié)果是可行的，與文獻(xiàn)[3]排班所得結(jié)果相比更能體現(xiàn)公平、合理原則。得到了多目標(biāo)組合優(yōu)化問題的最優(yōu)解，與免疫算法相比，該算法速度快，求得的解具有更好的特性。4結(jié)論本文研究了帶時間窗的多目標(biāo)飛機(jī)排班問題，提出了以使用飛機(jī)最少、飛機(jī)運(yùn)營成本最低、消費(fèi)者滿意度為目標(biāo)的飛機(jī)排班模型，并運(yùn)用離散量子粒子群算法對模型進(jìn)行了實(shí)例分析，結(jié)果顯示：該模型能有效提高飛機(jī)的利用率，有效節(jié)約成本。但是當(dāng)航班排班問題規(guī)模增大、約束增多，此模型及算法是否有效，有待進(jìn)一步的研究論證。5參考文獻(xiàn)Brian,R.,Cynthia,B.,Tim,K.andAhmad,[J].AirlineFleetAssignmentwithTimeWindows,TransportationScience.2000,Vol.34(1).XuHair