Top-k停機位推薦問題研究

吳彬林，梁磊，繆楊帆，李川（.國家金屬制品質檢中心，鄭州　450000；.中國石化潤滑油有限公司鄭州分公司，鄭州　450000；.四川大學計算機學院，四川　60065）

Top-k停機位推薦問題研究

吳彬林1，梁磊2，繆楊帆3，李川3
（1.國家金屬制品質檢中心，鄭州450000；2.中國石化潤滑油有限公司鄭州分公司，鄭州450000；3.四川大學計算機學院，四川610065）

0　引言

停機位是機場運營的重要資源，是飛機在地面活動的中心，合理高效地分配停機位是機場管理的重要內容［1］。停機位分配是指給未來一段時間內進離港航班的飛機分配一個停機位，以保證旅客正常有序的上下飛機。合理高效的停機位分配方案能很大程度上提高機場資源的利用率，提高旅客對機場和航空公司的滿意程度。機場停機位分配問題是機場地面作業中的一項核心任務。如何分配好停機位，是一個很復雜的問題，需要考慮很多因素。文獻［2］提出停機位物理特性，航班飛行時長，機場經營管理的商務約束，航班優先級，飛機停場時長，遠停機位與靠橋停機位的選擇等因素，這些因素都對停機位的分配起著至關重要的作用。

目前，研究人員對停機位分配問題進行了深入的研究，提出了大量的停機位分配模型，這些模型都在一定程度上提高了機場的運營管理效率。文獻［4］將這些模型主要分為兩類：一類是專家系統，基于分配原則建立知識庫系統，考慮較多的非量化準則，文獻［5］由知識的組成出發，給出基于關系型數據庫的通用知識庫結構設計，同時用拆分規則的形式化方法表示知識，來完善地表達事實規則體系知識，使推理過程簡單、高效；另一類是基于數學規劃的方法，建立目標函數，進行優化求解。文獻［6］、［7］、［8］考慮的主要目標函數實質是一致的，都是使旅客滿意度最優化。文獻［3］、［9］、［10］則通過機場運營角度來考慮優化停機位分配問題，具有較好的魯棒性，減少航班延誤帶來的影響。但隨著問題影響因素維度的增加，解空間將呈爆炸式增長，隨機算法難以得到全局最優解?；趯＜蚁到y的方法往往受制于搜索范圍，忽視關鍵因素而導致分配結果不理想；后一方法受目標函數的影響很大，優化的維度很多時，將導致計算量的指數級增長，并且會經常出現將較多的航班分配給較少的有吸引力的停機位的情況。

文獻［11］指出基于統計分析的方法在自然語言處理、語音識別、多媒體及推薦系統等領域中，都有很廣泛的應用，且已取得較好的效果。因此，本研究采用統計分析的思想來進行停機位分配。首先，停機位分配的歷史數據中已經潛藏著大量的知識信息；其次，這些知識是不能窮盡列舉出來，如曾采用過多種優化方法進行停機位分配，則對歷史停機位分配數據的統計分析就能得到更均衡的分配方案。再次，停機位分配不得不需要業務員的參與，新業務員往往缺乏經驗，而對歷史數據進行分析，然后推薦分配停機位，能讓新業務員對停機位分配有據可依。

1　基于統計分析的停機位分配推薦模型

停機位分配需滿足固定強規則（商務規則、停機位與飛機規格約束和固定停機位等）和適當弱規則（航班優先級相關規則，如，停場時間、旅客數量等）。經過規則的過濾得到初步的候選停機位，然后利用訓練出的停機位分配模型推薦Top-k個停機位。

對每個航班賦予一個優先級P，x是需要考慮的弱規則，而β是各規則對應的權重，根據不同階段實際的需求可以調整各個規則的權重，達到按需優先的目的。也可以擬合數據得到適當的權重參數。

推薦停機位概率：

xi為弱規則，k為航班，y為停機位。對訓練數據進行統計分析，運用貝葉斯方法，可算出弱規則集X下，分配停機位y概率。按概率進行排序后，得到Top-k個推薦停機位。

