基于Gecode的飛機排班問題的研究

摘要：隨著航空運輸需求的增大，各個航空公司擁有的飛機數(shù)量不斷增加，飛機排班的重要性日益突出。飛機排班是航空運輸?shù)闹匾鴱?fù)雜的環(huán)節(jié)，直接影響到航空公司的經(jīng)濟效益。飛機排班問題通常被看作整數(shù)規(guī)劃問題，其模型是一個NP-hard問題。本文利用約束編程的理論為飛機排班問題建立一個適用于Gecode編程平臺的模型，并利用Gecode平臺產(chǎn)生各航班串的簡單成本。最后利用實際案例進行了模型驗證以及平臺有效性驗證，并且和國內(nèi)其他研究作比較研究。

關(guān)鍵詞：航班；約束編程；Gecode

中圖分類號：V355 文獻標(biāo)識碼：A 文章編號：1007-9599 （2012） 24-0016-03

1 引言

飛機是航空公司的重要盈利工具，直接關(guān)系到航空公司的經(jīng)濟效益。飛機排班問題實際上是一個組合優(yōu)化問題，在研究中，通常被歸類于嚴(yán)重退化的NP-hard問題。

飛機排班問題在國內(nèi)外都有豐富的研究，尤其以國外研究成果最多，國內(nèi)研究成果稍顯遜色。在歐美.比較有代表性的研究有：MarkS.Daskin 建立了一個適應(yīng)歐洲各個航空運輸公司大多采用的單個樞紐航線特征的FAM整數(shù)規(guī)劃模型，并利用Lagrangican松弛算法得到最大航班收益值[1]。Hance.A進一步擴大求解的規(guī)模，通過求解大規(guī)模整數(shù)規(guī)劃問題，提出了一種通用的航班機隊分配問題[2]。L.w.Clarke基于Hance的成果，對數(shù)學(xué)模型進行了完善，首次引入了飛機的維修計劃以及機組排班等因子，使得模型更加的貼近現(xiàn)實的要求[3][4]，Clarke把飛機排班問題轉(zhuǎn)化為安排飛機維護路徑的問題，并且將該路徑問題轉(zhuǎn)化成帶有邊約束的旅行商問題（TSP）。Brian首先引入了航班時間窗機制，優(yōu)化了航班的機型分配，并且提供了有效的優(yōu)化分析工具[5]。Talluri和Gopalan等利用圖論對飛機排班問題進行了深入的探討，并且試圖找到K天的飛機維護路線圖，最終，得到了4天以上飛機維護問題的算法復(fù)雜性以及存在可行解的條件，并且構(gòu)造了一種“4-MET”問題的啟發(fā)式算法[6]。Barbhart等人建立了基于類生成法的機型指派與飛機的多商品網(wǎng)絡(luò)流模型[7]。

從國內(nèi)看，比較著名的研究有：孫宏的基于調(diào)度指令要求、基于最少需用飛機數(shù)、基于飛機使用均衡要求的飛機排班問題及求解算法[8]；李耀華等主要考慮航站銜接及過站時間要求，建立航班串的優(yōu)化模型，并構(gòu)造了一種自適應(yīng)遺傳算法[9]。

目前的成果仍然存在著一些問題，主要體現(xiàn)在以下幾個方面：首先，這些研究建立的模型，大都有這苛刻的限制。其次，無論國內(nèi)外的研究大都從具體的市場需求出發(fā)，建立的模型都只能適應(yīng)特殊的應(yīng)用環(huán)境。

本文分析了國內(nèi)外的研究成果，結(jié)合國內(nèi)實際，運用約束編程相關(guān)概念，提出了基于Gecode的解決航班排班問題的約束編程模型，并且生成了航班串。

約束編程是一種起源于人工智能技術(shù)，結(jié)合邏輯推理的通用搜索技術(shù)[10]。在該理論下，我們可以把問題抽象描述成約束滿足問題，通過約束傳播和搜索，不斷約減搜索域和變量個數(shù)[11]，最終得到問題的解決（或者得到無解的結(jié)論）。約束問題求解器系統(tǒng)主要有Gecode、CHIP、Prolog、ECLiPSe、ILOG Solver等[12]，本文主要應(yīng)用Gecode來求解。Gecode是一個可移植的、高效的約束編程環(huán)境[13]。

