《航空運輸規(guī)劃學》

航空運輸規(guī)劃學

目錄

航空運輸規(guī)劃學...........................................1

第一章緒論..............................................1

1-1航空運輸系統(tǒng)概述.............................................1

1-2航空運輸營運要素.............................................2

1-2-1航空運輸計劃.......................................................2

1-2-2航空運輸組織.......................................................2

1-2-3航空運輸運行.......................................................3

1-3航空運輸規(guī)劃概述.............................................4

1-3-1航空運輸規(guī)劃定義和意義............................................4

1-3-2航空運輸規(guī)劃的分類.................................................4

1-3-3航空運輸規(guī)劃的內(nèi)容.................................................4

第二章航空運輸規(guī)劃基礎(chǔ)..................................5

2-2大規(guī)模整數(shù)規(guī)劃問題...........................................5

2-2-1一個例子和問題的提出..............................................5

2-2-2整數(shù)規(guī)劃的分類和可行解集..........................................8

2-3高級網(wǎng)絡(luò)流問題..............................................10

2-3-1約束最短路問題....................................................10

2-3-2多商品流問題......................................................11

第三章機場運行規(guī)劃.....................................14

3-1引言........................................................14

3-1-1機場生產(chǎn)組織......................................................14

3-1-2繁忙機場和航班延誤問題............................................15

3-1-3機場運行規(guī)劃及其意義.............................................16

3-2機場運行規(guī)劃基礎(chǔ)............................................17

3-2-1排隊網(wǎng)絡(luò)..........................................................17

3-2-2累計分布曲線......................................................18

3-2-3高峰小時的定義....................................................18

3-2-4機場服務(wù)質(zhì)量標準.................................................19

3-2-5動態(tài)排隊系統(tǒng)分析.................................................19

3-3航站樓運行規(guī)劃..............................................22

3-3-1旅客的進離港流程..................................................22

3-3-3旅客流程規(guī)劃......................................................25

3-3-4行李流程..........................................................32

3-4機場貨郵運行規(guī)劃............................................35

3-4-1機場貨站功能與規(guī)劃...............................................35

3-4-2國際進港貨郵業(yè)務(wù)流程及作業(yè)介紹...................................38

3-5樞紐機場運行規(guī)劃............................................40

3-5-1樞紐機場的運行特點...............................................40

3-5-2中轉(zhuǎn)旅客流程的規(guī)劃................................................40

3-5-3中轉(zhuǎn)行李流程規(guī)劃..................................................41

第四章市場計劃和機隊規(guī)劃..............................44

4-1引言........................................................44

4-2市場計劃....................................................45

4-2-1市場計劃概述......................................................45

4-2-2市場計劃的內(nèi)容....................................................46

4-2-3市場計劃書的編制方法.............................................49

4-3機隊規(guī)劃....................................................50

4-3-1機隊規(guī)劃概述......................................................50

4-3-2飛機選型的基本方法...............................................54

5-3-3機隊規(guī)劃方法......................................................57

第五章航線規(guī)劃.........................................63

5-1引言........................................................63

5-1-1航線及其航線網(wǎng)絡(luò)的重要性.........................................63

5-1-2影響航空公司航線結(jié)構(gòu)決策的主要因素..............................63

5-1-3航線網(wǎng)絡(luò)規(guī)劃問題..................................................64

5-1-4幾個概念..........................................................65

5-2航線網(wǎng)絡(luò)結(jié)構(gòu)模式及其比較....................................67

5-2-2城市對航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò)的比較分析..........................67

5-3航線網(wǎng)絡(luò)經(jīng)濟性分析..........................................69

5-3-1航空運輸網(wǎng)絡(luò)具有網(wǎng)絡(luò)經(jīng)濟效應(yīng)......................................69

5-3-2航空運輸業(yè)的規(guī)模經(jīng)濟性和范圍經(jīng)濟性..............................69

5-3-3樞紐航線網(wǎng)絡(luò)的規(guī)模經(jīng)濟性和范圍經(jīng)濟性分析........................71

5-3-4航線網(wǎng)絡(luò)結(jié)構(gòu)經(jīng)濟性比較簡例分析...................................72

7-4航線網(wǎng)絡(luò)優(yōu)化模型............................................76

7-4-1一般航線網(wǎng)絡(luò)的優(yōu)化模型............................................76

7-4-2樞紐航線網(wǎng)絡(luò)的優(yōu)化模型............................................78

