程望斌，馮彩英，曾 毅，羅百通，向燦群（湖南理工學(xué)院 信息與通信工程學(xué)院，湖南 岳陽(yáng) 414006）

航班計(jì)劃的優(yōu)化設(shè)計(jì)研究

程望斌，馮彩英，曾 毅，羅百通，向燦群
（湖南理工學(xué)院 信息與通信工程學(xué)院，湖南 岳陽(yáng) 414006）

以航空公司的正常營(yíng)運(yùn)和最大收益為目標(biāo)，結(jié)合統(tǒng)計(jì)數(shù)據(jù)和目標(biāo)要求，建立航班計(jì)劃動(dòng)態(tài)規(guī)劃模型，采用貪婪算法對(duì)其進(jìn)行求解，得到航空公司的航班計(jì)劃、飛機(jī)數(shù)量的規(guī)劃，從而為航空公司編制和優(yōu)化航班計(jì)劃提供一定的理論依據(jù)和方法支持. 以某航空公司特定機(jī)型的航班計(jì)劃數(shù)據(jù)進(jìn)行實(shí)證，驗(yàn)證了該模型和算法的可行性.

航班計(jì)劃； 動(dòng)態(tài)規(guī)劃； 貪婪算法； 優(yōu)化設(shè)計(jì)

引言