本文具體將采用最小消耗的分支界定（branch-and-bo und， BAB）算法進行解空間樹的搜索。分支定界算法[14]采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。如果要查找一個具有最小耗費的解，那么要選擇的下一個擴展結(jié)點就是活結(jié)點表中具有最小耗費的活結(jié)點[15]。

2 問題建模

本文以時間和空間為線索，以最小成本為目標(biāo)，以航班信息和機型信息為基礎(chǔ)來構(gòu)建在Gecode上可實現(xiàn)的約束編程模型。

2.1 問題描述及符號定義

本文在航班信息和機型信息的基礎(chǔ)上建立一個簡約模型。各個航空公司都有多種不同的機型，機型有沒有能力執(zhí)行一個航班是問題的最大前提，因此，機型信息顯得尤其重要。把一個航空公司的所有機型信息用集合K表示，機型k∈K。每種機型信息的主要參數(shù)如表1所示：

表1 機型信息參數(shù)

參數(shù)名稱飛機數(shù)量座位數(shù)基地小時成本最小過站時間

符號表示k_numberk_seatk_baseportk_hour_costk_mix_stop_time

我們用F表示航班信息集合，航班f∈F，航班信息主要參數(shù)如表2所示：

表2 航班信息參數(shù)

參數(shù)名稱出發(fā)時間到達時間出發(fā)機場到達機場平均票價預(yù)測旅客量

符號表示f_dep_timef_arr_timef_dep_portf_arr_portf_pricef_travel

航班排班問題最終的結(jié)果是要得到一系列航班串。航班串指一架飛機執(zhí)行的航班集合。我們用S表示航班串集合。地面弧指一段時間內(nèi)飛機在地面停留。每架飛機都有一個或者多個基地，通常要求飛機執(zhí)行的第一個航班的出發(fā)機場是飛機的基地。飛機執(zhí)行的最后一個航班的到達機場也必須是該飛機的基地。航班串s∈S， 表示以飛機f開頭的航班串； 表示以飛機f結(jié)束的航班串，start_s表示航班串的首航班，end_s表示航班串的尾航班。

與盈利相對的對偶變量可以解釋為在可預(yù)知客流和有限資源的前提下，使運營成本最低。因此，本文以最小成本為目標(biāo)，機型k執(zhí)行一個航班串s的成本表示為 ，其簡單計算方式是機型k的小時成本乘以總飛行小時數(shù)。如果一架飛機沒有執(zhí)行航班任務(wù)，我們說飛機正在通過時間線的地面弧，用符號 來表示航班通過時間線的地面弧集合。這里，使用 表示飛機k執(zhí)行的航班串s通過時間線的次數(shù)；用 來統(tǒng)計機型k通過地面弧j的數(shù)量。這里我們使用一些布爾變量來標(biāo)識每架飛機的狀態(tài)。用 標(biāo)識機型k是否通過地面弧j，如果通過則為1，否則為0；用 標(biāo)識航班串s是否由機型k執(zhí)行，如果是則為1，否則為0。同時，也需要對航班進行標(biāo)識， 標(biāo)識航班f是否包含在航班串s中，如果是則為1，，否則為0。

機型k被選中執(zhí)行航班串s事件發(fā)生時以及執(zhí)飛完成時，需要事件發(fā)生前后飛機執(zhí)飛數(shù)量的變化對 狀態(tài)進行更新。我們把事件發(fā)生之前（后）所有飛機都未改變狀態(tài)的一段時間內(nèi)發(fā)生的任意事件稱為該事件的緊前（后）事件。把地面弧變量 （ ）用來統(tǒng)計機型k在航班f到達（離港）時和緊前事件之間的飛機數(shù)； （ ）用來統(tǒng)計機型k在航班f到達（離港）時和緊后事件之間的飛機s數(shù)。其中 分別表示機型k執(zhí)飛的航班f的到達、離港事件， 和 分別表示對應(yīng)的緊前和緊后事件。

另外，MAX_N表示飛機的日起降次數(shù)的上限；MAX_T表示飛機每天最多飛行的時間；集合B表示飛機的基地機場的集合，有k_baseport∈B。

2.2 問題建模

通過上面的描述，可以把模型建立為：

目標(biāo)函數(shù)約束：

min total_cost= （1）

約束：

