《航空運(yùn)輸規(guī)劃學(xué)》

航空運(yùn)輸規(guī)劃學(xué)

目錄

航空運(yùn)輸規(guī)劃學(xué)...........................................1

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

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

1-2航空運(yùn)輸營(yíng)運(yùn)要素.............................................2

1-2-1航空運(yùn)輸計(jì)劃.......................................................2

1-2-2航空運(yùn)輸組織.......................................................2

1-2-3航空運(yùn)輸運(yùn)行.......................................................3

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

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

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

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

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

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

2-2-1一個(gè)例子和問題的提出..............................................5

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

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

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

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

第三章機(jī)場(chǎng)運(yùn)行規(guī)劃.....................................14

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

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

3-1-2繁忙機(jī)場(chǎng)和航班延誤問題............................................15

3-1-3機(jī)場(chǎng)運(yùn)行規(guī)劃及其意義.............................................16

3-2機(jī)場(chǎng)運(yùn)行規(guī)劃基礎(chǔ)............................................17

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

3-2-2累計(jì)分布曲線......................................................18

3-2-3高峰小時(shí)的定義....................................................18

3-2-4機(jī)場(chǎng)服務(wù)質(zhì)量標(biāo)準(zhǔn).................................................19

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

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

3-3-1旅客的進(jìn)離港流程..................................................22

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

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

3-4機(jī)場(chǎng)貨郵運(yùn)行規(guī)劃............................................35

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

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

3-5樞紐機(jī)場(chǎng)運(yùn)行規(guī)劃............................................40

3-5-1樞紐機(jī)場(chǎng)的運(yùn)行特點(diǎn)...............................................40

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

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

第四章市場(chǎng)計(jì)劃和機(jī)隊(duì)規(guī)劃..............................44

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

4-2市場(chǎng)計(jì)劃....................................................45

4-2-1市場(chǎng)計(jì)劃概述......................................................45

4-2-2市場(chǎng)計(jì)劃的內(nèi)容....................................................46

4-2-3市場(chǎng)計(jì)劃書的編制方法.............................................49

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

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

4-3-2飛機(jī)選型的基本方法...............................................54

