摘 要：隨著我國航空事業(yè)的高速發(fā)展，快速、便捷的空中運(yùn)輸業(yè)備受人們的關(guān)注。由于航班數(shù)量的急劇增長，單純依賴人工決策進(jìn)行航班調(diào)度愈加困難。因此，本文在充分考慮安全性和效率的情況下，借助于計(jì)算機(jī)建立基于最短路徑和最短時(shí)間的多目標(biāo)優(yōu)化算法對上海虹橋機(jī)場進(jìn)行智能調(diào)度，對航班起飛和降落的次序、時(shí)間以及地面的滑行路徑進(jìn)行規(guī)劃。

關(guān)鍵詞：Floyd算法；FCFS/SJF算法；向圖；多跑道調(diào)度

中圖分類號：V355；TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2018）06-0135-03

Abstract：With the rapid development of China’s aviation industry，the fast and convenient air transportation industry has attracted people’s attention. Due to a sharp increase in the number of flights which rely on artificial decision in flight scheduling becomes harder and harder. Therefore，in this paper，with the full consideration of security and efficiency，a multi-objective optimization algorithm based on the shortest path and the shortest time is established by means of a computer，to schedule intelligent dispatch of Shanghai Hongqiao Airport. The flight departure and landing sequence， time and ground skating path are planned.

Keywords：Floyd algorithm；FCFS/SJF algorithm；directed graph；multiple runway scheduling

1 問題的提出

1.1 背景

2016年10月11日，在上海虹橋機(jī)場：東航一架A320客機(jī)在滑出跑道即將起飛時(shí)發(fā)現(xiàn)另一架A330客機(jī)正在橫穿跑道。A320客機(jī)緊急起飛，從A330上方掠過，避免了一起慘烈空難的發(fā)生，這是一起嚴(yán)重的A類穿越事件。近日搜索各航班信息平臺不難發(fā)現(xiàn)，各地區(qū)機(jī)場出現(xiàn)延誤的原因中，除天氣因素外，大部分顯示“受流控影響”，航班準(zhǔn)點(diǎn)率低于30%，最低甚至僅為4%。因而導(dǎo)致乘客產(chǎn)生情緒化行為，使得機(jī)場現(xiàn)有的管理模式面臨重重危機(jī)。

1.2 問題

為提高機(jī)場運(yùn)行安全性，本文借助計(jì)算機(jī)建立一種智能調(diào)度算法以提高機(jī)場的運(yùn)行效率。對此，本文以虹橋機(jī)場2017年某日下午一小時(shí)內(nèi)的航班起降信息為研究對象，設(shè)計(jì)每架航班起降的次序和在地面滑行路徑的智能調(diào)度算法。

2 智能調(diào)度算法

2.1 Floyd算法調(diào)度

2.1.1 建立最短路徑模型

Step 1 建坐標(biāo)系首先將虹橋機(jī)場的地圖轉(zhuǎn)化為坐標(biāo)系如圖1所示。

Step 2 構(gòu)建可達(dá)矩陣。用來描述有向連接圖各節(jié)點(diǎn)之間經(jīng)過一定長度的通路后可達(dá)到的程度的矩陣。將圖1中各路口看作一個(gè)節(jié)點(diǎn)，則可達(dá)矩陣A={amn}中的元素滿足：

Step 3 計(jì)算可達(dá)距離。將各架飛機(jī)看作質(zhì)點(diǎn)，將整個(gè)機(jī)場看作一個(gè)圖，則飛機(jī)i到達(dá)路口j的可達(dá)距離dij為：

Step 4 Floyd算法。從圖的鄰接矩陣An×n=[a（i，j）]開始，對矩陣D進(jìn)行N次更新：第1次更新時(shí)，如果dij>di0+d0j，則dij=di0+d0j；第k次更新時(shí)，如果dij>di0+d0j則dij=di0+d0j。更新N次之后：

