Top-k停機(jī)位推薦問題研究

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

Top-k停機(jī)位推薦問題研究

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

0　引言

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

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

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

1　基于統(tǒng)計(jì)分析的停機(jī)位分配推薦模型

停機(jī)位分配需滿足固定強(qiáng)規(guī)則（商務(wù)規(guī)則、停機(jī)位與飛機(jī)規(guī)格約束和固定停機(jī)位等）和適當(dāng)弱規(guī)則（航班優(yōu)先級相關(guān)規(guī)則，如，停場時(shí)間、旅客數(shù)量等）。經(jīng)過規(guī)則的過濾得到初步的候選停機(jī)位，然后利用訓(xùn)練出的停機(jī)位分配模型推薦Top-k個(gè)停機(jī)位。

對每個(gè)航班賦予一個(gè)優(yōu)先級P，x是需要考慮的弱規(guī)則，而β是各規(guī)則對應(yīng)的權(quán)重，根據(jù)不同階段實(shí)際的需求可以調(diào)整各個(gè)規(guī)則的權(quán)重，達(dá)到按需優(yōu)先的目的。也可以擬合數(shù)據(jù)得到適當(dāng)?shù)臋?quán)重參數(shù)。

推薦停機(jī)位概率：

xi為弱規(guī)則，k為航班，y為停機(jī)位。對訓(xùn)練數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，運(yùn)用貝葉斯方法，可算出弱規(guī)則集X下，分配停機(jī)位y概率。按概率進(jìn)行排序后，得到Top-k個(gè)推薦停機(jī)位。

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

模型執(zhí)行流程如圖1所示。

2　數(shù)據(jù)說明

實(shí)驗(yàn)數(shù)據(jù)采用了某機(jī)場2012年5月1日至2013 年4月10日的產(chǎn)生的航班信息，里面包括了航班號(hào)、機(jī)型、起降時(shí)間、延誤信息、載客數(shù)等。還包括各航空公司信息數(shù)據(jù)以及該機(jī)場的停機(jī)位-機(jī)型約束數(shù)據(jù)，停機(jī)位基礎(chǔ)信息數(shù)據(jù)，停機(jī)位-任務(wù)數(shù)據(jù)和停機(jī)位優(yōu)先規(guī)則數(shù)據(jù)。

圖1　基于統(tǒng)計(jì)分析的停機(jī)位分配推薦系統(tǒng)流程圖

篩選出的航班屬性如下：

航班編號(hào)，飛機(jī)型號(hào)，航線，停機(jī)位，降落時(shí)間，起飛時(shí)間，進(jìn)港人數(shù)，離港人數(shù)。

經(jīng)過預(yù)處理后提取出的數(shù)據(jù)用JSON格式表示如下：

各字段如表1所示：

表1　停機(jī)位信息表

對歷史數(shù)據(jù)的訓(xùn)練結(jié)果trainResults.json

因?yàn)椴煌瑫r(shí)段，停機(jī)位分配的策略有很大差異，比如：早上、中午和下午到達(dá)的過夜飛機(jī)傾向于遠(yuǎn)停機(jī)位?？浚黹g飛機(jī)更多靠橋?？俊榱死眠@些知識(shí)，可將航班按時(shí)間段劃分為四個(gè)區(qū)間，如表2所示：

表2　時(shí)間段標(biāo)識(shí)碼表

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

3　Top-k停機(jī)位推薦KGatesRec算法

該KGatesRec算法偽代碼如下：

航班的選取策略：如果flights隊(duì)首航班為出港航班，則直接選取該航班并返回；如果flights隊(duì)首航班為入港航班，則在沖突時(shí)間范圍（10分鐘）內(nèi)的進(jìn)港航班中選取權(quán)重最高的航班。

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

●根據(jù)bitMapOfGates獲取機(jī)場空閑停機(jī)位集合totalGates。

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

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

（3）對emptyGates中的停機(jī)位，結(jié)合航班信息查詢trainResults中的數(shù)據(jù)，按照頻次進(jìn)行排序，選前k個(gè)停機(jī)位，得到Top-k推薦停機(jī)位列表recGates，并返回。