第六章航班計劃.........................................81

-1引言.........................................................81

6-1-1航班計劃的定義....................................................81

6-L2航班計劃相關(guān)概念..................................................82

6-1-3航班計劃的影響因素...............................................83

6-1-4航班計劃的內(nèi)容....................................................84

6-2航班計劃編制流程............................................85

6-2-1航班計劃編制步驟..................................................85

6-3航班計劃的旅客需求特征分析..................................87

6-3-2航空旅客需求特征..................................................88

6-3-3關(guān)于航空旅客0-D流預(yù)測...........................................89

6-5航班頻率優(yōu)化...............................................89

6-5-1單航線航班頻率計算................................................89

則公司的生產(chǎn)效率較高,否則本公司在競爭中處于劣勢。

8-5-2單航線航班頻率優(yōu)化...............................................91

8-5-3多條航線航班頻率優(yōu)化.............................................92

6-6航班時刻優(yōu)化................................................94

第七章機組排班問題.....................................96

7-1引言........................................................96

7-1-1機組排班的基本概念...............................................96

7-1-2機組排班的目的和意義.............................................97

7-1-3機組排班研究內(nèi)容..................................................97

7-1-4機組排班的影響因素...............................................97

7-1-5本章相關(guān)專業(yè)術(shù)語.................................................98

7-2機組適航規(guī)定和機組排班管理..................................99

7-2-7CCAR61部和141部的有關(guān)規(guī)定......................................99

7-2-2機組排班實踐.....................................................102

第八章航空運輸收益管理................................104

8-1引言.......................................................104

8-1-2航空旅客市場細分和艙位等級......................................104

11-1-4收益管理系統(tǒng)簡介...............................................105

8-2航班旅客選擇和需求預(yù)測.....................................107

8-2-1旅客選擇行為分析.................................................107

8-2-2旅客訂座數(shù)據(jù)的采集和需求預(yù)測....................................109

8-3機票定價策略...............................................112

8-3-1機票定價方法.....................................................112

8-3-2機票價格彈性.....................................................113

8-3-3艙位劃分和機票定價策略..........................................114

8-4客運收益管理的艙位控制與超售控制...........................116

8-4-2嵌套法座位分配...................................................118

8-4-3航班靜態(tài)艙位控制.................................................119

第一章緒論

1-1航空運輸系統(tǒng)概述

航空運輸系統(tǒng)由航空公司子系統(tǒng)、機場子系統(tǒng)和空管子系統(tǒng)組成。

航空運輸系統(tǒng)的組成如圖1-1所示，系統(tǒng)的邊界是“機場陸路到達系統(tǒng)”，它有時也被

作為航空運輸系統(tǒng)的一部分進行處理。航空運輸系統(tǒng)作為社會系統(tǒng)的子系統(tǒng)，它的外部是社

會系統(tǒng)的其他部分和氣象等自然系統(tǒng)，系統(tǒng)的服務(wù)對象是運輸需求發(fā)生地（需求源）。

圖1-1航空運輸系統(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ì)量。

第1頁共125頁

機場公司和空中交通管理局則為航空公司提供生產(chǎn)保障服務(wù)，幫助和支持航空公司完成

運輸生產(chǎn)任務(wù)，因此航空公司在航空運輸系統(tǒng)內(nèi)部是機場和空管局的客戶。

1-2航空運輸營運要素

航空運輸?shù)某晒I運除了需要航空器、空勤人員、地勤人員和其它硬件資源以外，還需

要軟件要素的成功運用，包括航空運輸計劃、組織和運行，這軟件三要素前后相繼，又反饋

控制，形成航空運輸營運系統(tǒng)的閉合鏈。本節(jié)簡要介紹這三要素。

1-2-1航空運輸計劃

航空運輸計劃的主體是航空公司，航空公司將制定好的航班計劃提交給相關(guān)機場和空管

局，機場和空管局在此基礎(chǔ)上形成自己的航班計劃。但航空公司在設(shè)計航班計劃時必須與機

場當局和空管局溝通、協(xié)調(diào)，對新增的航班還須獲得他們的批準，才能最終形成自己的航班

計劃。

1-2-2航空運輸組織

有了運輸計劃，必須建立有效的運輸組織才能使運行有章可循，按程序流動。因此航空

運輸組織是完成運輸任務(wù)的流程、章程和法規(guī)。