例如，現有航班3U8555和8Y9034機型分別為320和738，降落時間同為早上八點十分，利用弱規則算出這兩個航班的優先級，假設算出的優先級3U8555高于8Y9034，則在航班優先級隊列中3U8555位于隊首，8Y9034位于其后，從優先級隊列中取出優先級最高的航班3U8555，用強規則 （航空公司3U機型320等）過濾出可用停機位列表，再利用航班信息和可用停機位列表應用推薦模型得到分配概率最大的k個停機位。該例只是簡要的介紹模型功能，實際中的優先級計算和強規則過濾是比較復雜的過程。

模型執行流程如圖1所示。

2　數據說明

實驗數據采用了某機場2012年5月1日至2013 年4月10日的產生的航班信息，里面包括了航班號、機型、起降時間、延誤信息、載客數等。還包括各航空公司信息數據以及該機場的停機位-機型約束數據，停機位基礎信息數據，停機位-任務數據和停機位優先規則數據。

圖1　基于統計分析的停機位分配推薦系統流程圖

篩選出的航班屬性如下：

航班編號，飛機型號，航線，停機位，降落時間，起飛時間，進港人數，離港人數。

經過預處理后提取出的數據用JSON格式表示如下：

各字段如表1所示：

表1　停機位信息表

對歷史數據的訓練結果trainResults.json

因為不同時段，停機位分配的策略有很大差異，比如：早上、中午和下午到達的過夜飛機傾向于遠停機位?？?，而晚間飛機更多靠橋?？?。為了利用這些知識，可將航班按時間段劃分為四個區間，如表2所示：

表2　時間段標識碼表

訓練結果中的key值中包含了時段的信息，value值代表了A航空公司B機型C時段停在Dk停機位的頻數，表示為S（Dk|A，B，C），那么A航空公司B機型C時段停在Dk停機位的條件概率為：

3　Top-k停機位推薦KGatesRec算法

該KGatesRec算法偽代碼如下：

航班的選取策略：如果flights隊首航班為出港航班，則直接選取該航班并返回；如果flights隊首航班為入港航班，則在沖突時間范圍（10分鐘）內的進港航班中選取權重最高的航班。

●allocateAGate（flight）：為一個航班獲取推薦停機位。具體步驟如下：

●根據bitMapOfGates獲取機場空閑停機位集合totalGates。

（1）根據GatesInfo選出航班滿足停機位-航空公司和停機位-機型約束的停機位集合companyAndType-Gates。

（2）對totalGates和companyAndTypeGates求交集得到可用停機位集合emptyGates。

（3）對emptyGates中的停機位，結合航班信息查詢trainResults中的數據，按照頻次進行排序，選前k個停機位，得到Top-k推薦停機位列表recGates，并返回。

半柔性路面作為一種新型路面結構，是將一定級配的水泥砂漿灌入到大空隙母體瀝青混凝土中，具有高于水泥混凝土柔性和瀝青混凝土剛性的特點。半柔性路面在國外已進行了大量的研究和應用，實際工程中表現出良好的高溫性能、水穩定性等使用性能，且具有較小的線收縮系數。但國內對半柔性路面的研究仍處于起步階段，對原材料指標、級配和施工工藝沒有統一的技術標準。本文針對高性能半柔性路面，結合實際工程的應用，提出一套系統的施工工藝和質量控制標準，為以后半柔性路面技術的應用奠定基礎。

●updateBitMapOfGates（flight，flights）：更新停機位位圖表。

因為是從實際的歷史數據出發，并不能真正得到某時刻完全正確的停機位狀態。本研究假設機場在執行若干天航班后，停機位的占用狀態接近真實的狀態，這樣就得到了某一時刻接近真實的停機位狀態。晚間飛機通常會分配在靠橋停機位，然后依據該飛機第二天計劃航班情況可能會被調整到遠停機位，而數據當中缺少停機位調整的相關信息，這樣必定會造成一定的誤差?？梢砸勒盏诙鞂嶋H安排航班情況來確定?？吭谠摽繕蛲C位的飛機是否調整到遠停機位過夜。具體策略如下：

（1）如果該飛機今天不過夜，則飛機進港停機位分配后，對停機位加鎖，并更新對應離場航班的停機位，飛機離港后對停機位解鎖。

（2）如果是過夜飛機，離港時如果停機位為空，則說明對該飛機的?？客C位進行過調整，需要在未加鎖的停機位中找出同航空公司同機型的飛機，并將該停機位占用狀態置空。

