飛機(jī)排班一體化模型與算法研究＊

高 強(qiáng) 朱星輝 李 云 朱金福

（南京航空航天大學(xué)民航學(xué)院 南京 210016）

0 引 言

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

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

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

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

1 飛機(jī)排班一體化路徑模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 約束傳播

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

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

表1 域縮減

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

算法2 搜索策略

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

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

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

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

3 算例分析

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

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

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

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

圖1 負(fù)簡約成本飛機(jī)路線隨主問題迭代的變化趨勢

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

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

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

4 結(jié)束語

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

［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］．武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2007，31（5）：811－814．

［5］張 煜，李文鋒，嚴(yán)新平．集裝箱作業(yè)系統(tǒng)一體化調(diào)度研究綜述［J］．武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，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．