機場是航空運輸活動的主要場所，圖1-2是機場子系統(tǒng)的進出港流程圖。機場陸路到達

系統(tǒng)由陸路交通系統(tǒng)和機場停車場、車站和道邊系統(tǒng)構(gòu)成，陸路交通系統(tǒng)可能是機場高速、

機場輕軌、機場地鐵。機場高速的交通工具可能是出租車、公交車、機場巴士、團隊客車和

私家車，公交車需要設(shè)立車站：出租車到達機場后只在航站樓前短暫停車，下客后即離開，

應(yīng)當為他們設(shè)置道邊系統(tǒng)；私家車和團隊車下客后一般需要停車，因此應(yīng)當為它們建設(shè)停車

場。為此應(yī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),

以方便旅客值機。

第2頁共125頁

圖1-2機場子系統(tǒng)旅客進出港作業(yè)流程

出發(fā)貨郵到達機場后首先在陸側(cè)進入貨站，對貨物進行分理、裝箱、打包、過磅、安檢

等服務(wù)，然后使用機場平板車進入停機坪裝機。到達貨郵到達機場后首先卸機，然后通過場

面運輸進入貨站，進行分理后，再通過機場陸路到達系統(tǒng)運輸?shù)阶罱K目的地。如果是國際出

發(fā)/到達貨郵，還必須通過海關(guān)和動植物檢驗后放行才能出/入關(guān)。中轉(zhuǎn)行李需要通過自動化

分揀設(shè)備或人工分揀，然后準確轉(zhuǎn)運到各出發(fā)飛機上。

1-2-3航空運輸運行

有了航空運輸計劃和運輸生產(chǎn)組織體系，接下來是航空運輸生產(chǎn)運行。

航空運輸運行包括航空公司運行、機場運行和空中交通管理三部分。航空公司的運行控

制中心是負責生產(chǎn)運行的控制部門，在這里集中了市場部門、機務(wù)部門、飛行和客艙部門、

地面服務(wù)部門的代表，以及航行情報、性能工程和飛行簽派的專家。運輸生產(chǎn)在這里組織實

施，生產(chǎn)狀態(tài)在這里進行監(jiān)控。生產(chǎn)發(fā)生一般性問題，由運控中心領(lǐng)導與有關(guān)部門代表協(xié)商

解決。這里還有公司的值班領(lǐng)導，生產(chǎn)運行一旦發(fā)生重大問題，由公司領(lǐng)導牽頭，各部門代

表會商解決，必要時須與機場監(jiān)控中心（指揮處）以及空管部門協(xié)商解決。

負責機場生產(chǎn)運行的部門是機場監(jiān)控中心（指揮處），其職責是調(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)，解決問題的部門。

空管部門根據(jù)航班計劃和跑道容量、空域容量等對空中交通流量進行管理，保障t機安

全有序飛行。管制區(qū)域通常分為塔臺管制區(qū)、近進管制區(qū)和區(qū)域管制，分別由塔臺管制員、

近進管制員和區(qū)域管制員管理。管制員主要和飛行員發(fā)生聯(lián)系，以實現(xiàn)指揮飛機飛行的目的,

必要時還會與航空公司運控中心、機場監(jiān)控中心進行聯(lián)系。根據(jù)自己管制的扇區(qū)容量和扇區(qū)

內(nèi)飛機流量情況，管制員決定飛機通過某定位點的順序以及同一航路上前后兩架飛機的間

隔，保障飛機的安全飛行。

第3頁共125頁

1-3航空運輸規(guī)劃概述

1-3-1航空運輸規(guī)劃定義和意義

如前所述，計劃是航空運輸生產(chǎn)的依據(jù)和出發(fā)點，而規(guī)劃則是為實現(xiàn)預(yù)定目標對未來的

行動做出的計劃。航空運輸規(guī)劃是為實現(xiàn)航空運輸系統(tǒng)的目標對系統(tǒng)的結(jié)構(gòu)、規(guī)模、作用、

反應(yīng)和市場等做出的計劃。航空運輸生產(chǎn)能力的安排應(yīng)當與運輸需求相適應(yīng)，或兩者應(yīng)當盡

可能保持平衡。如果生產(chǎn)能力大于運輸需求，則由于運輸產(chǎn)品不能存儲，多余的生產(chǎn)能力將

浪費掉；如果生產(chǎn)能力小于運輸需求，那么將會有部分需求得不到滿足，導致需求溢出

