楊新湦, 屈琮博, 王梓旭
(1.中國民航大學(xué)中歐航空工程師學(xué)院, 天津 300300; 2.中國民航大學(xué)空中交通管理學(xué)院, 天津 300300)
航空運(yùn)輸系統(tǒng)是一個復(fù)雜的巨系統(tǒng),航班不正常是每個航空公司不可避免會面臨的問題。航空公司大面積不正常航班恢復(fù)是困難問題,一般而言,航空公司不正常航班恢復(fù)可分為分階段恢復(fù)與一體化恢復(fù)。分階段恢是將整個恢復(fù)問題分為飛機(jī)恢復(fù)、機(jī)組恢復(fù)、旅客恢復(fù)三個階段逐步求解;一體化恢復(fù)則是綜合考慮飛機(jī)、機(jī)組、旅客因素。
對不正常航班恢復(fù)的研究多數(shù)集中于分階段恢復(fù)研究。Teodorovic等[1-4]在1984~1995年先后對飛機(jī)停運(yùn)、機(jī)場關(guān)閉航班恢復(fù)問題、旅客恢復(fù)和機(jī)組恢復(fù)問題進(jìn)行了研究。分別使用分支定界、動態(tài)規(guī)劃、啟發(fā)式算法進(jìn)行了求解,奠定了不正常航班分階段恢復(fù)的基礎(chǔ)。吳剛等[5]提出一種改進(jìn)列生成算法,每次迭代過程中加入多個列,并對加入的多個列需要滿足的條件進(jìn)行了分析,最后給出的算例驗(yàn)證了該方法的正確性和有效性。田倩南等[6]改進(jìn)時空網(wǎng)絡(luò)算法,給出占優(yōu)準(zhǔn)則,有效減少了可恢復(fù)航線的組合數(shù)量,提升計(jì)算效率。

已有文獻(xiàn)中多采用時空網(wǎng)絡(luò)進(jìn)行建模,時空網(wǎng)絡(luò)中不僅有描述航班銜接的航班邊,還有機(jī)場節(jié)點(diǎn)和時間節(jié)點(diǎn)。當(dāng)進(jìn)行一體化建模時導(dǎo)致模型過于復(fù)雜。Sherali等[12]系統(tǒng)介紹了航班網(wǎng)絡(luò)的使用,相比時空網(wǎng)絡(luò)模型復(fù)雜度低,但是不能將時間、地點(diǎn)等屬性表現(xiàn)在圖中,諸如飛機(jī)維修約束、機(jī)組執(zhí)勤時間約束、客票取消操作不易表達(dá)。……