航班執(zhí)飛唯一性約束：

=1，?f∈F（2）

飛機數(shù)量架數(shù)約束：

+ k_number，?k∈K（3）

航班流中飛機數(shù)量：

= - （4）

= - （5）

時空約束，即后一個航班的出發(fā)機場等于前一個航班的到達機場，兩個航班之間的時間差要大于最小過站時間：{f1.f_arr_port=f2.f_dep_port f2.f_dep_time-f1.f_arr_ time k_mix_stop_time}，

?f1，f2∈F，f1

通常飛機執(zhí)飛航班應(yīng)該滿足首（尾）航班的出發(fā)（到達）機場應(yīng)為飛機的基地機場：{start_s. f_dep_port∈k_b aseport end_s. f_arr_port∈k_baseport | =1}

?k∈K ?s∈S （7）

飛機執(zhí)飛次數(shù)約束：

MAX_N，?k∈K ?s∈S （8）

飛機執(zhí)飛總時間約束：

MAX_T，?s∈S （9）

變量約束：

的整數(shù)，?j∈ ，?k∈K （10）

?k∈K，?s∈S （11）

2.3 Gecode實現(xiàn)

對于整型變量，Gecode實現(xiàn)了大于、等于、小于、包含、值域、唯一、不為空等常見的約束。由于篇幅的關(guān)系，本文不列舉所有代碼，只列舉部分語句作為解釋說明。

（1）建立飛機機型類和航班信息類，作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。

（2）建立flightSchedule類。該類繼承自Gecode命名空間的Space類。使用兩個數(shù)組：航班信息數(shù)組和機型信息數(shù)組作為輸入。

在該類中，首先，把上面模型中的約束用Gecode的方式編寫。這其中有各種關(guān)系約束、包含約束以及線性表達式等。為了得到最小成本的排班序列，式（1）可表示為：linear（*this，c，x，IRT_LE，total_cost）；這樣，結(jié)合BAB搜索算法，最后得到的序列將是成本最小的序列。

然后，注冊選擇器。選擇器將決定搜索樹的范圍和搜索次序。航班信息表的搜索次序可以表示為：branch（*this，flightInfo，INT_VAR_NONE，INT_VAL_MIN）；意為把flightInfo作為一個搜索空間，按變量順序搜索，該變量的最小值首先參與計算。

（3）建立搜索引擎計算結(jié)果，打印最小成本的航班串以及成本。

3 案例分析

我們以國內(nèi)某航空公司的運營數(shù)據(jù)為案例，分析實驗的結(jié)果。該航空公司有飛機44架，5個機型，每天運營48個機場的232個航班。機型信息如表3所示[8]。

表3 機型信息表

機型型1型2型3型4型5

飛機數(shù)量（架）1201264

基地數(shù)量（個）13211

座位（個）121148164184284

小時成本（萬元）2.83.44.14.76.2

最小過站時間（分）4040404545

最大日飛行時間（時）1212121212

由于航班數(shù)量太多，本文不作詳細列舉，只列舉其中3個作為示例。航班信息如表4所示。平均票價由航班收益除以旅客數(shù)量，預(yù)計旅客量由歷史數(shù)據(jù)預(yù)測獲得。

表4 航班信息示例表

航班號出發(fā)機場到達機場出發(fā)

時間到達

時間平均

票價預(yù)計旅客量

F1A1A29：0011：00600160

F2A3A420：0023：00800180

為了驗證本文中設(shè)計的模型，我們進行了多組不同規(guī)模的實驗，實驗結(jié)果如表5所示。實驗環(huán)境：CPU：Intel T5870*2 2.0GH；內(nèi)存：2GB； 系統(tǒng)：windows 7。在表5中，實際成本以航空公司歷史運營記錄統(tǒng)計得到。可以看出，表中實驗成本在飛機架數(shù)達到一定規(guī)模的時候，運營成本較實際成本有優(yōu)化，根據(jù)表中的數(shù)據(jù)，該航空公司一天可以節(jié)約成本（1525.26-1469.92=55.34）萬元，一年可以節(jié)約成本20199.1萬元。因此，本文設(shè)計的模型是有效的，能夠在有限時間內(nèi)計算出各個航班串的簡單成本。從計算時間上看，計算該航空公司所有航班的時間僅需31.12秒，比文獻[7]中的計算同等規(guī)模的問題需要以小時計的時間提高了兩個數(shù)量級。

