飛機排班一體化模型與算法研究＊

高 強 朱星輝 李 云 朱金福

（南京航空航天大學民航學院 南京 210016）

0 引 言

廣義的航班計劃按照計劃進行的先后順序分為如下幾個層次：（1）市場分析和航線的確立（包括城市之間旅客需求分析，每條航線航班頻率的確定）；（2）航班時刻的編制（時刻表的設計）；（3）機型指派；（4）飛機排班（決定航班順序，指定具體執(zhí)行航班的飛機）（5）機組人員的排班．狹義的航班計劃是指前3個層次，廣義航班計劃編制的步驟是按順序完成的，沒有任何反饋，實際操作管理中，航班計劃的實施也是按順序完成的．國外關于航班時間頻率優(yōu)化，機型指派的研究已經(jīng)初具規(guī)模，飛機排班的研究主要集中在維護路線選擇和機尾號指派［1－3］．現(xiàn)在，研究趨向于綜合廣義航班計劃不同層次的計劃，例如，機型指派可以綜合航班時刻，飛機路線和機組計劃．綜合考慮有不同的方法．一種是完全一體化，一種是在各個步驟中反復進行［4－5］．

Ioachim［6］綜合飛機指派和路線選擇問題，同時考慮時間重排，提出了基于分支定界法的Dantzig－Wolfe分解尋找整數(shù)解．Desaulniers［7］使用Dantzig－Wolfe分解解決了日飛機路線選擇和飛機指派問題．Sandhu和 Klabjan［8］將機型、路線和機組計劃統(tǒng)一在同一個模型中．模型通過價值約束解決路線問題，這一點本質(zhì)上意味著模型忽視了飛機路線的維修活動．并采用一種基于混合Lagrangian松弛與列生成算法和另一種Bender分解算法兩種不同方法求解該問題，最后利用U．S航空公司數(shù)據(jù)進行了實例分析．

第二種一體化的方式是首先按照航班計劃編制步驟順序進行計劃，通過后續(xù)計劃對前面計劃結(jié)果的反饋，重新調(diào)整方案，通常使用已經(jīng)很成熟的模型，沒有更深入的理論研究工作．國內(nèi)關于廣義航班計劃一體化研究很不充分．飛機排班通常在機型指派的基礎上，對同一種機型的航班進行路線選擇和尾號指派．這樣分步優(yōu)化可以簡化問題，降低求解難度，但基本不能得到全局最優(yōu)解．同時，由于機型指派沒有考慮飛機的運行約束，因此飛機排班可能無解．

為了改善分步優(yōu)化的次優(yōu)性，本文提出飛機排班一體化優(yōu)化模型，同時對多機型的航班構(gòu)建航班環(huán)，完成飛機指派工作．即機型指派，路線選擇，尾號指派同時進行．該問題為大規(guī)模整數(shù)求解問題，是一個NP－Hard問題．本文提出一種改進的混合技術，即基于列生成算法的約束編程思想，采用混合約束編程（CP）和運籌學（OR）的技術求解飛機排班技術．即將CP算法嵌入到OR框架中，在基于約束編程的列生成算法中，主問題求解線性規(guī)劃（OR），子問題通過CP列生成以求解困難約束，實現(xiàn)模型的高效求解．采用本方法還具有一個優(yōu)勢，可以識別航班計劃的所需要的最小飛機架數(shù)與機型．當求解結(jié)束不存在可行解時，可逐步增加飛機數(shù)量直到求解結(jié)束得到可行解．當確定了最小飛機數(shù)量之后，可以變動飛機的機型以獲得最低成本的機型配置．因此本方法對于航空公司中長期機隊規(guī)劃也具有一定的指導意義．

1 飛機排班一體化路徑模型