(SpilledDemand),降低航空運輸系統(tǒng)的服務(wù)質(zhì)量，影響航空運輸系統(tǒng)的公眾形象，被溢出

的旅客將轉(zhuǎn)向其他交通模式，因而進一步影響航空運輸系統(tǒng)的競爭能力。因此必須對航空運

輸?shù)男枨笞龀鲱A(yù)測和評估，然后對生產(chǎn)能力做出科學的安排，這就是航空運輸規(guī)劃必須解決

的問題。

但航空運輸需求的影響因素復(fù)雜，需求波動嚴重，不能準確預(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)當體現(xiàn)在運輸規(guī)劃的核

心技術(shù)上，和掌握了這些核心技術(shù)的技術(shù)人員上。在先進的航空公司，R&D小組主要的研

究工作就是開發(fā)運輸規(guī)劃的核心技術(shù)，該小組的成員則是公司的寶貴財富。

1-3-2航空運輸規(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ī)劃等。

1-3-3航空運輸規(guī)劃的內(nèi)容

?市場計戈I、機隊規(guī)劃和航線網(wǎng)絡(luò)規(guī)劃，這些屬于航空公司的戰(zhàn)略層次。

?航班計劃、航材管理計劃、飛機維修計劃和排班、機組人員排班，這些是戰(zhàn)術(shù)層次

的。

?收益管理、運行控制和地面服務(wù)人員排班等，這些是運行層次的規(guī)劃。

第4頁共125頁

第二章航空運輸規(guī)劃

基礎(chǔ)

2-2大規(guī)模整數(shù)規(guī)劃問題

整數(shù)規(guī)劃屬于組合優(yōu)化問題，由于它的NP難解性，在大學本科的運籌學課程中一般作

為選修內(nèi)容，不做課堂講授。難解性引起的困難只有對大規(guī)模的優(yōu)化問題才凸現(xiàn)出來，甚至

成為解決問題難以逾越的障礙，不得以放棄最優(yōu)解的獲得，退而求其次，用啟發(fā)式算法獲得

次優(yōu)解或滿意解。航空運輸規(guī)劃所遇到的整數(shù)規(guī)劃問題幾乎全是大規(guī)模的，因此需要對其作

專門介紹。本節(jié)介紹整數(shù)規(guī)劃的基本概念和基本問題，不涉及算法問題。算法將在第2-5

節(jié)中專門介紹。

2-2-1一個例子和問題的提出

例2-1某小型航空公司一周的航班計劃如表2T所示，機組基地機場是A、C和D,現(xiàn)

在要為該航空公司的機組人員排班。對于周一到周五每天都飛的航班，叫做日周期航班

(DailyFlight),為這樣的航班計劃進行機組人員排班時，首先生成可供選擇的航班環(huán)，其

結(jié)果如表2-2所示。這里的航班環(huán)是指山同一個機組執(zhí)行的符合銜接條件的航班串，并且第

一個航班的出發(fā)機場與最后一個航班的到達機場相同。這里的銜接條件至少有兩個：一個是

后一個航班的出發(fā)機場與前一個航班的到達機場相同；另一個是后一個航班的出發(fā)時間大于

前一個航班的到達時間，并且間隔大于規(guī)定的最小值。本例中我們要求在同一個航班環(huán)中，

前后兩航班的銜接時間間隔不小于40分鐘。關(guān)于如何山航班時刻表生成航班環(huán)，請參見第

八章。

表2T某小航空公司的航班時刻表

航班號出發(fā)時刻出發(fā)機場到達時刻到達機場頻率

1108:00A9:00B1,2,3,4,5

12012:30C14:00D1,2,3,4,5,6

13015:00D16:00A1,2,3,4,5,7

12110:00B11:00C1,2,3,4,5,6,7

11217:00A18:20B1,2,3,4,5,6,7

12215:00C16:30A1,2,3,4,5,6,7

12311:00B12:15C1,2,3,4,5

第5頁共125頁

在表2-2中P1-P4這四個航班環(huán)的周期是一天，P5-P12這八個航班環(huán)的周期是兩天，

P13的周期則是三天，沒有周期超過三天的航班環(huán)。對于周期是兩天的航班環(huán)，每天應(yīng)執(zhí)行

兩個（兩架飛機來飛），三天周期的航班環(huán)每天需執(zhí)行三個，需要三架飛機來飛。

