虹橋機(jī)場航班智能調(diào)度問題

摘 要：機(jī)場航班智能調(diào)度已經(jīng)逐漸納入評價(jià)機(jī)場的重要條件之一，目前機(jī)場調(diào)度規(guī)則大多還是人工決策模式。本文針對曾發(fā)生嚴(yán)重 A 類穿越事件的上海虹橋機(jī)場航班調(diào)度建立了跑道服務(wù)智能調(diào)度模型，提高了飛機(jī)調(diào)度安全和提高準(zhǔn)點(diǎn)率和起降效率，與人工管理相比，極大地提高了機(jī)場的安全性能和利用率。本文建立了基于遺傳算法和元胞自動(dòng)機(jī)模型的目標(biāo)規(guī)劃模型，首先建立基本的安全等待模型，將機(jī)場抽象為有向節(jié)點(diǎn)圖，滑行道抽象為隊(duì)列結(jié)構(gòu)，規(guī)定滑行道上只有節(jié)點(diǎn)處能停放飛機(jī)，借用元胞自動(dòng)機(jī)的方法，模擬了飛機(jī)在滑行道上的運(yùn)動(dòng)情況。為了能較真實(shí)地模擬實(shí)際飛機(jī)的運(yùn)動(dòng)情況，得到更有價(jià)值的模擬數(shù)據(jù)，我們設(shè)定了一組描述飛機(jī)單向滑行和排隊(duì)等待的的狀態(tài)變換規(guī)則。我們重點(diǎn)考慮了飛機(jī)運(yùn)動(dòng)的起始條件，終止條件，前進(jìn)條件，排隊(duì)等待條件，變道條件和穿越跑道條件等，以期保障飛機(jī)起降時(shí)絕對的安全性。其次，我們建立了運(yùn)行效率較高的安全等待模型，設(shè)定了準(zhǔn)點(diǎn)率和起降效率的具體形式，我們用計(jì)劃與起飛時(shí)間的殘差和和準(zhǔn)點(diǎn)的飛機(jī)與總的飛機(jī)的比值共同描述飛機(jī)的準(zhǔn)點(diǎn)率，用飛機(jī)在滑行道上的等待時(shí)間描述起降效率。

關(guān)鍵詞： 機(jī)場調(diào)度；元胞自動(dòng)機(jī)模型

一、問題重述

（一）問題背景

2016 年 10 月 11 日，上海虹橋機(jī)場發(fā)生了由于人工調(diào)度而引起的安全事故。塔臺(tái)空管人員的人工指揮的失誤，造成東航一家 A320 客機(jī)在滑出跑道即將起飛時(shí)，發(fā)現(xiàn)另外一家 A330 客機(jī)正在橫穿跑道，不得不從 A330 的上空強(qiáng)行掠過，倘若沒有 A320 機(jī)長的決斷，這將會(huì)是一場可怕的空難。因此，人工決策不能有效的解決機(jī)場調(diào)度的安全問題和運(yùn)行效率問題，智能調(diào)度模型的建立和運(yùn)用將會(huì)是解決機(jī)場安全問題和提高機(jī)場運(yùn)行效率的一種穩(wěn)定性好的，可行性高的，可操作性強(qiáng)的解決方案。

（二）問題提出

借助計(jì)算機(jī)建立一種智能調(diào)度模型，在保證絕對安全的前提下提高機(jī)場的運(yùn)行效率，調(diào)度內(nèi)容主要包括航班的實(shí)時(shí)起飛降落時(shí)間，以及航班起飛前和降落后的地面規(guī)劃路徑。

問題 ：依據(jù)附件 1 所示的上海虹橋機(jī)場地形圖和附件 2 所列的 2017 年某日下午一小時(shí)內(nèi)的預(yù)降落和起飛航班信息，設(shè)計(jì)一個(gè)跑道服務(wù)智能調(diào)度模型，調(diào)度內(nèi)容包括空中飛機(jī)降落時(shí)間及降落后的運(yùn)動(dòng)規(guī)劃，以及地面飛機(jī)起飛前的運(yùn)動(dòng)規(guī)劃及起飛時(shí)間，安排所有航班的起飛和降落（包括次序、時(shí)間、地面滑行路徑）。調(diào)度模型優(yōu)先考慮跑道上飛機(jī)的安全，防止 A類穿越事件發(fā)生，在此基礎(chǔ)上考慮提高準(zhǔn)點(diǎn)率和起降效率.（當(dāng)時(shí)機(jī)場的風(fēng)向?yàn)橛杀毕蚰希L(fēng)速為 20km/h，飛機(jī)逆風(fēng)起飛，逆風(fēng)降落，滑行速度假設(shè)為 10節(jié)/小時(shí).）

二、模型假設(shè)

（一）基本假設(shè)

附件 2所給的航班信息數(shù)據(jù)真實(shí)可靠；

每架飛機(jī)在同一跑道上起飛所需的時(shí)間相同；

不考慮天氣、空中交通管制等其他因素對飛機(jī)等待時(shí)間的影響。

（二）針對有向節(jié)點(diǎn)圖的假設(shè)

機(jī)場跑道僅用作飛機(jī)的起降，而不充當(dāng)滑行道；

飛機(jī)等待起飛的滑行道為 6 和 7；

飛機(jī)只在橫向滑行道上穿越跑道；

只考慮起飛飛機(jī)在滑行道上等待起飛的時(shí)間，不考慮它從停機(jī)坪到滑行道入口的運(yùn)動(dòng)時(shí)間；

降落到T2 航站樓的飛機(jī)穿越起飛跑道后即完成降落，不考慮之后的運(yùn)動(dòng)；