表5 實驗結(jié)果

計算信息實際成本

（萬元）實驗成本

（萬元）計算時間

（秒）

問題飛機

數(shù)量航班數(shù)機場數(shù)

1282142.08142.080.52

2105417387.15387.153.21

32011237931.51922.0210.87

444232481525.261469.9231.12

4 結(jié)論

實驗證明，本文以時間和空間為線索，以最小成本為目標(biāo)，以航班信息和機型信息為基礎(chǔ)構(gòu)建的在Gecode上可實現(xiàn)的約束編程模型是有效的。在問題規(guī)模不斷擴大的情況下，可以在較短的時間內(nèi)計算出航班串的簡單成本。并且引入約束編程的概念以及通過Gecode平臺的編程實現(xiàn)，航空公司的成本有一定的優(yōu)化，這對提高航空公司的整體經(jīng)濟效益有著重要的意義。

本文從航班信息和機型信息為出發(fā)點建立了一個可用于Gecode平臺的編程模型，但是，影響飛機排班的因素很多，比如機組成員信息、天氣、航空管制等，這些因素都會影響到飛機排班的結(jié)果。把這些因素引入到模型中，是未來要完善的工作。另外，本文只考慮了一天的飛機排版問題，未來的工作中，建立一個符合航空公司實際調(diào)度周期的模型是我們改進和完善的一個方向。

參考文獻：

[1]Daskin M S， Panayotopoulos N D. A Relaxation Approach to Assigning Aircraft to Routes in Hub and Spoke Networks[J]. Transportation Science. 1989，23：91-99.

[2]Hance C A， C Barnhart. The Fleet Assignment Problem： Solving Large-Scale Integer Programming[J]. Mathematical Programming. 1995，70：211-232.

[3]Clarke L W， Hance C A. Maintenance and Crew Considerations in Fleet Assignment [J]. Transportation Science， 1996，30：349-365.

[4]Clarke L W， E L JOHNSON， G L Nemhauser. The Aircraft Rotation Problem [J]. Annual Operational Research Mathematical Industrial System， 1997， 2（69）：33-46.

[5]Brian R， Cynthia B， Tim K， etc. Airline Fleet Assignment with time window [J]. Transportation Science， 2000，34（1）：1-20

[6]Talluri K T， The Four-day Aircraft Maintenance Routing Problem [J]. Transportation Science，1998：31.

[7]C Barnhart， N L Boland， L W Clarke， et al. Flight string models for aircraft fleeting and routing[J]. Transporttation Science， 1998， 32（3）：208-220.

[8]孫宏.航空公司飛機排班問題： 模型及算法研究[D].成都：西南交通大學(xué)，2003.

[9]李耀華，秦如如.基于混合遺傳算法的航班串優(yōu)化模型研究[J].中國民航大學(xué)學(xué)報，2010，28（6）：31-34.

[10]Van Beek，Peter. Principles and Practice of Constraint Programming[M].Springer，2005.

[11]Krzysztof R. Apt. Principles of Constraint Programming[M]. Cambridge University Press.2003.

[12]陳尚偉.基于JAVA的約束求解器的設(shè)計與實現(xiàn)[Z].吉林大學(xué)，2005.

[13]Christian Schulte， Guido Tack， Mikael Z. Lagerkvist. Modeling and Programming with Gecode. 2012[EB/OL]. http：//www.gecode.org/doc-latest/MPG.pdf.

[14]Thomas H.Cormen， Charles E.Leiserson， Ronald L.Rivest， Clifford Stein. Introduction to Algorithms[M]. 2006.

[15]王思臣，于潞，劉水，唐金元. 分支界定算法及其在特征選擇中的應(yīng)用研究[J].現(xiàn)代電子技術(shù).2008，10.

[作者簡介]劉剛（1987.6- ），男，漢族，重慶市合川區(qū)人，在讀碩士研究生，研究方向：數(shù)據(jù)庫與信息系統(tǒng)；胡大裟（1976- ），男，漢族，四川瀘州人，博士，講師，研究方向：并行計算，編程語言，軟件工程；蔣玉明，男，漢族，四川人，教授、博士，研究方向：數(shù)據(jù)庫，自動化。