4　實驗

實驗的訓練數據是采用某機場自2012年5月1日至2013年4月10日產生的航班數據。用2012年8 月21日數據來估算停機位占用狀態，測試數據為2012 年8月22日的航班，其中進港航班334次，出港航班335次。

航班的優先級計算選取了停場時間和進出港人數這兩個特征，權重分別設定為1和1/200，Top-k中k值取10，即每次推薦十個停機位。

4.1實驗環境

操作系統：Microsoft Windows 7旗艦版（64位）

處理器：Intel Core i5-2450M CPU@2.50GHz

內存：4.00 GB（1333 MHz）

運行平臺：Python 2.7［12］［13］［14］

4.2實驗結果

表3列出了2012年8月22日航班數據的部分測試情況，各字段意義如下：

序號：航班的執行順序。航班號：規定的航班號。航線：飛機飛行的路線。

航班類型：O-說明執行的航班為出港航班；I-說明執行的航班為進港航班。

進離港時間：航班類型為O，為進港時間，航班類型為I，為出港時間。

另外，本研究還對實驗的結果進行了統計，圖2～圖6顯示了一天中各個時段和全天的推薦命中情況，其中推薦命中指的是與歷史數據中業務員的分配結果一致。X軸表示命中時命中的停機位在推薦列表中的位置，Y軸表示命中次數。

表3　2012年8月22日部分航班執行情況表

例如，圖2中X=1，Y=21表示推薦列表的第一個結果命中的次數為21次，而X=0，Y=13表示實際的分配結果不在推薦列表中次數為13。

圖7顯示的是各時段top-10總體命中情況，命中率均在60%～80%之間。圖8顯示的是不同k值對推薦精度的影響。

圖2　早上推薦命中情況

圖3　中午推薦命中情況

圖4　下午推薦命中情況

圖5　晚上推薦命中情況

圖6　全天推薦命中情況

圖7　各時段總體命中情況

4.3實驗分析

本研究在實驗過程中發現，推薦列表沒有命中的時候，絕大多數是因為該時段該航空公司的該機型數量很少（或許屬于非固定航班），從而導致推薦列表中推薦列表中大部分停機位頻數都為1，表現出對該時段該航空公司該機型停機位分配的隨機性。

圖8　不同top-k命中情況

推薦命中的精度也與時段有關，在圖7中可以發現，早上和晚上的推薦精度比中午和下午的推薦精度要高，早上推薦精度較高是因為出港的航班較多（進港52，出港68）；中午進出港航班數幾乎持平（進港102，出港100）命中率略微下降；下午的進港航班數（68）大于出港航班數（54），導致機場擁堵情況加劇，從而命中率降低；而晚上進出港航班數幾乎持平（進港112，出港111），命中率較下午要高。

對于不同k的取值，推薦命中精度也有很大的不同。推薦命中精度隨著k值的增大而增大，當k增大到6之后增速會明顯減緩，而且k取值越大，推薦的價值就越小，因此選取合適的k值也是影響推薦精度的一個重要方面，實驗結果表明k取值3～6較為合適。

5　結語

停機位分配是機場運營管理的關鍵環節。合理高效的停機位分配方案，能提高機場的運營效率，使機場和航空公司達到雙贏。本研究采用基于統計分析的全新方法，來解決停機位分配問題。通過挖掘歷史運營數據中潛藏的大量知識信息，構建了一個停機位分配推薦模型，并提出了對停機位分配進行Top-k推薦的KGatesRec算法。

本研究在真實的數據集上進行實驗，實驗結果證明了該模型的有效性，本研究也從多個方面對實驗結果進行了分析，合理解釋了算法的有效性。

未來的工作，主要包括對停機位進行聚類分析［17］，視同一類的停機位等效，再進行推薦；考慮更多的航班信息來計算優先級，例如航班延誤率、航班任務類型和離港時間等。

［1］高菁，楊旭東.基于規則的機位分配問題研究［J］.計算機科學，2012，39（z1）.

［2］伍嶺.機位分配背后的學問［J］.中國民用航空，2007，07:51-52.

［3］劉兆明，葛宏偉，錢鋒.基于遺傳算法的機場調度優化算法［J］.華東理工大學學報（自然科學版），2008，03:392-398.