半柔性路面作為一種新型路面結(jié)構(gòu)，是將一定級配的水泥砂漿灌入到大空隙母體瀝青混凝土中，具有高于水泥混凝土柔性和瀝青混凝土剛性的特點(diǎn)。半柔性路面在國外已進(jìn)行了大量的研究和應(yīng)用，實(shí)際工程中表現(xiàn)出良好的高溫性能、水穩(wěn)定性等使用性能，且具有較小的線收縮系數(shù)。但國內(nèi)對半柔性路面的研究仍處于起步階段，對原材料指標(biāo)、級配和施工工藝沒有統(tǒng)一的技術(shù)標(biāo)準(zhǔn)。本文針對高性能半柔性路面，結(jié)合實(shí)際工程的應(yīng)用，提出一套系統(tǒng)的施工工藝和質(zhì)量控制標(biāo)準(zhǔn)，為以后半柔性路面技術(shù)的應(yīng)用奠定基礎(chǔ)。

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

因?yàn)槭菑膶?shí)際的歷史數(shù)據(jù)出發(fā)，并不能真正得到某時(shí)刻完全正確的停機(jī)位狀態(tài)。本研究假設(shè)機(jī)場在執(zhí)行若干天航班后，停機(jī)位的占用狀態(tài)接近真實(shí)的狀態(tài)，這樣就得到了某一時(shí)刻接近真實(shí)的停機(jī)位狀態(tài)。晚間飛機(jī)通常會(huì)分配在靠橋停機(jī)位，然后依據(jù)該飛機(jī)第二天計(jì)劃航班情況可能會(huì)被調(diào)整到遠(yuǎn)停機(jī)位，而數(shù)據(jù)當(dāng)中缺少停機(jī)位調(diào)整的相關(guān)信息，這樣必定會(huì)造成一定的誤差?？梢砸勒盏诙鞂?shí)際安排航班情況來確定停靠在該靠橋停機(jī)位的飛機(jī)是否調(diào)整到遠(yuǎn)停機(jī)位過夜。具體策略如下：

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

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

4　實(shí)驗(yàn)

實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)是采用某機(jī)場自2012年5月1日至2013年4月10日產(chǎn)生的航班數(shù)據(jù)。用2012年8 月21日數(shù)據(jù)來估算停機(jī)位占用狀態(tài)，測試數(shù)據(jù)為2012 年8月22日的航班，其中進(jìn)港航班334次，出港航班335次。

航班的優(yōu)先級計(jì)算選取了停場時(shí)間和進(jìn)出港人數(shù)這兩個(gè)特征，權(quán)重分別設(shè)定為1和1/200，Top-k中k值取10，即每次推薦十個(gè)停機(jī)位。

4.1實(shí)驗(yàn)環(huán)境

操作系統(tǒng)：Microsoft Windows 7旗艦版（64位）

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

內(nèi)存：4.00 GB（1333 MHz）

運(yùn)行平臺(tái)：Python 2.7［12］［13］［14］

4.2實(shí)驗(yàn)結(jié)果

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

序號(hào)：航班的執(zhí)行順序。航班號(hào)：規(guī)定的航班號(hào)。航線：飛機(jī)飛行的路線。

航班類型：O-說明執(zhí)行的航班為出港航班；I-說明執(zhí)行的航班為進(jìn)港航班。

進(jìn)離港時(shí)間：航班類型為O，為進(jìn)港時(shí)間，航班類型為I，為出港時(shí)間。

另外，本研究還對實(shí)驗(yàn)的結(jié)果進(jìn)行了統(tǒng)計(jì)，圖2～圖6顯示了一天中各個(gè)時(shí)段和全天的推薦命中情況，其中推薦命中指的是與歷史數(shù)據(jù)中業(yè)務(wù)員的分配結(jié)果一致。X軸表示命中時(shí)命中的停機(jī)位在推薦列表中的位置，Y軸表示命中次數(shù)。

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

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

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

