圖論最大流理論在機場登機口分配中的應(yīng)用

圖論最大流理論

在機場登機口分配中的應(yīng)用教師:張金山聯(lián)系方式:zjscdut@163.com;主要參考書籍:1.數(shù)學(xué)建模與數(shù)學(xué)實驗,趙靜,但琦2.數(shù)學(xué)實驗,蕭樹鐵3.數(shù)學(xué)建模方法及其應(yīng)用,韓中庚4.數(shù)學(xué)建模導(dǎo)論,陳理榮

數(shù)學(xué)建模簡介

理想與現(xiàn)實什么是數(shù)學(xué)建模?

數(shù)學(xué)建模是利用數(shù)學(xué)方法解決實際問題的一種實踐。即通過抽象、簡化、假設(shè)、引進變量等處理過程后，將實際問題用數(shù)學(xué)方式表達(dá)，建立起數(shù)學(xué)模型。數(shù)學(xué)建模所涉及的問題都是現(xiàn)實生活中的實際問題，范圍廣、學(xué)科多，包括工業(yè)、農(nóng)業(yè)、醫(yī)學(xué)、生物學(xué)、政治、經(jīng)濟、軍事、社會、管理、信息技術(shù)等方面。

1、問題的描述（背景）隨著機場航班日起降架次的增多和乘飛機出行旅客數(shù)量的迅速增長，現(xiàn)有的登機口資源正面臨著日益嚴(yán)峻的考驗。目前，大多數(shù)機場通過借鑒其他機場的做法，或根據(jù)以往的經(jīng)驗來進行登機口分配和調(diào)度，往往導(dǎo)致很多載客數(shù)量較多的大中型飛機?？吭诰喟矙z或者行李提取大廳較遠(yuǎn)的登機口；或由于遠(yuǎn)、近機位登機口航班密度安排不合理，使得每個登機口的航班組合沒有達(dá)到最優(yōu)，從而降低了登機口的利用效率。

相關(guān)信息

根據(jù)某機場一天中部分時段的航班計劃，將各航班信息匯總表1所示

航站樓布局登機口、安檢區(qū)與行李提取大廳的位置

安檢區(qū)與行李提取大廳不同層但位置相近安檢區(qū)與行李提取大廳(不)同層但位置不同在保證機場安全、高效運行的前提下，盡可能提高登機口利用效率，體現(xiàn)民航旅客運輸?shù)谋憬菪耘c舒適性。2、問題分析旅客步行距離最短模型的優(yōu)化目標(biāo)與約束條件優(yōu)化目標(biāo)1)使進、出港旅客的總步行距離最短，滿足旅客對航空運輸“便捷性”的需求；2)使現(xiàn)有設(shè)施使用效率達(dá)到最高，優(yōu)化資源配置。約束條件1)機型與機位類型相匹配；2)分配登機口時，一個航班必須被分配且僅能被分配至一個登機口；3)應(yīng)滿足最短過站時間和同機位安全間隔時問的要求；4)“航班對”的限制：由于在機場?？康慕^大部分航班既擔(dān)負(fù)著進港航班任務(wù)，又擔(dān)負(fù)著出港航班任務(wù)，因此，盡量將此類飛機盡可能安排在同一個登機口，降低航空公司運營成本。除此之外，根據(jù)各機場的性質(zhì)和特點不同，還需考慮登機口分配的優(yōu)先原則、航班過夜、飛機維修等約束條件。3、模型的建立與求解