表2-2可選擇的航班環(huán)

航班環(huán)第一天第二天第三天飛行小時基地機場

P1110-121-120-130重復(fù)重復(fù)4.5A

P2110-123-120-130重復(fù)重復(fù)4.25A

P3110-121-122重復(fù)重復(fù)3.5A

P4110-123-122重復(fù)重復(fù)3.75A

P5112121-120-130重復(fù)第一天4.83A

P6112121-122重復(fù)第一天3.83A

P7120-130-112121重復(fù)第一天4.83C

P8122-112123重復(fù)第一天4.08C

P9120-130-112123重復(fù)第一天5.08c

P10122-112121重復(fù)第一天3.83c

P11130110-123-120重復(fù)第一天4.75D

P12130110-121-120重復(fù)第一天4.5D

1204.33D

設(shè)決策變量七=0,1,等于。表示不飛航班環(huán)Pi,等于1表示飛航班環(huán)Pi。如果根據(jù)航

班環(huán)Pi的飛行小時計算出機組成本是G,則表2-1的航班計劃的機組執(zhí)行總成本是

我們希望這個總成本越小越好。

對于每個航班，每天必須有一個航班環(huán)執(zhí)行，而且只能有一個航班環(huán)執(zhí)行。例如對于航

班110,航班環(huán)Pl、P2、P3、P4、Pll、P12都包含它，這些航班環(huán)只能執(zhí)行一個，不能同

時都執(zhí)行，否則航班H0將被執(zhí)行多次。因此

X,+x2+x3+x4+X1]+xl2=1

對于其他航班，也有類似的約束條件，對于本問題一共有7個同類的約束條件。綜合上述討

論，我們可以給出該機組航班環(huán)問題的規(guī)劃模型如下：

第6頁共125頁

13

minz=

i=l

S.t.X]+%2+X3+X4++%12=1

X]+X3+X5+%6+X7+xio+尤[2+113=1

X]+冗2+x5+工7+X9+X]]+XJ2+X]3=1

/+乙+4+/+X10=1

x]+x2+x5+x7+X9+尤]]+x[2+x13=1

x5+x6+x7+x8+x9+x10+x]3=1

12+14+%8+%9+范1=1

xz-=0,1;/=1,2,…』3

這是一個OT型整數(shù)規(guī)劃模型，目標函數(shù)是機組飛行總成本最小，每個航班一個約束條

件，表示每個航班能且只能執(zhí)行一次。這是一個集合分割問題，即將航班集合分割成若干子

集合，任意航班屬于某一子集合，每兩兩子集合的交集為空，使分割的總代價最小。這里每

個航班子集就是一個航班環(huán)。有時由于航班計劃在時間上的安排協(xié)調(diào)不夠，導致某些航班在

當?shù)貦C場沒有機組去執(zhí)行，這時上述模型無可行解。實踐中，常采用加機組（又叫空飛，

Deadhead）的辦法，即從別的機場調(diào)機組跟隨某航班飛來本機場。如果允許機組空飛（加機

組），則約束條件的等號應(yīng)改為大于等于號，此時是集合覆蓋問題。

集合分割問題和集合覆蓋問題是航空運輸規(guī)劃經(jīng)常遇見的數(shù)學模型，它們的一般描述

是：

集合分割問題：把一個含有n個元素的集合A分割成若干個子集合A,,戶1,2,…,m,

產(chǎn)生每個子集合A需要付出相應(yīng)的成本G，現(xiàn)要求從這些子集合中選出若干個子集合，使

m

得4c4=RiH=1,2,…,〃2；UAj=A,并使分割這些子集合的總成本最小。

集合分割問題可以用數(shù)學模型表述’由下：

minz=ZGW

/=1

W（2-1）

s.t.=1,/=1,2,…,〃

片i

xi=0,1;z=

其中%=o或1,是一個示性算子，即當子集合可含有元素i時為1,否則為0。七是決策

變量，等于1時表示4被選中，等于0時表示不選擇4。上述模型的約束條件共有〃個，

每個元素一個，表示每個元素必須且只能包含在一個子集合中。

集合覆蓋問題：如果在集合分割問題中，允許多個子集合包含同一個元素，即允許

則叫做集合覆蓋問題，它的數(shù)學模型是

第7頁共125頁

minz=Z",

i=l

S.t.E%jXj2l,i=1,2,…,〃

;=i

Xj=0,1;z=1,2,…，m