圖2　早上推薦命中情況

圖3　中午推薦命中情況

圖4　下午推薦命中情況

圖5　晚上推薦命中情況

圖6　全天推薦命中情況

圖7　各時(shí)段總體命中情況

4.3實(shí)驗(yàn)分析

本研究在實(shí)驗(yàn)過程中發(fā)現(xiàn)，推薦列表沒有命中的時(shí)候，絕大多數(shù)是因?yàn)樵摃r(shí)段該航空公司的該機(jī)型數(shù)量很少（或許屬于非固定航班），從而導(dǎo)致推薦列表中推薦列表中大部分停機(jī)位頻數(shù)都為1，表現(xiàn)出對該時(shí)段該航空公司該機(jī)型停機(jī)位分配的隨機(jī)性。

圖8　不同top-k命中情況

推薦命中的精度也與時(shí)段有關(guān)，在圖7中可以發(fā)現(xiàn)，早上和晚上的推薦精度比中午和下午的推薦精度要高，早上推薦精度較高是因?yàn)槌龈鄣暮桨噍^多（進(jìn)港52，出港68）；中午進(jìn)出港航班數(shù)幾乎持平（進(jìn)港102，出港100）命中率略微下降；下午的進(jìn)港航班數(shù)（68）大于出港航班數(shù)（54），導(dǎo)致機(jī)場擁堵情況加劇，從而命中率降低；而晚上進(jìn)出港航班數(shù)幾乎持平（進(jìn)港112，出港111），命中率較下午要高。

對于不同k的取值，推薦命中精度也有很大的不同。推薦命中精度隨著k值的增大而增大，當(dāng)k增大到6之后增速會(huì)明顯減緩，而且k取值越大，推薦的價(jià)值就越小，因此選取合適的k值也是影響推薦精度的一個(gè)重要方面，實(shí)驗(yàn)結(jié)果表明k取值3～6較為合適。

5　結(jié)語

停機(jī)位分配是機(jī)場運(yùn)營管理的關(guān)鍵環(huán)節(jié)。合理高效的停機(jī)位分配方案，能提高機(jī)場的運(yùn)營效率，使機(jī)場和航空公司達(dá)到雙贏。本研究采用基于統(tǒng)計(jì)分析的全新方法，來解決停機(jī)位分配問題。通過挖掘歷史運(yùn)營數(shù)據(jù)中潛藏的大量知識(shí)信息，構(gòu)建了一個(gè)停機(jī)位分配推薦模型，并提出了對停機(jī)位分配進(jìn)行Top-k推薦的KGatesRec算法。

本研究在真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了該模型的有效性，本研究也從多個(gè)方面對實(shí)驗(yàn)結(jié)果進(jìn)行了分析，合理解釋了算法的有效性。

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

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

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

［3］劉兆明，葛宏偉，錢鋒.基于遺傳算法的機(jī)場調(diào)度優(yōu)化算法［J］.華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，03:392-398.

［4］楊守劍，白存儒.機(jī)場停機(jī)位優(yōu)化分配研究［J］.航空工程進(jìn)展，2010，03:301-305.

［5］周至，孟波.機(jī)場機(jī)位自動(dòng)分配系統(tǒng)知識(shí)庫的研究與設(shè)計(jì)［J］.計(jì)算機(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ī)場停機(jī)位優(yōu)化配置［J］.南京航空航天大學(xué)學(xué)報(bào)，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］吳軍.數(shù)學(xué)之美［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］盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計(jì)［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-），男，工程師，研究方向?yàn)閿?shù)據(jù)庫及應(yīng)用

梁磊（1973-），男，工程師，研究方向?yàn)閿?shù)據(jù)庫及應(yīng)用

繆楊帆（1994-），女，在讀研究生，研究方向?yàn)閿?shù)據(jù)挖掘

李川（1977-），男，副教授，博士，研究方向?yàn)閿?shù)據(jù)庫、數(shù)據(jù)挖掘，Email:lcharles@scu.edu.cn

2016-05-17

2016-06-05

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

停機(jī)位分配；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.