基于網(wǎng)絡(luò)流理論復(fù)合停機(jī)位分配模型

趙偉麗

(沈陽(yáng)理工大學(xué)理學(xué)院 遼寧 沈陽(yáng) 110159)

1 引言

復(fù)合停機(jī)位是指在同一時(shí)刻可以供兩個(gè)小型飛機(jī)或一個(gè)大型飛機(jī)停機(jī)的機(jī)位，采用復(fù)合機(jī)位可以有效提高近機(jī)位的利用率。例如浦東機(jī)場(chǎng)T2航站樓，一個(gè)大機(jī)位兼容兩個(gè)小機(jī)位，如1F兼1D和1C，1E兼2C。本文以飛機(jī)燃油消耗和旅客行走距離最小為目標(biāo)，建立高效使用復(fù)合機(jī)位的多商品網(wǎng)絡(luò)流單目標(biāo)的優(yōu)化模型[1-4]。使用真實(shí)航班數(shù)據(jù)進(jìn)行模型驗(yàn)證，計(jì)算結(jié)果表明本模型在充分使用復(fù)合停機(jī)位的條件下，達(dá)到了兼顧機(jī)場(chǎng)和旅客的利益，停機(jī)位的利用率更加高效科學(xué)的目的。同時(shí)為了提高計(jì)算的速度，在計(jì)算時(shí)采用分區(qū)的策略來加速模型的求解。模型求解使用IBM公司的ILOG最優(yōu)化軟件求解停機(jī)位分配問題，得到了國(guó)內(nèi)某大型機(jī)場(chǎng)航班分配的結(jié)果。

2 多商品網(wǎng)絡(luò)流復(fù)合停機(jī)位分配模型

文獻(xiàn)[5]給出了多商品網(wǎng)絡(luò)流模型，研究了停機(jī)位分配問題。本文在此基礎(chǔ)上探究復(fù)合停機(jī)位的分配問題。集合符號(hào)及參數(shù)說明不再贅述，可以參照文獻(xiàn)[5]。

約束條件作如下變更：

第一個(gè)約束方程（1）對(duì)流入弧進(jìn)行限制，它涉及到停機(jī)位流從源點(diǎn)到到港航班節(jié)點(diǎn)，要求分配給到港航班節(jié)點(diǎn)某個(gè)停機(jī)位的單位流，或者停機(jī)位未使用通過流通弧來連接。第二個(gè)約束方程（2）說明到達(dá)節(jié)點(diǎn)的流守恒。第三個(gè)約束方程（3）說明離開節(jié)點(diǎn)的流守恒。第四個(gè)約束方程（4）說明對(duì)于流出流的一個(gè)約束，要求所有離開節(jié)點(diǎn)的流必須流向終點(diǎn)。第五個(gè)約束方程（5）說明對(duì)于單位流服務(wù)弧的約束，只允許一個(gè)單位流通過服務(wù)弧流向停機(jī)位k，第六個(gè)約束（6）是大飛機(jī)只能停在復(fù)合停機(jī)位。第七個(gè)約束（7）是變量的二值約束條件。

3 模型求解

出于計(jì)算目的，使用了安裝在實(shí)驗(yàn)中心英特爾（R）Xenon（R）至強(qiáng)處理器28核64位處理器，核心頻率為3.0GHz，具有64GB內(nèi)存。根據(jù)模型變量中的二值約束條件可知本模型屬于二值混合整數(shù)規(guī)劃問題，使用優(yōu)化求解軟件ILOG編寫AMPL/CPLEX 12.5程序求出問題的結(jié)果。

模型算法求解流程見圖1。

圖1 模型算法計(jì)算流程

4 實(shí)例分析

通過查找國(guó)內(nèi)機(jī)場(chǎng)某一天的具體航班時(shí)刻表，選取某個(gè)時(shí)間段內(nèi)空閑的10個(gè)停機(jī)位為例，按照上述模型，對(duì)50個(gè)即將到達(dá)的航班進(jìn)行分配，使用ILOG軟件進(jìn)行求解。表1是各個(gè)航班到港和離港時(shí)刻表（表1僅列出部分航班），其中機(jī)型B767和B777為大型飛機(jī)只能停靠在復(fù)合停機(jī)位；停機(jī)位之間的距離見表2；模型中其它參數(shù)值參照文獻(xiàn)[5]。

表1 航班到港離港時(shí)刻表

表2 機(jī)位距離

利用ILOG軟件進(jìn)行程序編寫，計(jì)算得到本實(shí)例停機(jī)位分配結(jié)果見表3。

表3 計(jì)算結(jié)果

從停機(jī)位距離參數(shù)表2中可以看到停機(jī)位G 6距離飛機(jī)起飛和降落的跑道的距離是最近的，分別是12224.65m和13831.98m。機(jī)位的分配計(jì)算結(jié)果表3中停機(jī)位G 6分配到了最多的航班，這一結(jié)果和目標(biāo)函數(shù)表示距離最短是吻合的，表明模型和求解與實(shí)際是相符的。

5 結(jié)論

文中采用多商品網(wǎng)絡(luò)流模型原理解決復(fù)合停機(jī)位分配問題，這一模型兼顧了機(jī)場(chǎng)和旅客，達(dá)到雙贏的目的。同時(shí)使用IBM公司的ILOG軟件求得深圳機(jī)場(chǎng)某時(shí)間段的航班停機(jī)位的分配結(jié)果，表明模型是正確可行的。