基于多目標(biāo)優(yōu)化的停機(jī)位再分配系統(tǒng)開發(fā)

懷永成 程鵬 王奕為 梁梓博 聶晨 喬龍

中國民航大學(xué) 300300

正文：

1 背景

對(duì)于機(jī)場運(yùn)行效率來說，合理有效的分配停機(jī)位，及在航班延誤的情況下在原有方案上進(jìn)行有效調(diào)整，是提高機(jī)場運(yùn)行效率的重要途徑。針對(duì)延誤問題，機(jī)場一般進(jìn)行人工調(diào)整，此方法是將延誤班機(jī)直接分配到遠(yuǎn)機(jī)位，此方法雖然簡單可行，但會(huì)給機(jī)場運(yùn)行帶來諸多問題，機(jī)場運(yùn)行效率降低，旅客滿意度下降，因此開發(fā)一套停機(jī)位再分配系統(tǒng)對(duì)機(jī)場來說就顯得極為重要

1.1 停機(jī)位分配的研究現(xiàn)狀

關(guān)于機(jī)位分配問題，國內(nèi)外很多學(xué)者在此方面已經(jīng)做了很多研究。我們閱讀了近四十篇關(guān)于停機(jī)位分配的文獻(xiàn)來了解機(jī)場運(yùn)行相關(guān)的一些專業(yè)知識(shí)，了解停機(jī)位初次分配的機(jī)理，并考慮能否再機(jī)位再分配的過程中加以運(yùn)用。在模型的最終目標(biāo)方面：航班延誤成本、機(jī)場運(yùn)行的安全性、航班間晚點(diǎn)傳播、航班延誤和停機(jī)位空閑時(shí)間、跑道頭滑行到停機(jī)位的時(shí)間與停機(jī)位到達(dá)航站樓的時(shí)間、機(jī)跑道行駛路程及時(shí)間、飛機(jī)油耗量、機(jī)場系統(tǒng)運(yùn)行擾動(dòng)大機(jī)位利用率、航班的分配次序及機(jī)場的收益都曾被專家學(xué)者納入考慮范疇加以研究；模型的約束條件需要考慮的因素頗為相近，航班與機(jī)位的獨(dú)占性、機(jī)型與機(jī)位的匹配要求及航班運(yùn)行的緩沖時(shí)間是研究重點(diǎn)

1.2 停機(jī)再位分配的研究現(xiàn)狀

在航班再分配問題中大多數(shù)作者都基于航班延誤，根據(jù)提高機(jī)場運(yùn)行效率和顧客滿意度的優(yōu)化原則，進(jìn)行優(yōu)化設(shè)計(jì)求解。劉長有，曹強(qiáng)考慮了停機(jī)坪的航班數(shù)最少和停機(jī)位分配擾動(dòng)最少及占用時(shí)間均衡的目標(biāo)函數(shù)，其創(chuàng)新于在其模型中引入了安全性的約束條件避免潛在的航班雙推沖突，利用粒子群遺傳算法求解。衛(wèi)東選，也考慮了分配到遠(yuǎn)機(jī)位的航班數(shù)最少及擾動(dòng)性最小為優(yōu)化目標(biāo)，采用混合算法求解。

2.模型建立

為了全面地分析掌握機(jī)場停機(jī)位再分配模型的目標(biāo)和約束條件，滿足機(jī)場的真正需求。我們小組特意開展了實(shí)地調(diào)研活動(dòng)，派出代表分別以天津?yàn)I海國際機(jī)場、南京祿口國際機(jī)場和深圳寶安機(jī)場為對(duì)象深入調(diào)研。聶晨在天津?yàn)I海國際機(jī)場為期一周的實(shí)習(xí)過程中，在天津機(jī)場的應(yīng)急救援指揮中心進(jìn)行見習(xí)，旁觀了每日的例行民航總局會(huì)議，并參觀了停機(jī)坪及停機(jī)位，認(rèn)真地參加了機(jī)場工作人員的講座。懷永成通過與深圳寶安機(jī)場的宋兆康學(xué)長的多次交流，吸取了很多寶貴的一線經(jīng)驗(yàn)。梁梓博、喬龍去到南京祿口國際機(jī)場開展了為期三天的調(diào)研活動(dòng)，深入到南京機(jī)場的運(yùn)行指揮中心，同運(yùn)行指揮中心的學(xué)長認(rèn)真地探討了停機(jī)位的分配問題。通過與這三個(gè)機(jī)場的一線人員的交流以及小組成員之間的討論，我們最終確定了停機(jī)位再分配模型的最為迫切需要改進(jìn)的兩個(gè)目標(biāo)（變動(dòng)機(jī)位最少、近機(jī)位使用最多）和一個(gè)約束條件（緩沖時(shí)間約束）。