［4］楊守劍，白存儒.機場停機位優化分配研究［J］.航空工程進展，2010，03:301-305.

［5］周至，孟波.機場機位自動分配系統知識庫的研究與設計［J］.計算機工程，2004，06:145-147+161.

［6］Xu J.，Huo C.The Airport Gate Assignment Problem:Mathematical Model and a Tabu Search Algorithm［C］.Proceedings of the 34th Hawaii International Conference on System Sciences，Hawaii，2001：102-111.

［7］Ding H.，Lim.A.，Rodrigues B.，Zhu Y.Aircraft and Gate Scheduling Optimization at Aitports［C］.Proceedings of the 37th Hawaii International Conference on System Sciences，Hawaii，2004：74-81.

［8］王力，劉長有，涂奉生.民用機場停機位優化配置［J］.南京航空航天大學學報，2006，38（4）：433-437.

［9］Bolat A.Models and a Genetic Algorithm for Static Aircraft-Gate Assignment Problem［J］.Journal of the Operational Research Society 2001，52：1107-1120.

［10］Lim A.，Wang F.Robust Airport Gate Assignment［C］.Proceedings of 17th International Conference on Tools with Artificial Intelligence，Hong Kong，November 14-16，2005.

［11］吳軍.數學之美［M］.第1版.北京：人民郵電出版社，2012.

［12］Punch W F，Enbody R.The Practice of Computing Using Python［M］.Addison-Wesley Publishing Company，2010.

［13］Chun W J.Core Python Programming［M］.Prentice Hall PTR，2006.

［14］Hetland M L.Beginning Python:from Novice to Professional［M］.Dreamtech Press，2008.

［15］Ross S M.Introduction to Probability Models［M］.Academic press，2006.

［16］盛驟，謝式千，潘承毅.概率論與數理統計［J］.北京:高等教育出板社，2006.

Aircraft Parking Location Allocation；Top-k

Research on the Aircraft Parking Position Recommended Using Top-k Optimization

WU Bin-lin1，LIANG Lei2，MIU Yang-fan3，LI Chuan3
（1.National Metal Products Quality Inspection Center，Zhengzhou 450000；2.Sinopec Lubricating Oil Co.，Ltd.Zhengzhou Branch，Zhengzhou 450000；3.School of Computer Science，Sichuan University，Sichuan 610065）

1007-1423（2016）18-0003-06

10.3969/j.issn.1007-1423.2016.18.001

吳彬林（1969-），男，工程師，研究方向為數據庫及應用

梁磊（1973-），男，工程師，研究方向為數據庫及應用

繆楊帆（1994-），女，在讀研究生，研究方向為數據挖掘

李川（1977-），男，副教授，博士，研究方向為數據庫、數據挖掘，Email:lcharles@scu.edu.cn

2016-05-17

2016-06-05

停機位分配是機場運營管理的關鍵技術環節，合理高效的停機位分配策略能在很大程度上提高機場的運營效率，使航空公司和機場達到雙贏?；诮y計分析的思想，對往期停機位分配數據進行統計，得到停機位分配策略模型，再結合推薦系統的模式，為業務員提供Top-k個分配停機位推薦服務。這種利用歷史數據經過訓練得到的模型，使得新手業務員能借鑒資深業務員的分配經驗進行停機位分配，從而提高機場運營效率，也能避免由業務員疏忽大意而造成的損失。實驗表明基于統計分析的Top-k停機位推薦方法，具有較好的推薦覆蓋率和準確率。

停機位分配；Top-k

Aircraft parking location allocation is the key technology of airport operation management，reasonable and efficient aircraft parking location allocation strategy can largely improve the operational efficiency of the airport，make the airlines and airports to achieve a win-win situation.Based on the statistical analysis of the previous allocation of aircraft parking position data and statistics，obtains the position assignment policy model，combined with the recommender system model Top-k were allocated parking location for sales referral service. Uses historical data，with training the model，makes newbie salesman to benefit from the allocation of senior sales experience in the allocation of parking bays，so as to improve the operational efficiency，it can avoid by sales losses due to negligence.Experiments show that stands at Top-k recommendation method based on statistical analysis，and recommended better coverage and accuracy.