孫成豪+王婉貞+周潤

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

關(guān)鍵詞：航空公司運(yùn)營；不正常航班；飛機(jī)恢復(fù)；機(jī)會(huì)約束規(guī)劃；遺傳算法

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

0 引言

由于航空業(yè)的特點(diǎn)和競爭的需要，航空公司的航班運(yùn)行控制對(duì)運(yùn)籌學(xué)的許多分支理論和方法，特別是最優(yōu)化技術(shù)有著非常迫切的需求。

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

1 隨機(jī)機(jī)會(huì)約束規(guī)劃

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

2 問題描述與基本方法

當(dāng)惡劣天氣或機(jī)械故障引起航班延誤時(shí)，由于惡劣天氣持續(xù)時(shí)間和故障機(jī)械修復(fù)時(shí)間都是不確定的，從而航班延誤時(shí)間是不確定的。本文將總延誤時(shí)間作為優(yōu)化目標(biāo)，而公司成本預(yù)算作為約束條件，建立問題的模型及算法。Argüello [7]提出了時(shí)間帶近似模型相關(guān)理論，本文采用時(shí)空網(wǎng)絡(luò)結(jié)構(gòu)來調(diào)整航班安排。

3 飛機(jī)恢復(fù)問題的機(jī)會(huì)約束規(guī)劃模型與算法

約束二：飛行的覆蓋范圍。每個(gè)航班都只有飛行或取消兩種狀態(tài)，因此，每個(gè)航班k對(duì)應(yīng)的飛行和取消狀態(tài)和為1。例如，航班34有兩種可選飛行航線，一個(gè)取消狀態(tài)，每個(gè)航班僅執(zhí)行一次，可得以下公式：

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

約束三：轉(zhuǎn)送結(jié)點(diǎn)飛機(jī)流。結(jié)點(diǎn)中的飛機(jī)數(shù)量=在該結(jié)點(diǎn)起飛飛機(jī)數(shù)量-在該結(jié)點(diǎn)降落飛機(jī)數(shù)量+由該結(jié)點(diǎn)轉(zhuǎn)移到同一城市沉落結(jié)點(diǎn)的飛機(jī)數(shù)量。

約束四：沉落結(jié)點(diǎn)飛機(jī)流。沉落結(jié)點(diǎn)需要的飛機(jī)數(shù)量=在該沉落結(jié)點(diǎn)降落的結(jié)束航班的飛機(jī)數(shù)量+從同一城市其他結(jié)點(diǎn)轉(zhuǎn)移來過夜的飛機(jī)數(shù)量。

每個(gè)沉落結(jié)點(diǎn)都有相對(duì)應(yīng)的約束條件：

由此得到模型：