同時(shí)，為了使我們的分配模型更有科學(xué)依據(jù)和說服力，我們查閱了大量相關(guān)資料和與指導(dǎo)老師深入探討和推敲，最終確定了停機(jī)位再分配模型的另外一個(gè)目標(biāo)（旅客行走距離最短）和兩個(gè)約束條件（獨(dú)立性約束條件，每個(gè)航班必須分配到一個(gè)機(jī)位；機(jī)位匹配約束）。至此，停機(jī)位分配模型的目標(biāo)和約束條件基本確立。

3.算法實(shí)現(xiàn)

針對(duì)機(jī)場機(jī)位分配問題的特性，直接求解多目標(biāo)優(yōu)化問題的優(yōu)化較為困難，本文采用YALMIP工具箱進(jìn)行求解。

3.1 目標(biāo)函數(shù)

目標(biāo)函數(shù)是YALMIP工具箱中求解最優(yōu)解問題的關(guān)鍵。本文以旅客行走距離最短，表示為，Ni為航班fi進(jìn)港或離港的旅客總?cè)藬?shù)，Lkl為停機(jī)位fk到fl的距離；變動(dòng)機(jī)位最少，表示為，當(dāng)機(jī)位改變時(shí)Si=1，機(jī)位不變時(shí)Si=0；近機(jī)位使用最多，表示為，Zi表示航班fi分到近機(jī)位為1，否則為0；以上三個(gè)條件為目標(biāo)構(gòu)建目標(biāo)函數(shù)。

3.2 約束條件

YALMIP工具箱求解多目標(biāo)線性優(yōu)化需要設(shè)立求解的約束條件。此處為作機(jī)位的獨(dú)立性約束、機(jī)位匹配約束和機(jī)位緩沖時(shí)間約束。獨(dú)立性約束即每個(gè)航班必須分配到一個(gè)機(jī)位，表示為，yik表示航班i分配到k機(jī)位時(shí)值為1，否則為0；機(jī)位匹配約束主要體現(xiàn)為機(jī)位大小對(duì)停靠飛機(jī)限制的約束。表示為bi＞ai，成立時(shí)為1，不成立時(shí)為0。

確定了目標(biāo)函數(shù)和約束條件后，調(diào)用YALMIP工具箱函數(shù)。使用binvar命令生成初始機(jī)型分配矩陣，在約束條件下計(jì)算目標(biāo)函數(shù)的最小值，此時(shí)最小值對(duì)應(yīng)的機(jī)位分配矩陣就是最優(yōu)的分配方案。

4.結(jié)果分析

我們從北京首都機(jī)場的某一天航班信息中篩選了40個(gè)在T3航站樓運(yùn)行的航班，航班號(hào)、計(jì)劃到達(dá)時(shí)間、預(yù)計(jì)分配機(jī)位，我們假設(shè)這些航班一共使用20個(gè)機(jī)位，其中5-15機(jī)位是近機(jī)位，其他機(jī)位為遠(yuǎn)機(jī)位，并按相對(duì)情況假設(shè)各個(gè)機(jī)位間的距離。

由于天氣或其他原因，一部分航班有不同程度的延誤，導(dǎo)致初次分配的機(jī)位不再適用，我們設(shè)置航班延誤時(shí)間超過15分鐘要進(jìn)行機(jī)位的再次分配，通過我們的模型的到的再分配機(jī)位如表4-1

表4 -1

5.軟件整合

5.1 開發(fā)環(huán)境：

Python 3.7

Spyder

Matlab

5.2 開發(fā)架構(gòu)：

Tkinter：應(yīng)用tkinter庫所帶控件和函數(shù)，在維持主界面不斷刷新的同時(shí)，將航班再分配信息讀入，分條顯示在屏幕左右兩個(gè)區(qū)域。左區(qū)按條顯示初始航班信息，包含序號(hào)，航班號(hào)，航班計(jì)劃時(shí)間，航班使用機(jī)型以及計(jì)劃分配機(jī)位。再點(diǎn)擊更新按鈕后，逐條顯示再分配信息在右側(cè)區(qū)域，包含航班實(shí)際時(shí)間和實(shí)際分配機(jī)位，并適當(dāng)滾動(dòng)，與左側(cè)同步顯示。

5.3 軟件功能：

整合航班再分配信息，在可視化界面顯示

5.4 軟件流程：

主界面-＞初始航班信息-＞讀入運(yùn)行在分配算法后的結(jié)果-＞點(diǎn)擊更新-＞按條輸出顯示