圖論最大流理論

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

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

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

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

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

相關(guān)信息

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

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

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

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