針對國內(nèi)航線網(wǎng)絡和航班計劃的特點，在航班時刻表確定，不考慮經(jīng)停，只考慮飛機A檢并且機場無容量限制的前提下，綜合考慮機型指派、路線選擇以及尾號指派，建立日飛機排班一體化0－1整數(shù)規(guī)劃模型，給出指派結(jié)果以及飛機路線．本模型基于飛機路線D:xmlJTKJ15106591JTKJ15106591 楊艷紅 （已改），即對于具體一架飛機，首先構(gòu)建滿足航班銜接、維護、預指派等要求的一天航班環(huán)，然后綜合考慮航空公司飛機等資源限制，以成本最小為目標建立模型．

式中：F為航班集合，f∈F，每個航班信息包括出發(fā)時間（f．dep T），到達時間（f．a(chǎn)rr T），出發(fā)機場（f．dep A），到達機場（f．a(chǎn)rr T），預測旅客量（f．pax）和平均票價（i．price）；A 為飛機集合，a∈A；K 為所有機型集合，?a∈A，k（a）∈K，k（a）為飛機a的機型．機型包括最小過站時間（k．turnround）；基地機場b（k），可以是單維修基地或者多維修基地；機型座位數(shù)（k．S）；日最大起降 次 數(shù) （k．Max duty）；機 型 單 位 運 行 成 本（k．cost）．B 為所有基地機場的集合，?a∈A，b（k（a））∈B；L 為所有滿足要求的飛機路線集合．a(chǎn)∈A，La表示所有由飛機a執(zhí)行的飛機路線集合，l∈La?L．按照f．dep T 對航班排序，即ordered by dep T，low（l）為飛機路線l的首航班，up（l）為飛機路線l的尾航班．Pa為預先指定必須由飛機a執(zhí)行的航班集合，即預指派；Ra為預先指定不能由飛機a執(zhí)行的航班集合，即航班限制．CL為執(zhí)行該飛機路線的成本，包括該飛機執(zhí)行所有航班的運行成本clope和旅客溢出（座位數(shù)少于旅客數(shù)）成本cslpi．這里，clope為機型單位運行成本與飛機路線上所有航班總飛行時間的乘積，為所有航班旅客溢出成本之和．a(chǎn)fl：示性算子

bal：示性算子飛機a執(zhí)行飛機路線l飛機a不執(zhí)行飛機路線l xj：0－1型決策變量，

式（1）為成本最小化目標函數(shù)．式（2）為覆蓋約束，要求每個航班指派一架飛機且只有一架，如果允許加班，可放寬約束．式（3）為飛機數(shù)目約束，一架尾號的飛機只能執(zhí)行一條路線，要求所需飛機架數(shù)不超過可用飛機數(shù)．式（4）與（5）為航班限制約束．式（6）為資源約束，指一種機型執(zhí)行的航班總數(shù)不能超過最大值．式（7）為對于每架飛機的路線合法性要求，滿足航班機場銜接，最小過站時間要求，飛機路線首航班從基地出發(fā)，尾航班到達機場與首航班出發(fā)機場一致，滿足日維修要求，同時使次日有同樣的飛機分布．

除了上述連接約束、維修和航班限制，航空公司實際運營中還有一些別的約束，比如保證飛機路線與機組匹配，規(guī)定飛機轉(zhuǎn)場時間滿足機組換班時間要求．此外，飛機均衡使用要求也是常見的．有時，某些特定機場會限制著陸次數(shù)，飛行時間，飛行工作日等，這些要求都可以通過累積約束建模．數(shù)學規(guī)劃中，這些約束稱為資源約束．

2 基于約束編程的列生成算法

由路徑模型看出，飛機排班一體化主要有兩類約束：

1）對具體一條飛機路線的約束．包括預指派（4），航班限制約束（5）以及最大起飛架次（6），航班銜接及維修基地約束（7），約束中的參數(shù)只與所用飛機及其機型相關，稱CP約束．

2）對通解的約束．包括航班覆蓋約束（2）和飛機總資源約束（3），稱為LP約束．

2．1 主問題（master problem，MP）

根據(jù)列生成的特點，主問題是根據(jù)LP約束求解整數(shù)規(guī)劃，根據(jù)路徑模型得到主問題