卜.述的集合分割問題和集合覆蓋問題的決策變量是特殊的整數(shù)，因此它們是特殊的整數(shù)

規(guī)劃。一般的整數(shù)規(guī)劃問題可以這樣定義：

定義2-1凡規(guī)定某些決策變量取整數(shù)值的數(shù)學規(guī)劃問題都叫做整數(shù)規(guī)劃問題。

例如

minz=f(Xt,X2)

s.t.g(Xt,X2)>b

X「X2N0,X1取整數(shù)

其中￡g是XkX2的任意函數(shù)，X1,X2是決策變量矢量，匕是約束條件的右手邊矢量。

2-2-2整數(shù)規(guī)劃的分類和可行解集

定義2-1告訴我們，只要某數(shù)學規(guī)劃問題的某些決策變量規(guī)定為整數(shù)，就是整數(shù)規(guī)劃。

這就告訴我們，整數(shù)規(guī)劃中可以規(guī)定變量取?；?,也可以規(guī)定取其它整數(shù)值。有些整數(shù)規(guī)

劃甚至允許某些決策變量取實數(shù)值，某些取整數(shù)值。而且目標函數(shù)和約束條件的左邊可以是

線性的，也可以是非線性的。本小節(jié)首先對整數(shù)規(guī)劃進行分類。

一、根據(jù)決策變量的取值規(guī)定進行分類

1.0-1型整數(shù)規(guī)劃：有決策變量取0或1的整數(shù)規(guī)劃。如果全部決策變量都只取0或1,

則稱為純0-1型整數(shù)規(guī)劃，否則稱為混合0-1型整數(shù)規(guī)劃。

2、純整數(shù)規(guī)劃：所有的決策變量都取整數(shù)的整數(shù)規(guī)劃問題叫做純整數(shù)規(guī)劃問題。

3、混合整數(shù)規(guī)劃：有些變量取整數(shù)，有些變量取實數(shù)的規(guī)劃問題，叫做混合整數(shù)規(guī)劃。

二、根據(jù)目標函數(shù)、約束條件左邊是否為線性進行分類

1、線性整數(shù)規(guī)劃：目標函數(shù)和約束條件左邊全都是決策變量的線性函數(shù)的整數(shù)規(guī)劃叫

做線性整數(shù)規(guī)劃。

2、非線性整數(shù)規(guī)劃：目標函數(shù)或者某些約束條件左邊是決策變量的非線性函數(shù)的整數(shù)

規(guī)劃。

整數(shù)規(guī)劃各種類型和劃分標準可見表2-3所示。

表2-3整數(shù)規(guī)劃分類

類型線性整數(shù)規(guī)劃非線性整數(shù)規(guī)劃

X整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃

條件純整數(shù)規(guī)混合整數(shù)純整數(shù)規(guī)混合整數(shù)純整數(shù)規(guī)混合整數(shù)純整數(shù)規(guī)混合整數(shù)

劃規(guī)劃戈U規(guī)劃劃規(guī)劃劃規(guī)劃

第8頁共125頁

變量全部取整部分取整全部取整部分取整全部取整部分取整全部取整部分取整

數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)

目標函數(shù)和約束全部為。它性函數(shù)部分為非線性函數(shù)

條件

本章只討論線性整數(shù)規(guī)劃問題。線性整數(shù)規(guī)劃由于規(guī)定某些變量取整數(shù)值，大大地加大

了求解難度。如果放松整數(shù)約束，則線性整數(shù)規(guī)劃問題成為線性規(guī)劃問題，叫做整數(shù)規(guī)劃的

松弛線性規(guī)劃問題，簡稱為松弛線性規(guī)劃問題。如果是0-1型的整數(shù)規(guī)劃，整數(shù)約束巧=0,1

將松弛成04玉<1?

設(shè)松弛線性規(guī)劃問題的可行域是S,則對應(yīng)的整數(shù)規(guī)劃的可行域是S中整數(shù)點的集合。

例如如卜的整數(shù)規(guī)劃

maxz=7X]+5x2

s.t.24x(+1lx<88

2(2-2)

2X1+3X2<10

Xf,x2NO,整數(shù)

對應(yīng)的松弛線性規(guī)劃問題為

maxz=7X]+5x2

s.t.24x.+1lx<88

27(2-3)

2x,+3X2<10

xt,x2>0