由于所有航班須在規(guī)定時(shí)間內(nèi)起降，相同時(shí)刻有且僅有一個(gè)航班在起飛或降落跑道上，且一條跑道最多有α架航班。為使所有航班到達(dá)起降跑道的路徑和最短，建立目標(biāo)函數(shù)：

2.1.2 確定最短路徑

Step 1 確定坐標(biāo)。根據(jù)虹橋機(jī)場地圖及比例，可得到各節(jié)點(diǎn)坐標(biāo)。圖1中①～⑩點(diǎn)坐標(biāo)為：

（1736.8，184）（1968.4，368）（1302.6，368）（1986.4，552）（1302.6，552）（868.4，368）（868.4，552）（1986.4，736）（1302.6，736）（868.4，736）

Step 2 運(yùn)用Floyd算法求解最短距離。將表1代入式（1），則任意可直接到達(dá)的節(jié)點(diǎn)間距離dij，使用Floyd算法迭代可得航班降落且停在T2航站樓的最短路徑（序號見圖1）為：

①②④⑦或①③⑤⑧或①③⑥⑨⑩

2.2 FCFS/SJF算法調(diào)度

2.2.1 建立最短起降所有航班時(shí)間模型

Step 1 由于航班的起降受尾流影響[1]，前后兩架飛機(jī)起降間隔如表1所示。

Step 2 FCFS算法。按照航班到達(dá)的順序給航班安排跑道，確定其降落時(shí)間。在實(shí)際空管程序中采用此策略[2]。考慮尾流影響，相同時(shí)刻重型機(jī)優(yōu)先于輕型機(jī)，則起降時(shí)間增加。

Step 3 SJF算法。相同起降時(shí)間段內(nèi)，起降用時(shí)短的航班優(yōu)先起降。若采用此算法，則原航班的升降次序改動(dòng)過大，調(diào)整難度加大。

對此，本文采用FCFS/SJF算法，在相同時(shí)刻起降的航班，優(yōu)先升降輕型航班，若型號相同的航班，則遵從FCFS原則。起降完所有航班所需時(shí)間由各個(gè)航班等待起降時(shí)間、占用跑道用時(shí)和穿越跑道的時(shí)間組成，即：

由于各個(gè)航班占用跑道的時(shí)間大致相同，約為60s，穿越跑道的時(shí)間約為50s[2]，則式（4）可描述為：

2.2.2 確定最短起降所有航班時(shí)間

結(jié)合表1和式（4）可得到每一時(shí)刻航班起降最短時(shí)間，代入式（5）即可求出起飛完所有航班最短時(shí)間為67.97分鐘，降落完所有航班最短時(shí)間為66.83分鐘。以4：15P.M.這一時(shí)刻（記為0時(shí)刻，每過一秒鐘數(shù)值加1）所有航班起降為例，起飛次序及滑行路徑規(guī)劃如表2所示，所有航班的起降規(guī)劃分別如表3所示。

3 結(jié) 論

本算法起降完所有航班用時(shí)較計(jì)劃起降原計(jì)劃有所增加，故考慮實(shí)際起降效率，定義計(jì)劃與實(shí)際起降數(shù)量之比為起降效率P。原計(jì)劃P=18/27；本文的算法中P=19/2，起降效率提高8%左右，且可有效地避免A類穿插事件。本算法還可用于很多排班問題，如交通路網(wǎng)規(guī)劃、輪船調(diào)度等。

參考文獻(xiàn)：

[1] 李珍，張軍，張學(xué)軍.基于遺傳算法的航班離港調(diào)度建模及仿真 [J].交通與計(jì)算機(jī)，2008，26（6）：39-42.

[2] 余江，劉曉明，蒲云.飛機(jī)著陸調(diào)度問題的MPS優(yōu)化算法研究 [J].系統(tǒng)工程理論與實(shí)踐，2004（3）：119-122+133.

通訊作者：朱雪（1995-），女，漢族，河南商城人，本科在讀。研究方向：圖像處理。