航班計(jì)劃（Schedule）是航空公司一切生產(chǎn)活動(dòng)的基礎(chǔ)和核心，其它任何生產(chǎn)計(jì)劃都是圍繞航班計(jì)劃來制定，并為航班計(jì)劃的順利實(shí)施提供保障[1］. 航班計(jì)劃是航空公司運(yùn)輸生產(chǎn)計(jì)劃的具體實(shí)施計(jì)劃，它規(guī)定了飛行的航線、航段、機(jī)型、航班號(hào)、班次和班期、起降時(shí)刻等. 航空公司運(yùn)行指揮中心每個(gè)月的月末都會(huì)對(duì)本月各航線、機(jī)型的收益情況進(jìn)行市場(chǎng)分析，然后結(jié)合本公司現(xiàn)有的生產(chǎn)資源情況編排下一個(gè)月的航班計(jì)劃，在航班計(jì)劃制定之后需送給機(jī)務(wù)部門進(jìn)行飛機(jī)排班作業(yè)，機(jī)務(wù)部門在制定飛機(jī)排班計(jì)劃時(shí)主要考慮滿足飛機(jī)維修的需要，飛機(jī)排班計(jì)劃完成以后形成可執(zhí)行的航班計(jì)劃，該計(jì)劃需下發(fā)到飛行總隊(duì)具體執(zhí)飛. 一個(gè)合理的航班計(jì)劃應(yīng)該既有助于航班的安全運(yùn)行，又能提高飛機(jī)的利用率，還可以有效地降低運(yùn)營(yíng)及維護(hù)成本，提高公司的經(jīng)濟(jì)效益[2］. 本文將某航空公司根據(jù)市場(chǎng)要求安排的航班時(shí)刻匯總的所有可以選擇的候選航班，作為優(yōu)化決策的備選方案. 航班計(jì)劃時(shí)刻優(yōu)化決策即從候選航班中選擇最佳方案，使飛機(jī)數(shù)目最少，航空公司利益最大化.

1 問題提出與分析

國(guó)內(nèi)某個(gè)以客運(yùn)為主的航空公司運(yùn)行指揮中心每個(gè)月的月末都會(huì)對(duì)本月各航線、機(jī)型的收益情況進(jìn)行市場(chǎng)分析，然后結(jié)合本公司現(xiàn)有的生產(chǎn)資源情況編排下一個(gè)月的航班計(jì)劃，在航班計(jì)劃制定之后需送給機(jī)務(wù)部門進(jìn)行飛機(jī)排班作業(yè)，機(jī)務(wù)部門在制定飛機(jī)排班計(jì)劃時(shí)主要考慮滿足飛機(jī)維修的需要，飛機(jī)排班計(jì)劃完成以后形成可執(zhí)行的航班計(jì)劃，該計(jì)劃需下發(fā)到飛行總隊(duì)具體執(zhí)飛.

已知該公司有兩種類型的飛機(jī)，A320飛機(jī)和E190飛機(jī). 其中A320飛機(jī)2架，E190飛機(jī)4架. 維修基地設(shè)在西安和天津. 由于航線資源是航空公司的稀缺資源，所以制定航班計(jì)劃時(shí)一般不會(huì)取消，也不會(huì)隨意拆分帶有經(jīng)停航點(diǎn)的航線. 在航班計(jì)劃制定時(shí)，若本公司飛機(jī)數(shù)量無法滿足現(xiàn)有航線需要，可向?qū)I(yè)的飛機(jī)租賃公司申請(qǐng)租賃； 反之，若在滿足現(xiàn)有航線需要的前提下，本公司尚有一定數(shù)量的剩余飛機(jī)，則可作為備用飛機(jī)在航線發(fā)生延誤及飛機(jī)出現(xiàn)臨時(shí)故障時(shí)使用，或者直接出租給其它航空公司以便獲取額外利潤(rùn). 已知該公司某月各航線單日運(yùn)行成本及收入明細(xì)，并假定每個(gè)航線每日只安排一個(gè)班次的飛機(jī)，各航線的航班時(shí)刻可以根據(jù)需要變動(dòng)，同時(shí)假定現(xiàn)有飛行航線和航空公司的營(yíng)銷能力是穩(wěn)定的. 為此航空公司需制定一份下個(gè)月的航班計(jì)劃，使航空公司的收益最大化.

2 飛機(jī)排班計(jì)劃的數(shù)學(xué)模型建立

飛機(jī)排班是航班計(jì)劃的一項(xiàng)控制性工作，排班質(zhì)量不僅決定著運(yùn)輸生產(chǎn)能否安全、正點(diǎn)的運(yùn)行，而且還關(guān)系到飛機(jī)維護(hù)計(jì)劃能否順利執(zhí)行[3］. 飛機(jī)排班工作中必須遵守以下基本要求： 飛機(jī)排班應(yīng)與制定的航班計(jì)劃相符； 每條航線應(yīng)當(dāng)且僅安排一架飛機(jī)執(zhí)行任務(wù)； 每架飛機(jī)在同一時(shí)段最多只能執(zhí)行一條航線的任務(wù)； 飛機(jī)的使用要求均衡； 在航班計(jì)劃正常營(yíng)運(yùn)的情況下，所需飛機(jī)數(shù)目最少，使航空公司獲取最大化的收益.

要滿足上述要求，關(guān)鍵是做到： （1）根據(jù)緊湊銜接的原則將航班節(jié)編組，然后對(duì)航班節(jié)組指派飛機(jī)； （2）允許對(duì)標(biāo)準(zhǔn)過站時(shí)間GT進(jìn)行壓縮，但不得低于最低過站時(shí)間即GTmin； （3）重要航班應(yīng)優(yōu)先保障； （4）應(yīng)盡量減少由于過站時(shí)間壓縮而引起的航班延誤. 為此建立如下飛機(jī)排班數(shù)學(xué)模型：

航班節(jié)集合定義為J=｛Ji，j=1，…，n ｝，n表示航班節(jié)總數(shù)，所有可用于執(zhí)行航班任務(wù)的飛機(jī)集合為F=|k=1，…，m｝，m表示某機(jī)型的飛機(jī)數(shù)量，機(jī)場(chǎng)的集合定義為D=｛Di |i=1，2，…，d ｝，d表示所有可到達(dá)的機(jī)場(chǎng)總數(shù)，某飛機(jī)的起點(diǎn)與前一個(gè)航班任務(wù)的降落點(diǎn)為同一地點(diǎn)的匹配函數(shù)為

式（1）中，在樞紐機(jī)場(chǎng)的起飛時(shí)間為rt，在樞紐機(jī)場(chǎng)的過站時(shí)間為GT，某飛機(jī)在航班節(jié)中包含的起降次數(shù)為jC，飛行時(shí)間為jt，完備時(shí)間為jtf，航班節(jié)的時(shí)間要求jta，飛行成本為C，飛機(jī)收入為L(zhǎng)，飛機(jī)與航班節(jié)的匹配函數(shù)定義

飛機(jī)任務(wù)是否執(zhí)行定義為

完成所有的航班任務(wù)所用的飛機(jī)數(shù)量為

根據(jù)排班原則“飛機(jī)型號(hào)與所分配的航班節(jié)相匹配”，即

根據(jù)排班原則“同一架飛機(jī)的相鄰兩個(gè)航班應(yīng)符合過站時(shí)間銜接”，即

根據(jù)排班原則“同一架飛機(jī)的相鄰兩個(gè)航班應(yīng)符合航班地點(diǎn)銜接”，即

根據(jù)排班原則“一架飛機(jī)的總的飛行時(shí)間與過站時(shí)間之和不大于標(biāo)準(zhǔn)工作間”，

根據(jù)飛機(jī)排班原則“一架飛機(jī)執(zhí)行的飛行任務(wù)必須滿足航班節(jié)的時(shí)間要求”，

根據(jù)排班原則“所有航班節(jié)有且只有一架飛機(jī)執(zhí)行”，因此，對(duì)于任意航班節(jié)i，有且只有一個(gè)是否執(zhí)行任務(wù)的變量Xikj為“值1”，即

根據(jù)排班原則“一架飛機(jī)同一時(shí)間段最多只能執(zhí)行一個(gè)航班節(jié)任務(wù)”，因此飛機(jī)k在執(zhí)行完航班節(jié)i之后，最多只能執(zhí)行一個(gè)后續(xù)航班節(jié)j，即對(duì)于給定的飛機(jī)k與航班節(jié)i，飛機(jī)任務(wù)是否執(zhí)行變量最多只有一個(gè)為“值1”，即

同理飛機(jī)k在執(zhí)行航班節(jié)j之前，最多只能執(zhí)行一個(gè)航班節(jié)i，即對(duì)于給定的飛機(jī)k與航班節(jié)j，飛機(jī)任務(wù)是否執(zhí)行變量Xikj最多只有一個(gè)為“值1”，即：

根據(jù)排班原則“全部飛行任務(wù)執(zhí)行完畢后，雙樞紐機(jī)場(chǎng)的飛機(jī)數(shù)量與執(zhí)行任務(wù)飛機(jī)數(shù)量一致”即

綜合（5）～（14）即可得到飛機(jī)對(duì)航班節(jié)分配問題的數(shù)學(xué)模型：

其中公式（15）為目標(biāo)函數(shù)，公式（16）至公式（24）為約束條件[4］.

3 航班計(jì)劃的編排

航空公司在制定計(jì)劃時(shí)的一項(xiàng)基本內(nèi)容就是飛機(jī)排班，飛機(jī)排班是指： 飛機(jī)調(diào)度員根據(jù)市場(chǎng)部下達(dá)的航班計(jì)劃，機(jī)務(wù)部提供的飛機(jī)維修計(jì)劃，每架飛機(jī)的技術(shù)狀況以及飛機(jī)調(diào)度指令，為每個(gè)航班指定一架具體執(zhí)行的飛機(jī).

3.1 飛機(jī)排班的算法設(shè)計(jì)

我們建立的飛機(jī)排班的數(shù)學(xué)模型是一個(gè)動(dòng)態(tài)規(guī)劃問題[5］，且含有多個(gè)約束條件. 目前解決該類問題的算法有很多，如隨機(jī)模擬算法，遺傳算法等. 由于文中涉及的機(jī)型僅為兩種，航班節(jié)僅有26個(gè)，因此可考慮用遍歷的方法尋找最優(yōu)解. 同時(shí)，本文還使用貪婪算法[6］對(duì)問題進(jìn)行了求解，并在此基礎(chǔ)上進(jìn)行算法的改進(jìn)，使其盡可能的滿足飛機(jī)使用均衡.

（1） 掃描法尋找最優(yōu)解

掃描的基本思想就在于能夠遍歷所有解，記錄產(chǎn)生的最優(yōu)解，直到有新的最優(yōu)解替代它. 算法基本流程如下：

Step1 遞歸實(shí)現(xiàn)二路歸并排序?qū)崿F(xiàn)所有解的遍歷；

Step2 比較每一個(gè)解下面目標(biāo)函數(shù)值與所設(shè)最小值，如果小于所設(shè)最小值則完成最小值的替代，并記錄此解；

Step3 遍歷以后輸出最小值和此最小值下的解.

用此算法得到過站時(shí)間設(shè)為20～50min，每個(gè)樞紐點(diǎn)需要的不同飛機(jī)最小數(shù)量見表1.

表1 飛機(jī)排班情況

（2） 貪婪算法尋找最優(yōu)解

貪婪算法是指在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇. 也就是說，不從整體最優(yōu)上加以考慮，它所做出的是在某種意義上的局部最優(yōu)解，但它可以大大提高運(yùn)算速度，加快收斂，應(yīng)用于更大數(shù)量的航班節(jié)指派飛機(jī)場(chǎng)合.

針對(duì)我們所建立的飛機(jī)排班模型，具體均衡貪婪算法的實(shí)現(xiàn)如下：

Step1 對(duì)所有航班節(jié)以其完成的時(shí)間長(zhǎng)短進(jìn)行從大到小的排序；

Step2 將航班節(jié)綁定在可以綁定的飛機(jī)上，如有多臺(tái)飛機(jī)可完成綁定，則優(yōu)先綁定目前工作時(shí)間短的飛機(jī)，并標(biāo)識(shí)；

Step3 如果沒有可綁定的飛機(jī)，則指派一架新的飛機(jī)來綁定該航班節(jié)，并標(biāo)識(shí)；

Step4 完成所有航班節(jié)的綁定，并將結(jié)果輸出.

通過實(shí)驗(yàn)得到的均衡貪婪算法實(shí)驗(yàn)結(jié)果和掃描法結(jié)果一致，驗(yàn)證了該算法的可行性.

3.2 航班計(jì)劃的實(shí)現(xiàn)

采用均衡貪婪算法可以得到飛機(jī)排班指派表如表2所示.

表2 飛機(jī)執(zhí)行表（A320機(jī)型過站時(shí)間為40min，E190過站時(shí)間30min）

同時(shí)本文還對(duì)A320過站時(shí)間為30min進(jìn)行了仿真，得到的結(jié)果和過站時(shí)間為40min一樣，而A320過站時(shí)間為50min則需要增加飛機(jī)數(shù)量，因此設(shè)置A320過站時(shí)間為40min. 同時(shí)也對(duì)E190過站時(shí)間分別為40min、50min進(jìn)行了仿真，得到過站時(shí)間為40min時(shí)E190需要增加一架飛機(jī)，50 min則需要更多，因此設(shè)置E190過站時(shí)間為30 min，可以達(dá)到效益最大化.

根據(jù)算法給出的航班串組成及各航線往返耗時(shí)能給出航班的具體排班及起降時(shí)間表. 各航班的起飛時(shí)間確定主要考慮如下四個(gè)因素：

（1） 最早航班的起飛時(shí)間和最晚航班的降落時(shí)間在合理范圍；

（2） 只有一個(gè)航班的航班串，起飛時(shí)間盡量和給出的數(shù)據(jù)相吻合；

（3） 航班串中有多個(gè)組成時(shí)，先后順序的確定也盡量保持一致，在無法都保證的情況下優(yōu)先考慮收益多的航班；

（4） 起飛時(shí)間和降落時(shí)間錯(cuò)開，盡量避免同一基地機(jī)場(chǎng)存在多架飛機(jī)同時(shí)起飛或同時(shí)降落的情況.

各航班排班結(jié)果如表3所示.

表3 各航班排班結(jié)果

XX1572 E190 19：1023：05XX1658成都-天津 A320 21：30 23：50 XX1583 天津-桂林 A320 11：1514：10XX1661天津-上海 A320 6：00 7：55 XX1584 桂林-天津 A320 14：5017：25XX1662上海-天津 A320 8：35 10：35 XX1599 西安-南昌-廈門 A320 15：0519：15XX1663西安-桂林 A320 15：45 17：30 XX1600 廈門-南昌-西安 A320 19：550：00 XX1664桂林-西安 A320 18：10 19：55 XX1603 天津-寧波 A320 10：3012：00XX1667西安-貴陽(yáng)-三亞A320 15：30 19：55 XX1604 寧波-天津 A320 17：0018：30XX1668三亞-貴陽(yáng)-西安A320 10：25 14：50 XX1607 天津-臨沂-福州 E190 15：2018：50XX1669天津-重慶 A320 11：00 13：45 XX1608 福州-臨沂-天津 E190 19：3023：00XX1670重慶-天津 A320 14：25 16：50 XX1609 天津-鄭州-南寧 E190 6：00 10：30XX1681天津-武漢-三亞A320 8：55 14：05 XX1610 南寧-鄭州-天津 E190 11：1014：40XX1682三亞-武漢-天津A320 14：50 19：40 XX1611 天津-鄭州-桂林 E190 6：00 10：05XX1689天津-廈門 A320 17：30 20：30 XX1612 桂林-鄭州-天津 E190 10：3514：35XX1690廈門-天津 A320 21：10 23：35 XX1614 溫州-青島-天津 E190 19：3523：05XX1691天津-三亞 E190 6：00 10：15 XX1615 天津-青島-溫州 E190 15：2519：05XX1692三亞-天津 E190 10：45 14：55

由表3可知，飛機(jī)降落時(shí)間均未超過凌晨一點(diǎn)，符合機(jī)場(chǎng)實(shí)際情況. 同一基地中所有航班的起飛和降落時(shí)間均不同，很好地錯(cuò)開了時(shí)間，避免了機(jī)場(chǎng)擁塞，滿足了以上四個(gè)主要因素的要求，所以表3的排班接近最優(yōu)且實(shí)際可行.

4 結(jié)語

本文設(shè)計(jì)的航班計(jì)劃，雖然是在固定模式下制定的，有一定的局限性，但其中建立的模型和采用的分析方法對(duì)我國(guó)航班計(jì)劃的制定具有一定的借鑒作用. 由于時(shí)間和知識(shí)水平的關(guān)系，還有不少因素需要考慮，有不少環(huán)節(jié)需要優(yōu)化設(shè)計(jì)，因此模型的設(shè)計(jì)和航班計(jì)劃的優(yōu)化還有待進(jìn)一步完善[7］.

[1]張海峰，胡明華. 航空公司短期航班計(jì)劃編排模型及算法[J[. 南京航空航天大學(xué)學(xué)報(bào)，2015，47（4）： 553～558

[2]羅 俊，閻 煜. 短期航班調(diào)整的利潤(rùn)分析[J[. 知識(shí)經(jīng)濟(jì)，2012（6）：138～139

[3]劉 山，秦易達(dá).飛機(jī)排班模型的分層優(yōu)化方法[J[. 計(jì)算機(jī)仿真，2014，31（2）： 111～115

[4]譚 娜，李耀華. 基于改進(jìn)遺傳算法的機(jī)組指派優(yōu)化方法研究[J[. 控制工程，2015，22（4）： 674～678

[5]張伯生，劉 飛. 實(shí)現(xiàn)航班計(jì)劃優(yōu)化的動(dòng)態(tài)規(guī)劃模型[J[. 上海工程技術(shù)大學(xué)學(xué)報(bào)，2004，18（2）： 135～141

[6]晏 杰. 基于改進(jìn)的貪婪算法在0/1背包問題中的研究與應(yīng)用[J[. 廊坊師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2011，11（5）： 27-30

[7]高 偉，張騰飛. 隨機(jī)模擬法在仿真航班計(jì)劃生成中的應(yīng)用[J[. 科技創(chuàng)新導(dǎo)報(bào)，2014，（2）： 89～91

Research on Optimization Design of Flight Plan

CHENG Wang-bin，F(xiàn)ENG Cai-ying，ZENG Yi，LUO Bai-tong，XIANG Can-qun
（College of Information and Communication Engineering，Hunan Institute of Science and Technology，Hunan Yueyang 414006）

Taking normal operation of the airline and the maximum profit as the goal，combining with the statistical data and the goals and objectives，flight schedule dynamic programming model was established. The greedy algorithm was used to plane the airline's flight plan and the number of aircraft. So as to provide theoretical basis and method support for airline coding system and the optimization of flight plan. The feasibility of the model and algorithm was verified by the data of flight plan of a certain airline.

flight planning，dynamic programming，greedy algorithm，optimization design

F560

A

1672-5298（2016）02-0038-05

2016-03-18

程望斌（1979- ），男，湖北咸寧人，碩士，湖南理工學(xué)院信息與通信工程學(xué)院副教授. 主要研究方向： 光電子技術(shù)、學(xué)科競(jìng)賽