航路資源分配下的航班時(shí)刻優(yōu)化

陳亞青 宋 斐 羅 亮

航路資源分配下的航班時(shí)刻優(yōu)化

陳亞青 宋 斐 羅 亮

本文分析了航路資源合理分配的必要性，以航路上所有航班的總延誤成本最小為目標(biāo)函數(shù)，以航班時(shí)刻變動(dòng)范圍、時(shí)刻數(shù)量和航路容量限制為約束條件，建立了航路耦合容量模型和航班延誤成本模型。再以京－滬航路航班數(shù)據(jù)為基礎(chǔ)進(jìn)行算例分析，運(yùn)用匈牙利算法求解模型。計(jì)算結(jié)果表明：新增了10個(gè)航班時(shí)刻；縮短了11個(gè)航班的延誤時(shí)間；優(yōu)化后航班最小總延誤成本明顯降低。通過(guò)改航到臨時(shí)航線，使其利用率提高了43.5%；各飛行航段的實(shí)時(shí)流量與容量限制更加匹配，降低了空中交通延誤時(shí)間。

隨著我國(guó)民航業(yè)的快速發(fā)展，航班延誤問(wèn)題日益凸顯，嚴(yán)重影響了旅客出行需求和民航的發(fā)展。對(duì)于航空公司而言，航班時(shí)刻是非常重要的資源，是占有市場(chǎng)的直接體現(xiàn)，但大量航班延誤導(dǎo)致航空公司非正常運(yùn)行成本的急劇攀升。如何利用科學(xué)的方法優(yōu)化航班時(shí)刻分配，緩解延誤，一直是全球民航界關(guān)注的重點(diǎn)問(wèn)題之一。

國(guó)外對(duì)于航班時(shí)刻優(yōu)化主要集中在地面等待策略的研究。1987年，Romanin Jacur等人試圖通過(guò)建立數(shù)學(xué)模型解決地面等待時(shí)間分配的問(wèn)題。2003年，Michael等人深入研究了更易于與協(xié)同決策系統(tǒng)集成的地面等待策略雙層網(wǎng)絡(luò)結(jié)構(gòu)整數(shù)規(guī)劃模型。2011年，Dimitris Bertsimas等人提出了一個(gè)考慮公平性和航空公司協(xié)作的航班時(shí)刻優(yōu)化分配網(wǎng)絡(luò)模型。

國(guó)內(nèi)對(duì)于航班時(shí)刻優(yōu)化的研究主要通過(guò)基于多機(jī)場(chǎng)地面等待策略建立的模型和算法進(jìn)行的。1998年，胡明華教授對(duì)多機(jī)場(chǎng)地面等待策略問(wèn)題進(jìn)行了建模求解，并研發(fā)出一套航班時(shí)刻規(guī)劃專(zhuān)家系統(tǒng)。2010年，張洪海等人提出了體現(xiàn)公平性、工效性和有效性的協(xié)同地面等待時(shí)刻分配優(yōu)化算法，給出了一種多目標(biāo)優(yōu)化模型。2013年，朱承元等人采用空域機(jī)場(chǎng)仿真模型（SIMMOD）對(duì)珠三角地區(qū)多機(jī)場(chǎng)系統(tǒng)的航班時(shí)刻優(yōu)化分配進(jìn)行了仿真研究。

上述研究主要是基于地面等待策略實(shí)現(xiàn)對(duì)航班時(shí)刻的優(yōu)化，本文通過(guò)考慮管制單元之間的航路耦合容量限制，將空域擁堵轉(zhuǎn)化為航路擁堵問(wèn)題，并基于臨時(shí)航線建立航班時(shí)刻優(yōu)化模型，為延誤航班分配時(shí)刻提供決策依據(jù)。

模型建立

本文中的“航路”是包括起飛機(jī)場(chǎng)、航路、落地機(jī)場(chǎng)的一個(gè)整體。通過(guò)研究航路資源分配的約束條件，建立相應(yīng)的模型。

在N 個(gè)空域管制單元的耦合約束下，航路r在t時(shí)間片的運(yùn)行容量為：

航路耦合容量模型

其中，

航班延誤成本模型

航班的成本函數(shù)定義如（4）式：

航班的改航成本函數(shù)如（5）式：

基于航路資源分配的航班時(shí)刻優(yōu)化模型

本文假設(shè)所有的航班都是可以調(diào)整航班時(shí)刻的。模型中所涉及的參數(shù)含義如下：

T:T={1,2,…,t}為每15min一個(gè)時(shí)間片；

F={1,…,f}是一個(gè)城市對(duì)之間的航班序列；

K={1,…,k}為機(jī)場(chǎng)集合，k 為起飛機(jī)場(chǎng)，k′為落地機(jī)場(chǎng)；

M ：航路資源集合，其中m∈M 表示計(jì)劃航路，n∈M表示臨時(shí)航線；

Cm(t)：在時(shí)間片t內(nèi)計(jì)劃航路m 的耦合容量；

Cn(t)：在時(shí)間片t內(nèi)臨時(shí)航線n 的耦合容量；

圖1 求解流程

算法設(shè)計(jì)