ILOG的OPL語言支持約束聲明，如：Constraint fcstf，acsta；表示分別聲明約束數(shù)組fcst和acst，?f是與航班f相關約束的對偶值，βa是與飛機a相關約束的對偶值．求解MP，返回每個約束的對偶值，即

以中型航空公司日航班計劃為例，滿足CP約束的列（飛機路線）的數(shù)目也是巨大的，所以這里采用動態(tài)列生成算法，即LP中只使用飛機路線的子集，如果這些路線集合是一體化模型的可行解，主問題為限制主問題（RMP）．

2．2 基于約束編程的子問題（Subproblem，SP）

根據(jù)飛機排班的特點，列生成算法中的列定義為飛機路線，即由某架飛機執(zhí)行一系列航班的集合，滿足航班時刻表、維修約束、預指派、航班限制等CP約束．根據(jù)列生成的簡約成本更新路線子集．列l(wèi)的簡約成本rcl和負簡約成本NRCl為

使用約束編程生成可能的路線．約束編程（constraint programming，CP）能高效實現(xiàn)飛機排班的列生成算法：（1）搜索策略：本文使用CP求解器為ILOG Solver，提供約束語言描述問題的變量、約束條件以及默認的搜索算法（深度優(yōu)先、廣度優(yōu)先），可根據(jù)需要自己定義控制搜索策略．（2）約束傳播：也稱信息傳播．ILOG平臺能夠在搜索過程中，集中利用約束，計算并傳播每個決策點的結(jié)果，及時檢測，刪除不可能出現(xiàn)在最終解的變量賦值．與傳統(tǒng)搜索相比，可以有效的域縮減，減少回溯次數(shù)．搜索和傳播通常是結(jié)合使用，相輔相成的．

1）最優(yōu)路線 即最優(yōu)列，指當前列集L中具有最大負簡約成本的列，單機型問題中是資源約束最短路，多機型中可以認為最小費用流問題，根據(jù)主問題得到最優(yōu)路線的目標函數(shù)為

根據(jù)CP約束中航班銜接約束，構(gòu)建約束傳播算法：

算法1 約束傳播

路線生成中，同時使用集合變量．如集合flt Rng，是一條路線中航班順序集合，flt Rng［i］是路線中第i個航班．同樣citySeq路線中依次經(jīng)由機場集合．citySeq［0］是出發(fā)基地機場．根據(jù)上界和下界確定集合變量的當前域，稱為指定集req（flt Rng）和可能集pos（flt Rng），集合變量的值是req（fltRng）的超集，pos（flt Rng）的子集．初始，pos（flt Rng）包含所有的航班，req（flt Rng）為空，在路線生成的時候，約束傳播和搜索策略不斷刪除可能集中的航班，增加指定集中的航班．一旦兩集合相等，得到一個集合變量的值．例如，初始pos（fit Rng）含有4個航班，f1，f2，f3，f4，滿足性質(zhì)

f1加入req（flt Rng），f2與f1不滿足最小過站時間，將f2從pos（fltRng）中刪除．此時f1后航班為f3，不滿足機場銜接，將f3從pos（flt Rng）中刪除．f4與f1滿足時間和機場銜接要求，將其加入req（flt Rng）．最后得到集合變量flt Rng的值為：flt Rng［0］＝f1；flt Rng［1］＝f4．域縮減變化見表1．

表1 域縮減

同樣，利用約束編程表述維修基地約束、預指派航班限制約束、最大起飛架次約束，好的約束描述能夠起到加快傳播的作用．另外可以結(jié)合使用搜索策略．

算法2 搜索策略

針對目標函數(shù)求最大負簡約成本的特點，首先根據(jù)對偶值?f對航班排序，利用ILOG內(nèi)置深度搜索，確定選擇點（choice），然后通過約束傳播約束以及其他CP約束對選擇點判斷．直至完成搜索．得到最優(yōu)路線，返回最優(yōu)路線的目標值為

2）更新列集 利用當前列集獲得的最優(yōu)路線的負簡約成本，生成滿足一定條件的列集更新L，減少迭代次數(shù)．比如要求新生成列滿足