線性規(guī)劃(2-3)的可行域S是圖2-1中的陰影部分構(gòu)成的凸集，而整數(shù)規(guī)劃的可行域是該

凸集中的整數(shù)點:{(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),

(3,0),(3,1)}。求整數(shù)規(guī)劃的最優(yōu)解即是在該可行域的整數(shù)點集中尋找使目標函數(shù)最優(yōu)的

點。點(3,1)即是(2-2)的最優(yōu)解。

第9頁共125頁

圖2-1線性規(guī)劃和整數(shù)規(guī)劃的可行域

2-3高級網(wǎng)絡(luò)流問題

我們在運籌學課程中已經(jīng)知道一些經(jīng)典的網(wǎng)絡(luò)優(yōu)化問題，例如最小支撐樹問題、最短路

問題、最大流問題和最小費用流問題。對于這些問題，已經(jīng)有了有效的多項式算法。但這些

經(jīng)典網(wǎng)絡(luò)優(yōu)化模型只能解決一些比較簡單的問題。例如最短路問題只考慮邊的長度，沒有考

慮路徑上其它因素的約束，如規(guī)定燃油的消耗量或規(guī)定允許的最長流動時間；最小費用流問

題假設(shè)網(wǎng)絡(luò)上流動的是同一種“商品”，而實際情況可能存在多種“商品”，而且假設(shè)單位流

的費用相同，不考慮網(wǎng)絡(luò)的建設(shè)投資等。因此實際問題比經(jīng)典的網(wǎng)絡(luò)流問題要復(fù)雜得多。本

節(jié)主要討論在航空運輸規(guī)劃中經(jīng)常遇到的網(wǎng)絡(luò)優(yōu)化高級問題:約束最短路問題和多商品流問

題。

2-3-1約束最短路問題

圖2-2是大家熟悉的最短路問題，其中節(jié)點以和珠分別是始發(fā)節(jié)點（源節(jié)點）和終止

節(jié)點（匯節(jié)點），圖中每邊上權(quán)重表示長度，要求從始發(fā)節(jié)點到終止節(jié)點的這樣一條路徑，

該路徑上各邊的權(quán)重之和最?。窂介L度最短）。在圖2-2中，節(jié)點到v8的最短路徑是

V|―?V7?V;------?1,6-------?Vg,最短路程是9。

圖2-2最短路問題

可見經(jīng)典的最短路問題只考慮網(wǎng)絡(luò)每邊的長度，可以用如下的數(shù)學模型來描述:

1,i-s

St=0,Otherwise

-1,i=t

x-.j=0,1

其中，%是邊GJ）的長度，勺是0-1型的決策變量（路徑選擇變量），邊（切）在最短路徑上

時=1,否則=0。該問題是一個易解問題，經(jīng)典的標號法是多項式的算法。

但在一些路徑最短問題中，不但要考慮選取最短（或成本最小的）路徑，而且沿某路徑

流動時存在資源消耗。例如根據(jù)機組適航性要求，每機組在24小時內(nèi)的飛行小時?般不得

第10頁共125頁

超過8小時，即所謂的8-in-24規(guī)則。此時，這8小時就成為機組航班環(huán)（配對，Pairing）

問題的有限資源。確定每個機組航班環(huán)是航班網(wǎng)絡(luò)中的約束最短路問題。再如，在考慮飛機

路線時，需要考慮飛機的飛行小時，一般要選擇日利用率在給定范圍內(nèi)的航班環(huán)作為飛機的

可行路線，因此飛機的飛行小時是飛機路線問題的有限資源。

,般地，約束最短路問題可以描述成如下的網(wǎng)絡(luò)流問題：網(wǎng)絡(luò)的每條邊（ij）的權(quán)重是一

對數(shù)（4叱叼），其中先是該邊的“長度”，為是在該邊流動時消耗的資源（可以有多個）。

要求網(wǎng)絡(luò)的始發(fā)節(jié)點到終止節(jié)點的一條滿足資源消耗約束的最短路經(jīng)。如圖2-3所示的網(wǎng)絡(luò)

中，從源s到匯，有5條路經(jīng)，最短路經(jīng)是：s―5—該路徑長度是9,消耗資源量13。

如果我們限制該流可消耗資源量最大為10,則約束最短路徑是：s—>1一2—>4—>3

該路徑的長度是1109）,但資源消耗量等于10,滿足資源約束條件。

圖2-3約束最短路問題

約束最短路問題的數(shù)學模型如下:

minz，Z4產(chǎn)(2-4a)

ieVjeV

(2-4b)

廠=0,Otherwise

jwadj(i)j:ieadj(j)—1,i—t

工工，/"<s(2-4c)

ieVjeV

Xjj=0,1

2-3-2多商品流問題

經(jīng)典的網(wǎng)絡(luò)流問題只涉及到一種“商品”（singlecommodity）,即在網(wǎng)絡(luò)上流動的只有

一種商品。請大家回顧一下單商品流的數(shù)學模型是什么樣子的。在最小費用流問題中，給定

了網(wǎng)絡(luò)的流量力以及每邊（燈）的容量％和單位流費用%要求網(wǎng)絡(luò)流”在網(wǎng)絡(luò)上的最小

第11頁共125頁

費用的分布模式，如圖2-4所示。

圖2-4最小費用流問題（網(wǎng)絡(luò)流b=7）

最小費用流問題的數(shù)學模型如式（2-5）所示。其中（2-5a）是目標函數(shù)，要求總費用

最小，（2-5b）是節(jié)點的流量平衡約束條件，每個節(jié)點具有一個這樣的約束條件，（2-5c）是邊

的容量約束條件，要求每條邊的流量不大于容量。

minz=ZZ與x。(2-5a)

ieVjeV

d,i=s

s.t.-=4°，Otherwise

(2-5b)

jwadj(i)j:iwadj(j)；.

-a,i=t

0<x..<u.；GjeV(2-5c)

生產(chǎn)實際上，我們常常碰見網(wǎng)絡(luò)上同時流動著多種“商品”的問題，例如在航線網(wǎng)絡(luò)上

同時流動著各種機型的飛機，一種機型的飛機就是一種“商品”，這樣的問題叫做多商品流

問題（multicommodityflowproblem）。下面我們來為多商品流問題建模。

假設(shè)在網(wǎng)絡(luò)上流動著K種商品，令k=l,2,...,K表示任意第k種商品，在任意邊（芍）

上，商品流存在容量限制，各種商品的單位流都是占有一個單位的容量，因此各種商品流之

和不能超過該邊的容量陶,第k種商品的網(wǎng)絡(luò)流量（總需求）為d”,在邊（辦）上的單位流

費用是耳，并進一步假設(shè)受到該種商品流容量力的限制。根據(jù)以上假設(shè)，多商品流問題的

數(shù)學模型是

第12頁共125頁

K

(2-6a)

k=\/eVjeV

dk,i=S

s.t.2*-2尤；=<°，Otherwise,k=1,2、…，K(2-6b)

-a,i=t

K(2-6c)

k=l

(2-6d)

0<x*<u^,i,jeV,k=\,2,-,K

可見，多商品流問題是最小費用流問題的直接推廣，其中（2-6a）是目標函數(shù)，要求總費

用最小，（2-6b）是對每種商品，每個節(jié)點都必須滿足的流平衡約束條件，（2-6d）是對每種商

品，每條邊都必須滿足的容量限制條件，（2-6c）表示每條邊上各種商品流之和不得大于該邊

的容量。如果網(wǎng)絡(luò)有n個節(jié)點，m條邊，那么對于每個商品，這個模型將有m個流變量，

因此共有Km個決策變量。而且模型共有Kn個節(jié)點的流守恒約束，m個邊的總?cè)萘考s束，

以及可能存在Km個各商品流的邊容量約束條件。

第13頁共125頁

第三章機場運行規(guī)劃

3-1引言

3-1-1機場生產(chǎn)組織

機場是組織航空運輸生產(chǎn)的重要場所。在這里，K機起飛、著陸、停放；旅客下機、領(lǐng)

取托運行李，辦理乘機手續(xù)、候機和登機以及轉(zhuǎn)機；到達的貨物在這里卸下和轉(zhuǎn)運，離港的

貨物在這里分理、打包、裝箱和裝機。這里一片繁忙景象，人來客往，車輛穿梭，如果沒有

高效的組織，很難想象這里的運輸生產(chǎn)可以有條不紊地進行。

機場分為陸側(cè)(Landside)和空側(cè)(Airside)兩部分。航站樓和地面到達系統(tǒng)組成陸側(cè)部分，

是旅客轉(zhuǎn)換交通模式的地方；跑道、滑行道和停機坪組成空側(cè)部分(也稱飛行區(qū))，是飛機

活動的場