5-3-3機(jī)隊(duì)規(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幾個(gè)概念..........................................................65

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

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

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

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

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

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

5-3-4航線網(wǎng)絡(luò)結(jié)構(gòu)經(jīng)濟(jì)性比較簡(jiǎn)例分析...................................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

第六章航班計(jì)劃.........................................81

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

6-1-1航班計(jì)劃的定義....................................................81

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

6-1-3航班計(jì)劃的影響因素...............................................83

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

6-2航班計(jì)劃編制流程............................................85

6-2-1航班計(jì)劃編制步驟..................................................85

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

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

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

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

6-5-1單航線航班頻率計(jì)算................................................89

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

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

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

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

第七章機(jī)組排班問題.....................................96

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

7-1-1機(jī)組排班的基本概念...............................................96

7-1-2機(jī)組排班的目的和意義.............................................97

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

7-1-4機(jī)組排班的影響因素...............................................97

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

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

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

7-2-2機(jī)組排班實(shí)踐.....................................................102

第八章航空運(yùn)輸收益管理................................104

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

8-1-2航空旅客市場(chǎng)細(xì)分和艙位等級(jí)......................................104

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

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

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

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

8-3機(jī)票定價(jià)策略...............................................112

8-3-1機(jī)票定價(jià)方法.....................................................112

8-3-2機(jī)票價(jià)格彈性.....................................................113

8-3-3艙位劃分和機(jī)票定價(jià)策略..........................................114

8-4客運(yùn)收益管理的艙位控制與超售控制...........................116

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

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

第一章緒論

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

航空運(yùn)輸系統(tǒng)由航空公司子系統(tǒng)、機(jī)場(chǎng)子系統(tǒng)和空管子系統(tǒng)組成。

航空運(yùn)輸系統(tǒng)的組成如圖1-1所示，系統(tǒng)的邊界是“機(jī)場(chǎng)陸路到達(dá)系統(tǒng)”，它有時(shí)也被

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

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

圖1-1航空運(yùn)輸系統(tǒng)

航空公司是運(yùn)輸生產(chǎn)的主體，是航空運(yùn)輸系統(tǒng)直接面對(duì)旅客或貨主的最主要部分，旅客

的不滿幾乎全部撒向航空公司，即使延誤是由惡劣天氣或飛機(jī)流量管理造成的，也會(huì)造成旅

客對(duì)航空公司的抱怨。

旅客通過與航空公司接觸的界面感受航空公司的服務(wù)質(zhì)量，包括機(jī)票銷售、航站樓服務(wù)

和機(jī)上服務(wù)等，但航空公司的服務(wù)質(zhì)量取決于服務(wù)鏈上的每個(gè)環(huán)節(jié)，從機(jī)隊(duì)規(guī)劃（機(jī)型的選

擇）、航線規(guī)劃、航班計(jì)劃、機(jī)務(wù)維修到運(yùn)行控制，甚至為旅客服務(wù)的信息系統(tǒng)，處處都體

現(xiàn)出航空公司的服務(wù)水平和服務(wù)質(zhì)量。

第1頁共125頁

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

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

1-2航空運(yùn)輸營(yíng)運(yùn)要素

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

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

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

1-2-1航空運(yùn)輸計(jì)劃

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

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

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

計(jì)劃。

1-2-2航空運(yùn)輸組織

有了運(yùn)輸計(jì)劃，必須建立有效的運(yùn)輸組織才能使運(yùn)行有章可循，按程序流動(dòng)。因此航空

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

機(jī)場(chǎng)是航空運(yùn)輸活動(dòng)的主要場(chǎng)所，圖1-2是機(jī)場(chǎng)子系統(tǒng)的進(jìn)出港流程圖。機(jī)場(chǎng)陸路到達(dá)

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

機(jī)場(chǎng)輕軌、機(jī)場(chǎng)地鐵。機(jī)場(chǎng)高速的交通工具可能是出租車、公交車、機(jī)場(chǎng)巴士、團(tuán)隊(duì)客車和

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

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

場(chǎng)。為此應(yīng)當(dāng)對(duì)機(jī)場(chǎng)高速的車輛結(jié)構(gòu)和數(shù)量進(jìn)行調(diào)研、預(yù)測(cè)和評(píng)估，為規(guī)劃停車場(chǎng)面積、道

邊長(zhǎng)度和寬度以及公交車車站提供依據(jù)。

對(duì)于出發(fā)旅客，機(jī)場(chǎng)陸側(cè)指從值機(jī)大廳入口到登機(jī)口（又叫閘口）的部分，其間提供的

服務(wù)有值機(jī)、安檢、候機(jī)、登機(jī)等，對(duì)于國(guó)際旅客還必須提供海關(guān)、邊防檢查等服務(wù)；對(duì)于

到達(dá)旅客，機(jī)場(chǎng)陸側(cè)指從旅客到達(dá)入口到迎客廳出口的部分，其間提供的服務(wù)主要是行李認(rèn)

領(lǐng)和迎客，對(duì)于國(guó)際到達(dá)旅客，還提供邊防、海關(guān)和動(dòng)植物檢驗(yàn)等服務(wù)：對(duì)于中轉(zhuǎn)的旅客，

是指航站樓中辦理換取登機(jī)牌和提供中轉(zhuǎn)候機(jī)服務(wù)的部分。有些陸側(cè)的服務(wù)（主要是值機(jī)）

可以前移至城市航站樓、火車站、機(jī)場(chǎng)到達(dá)交通工具上，以方便旅客，因此也可將陸路交通

系統(tǒng)歸入機(jī)場(chǎng)陸側(cè)系統(tǒng)?，F(xiàn)在也有網(wǎng)上值機(jī)系統(tǒng)，在航站樓值機(jī)大廳還設(shè)有自助式值機(jī)系統(tǒng),

以方便旅客值機(jī)。

第2頁共125頁

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

出發(fā)貨郵到達(dá)機(jī)場(chǎng)后首先在陸側(cè)進(jìn)入貨站，對(duì)貨物進(jìn)行分理、裝箱、打包、過磅、安檢

等服務(wù)，然后使用機(jī)場(chǎng)平板車進(jìn)入停機(jī)坪裝機(jī)。到達(dá)貨郵到達(dá)機(jī)場(chǎng)后首先卸機(jī)，然后通過場(chǎng)

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

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

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

1-2-3航空運(yùn)輸運(yùn)行

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

航空運(yùn)輸運(yùn)行包括航空公司運(yùn)行、機(jī)場(chǎng)運(yùn)行和空中交通管理三部分。航空公司的運(yùn)行控

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

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

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

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

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

負(fù)責(zé)機(jī)場(chǎng)生產(chǎn)運(yùn)行的部門是機(jī)場(chǎng)監(jiān)控中心（指揮處），其職責(zé)是調(diào)配機(jī)場(chǎng)的生產(chǎn)資源，

保障機(jī)場(chǎng)正常和安全生產(chǎn)。這里集中著最先進(jìn)的監(jiān)控設(shè)備和生產(chǎn)管理信息系統(tǒng)、服務(wù)信息系

統(tǒng)，生產(chǎn)現(xiàn)場(chǎng)的情形在這里一目了然，監(jiān)控人員隨時(shí)可以和生產(chǎn)部門進(jìn)行聯(lián)系，解決發(fā)生的

問題。這里也是機(jī)場(chǎng)與航空公司和空管部門進(jìn)行協(xié)調(diào)，解決問題的部門。

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

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

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

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

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

隔，保障飛機(jī)的安全飛行。

第3頁共125頁

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

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

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

行動(dòng)做出的計(jì)劃。航空運(yùn)輸規(guī)劃是為實(shí)現(xiàn)航空運(yùn)輸系統(tǒng)的目標(biāo)對(duì)系統(tǒng)的結(jié)構(gòu)、規(guī)模、作用、

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

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

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

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

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

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

的問題。

但航空運(yùn)輸需求的影響因素復(fù)雜，需求波動(dòng)嚴(yán)重，不能準(zhǔn)確預(yù)測(cè)。而且需求除了受需求

發(fā)生地的社會(huì)、經(jīng)濟(jì)的因素影響外，還受到系統(tǒng)提供的生產(chǎn)能力的影響。生產(chǎn)能力不足，產(chǎn)

生需求溢出，生產(chǎn)能力偏大，可能吸引其他運(yùn)輸模式的運(yùn)輸需求，因此需求不完全是外生變

量。

航空運(yùn)輸規(guī)劃不但直接影響航空運(yùn)輸系統(tǒng)運(yùn)行的效率和安全，還是航空運(yùn)輸系統(tǒng)競(jìng)爭(zhēng)能

力和決策水平的體現(xiàn)。各航空公司的飛行器和運(yùn)行規(guī)范等都符合適航規(guī)定，服務(wù)產(chǎn)品幾乎是

同質(zhì)的，創(chuàng)新的服務(wù)產(chǎn)品很容易摹仿。例如常旅客計(jì)劃，首先由美國(guó)航空公司推出，但很快

傳播到其他航空公司。那么航空公司的核心競(jìng)爭(zhēng)力體現(xiàn)在哪里呢？應(yīng)當(dāng)體現(xiàn)在運(yùn)輸規(guī)劃的核

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

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

1-3-2航空運(yùn)輸規(guī)劃的分類

航空運(yùn)輸規(guī)劃可以有多種分類方法。根據(jù)規(guī)劃的層次分類，可以分為戰(zhàn)略規(guī)劃、戰(zhàn)術(shù)規(guī)

劃和運(yùn)行規(guī)劃。一般地"Planning”是戰(zhàn)略層次的，”Scheduling”是戰(zhàn)術(shù)層次到運(yùn)行操作層次的

規(guī)劃。

根據(jù)子系統(tǒng)分類，可以分為航空公司子系統(tǒng)規(guī)劃、機(jī)場(chǎng)子系統(tǒng)規(guī)劃和空管子系統(tǒng)規(guī)劃。

根據(jù)規(guī)劃內(nèi)容分類，可以分為航空交通基礎(chǔ)實(shí)施規(guī)劃、市場(chǎng)布點(diǎn)規(guī)劃、機(jī)隊(duì)規(guī)劃、空域

規(guī)劃、人力資源規(guī)劃，信息系統(tǒng)規(guī)劃、生產(chǎn)規(guī)劃等。

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

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

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

的。

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

第4頁共125頁

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

基礎(chǔ)

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

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

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

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

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

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

節(jié)中專門介紹。

2-2-1一個(gè)例子和問題的提出

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

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

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

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

一個(gè)航班的出發(fā)機(jī)場(chǎng)與最后一個(gè)航班的到達(dá)機(jī)場(chǎng)相同。這里的銜接條件至少有兩個(gè)：一個(gè)是

后一個(gè)航班的出發(fā)機(jī)場(chǎng)與前一個(gè)航班的到達(dá)機(jī)場(chǎng)相同；另一個(gè)是后一個(gè)航班的出發(fā)時(shí)間大于

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

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

八章。

表2T某小航空公司的航班時(shí)刻表

航班號(hào)出發(fā)時(shí)刻出發(fā)機(jī)場(chǎng)到達(dá)時(shí)刻到達(dá)機(jī)場(chǎng)頻率

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這四個(gè)航班環(huán)的周期是一天，P5-P12這八個(gè)航班環(huán)的周期是兩天，

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

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

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

航班環(huán)第一天第二天第三天飛行小時(shí)基地機(jī)場(chǎng)

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的飛行小時(shí)計(jì)算出機(jī)組成本是G,則表2-1的航班計(jì)劃的機(jī)組執(zhí)行總成本是

我們希望這個(gè)總成本越小越好。

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

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

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

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

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

論，我們可以給出該機(jī)組航班環(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

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

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

集合，任意航班屬于某一子集合，每?jī)蓛勺蛹系慕患癁榭?，使分割的總代價(jià)最小。這里每

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

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

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

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

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

是：

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

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

m

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

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

minz=ZGW

/=1

W（2-1）

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

片i

xi=0,1;z=

其中%=o或1,是一個(gè)示性算子，即當(dāng)子集合可含有元素i時(shí)為1,否則為0。七是決策

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

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

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

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

第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ù)學(xué)規(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ù)學(xué)規(guī)劃問題的某些決策變量規(guī)定為整數(shù)，就是整數(shù)規(guī)劃。

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

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

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

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

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í)數(shù)的規(guī)劃問題，叫做混合整數(shù)規(guī)劃。

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

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

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

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

