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