3.1數(shù)據(jù)收集與整理利用表l中已知航班信息作為實例分析的數(shù)據(jù)來源，采用最廣泛的航站樓布局形式即假定安檢區(qū)和行李提取大廳分別位于航站樓的上、下兩層，位置近似相同，以此來說明該模型的構(gòu)建方法和應(yīng)用過程。3.2優(yōu)化分配網(wǎng)絡(luò)模型的構(gòu)建3.2.1進、出港旅客步行距離最短模型建立與實證分析對于國內(nèi)大部分干線和支線機場而言，始發(fā)或終到旅客所占比例甚多，從長時間的數(shù)據(jù)統(tǒng)計來看，這兩部分旅客所占比例相當(dāng)，因此，可將其步行距離視為近似相等。以下就是進、出港旅客步行距離最短模型的實施步驟：步驟1按照登機口啟用時間的先后順序，由左至右把每個航班作為網(wǎng)絡(luò)圖上的一個節(jié)點，在考慮各種約束條件的基礎(chǔ)上，將節(jié)點之間進行有向連線，方向為由離港時間早的航班指向晚的，由此形成一個由節(jié)點和箭頭構(gòu)成的網(wǎng)絡(luò)圖。不難理解，網(wǎng)絡(luò)圖中從起點到終點的每一條有向路徑上的節(jié)點都是可以安排在一個登機口上的航班組合，如圖3所示。步驟2在圖3上，按照各節(jié)點的時間順序?qū)ζ溥M行二次編號G(A，B)，G表示航班編號；A表示航班G的前一個航班的編號(若為起始航班，則其編號為本次航班的號碼)；B表示航班載客人數(shù)的累計，即前一個航班A的實際載客人數(shù)與本次航班G的實際載客人數(shù)之和。需要注意的是，若A前有兩個或多個已編號航班，則擇選B最大的那個航班作為G的前一個航班，如圖4所示。步驟3將每架航班的人數(shù)看成是網(wǎng)絡(luò)圖中的流量，從登機口結(jié)束使用的這個網(wǎng)絡(luò)圖的最大流量就表示可以使用同一個登機口的人數(shù)最多的航班組合。從終點開始逆向?qū)ふ乙粭l至起點航班人數(shù)最多的路徑，并把這條路徑上的航班安排在距安檢出口最近的登機口。在圖4中，01→04→07即為網(wǎng)絡(luò)圖中旅客流量最大的航班組合，可將這3個航班按照登機口啟用先后順序安排至離安檢區(qū)最近的登機口。步驟4在調(diào)度網(wǎng)絡(luò)圖上去掉已安排過的航班節(jié)點及與其相關(guān)聯(lián)的箭線，再從新的起點開始尋找一條至終點航班人數(shù)最多的路徑，并把這條路徑上的航班安排在距安檢出口次近的登機口，如圖5所示。在圖5中，02→03→05→08為網(wǎng)絡(luò)圖中旅客流量最大組合，可將這4個航班按照登機口啟用先后順序安排至離安檢區(qū)次近的登機口。步驟5重復(fù)步驟4，按照上述方法直到所有的航班安排完為止。本例中剩下06號航班，可將其安排至3號登機口。3.3.1算法的復(fù)雜度分析如前所述，該模型總運算次數(shù)不會超過n，而網(wǎng)絡(luò)圖中航班節(jié)點的總數(shù)也不會超過n，故總運算次數(shù)不會大于n2，即其計算復(fù)雜度為o(n2)。3.3算法復(fù)雜度分析和最優(yōu)性證明2.3.2算法的最優(yōu)性證明為了說明算法是最優(yōu)算法，現(xiàn)在登機口調(diào)度網(wǎng)絡(luò)圖上增加一個虛擬起始節(jié)點s和一個虛擬終結(jié)節(jié)點t，并將虛擬起始節(jié)點s與所有起始航班節(jié)點用箭頭相連，同樣，將所有終結(jié)節(jié)點與虛終結(jié)節(jié)點t也用箭頭相連，如圖6所示。由于各航班節(jié)點是按時間順序由左至右排列的，因此，圖6所示的網(wǎng)絡(luò)圖是一個具有兩端點s和t的無環(huán)路網(wǎng)絡(luò)圖。其中每一條從s到t的有向路徑，都是可在同一個登機口安排航班組合的可行方案。如果把各節(jié)點的航班人數(shù)作為以該節(jié)點為終點的各箭線的權(quán)值，則該網(wǎng)絡(luò)圖就相