規(guī)劃。

整數(shù)規(guī)劃各種類型和劃分標(biāo)準(zhǔn)可見表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ù)

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

條件

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

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

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

將松弛成04玉<1?

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

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

maxz=7X]+5x2

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

2(2-2)

2X1+3X2<10

Xf,x2NO,整數(shù)

對(duì)應(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ù)點(diǎn):{(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ù)點(diǎn)集中尋找使目標(biāo)函數(shù)最優(yōu)的

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

第9頁共125頁

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

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

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

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

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

慮路徑上其它因素的約束，如規(guī)定燃油的消耗量或規(guī)定允許的最長(zhǎng)流動(dòng)時(shí)間；最小費(fèi)用流問

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

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

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

題。

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

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

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

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

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

圖2-2最短路問題

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

1,i-s

St=0,Otherwise

-1,i=t

x-.j=0,1

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

時(shí)=1,否則=0。該問題是一個(gè)易解問題，經(jīng)典的標(biāo)號(hào)法是多項(xiàng)式的算法。

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

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

第10頁共125頁

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

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

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

可行路線，因此飛機(jī)的飛行小時(shí)是飛機(jī)路線問題的有限資源。

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

對(duì)數(shù)（4叱叼），其中先是該邊的“長(zhǎng)度”，為是在該邊流動(dòng)時(shí)消耗的資源（可以有多個(gè)）。

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

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

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

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

圖2-3約束最短路問題

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

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ò)上流動(dòng)的只有

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

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

第11頁共125頁

費(fèi)用的分布模式，如圖2-4所示。

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

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

最小，（2-5b）是節(jié)點(diǎn)的流量平衡約束條件，每個(gè)節(jié)點(diǎn)具有一個(gè)這樣的約束條件，（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)實(shí)際上，我們常常碰見網(wǎng)絡(luò)上同時(shí)流動(dòng)著多種“商品”的問題，例如在航線網(wǎng)絡(luò)上

同時(shí)流動(dòng)著各種機(jī)型的飛機(jī)，一種機(jī)型的飛機(jī)就是一種“商品”，這樣的問題叫做多商品流

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

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

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

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

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

數(shù)學(xué)模型是

第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

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

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

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

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

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

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

第13頁共125頁

第三章機(jī)場(chǎng)運(yùn)行規(guī)劃

3-1引言

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

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

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

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

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

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

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

活動(dòng)的場(chǎng)