航班時(shí)刻優(yōu)化問(wèn)題屬于戰(zhàn)略流量管理范疇，因此在設(shè)計(jì)算法時(shí)可以任意調(diào)整時(shí)刻。另外，航班時(shí)刻的分配問(wèn)題是0－1整數(shù)規(guī)劃問(wèn)題，亦為指派問(wèn)題。當(dāng)時(shí)刻數(shù)大于或小于航班數(shù)時(shí)，是非標(biāo)準(zhǔn)的指派問(wèn)題，通過(guò)添加虛擬航班或時(shí)刻化為標(biāo)準(zhǔn)的指派問(wèn)題，并使用匈牙利算法進(jìn)行求解。優(yōu)先分配計(jì)劃航路上的時(shí)刻，同時(shí)設(shè)置較大的改航成本系數(shù)，使航班分配到臨時(shí)航線作為次優(yōu)策略。求解流程如圖1所示。

算例驗(yàn)證

算例描述

本文采用《2014夏秋國(guó)內(nèi)公司航班計(jì)劃》，星期一7：00－22：00時(shí)間段中從北京首都機(jī)場(chǎng)飛往上海虹橋和浦東機(jī)場(chǎng)的50架航班進(jìn)行仿真和分析，將北京首都機(jī)場(chǎng)作為航班的決策點(diǎn)。計(jì)劃航路（R1）和臨時(shí)航線（R2）所經(jīng)過(guò)的空域管制單元的小時(shí)容量及在各空域管制單元飛行的時(shí)間如表1所示。其中，ZBAAR04，ZSSSAR06分別表示北京區(qū)域管制04號(hào)扇區(qū)和上海區(qū)域管制06號(hào)扇區(qū)，其余同理。

圖2 航班延誤成本對(duì)比

圖3 航班時(shí)刻優(yōu)化對(duì)比

表1 空域管制單元容量及航班飛行時(shí)間

算例分析

通過(guò)航班時(shí)刻仿真評(píng)價(jià)系統(tǒng)，結(jié)合航段在所屬扇區(qū)的流量需求比例以及扇區(qū)容量約束下的航段容量，計(jì)算航路R1、R2在各時(shí)間片內(nèi)的航路耦合容量和航段容量，進(jìn)而得出航路R1有40個(gè)時(shí)刻，航路R2有23個(gè)時(shí)刻。計(jì)劃航路上的40個(gè)時(shí)刻明顯不能滿足50架航班的需求，18架航班產(chǎn)生延誤，航班最小總延誤成本為970340元。將第一次分配后產(chǎn)生延誤的航班時(shí)刻與臨時(shí)航線上的航班時(shí)刻合并，進(jìn)行二次優(yōu)化分配，優(yōu)化后發(fā)生延誤的航班仍有17架，但其中10架被分配到臨時(shí)航線上，最終得到航班最小總延誤成本為151340元。每架航班的延誤成本變化如圖2所示。

圖3以分鐘表示時(shí)間給出了優(yōu)化前后給50架航班分配的時(shí)刻變化，優(yōu)化后新增了10個(gè)航班時(shí)刻，較初始的航班時(shí)刻分配更加平滑，不會(huì)出現(xiàn)同一時(shí)刻分配給多架飛機(jī)的情況，航班時(shí)刻分配更加合理。臨時(shí)航線的利用率提高了43.5%，航路資源分配更加高效。

表2 航路的容量和流量對(duì)比

表2表示了優(yōu)化前后航路的容量和流量對(duì)比。如CA1831航班所在時(shí)間片[7：30，7：45）內(nèi)，優(yōu)化前航路R1的流量大于耦合容量，必然會(huì)產(chǎn)生延誤；優(yōu)化后航路R1的耦合容量和流量更加匹配、降低了空中交通延誤時(shí)間。這表明本文所建立的航班時(shí)刻優(yōu)化模型和設(shè)計(jì)的求解算法是有效的。

結(jié)語(yǔ)

本文對(duì)基于航路資源分配的航班時(shí)刻優(yōu)化問(wèn)題進(jìn)行了研究，建立了相應(yīng)的航路耦合容量模型和航班延誤成本模型，并通過(guò)具體案例進(jìn)行分析。研究結(jié)果表明：以起飛機(jī)場(chǎng)為決策點(diǎn)全局考慮整個(gè)飛行過(guò)程中的容量限制，優(yōu)化后部分航班改航到臨時(shí)航線上，航程增加，但總的延誤成本大大降低，同時(shí)減少了空中交通延誤時(shí)間，提高了臨時(shí)航線利用率。由于航班延誤成本參數(shù)借鑒了歐控的相關(guān)文件，為更真實(shí)的反映我國(guó)航班運(yùn)行情況，進(jìn)一步需要加強(qiáng)對(duì)航班延誤成本參數(shù)的研究。

陳亞青1宋 斐2羅 亮3

1.中國(guó)民用航空飛行學(xué)院民航飛行技術(shù)與飛行安全科研基地；

2.中國(guó)民用航空飛行學(xué)院空中交通管理學(xué)院；3.中國(guó)民用航空青島空中交通管理站

陳亞青（1970 －）男，山西原平人，碩士，教授。研究方向：空中交通管理；通訊作者：宋斐（1989 －）男，山西太原人，碩士研究生。研究方向：空中交通管理

2014年民航安全能力建設(shè)資金項(xiàng)目，2015年學(xué)生科技活動(dòng)基金 基金號(hào)：X2015－25

10.3969/j.issn.1001-8972.2016.09.009