【正文】 航空運輸規(guī)劃學(xué) 2008年10月第一章 緒論11 航空運輸系統(tǒng)概述航空運輸系統(tǒng)由航空公司子系統(tǒng)、機場子系統(tǒng)和空管子系統(tǒng)組成。航空運輸系統(tǒng)的組成如圖11所示，系統(tǒng)的邊界是“機場陸路到達系統(tǒng)”，它有時也被作為航空運輸系統(tǒng)的一部分進行處理。航空運輸系統(tǒng)作為社會系統(tǒng)的子系統(tǒng)，它的外部是社會系統(tǒng)的其他部分和氣象等自然系統(tǒng)，系統(tǒng)的服務(wù)對象是運輸需求發(fā)生地（需求源）。圖11 航空運輸系統(tǒng)航空公司是運輸生產(chǎn)的主體，是航空運輸系統(tǒng)直接面對旅客或貨主的最主要部分，旅客的不滿幾乎全部撒向航空公司，即使延誤是由惡劣天氣或飛機流量管理造成的，也會造成旅客對航空公司的抱怨。旅客通過與航空公司接觸的界面感受航空公司的服務(wù)質(zhì)量，包括機票銷售、航站樓服務(wù)和機上服務(wù)等，但航空公司的服務(wù)質(zhì)量取決于服務(wù)鏈上的每個環(huán)節(jié)，從機隊規(guī)劃（機型的選擇）、航線規(guī)劃、航班計劃、機務(wù)維修到運行控制，甚至為旅客服務(wù)的信息系統(tǒng)，處處都體現(xiàn)出航空公司的服務(wù)水平和服務(wù)質(zhì)量。機場公司和空中交通管理局則為航空公司提供生產(chǎn)保障服務(wù)，幫助和支持航空公司完成運輸生產(chǎn)任務(wù)，因此航空公司在航空運輸系統(tǒng)內(nèi)部是機場和空管局的客戶。12 航空運輸營運要素 航空運輸?shù)某晒I運除了需要航空器、空勤人員、地勤人員和其它硬件資源以外，還需要軟件要素的成功運用，包括航空運輸計劃、組織和運行，這軟件三要素前后相繼，又反饋控制，形成航空運輸營運系統(tǒng)的閉合鏈。本節(jié)簡要介紹這三要素。121 航空運輸計劃航空運輸計劃的主體是航空公司，航空公司將制定好的航班計劃提交給相關(guān)機場和空管局，機場和空管局在此基礎(chǔ)上形成自己的航班計劃。但航空公司在設(shè)計航班計劃時必須與機場當(dāng)局和空管局溝通、協(xié)調(diào)，對新增的航班還須獲得他們的批準(zhǔn)，才能最終形成自己的航班計劃。122 航空運輸組織有了運輸計劃，必須建立有效的運輸組織才能使運行有章可循，按程序流動。因此航空運輸組織是完成運輸任務(wù)的流程、章程和法規(guī)。機場是航空運輸活動的主要場所，圖12是機場子系統(tǒng)的進出港流程圖。機場陸路到達系統(tǒng)由陸路交通系統(tǒng)和機場停車場、車站和道邊系統(tǒng)構(gòu)成，陸路交通系統(tǒng)可能是機場高速、機場輕軌、機場地鐵。機場高速的交通工具可能是出租車、公交車、機場巴士、團隊客車和私家車，公交車需要設(shè)立車站；出租車到達機場后只在航站樓前短暫停車，下客后即離開，應(yīng)當(dāng)為他們設(shè)置道邊系統(tǒng)；私家車和團隊車下客后一般需要停車，因此應(yīng)當(dāng)為它們建設(shè)停車場。為此應(yīng)當(dāng)對機場高速的車輛結(jié)構(gòu)和數(shù)量進行調(diào)研、預(yù)測和評估，為規(guī)劃停車場面積、道邊長度和寬度以及公交車車站提供依據(jù)。對于出發(fā)旅客，機場陸側(cè)指從值機大廳入口到登機口（又叫閘口）的部分，其間提供的服務(wù)有值機、安檢、候機、登機等，對于國際旅客還必須提供海關(guān)、邊防檢查等服務(wù)；對于到達旅客，機場陸側(cè)指從旅客到達入口到迎客廳出口的部分，其間提供的服務(wù)主要是行李認領(lǐng)和迎客，對于國際到達旅客，還提供邊防、海關(guān)和動植物檢驗等服務(wù)；對于中轉(zhuǎn)的旅客，是指航站樓中辦理換取登機牌和提供中轉(zhuǎn)候機服務(wù)的部分。有些陸側(cè)的服務(wù)（主要是值機）可以前移至城市航站樓、火車站、機場到達交通工具上，以方便旅客，因此也可將陸路交通系統(tǒng)歸入機場陸側(cè)系統(tǒng)?，F(xiàn)在也有網(wǎng)上值機系統(tǒng)，在航站樓值機大廳還設(shè)有自助式值機系統(tǒng)，以方便旅客值機。 圖12 機場子系統(tǒng)旅客進出港作業(yè)流程出發(fā)貨郵到達機場后首先在陸側(cè)進入貨站，對貨物進行分理、裝箱、打包、過磅、安檢等服務(wù)，然后使用機場平板車進入停機坪裝機。到達貨郵到達機場后首先卸機，然后通過場面運輸進入貨站，進行分理后，再通過機場陸路到達系統(tǒng)運輸?shù)阶罱K目的地。如果是國際出發(fā)/到達貨郵，還必須通過海關(guān)和動植物檢驗后放行才能出/入關(guān)。中轉(zhuǎn)行李需要通過自動化分揀設(shè)備或人工分揀，然后準(zhǔn)確轉(zhuǎn)運到各出發(fā)飛機上。123 航空運輸運行 有了航空運輸計劃和運輸生產(chǎn)組織體系，接下來是航空運輸生產(chǎn)運行。航空運輸運行包括航空公司運行、機場運行和空中交通管理三部分。航空公司的運行控制中心是負責(zé)生產(chǎn)運行的控制部門，在這里集中了市場部門、機務(wù)部門、飛行和客艙部門、地面服務(wù)部門的代表，以及航行情報、性能工程和飛行簽派的專家。運輸生產(chǎn)在這里組織實施，生產(chǎn)狀態(tài)在這里進行監(jiān)控。生產(chǎn)發(fā)生一般性問題，由運控中心領(lǐng)導(dǎo)與有關(guān)部門代表協(xié)商解決。這里還有公司的值班領(lǐng)導(dǎo)，生產(chǎn)運行一旦發(fā)生重大問題，由公司領(lǐng)導(dǎo)牽頭，各部門代表會商解決，必要時須與機場監(jiān)控中心（指揮處）以及空管部門協(xié)商解決。負責(zé)機場生產(chǎn)運行的部門是機場監(jiān)控中心（指揮處），其職責(zé)是調(diào)配機場的生產(chǎn)資源，保障機場正常和安全生產(chǎn)。這里集中著最先進的監(jiān)控設(shè)備和生產(chǎn)管理信息系統(tǒng)、服務(wù)信息系統(tǒng)，生產(chǎn)現(xiàn)場的情形在這里一目了然，監(jiān)控人員隨時可以和生產(chǎn)部門進行聯(lián)系，解決發(fā)生的問題。這里也是機場與航空公司和空管部門進行協(xié)調(diào)，解決問題的部門?？展懿块T根據(jù)航班計劃和跑道容量、空域容量等對空中交通流量進行管理，保障飛機安全有序飛行。管制區(qū)域通常分為塔臺管制區(qū)、近進管制區(qū)和區(qū)域管制，分別由塔臺管制員、近進管制員和區(qū)域管制員管理。管制員主要和飛行員發(fā)生聯(lián)系，以實現(xiàn)指揮飛機飛行的目的，必要時還會與航空公司運控中心、機場監(jiān)控中心進行聯(lián)系。根據(jù)自己管制的扇區(qū)容量和扇區(qū)內(nèi)飛機流量情況，管制員決定飛機通過某定位點的順序以及同一航路上前后兩架飛機的間隔，保障飛機的安全飛行。13 航空運輸規(guī)劃概述131 航空運輸規(guī)劃定義和意義如前所述，計劃是航空運輸生產(chǎn)的依據(jù)和出發(fā)點，而規(guī)劃則是為實現(xiàn)預(yù)定目標(biāo)對未來的行動做出的計劃。航空運輸規(guī)劃是為實現(xiàn)航空運輸系統(tǒng)的目標(biāo)對系統(tǒng)的結(jié)構(gòu)、規(guī)模、作用、反應(yīng)和市場等做出的計劃。航空運輸生產(chǎn)能力的安排應(yīng)當(dāng)與運輸需求相適應(yīng)，或兩者應(yīng)當(dāng)盡可能保持平衡。如果生產(chǎn)能力大于運輸需求，則由于運輸產(chǎn)品不能存儲，多余的生產(chǎn)能力將浪費掉；如果生產(chǎn)能力小于運輸需求，那么將會有部分需求得不到滿足，導(dǎo)致需求溢出(Spilled Demand)，降低航空運輸系統(tǒng)的服務(wù)質(zhì)量，影響航空運輸系統(tǒng)的公眾形象，被溢出的旅客將轉(zhuǎn)向其他交通模式，因而進一步影響航空運輸系統(tǒng)的競爭能力。因此必須對航空運輸?shù)男枨笞龀鲱A(yù)測和評估，然后對生產(chǎn)能力做出科學(xué)的安排，這就是航空運輸規(guī)劃必須解決的問題。但航空運輸需求的影響因素復(fù)雜，需求波動嚴重，不能準(zhǔn)確預(yù)測。而且需求除了受需求發(fā)生地的社會、經(jīng)濟的因素影響外，還受到系統(tǒng)提供的生產(chǎn)能力的影響。生產(chǎn)能力不足，產(chǎn)生需求溢出，生產(chǎn)能力偏大，可能吸引其他運輸模式的運輸需求，因此需求不完全是外生變量。航空運輸規(guī)劃不但直接影響航空運輸系統(tǒng)運行的效率和安全，還是航空運輸系統(tǒng)競爭能力和決策水平的體現(xiàn)。各航空公司的飛行器和運行規(guī)范等都符合適航規(guī)定，服務(wù)產(chǎn)品幾乎是同質(zhì)的，創(chuàng)新的服務(wù)產(chǎn)品很容易摹仿。例如常旅客計劃，首先由美國航空公司推出，但很快傳播到其他航空公司。那么航空公司的核心競爭力體現(xiàn)在哪里呢？應(yīng)當(dāng)體現(xiàn)在運輸規(guī)劃的核心技術(shù)上，和掌握了這些核心技術(shù)的技術(shù)人員上。在先進的航空公司，Ramp。D小組主要的研究工作就是開發(fā)運輸規(guī)劃的核心技術(shù)，該小組的成員則是公司的寶貴財富。132 航空運輸規(guī)劃的分類航空運輸規(guī)劃可以有多種分類方法。根據(jù)規(guī)劃的層次分類，可以分為戰(zhàn)略規(guī)劃、戰(zhàn)術(shù)規(guī)劃和運行規(guī)劃。一般地”Planning”是戰(zhàn)略層次的，”Scheduling”是戰(zhàn)術(shù)層次到運行操作層次的規(guī)劃。根據(jù)子系統(tǒng)分類，可以分為航空公司子系統(tǒng)規(guī)劃、機場子系統(tǒng)規(guī)劃和空管子系統(tǒng)規(guī)劃。根據(jù)規(guī)劃內(nèi)容分類，可以分為航空交通基礎(chǔ)實施規(guī)劃、市場布點規(guī)劃、機隊規(guī)劃、空域規(guī)劃、人力資源規(guī)劃，信息系統(tǒng)規(guī)劃、生產(chǎn)規(guī)劃等。133 航空運輸規(guī)劃的內(nèi)容l 市場計劃、機隊規(guī)劃和航線網(wǎng)絡(luò)規(guī)劃，這些屬于航空公司的戰(zhàn)略層次。l 航班計劃、航材管理計劃、飛機維修計劃和排班、機組人員排班，這些是戰(zhàn)術(shù)層次的。l 收益管理、運行控制和地面服務(wù)人員排班等，這些是運行層次的規(guī)劃。第二章 航空運輸規(guī)劃基礎(chǔ)22 大規(guī)模整數(shù)規(guī)劃問題 整數(shù)規(guī)劃屬于組合優(yōu)化問題，由于它的NP難解性，在大學(xué)本科的運籌學(xué)課程中一般作為選修內(nèi)容，不做課堂講授。難解性引起的困難只有對大規(guī)模的優(yōu)化問題才凸現(xiàn)出來，甚至成為解決問題難以逾越的障礙，不得以放棄最優(yōu)解的獲得，退而求其次，用啟發(fā)式算法獲得次優(yōu)解或滿意解。航空運輸規(guī)劃所遇到的整數(shù)規(guī)劃問題幾乎全是大規(guī)模的，因此需要對其作專門介紹。本節(jié)介紹整數(shù)規(guī)劃的基本概念和基本問題，不涉及算法問題。算法將在第25節(jié)中專門介紹。221 一個例子和問題的提出 例21 某小型航空公司一周的航班計劃如表21所示，機組基地機場是A、C和D，現(xiàn)在要為該航空公司的機組人員排班。對于周一到周五每天都飛的航班，叫做日周期航班(Daily Flight)。為這樣的航班計劃進行機組人員排班時，首先生成可供選擇的航班環(huán)，其結(jié)果如表22所示。這里的航班環(huán)是指由同一個機組執(zhí)行的符合銜接條件的航班串，并且第一個航班的出發(fā)機場與最后一個航班的到達機場相同。這里的銜接條件至少有兩個：一個是后一個航班的出發(fā)機場與前一個航班的到達機場相同；另一個是后一個航班的出發(fā)時間大于前一個航班的到達時間，并且間隔大于規(guī)定的最小值。本例中我們要求在同一個航班環(huán)中，前后兩航班的銜接時間間隔不小于40分鐘。關(guān)于如何由航班時刻表生成航班環(huán)，請參見第八章。表21 某小航空公司的航班時刻表航班號出發(fā)時刻出發(fā)機場到達時刻到達機場頻率1108:00A9:00B1,2,3,4,512012:30C14:00D1,2,3,4,5,613015:00D16:00A1,2,3,4,5,712110:00B11:00C1,2,3,4,5,6,711217:00A18:20B1,2,3,4,5,6,712215:00C16:30A1,2,3,4,5,6,712311:00B12:15C1,2,3,4,5在表22中P1P4這四個航班環(huán)的周期是一天，P5P12這八個航班環(huán)的周期是兩天，P13的周期則是三天，沒有周期超過三天的航班環(huán)。對于周期是兩天的航班環(huán)，每天應(yīng)執(zhí)行兩個（兩架飛機來飛），三天周期的航班環(huán)每天需執(zhí)行三個，需要三架飛機來飛。表22 可選擇的航班環(huán)航班環(huán)第一天第二天第三天飛行小時基地機場P1110121120130重復(fù)重復(fù)AP2110123120130重復(fù)重復(fù)AP3110121122重復(fù)重復(fù)AP4110123122重復(fù)重復(fù)AP5112121120130重復(fù)第一天AP6112121122重復(fù)第一天AP7120130112121重復(fù)第一天CP8122112123重復(fù)第一天CP9120130112123重復(fù)第一天CP10122112121重復(fù)第一天CP11130110123120重復(fù)第一天DP12130110121120重復(fù)第一天DP13130112121120D 設(shè)決策變量，等于0表示不飛航班環(huán)Pi，等于1表示飛航班環(huán)Pi。如果根據(jù)航班環(huán)Pi的飛行小時計算出機組成本是，則表21的航班計劃的機組執(zhí)行總成本是我們希望這個總成本越小越好。對于每個航班，每天必須有一個航班環(huán)執(zhí)行，而且只能有一個航班環(huán)執(zhí)行。例如對于航班110，航班環(huán)PPPPP1P12都包含它，這些航班環(huán)只能執(zhí)行一個，不能同時都執(zhí)行，否則航班110將被執(zhí)行多次。因此對于其他航班，也有類似的約束條件，對于本問題一共有7個同類的約束條件。綜合上述討論，我們可以給出該機組航班環(huán)問題的規(guī)劃模型如下：這是一個01型整數(shù)規(guī)劃模型，目標(biāo)函數(shù)是機組飛行總成本最小，每個航班一個約束條件，表示每個航班能且只能執(zhí)行一次。這是一個集合分割問題，即將航班集合分割成若干子集合，任意航班屬于某一子集合，每兩兩子集合的交集為空，使分割的總代價最小。這里每個航班子集就是一個航班環(huán)。有時由于航班計劃在時間上的安排協(xié)調(diào)不夠，導(dǎo)致某些航班在當(dāng)?shù)貦C場沒有機組去執(zhí)行，這時上述模型無可行解。實踐中，常采用加機組（又叫空飛，Deadhead）的辦法，即從別的機場調(diào)機組跟隨某航班飛來本機場。如果允許機組空飛（加機組）,則約束條件的等號應(yīng)改為大于等于號，此時是集合覆蓋問題。集合分割問題和集合覆蓋問題是航空運輸規(guī)劃經(jīng)常遇見的數(shù)學(xué)模型，它們的一般描述是：集合分割問題：把一個含有n個元素的集合A分割成若干個子集合Ai，i=1,2,…,m，產(chǎn)生每個子集合Ai需要付出相應(yīng)的成本ci，現(xiàn)要求從這些子集合中選出若干個子集合，使得，并使分割這些子集合的總成本最小。集合分割問題可以用數(shù)學(xué)模型表述如下：(21)其中=0或1，是一個示性算子，即當(dāng)子集合Aj 含有元素i時為1，否則為0。是決策變量，等于1時表示Ai 被選中，等于0時表示不選擇Ai。上述模型的約束條件共有n個，每個元素一個，表示每個元素必須且只能包含在一個子集合中。集合覆蓋問題：如果在集合分割問題中，允許多個子集合包含同一個元素，即允許，則叫做集合覆蓋問題，它的數(shù)學(xué)模型是 上述的集合分割問題和集合覆蓋問題的決策變量是特殊的整數(shù)，因此它們是特殊的整數(shù)規(guī)劃。一般的整數(shù)規(guī)劃問題可以這樣定義：定義21 凡規(guī)定某些決策變量取整數(shù)值的數(shù)學(xué)規(guī)劃問題都叫做整數(shù)規(guī)劃問題。例如其中是的任意函數(shù)，是決策變量矢量，是約束條件的右手邊矢量。222 整數(shù)規(guī)劃的分類和可行解集 定義21告訴我們，只要某數(shù)學(xué)規(guī)劃問題的某些決策變量規(guī)定為整數(shù)，就是整數(shù)規(guī)劃。這就告訴我們，整數(shù)規(guī)劃中可以規(guī)定變量取0或1，也可以規(guī)定取其它整數(shù)值。有些整數(shù)規(guī)劃甚至允許某些決策變量取實數(shù)值，某