不正常航班飛機恢復決策的隨機規劃方法

孫成豪+王婉貞+周潤

摘 要：航班計劃是一個實時優化問題。諸多不確定因素會造成正常航班的擾動，包括航空器故障，惡劣天氣，交通管制等。本文的目的是通過構建數學模型來得出不正常航班飛機恢復的優化方案。本文將航班的延誤時間處理為隨機變量，總延誤時間作為優化目標，在可用的資源和航空公司估計成本的機會約束條件下，構建了一個隨機機會約束規劃模型。

關鍵詞：航空公司運營；不正常航班；飛機恢復；機會約束規劃；遺傳算法

DOI：10.16640/j.cnki.37-1222/t.2017.12.238

0 引言

由于航空業的特點和競爭的需要，航空公司的航班運行控制對運籌學的許多分支理論和方法，特別是最優化技術有著非常迫切的需求。

在國外，文獻[1]中，Yu提出了針對航空公司不正常航班調度問題的擾動管理策略，就航空公司常規和非常規航班調度問題進行了建模優化。文獻[2]找到快速有效的算法和軟件處理航班調度問題。Teodorobic ，Stojkovicd等人[3]為了使取消航班數量和旅客總延誤時間最小，提出了一種基于Lexicographic動態規劃模型。在我國，趙秀麗[4]把航班延誤時間看作為常量，分別對不正常航班的取消航班問題、飛機路線恢復問題、機組恢復問題、一體化航班計劃恢復問題進行了研究。文獻[5]中就機組延誤問題，建立了基于概率的魯棒性機組配對問題和飛機排班問題的隨機模型。本文針對不正常航班下的飛機恢復問題研究建立相應的優化模型及算法。后續內容安排如下：第2章是預備知識；第3章是問題描述和基本建模方法；模型及算法在第4章；全文的總結和展望放在了第5章。

1 隨機機會約束規劃

定義2.1[6]假設x是一個決策向量，ξ是一個隨機向量，是目標函數，（j=1，2，…，p）是沒有給出確定的可行集的隨機約束函數。機會約束可以表示為如下的形式：

2 問題描述與基本方法

當惡劣天氣或機械故障引起航班延誤時，由于惡劣天氣持續時間和故障機械修復時間都是不確定的，從而航班延誤時間是不確定的。本文將總延誤時間作為優化目標，而公司成本預算作為約束條件，建立問題的模型及算法。Argüello [7]提出了時間帶近似模型相關理論，本文采用時空網絡結構來調整航班安排。

3 飛機恢復問題的機會約束規劃模型與算法

約束二：飛行的覆蓋范圍。每個航班都只有飛行或取消兩種狀態，因此，每個航班k對應的飛行和取消狀態和為1。例如，航班34有兩種可選飛行航線，一個取消狀態，每個航班僅執行一次，可得以下公式：

同理，所有航班k均可表達為上述形式。

約束三：轉送結點飛機流。結點中的飛機數量=在該結點起飛飛機數量-在該結點降落飛機數量+由該結點轉移到同一城市沉落結點的飛機數量。

約束四：沉落結點飛機流。沉落結點需要的飛機數量=在該沉落結點降落的結束航班的飛機數量+從同一城市其他結點轉移來過夜的飛機數量。

每個沉落結點都有相對應的約束條件：

由此得到模型：