基于Floyd、FCFS和SJF算法的機場智能調度

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

關鍵詞：Floyd算法；FCFS/SJF算法；向圖；多跑道調度

中圖分類號：V355；TP18 文獻標識碼：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日，在上海虹橋機場：東航一架A320客機在滑出跑道即將起飛時發(fā)現另一架A330客機正在橫穿跑道。A320客機緊急起飛，從A330上方掠過，避免了一起慘烈空難的發(fā)生，這是一起嚴重的A類穿越事件。近日搜索各航班信息平臺不難發(fā)現，各地區(qū)機場出現延誤的原因中，除天氣因素外，大部分顯示“受流控影響”，航班準點率低于30%，最低甚至僅為4%。因而導致乘客產生情緒化行為，使得機場現有的管理模式面臨重重危機。

1.2 問題

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

2 智能調度算法

2.1 Floyd算法調度

2.1.1 建立最短路徑模型

Step 1 建坐標系首先將虹橋機場的地圖轉化為坐標系如圖1所示。

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

Step 3 計算可達距離。將各架飛機看作質點，將整個機場看作一個圖，則飛機i到達路口j的可達距離dij為：

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

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

2.1.2 確定最短路徑

Step 1 確定坐標。根據虹橋機場地圖及比例，可得到各節(jié)點坐標。圖1中①～⑩點坐標為：

（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 運用Floyd算法求解最短距離。將表1代入式（1），則任意可直接到達的節(jié)點間距離dij，使用Floyd算法迭代可得航班降落且停在T2航站樓的最短路徑（序號見圖1）為：

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

2.2 FCFS/SJF算法調度

2.2.1 建立最短起降所有航班時間模型

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

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

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

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

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

2.2.2 確定最短起降所有航班時間

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

3 結 論

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

參考文獻：

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

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

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