約束表述中涵蓋了所有針對單個飛機所有的路徑約束，即CP約束．此時搜索策略為ILOG生成指令，為一架飛機生成執(zhí)行的航班集合

一旦新列滿足CP約束并且滿足式（16），將其加入L集合中，返回限制主問題，重新求解線性規(guī)劃．反復進行，直至沒有新列加入．如果無法繼續(xù)生成負簡約成本的列的時候，生成算法結(jié)束，此時得到整數(shù)規(guī)劃主問題最優(yōu)解．

3 算例分析

某航空公司有2種機型，6架飛機，日執(zhí)行31個航班，2個維修基地機場．基中航班F28為跨海航班，必須由飛機A0001執(zhí)行．航班信息表見表2．機型數(shù)據(jù)見表3．分階段排班結(jié)果與一體化排班結(jié)果見表4．

在ILOG＿studio中編寫OPL程序，輸入航班、機型、飛機數(shù)據(jù)，編譯各功能模型，運行scrip腳本語言控制模型之間的數(shù)據(jù)交換，并輸出最優(yōu)飛機路線集．首先生成初始列3 168條，在迭代過程中負簡約成本飛機數(shù)量不斷變化，其變化趨勢如圖1．LP中列數(shù)目隨主問題迭代的變化趨勢如圖2．最終生成5 890列．經(jīng)過測試，靜態(tài)列生成得到的14 778列，對比可知，基于約束編程的動態(tài)列生成大大減少了列規(guī)模．

表2 航班數(shù)據(jù)表

表3 各機型數(shù)據(jù)表

圖1 負簡約成本飛機路線隨主問題迭代的變化趨勢

表4 分階段排班與一體化排班比較

圖2 總列數(shù)隨主問題迭代的變化趨勢

運行結(jié)果給出最優(yōu)的6架飛機對應的飛機路線，最小成本為2 993 500元，比航空公司分階段排班結(jié)果成本降低約1%．運行時間為314．556 s（CPU：PM4，2．66 G，內(nèi)存512 M）．

4 結(jié)束語

針對航班計劃順序計劃次優(yōu)性，提出綜合考慮機型指派，維護路線選擇，飛機指派等因素的飛機排班一體化模型，并利用混合約束編程和列生成算法技術求解．實現(xiàn)航班計劃的自動化，保證全局最優(yōu)性．在ILOG平臺上編寫程序，利用實際數(shù)據(jù)測試驗證模型算法．可以看出，與傳統(tǒng)的列生成相比，約束編程可以簡單清楚的表達現(xiàn)實中的約束，系統(tǒng)易于維護，同時約束傳播和搜索策略可以顯著改善列生成的效率．

［1］Hane C A，Barnhart C．The fleet assignment problem［J］．Interfaces，1989，19（4）：20－28．

［2］Lloyd C．The aircraft rotation problem［J］．Annals of Operations Research，1997，69：34－35．

［3］Talluri K T．The four－day aircraft maintenance routing problem［J］．Thransportation Science，1998，31（1）：43－48．

［4］屈 援，汪 波，鐘石泉．單車場集送一體化車輛路徑問題及其混合算法研究［J］．武漢理工大學學報：交通科學與工程版，2007，31（5）：811－814．

［5］張 煜，李文鋒，嚴新平．集裝箱作業(yè)系統(tǒng)一體化調(diào)度研究綜述［J］．武漢理工大學學報：交通科學與工程版，2011，35（1）：11－14．

［6］Ioachim I，Desrosiers J，Soumis F，et al．Fleet assignment and routing with schedule synchronization constraints［J］．European Journal of Operational Research，1999，119（1）：75－90．

［7］Desaulniers J，Desrosiers J，Dumas Y，et al．Daily aircraft routing and scheduling［J］．Management Science，1997，43（6）：841－855．

［8］Sandhu R，Klabjan D．Integrated airline fleeting and crew－pairing decisions［J］．Operations Research，2007，55（3）：439－456．