航路資源分配下的航班時刻優化

陳亞青 宋 斐 羅 亮

航路資源分配下的航班時刻優化

陳亞青 宋 斐 羅 亮

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

隨著我國民航業的快速發展，航班延誤問題日益凸顯，嚴重影響了旅客出行需求和民航的發展。對于航空公司而言，航班時刻是非常重要的資源，是占有市場的直接體現，但大量航班延誤導致航空公司非正常運行成本的急劇攀升。如何利用科學的方法優化航班時刻分配，緩解延誤，一直是全球民航界關注的重點問題之一。

國外對于航班時刻優化主要集中在地面等待策略的研究。1987年，Romanin Jacur等人試圖通過建立數學模型解決地面等待時間分配的問題。2003年，Michael等人深入研究了更易于與協同決策系統集成的地面等待策略雙層網絡結構整數規劃模型。2011年，Dimitris Bertsimas等人提出了一個考慮公平性和航空公司協作的航班時刻優化分配網絡模型。

國內對于航班時刻優化的研究主要通過基于多機場地面等待策略建立的模型和算法進行的。1998年，胡明華教授對多機場地面等待策略問題進行了建模求解，并研發出一套航班時刻規劃專家系統。2010年，張洪海等人提出了體現公平性、工效性和有效性的協同地面等待時刻分配優化算法，給出了一種多目標優化模型。2013年，朱承元等人采用空域機場仿真模型（SIMMOD）對珠三角地區多機場系統的航班時刻優化分配進行了仿真研究。

上述研究主要是基于地面等待策略實現對航班時刻的優化，本文通過考慮管制單元之間的航路耦合容量限制，將空域擁堵轉化為航路擁堵問題，并基于臨時航線建立航班時刻優化模型，為延誤航班分配時刻提供決策依據。

模型建立

本文中的“航路”是包括起飛機場、航路、落地機場的一個整體。通過研究航路資源分配的約束條件，建立相應的模型。

在N 個空域管制單元的耦合約束下，航路r在t時間片的運行容量為：

航路耦合容量模型

其中，

航班延誤成本模型

航班的成本函數定義如（4）式：

航班的改航成本函數如（5）式：

基于航路資源分配的航班時刻優化模型

本文假設所有的航班都是可以調整航班時刻的。模型中所涉及的參數含義如下：

T:T={1,2,…,t}為每15min一個時間片；

F={1,…,f}是一個城市對之間的航班序列；

K={1,…,k}為機場集合，k 為起飛機場，k′為落地機場；

M ：航路資源集合，其中m∈M 表示計劃航路，n∈M表示臨時航線；

Cm(t)：在時間片t內計劃航路m 的耦合容量；

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

圖1 求解流程

算法設計

航班時刻優化問題屬于戰略流量管理范疇，因此在設計算法時可以任意調整時刻。另外，航班時刻的分配問題是0－1整數規劃問題，亦為指派問題。當時刻數大于或小于航班數時，是非標準的指派問題，通過添加虛擬航班或時刻化為標準的指派問題，并使用匈牙利算法進行求解。優先分配計劃航路上的時刻，同時設置較大的改航成本系數，使航班分配到臨時航線作為次優策略。求解流程如圖1所示。

算例驗證

算例描述

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

圖2 航班延誤成本對比

圖3 航班時刻優化對比

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

算例分析

通過航班時刻仿真評價系統，結合航段在所屬扇區的流量需求比例以及扇區容量約束下的航段容量，計算航路R1、R2在各時間片內的航路耦合容量和航段容量，進而得出航路R1有40個時刻，航路R2有23個時刻。計劃航路上的40個時刻明顯不能滿足50架航班的需求，18架航班產生延誤，航班最小總延誤成本為970340元。將第一次分配后產生延誤的航班時刻與臨時航線上的航班時刻合并，進行二次優化分配，優化后發生延誤的航班仍有17架，但其中10架被分配到臨時航線上，最終得到航班最小總延誤成本為151340元。每架航班的延誤成本變化如圖2所示。

圖3以分鐘表示時間給出了優化前后給50架航班分配的時刻變化，優化后新增了10個航班時刻，較初始的航班時刻分配更加平滑，不會出現同一時刻分配給多架飛機的情況，航班時刻分配更加合理。臨時航線的利用率提高了43.5%，航路資源分配更加高效。

表2 航路的容量和流量對比

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

結語

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

陳亞青1宋 斐2羅 亮3

1.中國民用航空飛行學院民航飛行技術與飛行安全科研基地；

2.中國民用航空飛行學院空中交通管理學院；3.中國民用航空青島空中交通管理站

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

2014年民航安全能力建設資金項目，2015年學生科技活動基金 基金號：X2015－25

10.3969/j.issn.1001-8972.2016.09.009