平行滑行道 B 只允許飛機(jī)單向通行。

三、模型建立

（一）問題分析

在問題一中我們需要解決的是如何刻畫安全的狀態(tài)，我們選取兩種特殊的情況分析，其一，跑道上有飛機(jī)時(shí)，此時(shí)處于滑行道的飛機(jī)應(yīng)該設(shè)為等待狀態(tài)，其二，滑行道前方有飛機(jī)時(shí)設(shè)為等待狀態(tài)。同時(shí)設(shè)定 0-1 狀態(tài)變換規(guī)則集，規(guī)定后方飛機(jī)不能超越前方飛機(jī)，相向飛機(jī)不允許相遇，飛機(jī)之間保留有最小安全間隔。因此，在這些約束下，我們將定量問題轉(zhuǎn)換為邏輯判斷進(jìn)行安全性能的刻畫。同時(shí)，設(shè)定指標(biāo)集，設(shè)定準(zhǔn)點(diǎn)率為計(jì)劃時(shí)間和起飛時(shí)間的殘差和，設(shè)定起降效率為所有飛機(jī)的等待的時(shí)間和。利用這兩個(gè)指標(biāo)可以定量的描述智能調(diào)度模型的性能。

（二）模型的準(zhǔn)備

1.地圖的準(zhǔn)備

（三）基本安全模型的建立

這是研究飛機(jī)在滑行道上等待的基本模型，建立在安全的前提下。因?yàn)橐延屑僭O(shè)，飛機(jī)在滑行道上的的運(yùn)動(dòng)都是速度為 10 節(jié)（308/m/min）的勻速運(yùn)動(dòng)，由此計(jì)算得滑行道上的安全間隔距離約為 30m；根據(jù)文獻(xiàn)資料，滑行道的寬度只能允許一架飛機(jī)通過，所以假設(shè)飛機(jī)在所有滑行道上單向運(yùn)動(dòng)。在本題情況下，我們假定降落的飛機(jī)在中間平行滑行道上只能向北單方向運(yùn)動(dòng)，在橫向滑行道中職能向西單方向運(yùn)動(dòng)，這樣就可以防止飛機(jī)相遇、相撞等事件發(fā)生。

下面是本文設(shè)定的滿足安全條件的約束規(guī)則，主要是從飛機(jī)起飛、降落和轉(zhuǎn)移三種情況出發(fā)， 根據(jù)附件 2 中飛機(jī)基本從 T2 航站樓出發(fā)或?？康?T2 航站樓，可將 T2 航站樓的飛機(jī)作為主要研究對象，而將少量的 T1 航站樓的飛機(jī)等效于一個(gè)全局的時(shí)間延遲。同時(shí)，根據(jù)飛機(jī)路線分配的就近原則和起飛與降落的相互制約關(guān)系，可以手動(dòng)指定以下初始的路線分配。

（五）模型的求解

將機(jī)場滑行道布局為有向圖， 將跑道圖轉(zhuǎn)化為節(jié)點(diǎn)圖，并且針對節(jié)點(diǎn)圖中節(jié)點(diǎn)的關(guān)系，建立隊(duì)列圖 2。

元胞自動(dòng)機(jī)的模型假設(shè)。

1）不同飛機(jī)，型號不同，占有的節(jié)點(diǎn)數(shù)不同，單位周期移過的節(jié)點(diǎn)數(shù)也不同，具體大小根據(jù)滑行道長度和飛機(jī)長度確定；

2）飛機(jī)在改變方向和穿越跑道時(shí)不需要額外的時(shí)間；

3）每個(gè)細(xì)胞單元的長度約為 30m，寬度為滑行道的平均寬度 60m。不同滑行道由于長度的不同，上面的細(xì)胞個(gè)數(shù)也不同；

4）模擬的時(shí)間單位為 1分鐘，即每次刷新飛機(jī)的狀態(tài)，都經(jīng)過 1分鐘。

根據(jù)元胞自動(dòng)機(jī)的原理，我們很容易在建立碰撞不相撞的規(guī)則，設(shè)跑道上的節(jié)點(diǎn)為主節(jié)點(diǎn)，滑行道上的節(jié)點(diǎn)分為頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，建立隊(duì)列的關(guān)系圖，如圖3所示。

1）如果主節(jié)點(diǎn)被占用，則尾節(jié)點(diǎn)的飛機(jī)處于等待狀態(tài)，該架飛機(jī)的 0-1 狀態(tài)不改變，相當(dāng)于等紅綠燈的狀態(tài)。

2）如果主節(jié)點(diǎn)未被占用，則尾節(jié)點(diǎn)中的飛機(jī)可以行進(jìn)，該節(jié)點(diǎn)的 0-1 狀態(tài)改變。

3）兩個(gè)隊(duì)列的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)是常量，不會(huì)改變。

4）如果某個(gè)細(xì)胞的尾節(jié)點(diǎn)的一個(gè)細(xì)胞的狀態(tài)為 1，則該細(xì)胞內(nèi)的飛機(jī)處于等待狀態(tài)。

5）如果某個(gè)細(xì)胞的尾節(jié)點(diǎn)的一個(gè)細(xì)胞的狀態(tài)為 0，則該細(xì)胞內(nèi)的飛機(jī)可以行進(jìn)。

參考文獻(xiàn)：

[1]楊秋輝，游志勝，馮子亮，樊鴻.自適應(yīng)遺傳算法在飛機(jī)調(diào)度問題中的應(yīng)用.四川大學(xué)學(xué)報(bào)，2004.

作者簡介：王昱（1996-），漢族，女，陜西人，本科，就讀西北工業(yè)大學(xué)理學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)。