基于相關機會約束規劃的應急調度機型指派問題研究

朱博文，唐福玉，徐書娟，陳 靜

（中國民航大學 理學院，天津 300300）

基于相關機會約束規劃的應急調度機型指派問題研究

朱博文，唐福玉，徐書娟，陳 靜

（中國民航大學 理學院，天津 300300）

為應對民航突發情況，保障民航運行安全，提出應急調度這一概念。本文闡述常規情況下航班調度的基本模型，分析其在應急情況下的弊端。引入相關機會約束，構建應對突發狀況的應急調度模型。根據擬合數據，利用基于隨機擬合的改進遺傳算法，借用matlab軟件求解模型。結果顯示，基于相關機會約束規劃的機型指派模型在考慮隨機因素的情況下，比基本模型更符合實際動態環境要求。

相關機會約束；應急調度；機型指派；遺傳算法

航空公司一般會提前1年制訂出相應的航班計劃，然而這些計劃在安排時常被不確定事件打亂。利用恰當的模型與優化算法，提出應急調度方案，有利于保障航空公司快速恢復正常運營，減少航班延誤。對此黃為 等論述了航空公司航班應急調度的目標、方法及對策。牟德一 等提出航班調度應急管理魯棒調度與受擾恢復策略研究。本文引進相關機會約束，在傳統的模型中加入隨機變量，建立帶有相關機會約束的航班調度模型。

1　應急情況下機型指派模型研究

1.1確定情況下航班調度問題的機型指派模型

機型指派管理對航空公司收益管理有較大影響，是整個航班計劃管理的核心部分。以下是馬蘇德·巴扎爾甘提出的機型指派模型簡化模式。

式中：C為到達機場集合，表示網絡中所有結點或停場過夜機場；F為航班集合；Pi， j為由機型j飛航班i的成本；如果航班i用機型j執行，則xi， j=1，否則為0，M為網絡中的機場（結點）數；J為機型集合。

1.2應急情況下的航班調度機型指派問題相關機會約束模型

在應急情況下，管理者期望在花費資金較少的情況下最大概率的實現預期的管理目標，由于在航班應急情況下，許多參量出現一定的隨機型，原來的一部分確定型變量轉化成為隨機變量，傳統的確定型數學規劃模型無法很好地求解這類機型指派問題，相關機會約束模型，在根據具體條件情況要求下設定一定的優先等級，允許在一定情況一定置信水平下滿足約束條件，其模型如下。

式中：ξ是個隨機向量；x是個決策向量；α和β是管理者預先給定的置信水平。為航班實際的成本。其中ξj表示航班j的旅客量，是一個隨機變量；Si表示機型i的座位數；Gk， j為機型j在機場k過夜的飛機數量。Nj為機型j的可用飛機數量；當結點k的航班i是進港航班，Sj，k=+1，當結點k的航班i是離港航班，Si，k=-1。

2　模型算法研究

2.1機會函數的計算機仿真擬合計算

設gj（x，ξ）≤0， j=1，2，…，P是事件Aj在點x的誘導約束，則機會函數式fj（x）由下式給出：

相關機會約束目標函數變化為Max（ f1（x）， f2（x），…， fp（x），其中x為管理變量；ξ為隨機變量，其分布為φ（ξ）。

我們允許采用蒙特卡羅隨機擬合方法估計機會函數fj（x）。具體思想是利用ξ為隨機變量的分布φ（ξ），從中產生N個隨機向量，分別記為ξ1，ξ2，…，ξN；設N次試驗中gj（x，ξk）≤0（k=1，2，…，N）成立的次數為n，即隨機變量中符合約束條件的個數。由中心極限定理和大數定理得出，機會函數允許用近似估計概率。

2.2隨機擬合仿真的改進遺傳算法

由于相關機會模型問題的復雜性，很難利用現有的理論方法求解，采用蒙特卡羅隨機仿真擬合的改進遺傳算法極大地方便求解模型。基于蒙特卡羅隨機擬合的改進遺傳算法求解步驟如下。步驟1：確定變異概率Pm，交叉概率Pc及種群數參數N；步驟2：編碼優化問題，形成有N個染色體的初始群體，并借用隨機擬合技術檢驗染色體的可行性；步驟3：借用隨機擬合技術估算初始種群中每個染色體的適應值；若停止規則滿足，則算法停止，否則轉下一步；步驟4：估算概率；步驟5：以概率Pi從初始種群中隨機選部分染色體構建新的種群；步驟6：按照給定的變異概率Pm與交叉概率Pc，對染色體實行變異與交叉操作，并借用蒙特卡羅隨機擬合技術檢驗后代的可行性；步驟7：重復步驟2至步驟6，直到完成設定的循環次數；步驟8：給出方案結果最好的染色體作為最終最優解。

3　算例分析

A航空公司為應對由風暴等不確定因素引起的大面積航變，提前制定應急預案。該公司有2種機型，6架Ⅰ型飛機，3架Ⅱ型飛機，Ⅰ、Ⅱ機型的座位數分別為185、200。設A航空公司甲、乙城市之間的航班旅客需求為ξ1（去）、ξ2（返）分別為正態分布ξ1～N（150，352）、ξ2～N（160，472），首先來解2.1中的模型，根據算例的數據，得到F=｛1，2，3，4，5，6｝，J=｛1，2｝，M=｛1，2，3｝，N1=6，N2=9，由程序得到最優解確定性模型最小成本為115 608，甲乙往返滿足旅客量需求置信水平分別是80%、52%。現引入相關機會約束，設定一定的優先等級，設定滿足甲去乙為第一優先級，置信水平不低于90%，乙返回甲地為第二優先級，置信水平不低于80%，滿足在相關基礎模型參數基礎上，求解的相關機會約束模型最小成本為121 956。并且誤差不超過2%。結果顯示，成本雖然有所增加，卻能夠以較高的置信度滿足旅客需求，模型具有魯棒性，往返置信水平分別提升到90%、80%以上，有效提升航空公司形象及顧客滿意度，有利于長遠發展。

4　結　語

在前人成果基礎上構建相關機會約束的機型指派模型，并運用蒙特卡羅隨機擬合與改進遺傳算法等方法求解模型，結果顯示模型的可行性及魯棒性，一定程度上可為航空公司的應急機型調度提供相應參考。但模型僅考慮了不確定旅客需求的隨機性，實際情況較為復雜，可以進一步研究同時包含模糊不確定性、隨機不確定性的突發狀況及應急調度。

主要參考文獻

［1］趙秀麗.航空公司不正常航班恢復模型及算法研究［D］.南京:南京航空航天大學.2010.

［2］［美］馬蘇德·巴扎爾甘.航空公司運營規劃與管理［M］.邵龍，王美佳，譯.北京:中國民航出版社，2006:39-56，81-91.

［3］牟德一，王志新，夏群.基于機組延誤概率的魯棒性機組配對問題［J］.系統管理學報，2011，20（2）:207-212.

［4］劉寶碇，趙瑞清，王綱.不確定規劃及應用［M］.北京:清華大學出版社，2003:84-91.

［5］黃為.國內航班的應急調度管理［J］.經濟與管理，2009（3）:74-76.

10.3969/j.issn.1673 - 0194.2015.12.103

F224.3；V352

A

1673-0194（2015）12-0135-02

2015-04-13