基于MapReduce框架的航班串編制算法

張 康，喻 瑛，王偉杰

(上海大學(xué) 機(jī)電工程與自動化學(xué)院，上海 200072)

基于MapReduce框架的航班串編制算法

張 康，喻 瑛，王偉杰

(上海大學(xué) 機(jī)電工程與自動化學(xué)院，上海 200072)

為解決小規(guī)模航班串編制問題，提出一種簡單的非分布式算法，并在單機(jī)運行平臺進(jìn)行測試。然而，隨著民航企業(yè)的迅速發(fā)展，航班數(shù)量不斷增加，非分布式的航班串編制算法已經(jīng)無法滿足實際生產(chǎn)需求。為解決大規(guī)模航班串編制問題，提出另外兩種基于MapReduce框架的分布式航班串編制算法。第一種算法將簡單的非分布式算法擴(kuò)展到MapReduce框架，解決大規(guī)模航班串編制問題；第二種算法在第一種算法的基礎(chǔ)上進(jìn)一步改進(jìn)，優(yōu)化Map和Reduce的處理流程，刪除第一種算法中的迭代過程，充分發(fā)揮MapReduce框架的批處理優(yōu)勢。搭建Hadoop平臺進(jìn)行驗證，實驗結(jié)果表明，提出的兩種分布式算法中，第二種算法即改進(jìn)后的分布式算法，較之簡單的非分布式算法和第一種分布式算法，能夠有效提高大規(guī)模航班串編制效率。

MapReduce框架；Hadoop平臺；航班串編制；大數(shù)據(jù)

0 引 言

飛機(jī)排班是民航企業(yè)制定生產(chǎn)計劃的一項基本內(nèi)容，排班人員根據(jù)航班計劃和飛機(jī)維修計劃以及商務(wù)部提供的航班連線信息、航站信息、飛機(jī)本身信息等，給出飛機(jī)調(diào)度決策，為每個運營航班指定一架具體執(zhí)行的飛機(jī)。2010年以來，隨著中國經(jīng)濟(jì)的快速發(fā)展，在市場需求旺盛和人民幣持續(xù)升值的雙重利好下，中國民航經(jīng)歷了新一輪的發(fā)展高峰。單就2015/2016年冬春航季，根據(jù)中國民航排定的航班計劃，在國內(nèi)航班方面，國內(nèi)39家航空公司每周共安排的航班數(shù)量高達(dá)54 956班次，比2014/2015年冬春航季增長6.2%。

航班串編制[1-2]是飛機(jī)排班的核心工作。隨著航班規(guī)模逐年擴(kuò)大，民航企業(yè)傳統(tǒng)上使用的非分布式航班串編制的方法已經(jīng)無法滿足實際生產(chǎn)需求，從而需要一種更高效的計算機(jī)技術(shù)處理大規(guī)模航班串編制問題。近年來，Hadoop分布式計算平臺在處理大規(guī)模數(shù)據(jù)問題上表現(xiàn)出了顯著優(yōu)勢，吸引了產(chǎn)業(yè)界、政府和學(xué)術(shù)界的廣泛關(guān)注。

Hadoop[3-5]是Apache軟件基金會旗下的一個開源分布式計算平臺，已成為大數(shù)據(jù)分析的主流框架。針對Hadoop的研究與應(yīng)用的相關(guān)工作正在積極展開。文獻(xiàn)[6]探討了蟻群算法的幾種并行方式與適用場景以及結(jié)合MapReduce編程框架的可行性。文獻(xiàn)[7]利用MapReduce并行編程模式，提出了一種基于Hadoop平臺的高效、可擴(kuò)展并行挖掘算法，節(jié)省了因大數(shù)據(jù)挖掘過程中產(chǎn)生的大量數(shù)據(jù)通信、中間數(shù)據(jù)以及執(zhí)行大量交集操作而產(chǎn)生的時間耗費。文獻(xiàn)[8]給出了基于MapReduce的計算等價類的數(shù)據(jù)約簡算法與樸素貝葉斯分類算法，實現(xiàn)了氣象數(shù)據(jù)挖掘研究。文獻(xiàn)[9]利用Hadoop平臺對醫(yī)保數(shù)據(jù)進(jìn)行挖掘，利用MapReduce編程方法實現(xiàn)并行挖掘，基于Hadoop平臺的醫(yī)保數(shù)據(jù)挖掘。文獻(xiàn)[10]基于列存儲數(shù)據(jù)庫Hbase的存儲模型，提出了一種MapReduce框架下的分布式關(guān)聯(lián)規(guī)則挖掘算法(MCM-Apriori算法)，并進(jìn)一步將改進(jìn)MCM-Apriori算法應(yīng)用于基于Hadoop云平臺的網(wǎng)上圖書銷售系統(tǒng)。

文中研究了基于MapReduce框架的航班串編制問題，提出一種簡單非分布式算法，并與兩種分布式算法進(jìn)行對比。搭建一主兩從Hadoop平臺，分別進(jìn)行不同規(guī)模的航班串編制，比較三種算法的性能。

1 相關(guān)理論

1.1 航班串編制數(shù)學(xué)模型

作如下定義(以下所有定義的變量均考慮的是一個排班周期內(nèi)，規(guī)定一天為一個排班周期)：

U為航班集合，ui為U中第i個航班；

Q0為航班串集合；

Qui為以航班ui為起始航班的航班串，Qui∈Q0；

qk為航班串中的第k個航班；

taqk為航班qk的到港時間；

tdqk為航班qk的離港時間；

aaqk為航班qk的到港機(jī)場；

daqk為航班qk的離港機(jī)場；

t0為完成一次過站作業(yè)所需的最短時間。

航班串編制數(shù)學(xué)模型可以描述為：

(1)

s.t.

(2)

taqk+t0≤tdqk+1

(3)

aaqk=daqk+1

(4)

1.2 Hadoop平臺

Hadoop基于Java語言開發(fā)，運行在Linux操作系統(tǒng)之上，核心是HDFS和MapReduce。其中HDFS負(fù)責(zé)的是大規(guī)模數(shù)據(jù)的存儲，MapReduce負(fù)責(zé)數(shù)據(jù)的并行計算。Hadoop基于主從式架構(gòu)，通過Namenode、Datanode、Jobtracker和Tasktracker管理，主要特性是移動計算，而不是移動數(shù)據(jù)。計算前，Namenode分析程序需要的數(shù)據(jù)存儲在集群中的哪些Datanode節(jié)點；Jobtracker將MapReduce計算任務(wù)分配給這些節(jié)點上的Tasktracker；Tasktracker啟動Map程序，開啟計算任務(wù)；經(jīng)過Combiner、Shuffle等過程，在Reduce階段生成計算結(jié)果[11]。

1.3 MapReduce框架

MapReduce[11-12]分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細(xì)節(jié)的情況下開發(fā)并行應(yīng)用程序。作為一種海量數(shù)據(jù)處理的并行編程模型，MapReduce將分布式編程分為Map(映射)和Reduce(歸約)兩個階段，Map函數(shù)負(fù)責(zé)分塊數(shù)據(jù)的處理，Reduce函數(shù)負(fù)責(zé)對分塊數(shù)據(jù)處理的中間結(jié)果進(jìn)行歸約。

MapReduce框架運行應(yīng)用程序的過程如下：

(1)輸入文件被分成固定大小(默認(rèn)為64 MB，用戶可以調(diào)整)的M個分片(split)。Master節(jié)點會盡量將任務(wù)分配到離輸入分片較近的節(jié)點上執(zhí)行，以減少網(wǎng)絡(luò)通信量。

(2)在Map階段，MapReduce模型以一組(key1,value1)作為Map函數(shù)的數(shù)據(jù)輸入，經(jīng)過映射，聚合所有具有相同的key值的中間結(jié)果，產(chǎn)生一組中間結(jié)果list(key2,value2)，中間結(jié)果存儲在本地磁盤上。

(3)在Reduce階段，所有Map中輸出的數(shù)據(jù)經(jīng)過分區(qū)、混洗、排序后都傳入到Reduce函數(shù)，函數(shù)把具有相同key值的中間結(jié)果進(jìn)行合并產(chǎn)生結(jié)果(key2,list(value2))，最終生成輸出文件。

2 航班串編制算法

文中提出的三種航班串編制算法如下：

算法1：不使用MapReduce框架的簡單算法。

算法2：基于MapReduce框架對算法1進(jìn)行擴(kuò)展。

算法3：在算法2的基礎(chǔ)上進(jìn)行改進(jìn)。

使用的原始航班數(shù)據(jù)中包括航班號、離港機(jī)場、到港機(jī)場、離港時間和到港時間等航班信息。為方便起見，使用表1中的形式。其中，離港時間“0725”，表示該航班的離港時間為7點25分。

航班銜接需要考慮兩個約束關(guān)系。約束1為機(jī)場銜接約束，即同一航班串中的前一航班的到港機(jī)場必須是下一航班的離港機(jī)場。約束2為過站時間約束，即同一航班串中的后一航班的離港時間與前一航班的到港時間之差必須大于等于飛機(jī)完成一次過站操作的時間。

表1 原始航班數(shù)據(jù)

文中某個航班的后續(xù)航班指與該航班同時滿足約束1與約束2，即該航班組成航班串的航班；后續(xù)航班集合為該航班所有后續(xù)航班的集合。

定義n為U中的航班數(shù)量，ui為U中的第i個航班；Qui為以航班ui為起始航班的航班串；Fui為航班ui的后續(xù)航班集合；子函數(shù)followFlightSet生成后續(xù)航班集合；子函數(shù)generate生成航班串。

2.1 算法1

算法1的航班串編制模型，輸入文件為表1所示的原始航班數(shù)據(jù)。首先，航班集合U中的航班，均要從航班集合中選擇與該航班同時滿足約束1和約束2的航班，生成該航班的后續(xù)航班集合。然后，對U中的航班依次調(diào)用遞歸函數(shù)generate。generate中，依次判斷航班集合中的航班是否屬于該航班的后續(xù)航班集合；如果是，則將搜索到的航班加入以該航班為起始航班的航班串中，同時，將搜索到的航班標(biāo)記為當(dāng)前航班，繼續(xù)調(diào)用遞歸函數(shù)generate；直至搜索完航班集合中的航班。

算法1的具體步驟如下：

(1)i=1；

(2)調(diào)用子函數(shù)followFlightSet(ui,U)，生成ui的后續(xù)航班集合Fui；

(3)i=i+1；

(4)如果i≤n+1，轉(zhuǎn)到(2)；

(5)i=1；

(6)q=ui，j=1，U'=U；

(7)調(diào)用子函數(shù)generate(Qui,q,j,U')，生成以航班ui為起始航班的航班串Qui；

(8)i=i+1；

(9)如果i≤n+1，轉(zhuǎn)到(6)；

(10)輸出航班串集合；

(11)算法結(jié)束。

2.1.1followFlightSet函數(shù)的偽代碼

輸入?yún)?shù)：航班ui、航班集合U；

輸出參數(shù)：ui的后續(xù)航班集合Fui、followFlightSet(ui,U)。

begin

Fui=?;

j=1;

whilej≤ndo//搜索U中所有的航班uj

ifuj與ui同時滿足約束1和約束2then//如果uj是ui的后續(xù)航班

Fui=Fui∪{uj}; //將uj加入Fui中

endif

j=j+1;

endwhile

returnFui;

End

使用子函數(shù)followFlightSet對表1所示的原始航班數(shù)據(jù)進(jìn)行處理，生成如表2所示的數(shù)據(jù)形式，即生成各個航班的后續(xù)航班集合。

表2 預(yù)處理后的航班數(shù)據(jù)

2.1.2generate函數(shù)的偽代碼

輸入?yún)?shù)：q為待處理航班串Qui中的當(dāng)前尾航班；j為U中航班編號；航班集合U'，U'=U；

輸出參數(shù)：ui為起始航班的航班串Qui；generate(Qui,q,j,U')

begin

whilej≤ndo//搜索U'中所有的航班uj

ifuj∈Fqthen//如果航班uj是Fq中的航班

Qui=Qui∪{uj}; //將航班uj加入航班串集合Qui中

U=U/{uj}; //集合U去掉航班uj

q=uj; //更新航班串Qui中的當(dāng)前尾航班

j=1;

U'=U;

generate(Qui,q,j,U'); //繼續(xù)調(diào)用generate函數(shù)

else//如果航班uj不是Qui中的航班，繼續(xù)判斷下一個航班

j=j+1;

endif

endwhile

end

2.2 算法2

算法2使用MapReduce框架對算法1進(jìn)行擴(kuò)展。將算法1的步驟進(jìn)行拆分，算法1中生成各個航班的后續(xù)航班集合的步驟，在算法2中的預(yù)處理中實現(xiàn)；算法1中生成航班串的步驟，在算法2的Reduce函數(shù)中實現(xiàn)。

(1)Main函數(shù)。

算法2的Main函數(shù)包含四個步驟。第一步，對原始航班數(shù)據(jù)進(jìn)行預(yù)處理，生成各航班的后續(xù)航班集合；第二步，分配Map函數(shù)；第三步，分配Reduce函數(shù)；第四步，輸出航班串。

(2)Map函數(shù)。

Map函數(shù)，輸入格式為，其中值為文本文件中的一行航班數(shù)據(jù)(以回車符作為行結(jié)束標(biāo)記)；鍵為該行的首字符相對于文本文件的首地址的偏移量。Map函數(shù)的輸出格式為，鍵為對每行文本進(jìn)行拆分后的航班，值為該航班的后續(xù)航班集合。

(3)Reduce函數(shù)。

Reduce函數(shù)，輸入數(shù)據(jù)為MapReduce框架對Map階段輸出的中間結(jié)果進(jìn)行分區(qū)、混洗、排序后的數(shù)據(jù)，即鍵相同的值的集合。Reduce函數(shù)的輸入格式為，其中鍵為航班，值為該航班的后續(xù)航班集合。以當(dāng)前航班、航班的后續(xù)航班集合、航班集合U等為輸入數(shù)據(jù)調(diào)用generate遞歸函數(shù)，生成當(dāng)前航班為起始航班的航班串。Reduce函數(shù)的輸出格式為，鍵為當(dāng)前航班，值為組成的航班串。

具體步驟如下：

(1)i=1；

(2)q=ui，j=1，U'=U；

(3)調(diào)用子函數(shù)generate(Qui,q,j,U')，生成以航班ui為起始航班的航班串Qui；

(4)i=i+1；

(5)如果i≤n+1，則轉(zhuǎn)到(2)，否則，進(jìn)入下一步；

(6)Reduce函數(shù)輸出航班串集合；

(7)結(jié)束。

2.3 算法3

算法3在算法2的基礎(chǔ)上進(jìn)一步改進(jìn)，去除算法2中的遞歸等操作，簡化Reduce函數(shù)，降低運算時間。

(1)Main函數(shù)。

Main函數(shù)中，首先對原始航班數(shù)據(jù)進(jìn)行預(yù)處理，初始flag=0。然后，判斷標(biāo)記flag，如果flag==1，則需要繼續(xù)分配Map和Reduce函數(shù)；否則，不需要分配新的Map和Reduce函數(shù)。具體步驟如圖1所示。

(2)Map函數(shù)。

Map函數(shù)，輸入格式為，其中值存儲文本文件中的一行航班數(shù)據(jù)(以回車符作為行結(jié)束標(biāo)記)；鍵為該行的首字符相對于文本文件的首地址的偏移量。Map函數(shù)的輸出格式為，鍵為對每行文本進(jìn)行拆分后的航班，值為以該航班為起始航班的航班串。

(3)Reduce函數(shù)。

Reduce函數(shù)，輸入數(shù)據(jù)為MapReduce框架對Map階段輸出的中間結(jié)果進(jìn)行分區(qū)、混洗、排序后的數(shù)據(jù)，即鍵相同的值的集合。Reduce函數(shù)的輸入格式為，其中鍵為當(dāng)前航班，值為以該航班為起始航班的航班串。再次從航班集合U中，搜索當(dāng)前航班的后續(xù)航班，添加到航班串中組成新的航班串。Reduce函數(shù)的輸出格式為，鍵為航班，值為航班串。具體步驟見圖1。

圖1 算法3的流程圖

3 算例分析

文中搭建的Hadoop集群，主節(jié)點(Namenode)命名為master，從節(jié)點(Datanode)分別命名為node1和node2，如圖2所示。三臺計算機(jī)內(nèi)存均為2G，使用的Linux版本為Ubuntu-14.04.2desktop，Java版本為jdk-6u45-linux-x64，Hadoop版本為hadoop-2.6.0。

圖2 一主兩從Hadoop架構(gòu)

分別實現(xiàn)三種航班串編制算法，測試相同航班數(shù)量下的運行時間。然后，逐步擴(kuò)大航班規(guī)模，測試三種算法的運行時間。實驗結(jié)果如表3所示。

從表3可知，算法1只適用于處理航班數(shù)量低于3 000時的航班串編制問題，當(dāng)航班規(guī)模為4 000時，編制航班串的運算時間大于9個小時，是實際生產(chǎn)中無法接受的。算法2中，由于Reduce函數(shù)邏輯復(fù)雜，當(dāng)航班數(shù)量為4 000時，消耗的時間為8 530 844ms，雖然少于算法1，但是遠(yuǎn)高于算法3。當(dāng)航班數(shù)量小于1 000時，算法3的運算時間大于算法1和算法2；當(dāng)航班數(shù)量大于2 000時，算法3的運算時間小于算法1和算法2；尤其當(dāng)航班數(shù)量大于4 000時，算法3的運算時間遠(yuǎn)小于算法1和算法2。由此說明算法3在航班數(shù)量較大時，運算時間少，運行效率高。

表3 不同算法的運行時間 ms

4 結(jié)束語

文中提出了三種航班串編制算法。算法1為不使用分布式框架的簡單算法，編制小規(guī)模航班串的效率高于算法2和算法3，但是不適用于編制大規(guī)模航班串。算法2在算法1的基礎(chǔ)上進(jìn)行擴(kuò)展，使用分布式MapReduce框架，將算法1的步驟拆分，利用了其處理大數(shù)據(jù)的特點，編制大規(guī)模航班串的效率高于算法1。算法3對算法2進(jìn)行改進(jìn)，去除了遞歸過程，簡化了Map和Reduce階段的流程，編制大規(guī)模航班串的效率遠(yuǎn)高于算法1和算法2。算法3充分發(fā)揮了MapReduce框架批處理和大數(shù)據(jù)處理的優(yōu)勢，做到了揚長避短，提高了大規(guī)模航班串的編制效率，為民航企業(yè)進(jìn)行航班串編制提供了一種切實可行的方案。

[1] 李耀華，譚 娜，郝貴和．飛機(jī)排班航班串編制模型及算法研究[J]．系統(tǒng)仿真學(xué)報，2008，20(3)：612-615．

[2] 付維方，張偉剛，孫春林.航班排班中航班串生成與篩選問題的算法與實現(xiàn)[J].中國民航學(xué)院學(xué)報，2006，24(5)：4-6.

[3]WhiteT．Hadoop權(quán)威指南[M]．周敏奇，王曉玲，金澈清，等，譯．第2版.北京：清華大學(xué)出版社，2011．

[4]RangerC,RaghuramanR,PenmetsaA,etal.EvaluatingMapReduceformulti-coreandmultiprocessorsystems[C]//Highperformancecomputerarchitecture.[s.l.]:[s.n.],2007:13-24.

[5]DeanJ,GhemawatS.Mapreduce:aflexibledataprocessingtool[J].CommunicationsoftheACM,2010,53(1):72-77.

[6] 王詔遠(yuǎn)，李天瑞，易修文．基于MapReduce的蟻群優(yōu)化算法實現(xiàn)方法[J]．計算機(jī)科學(xué)，2014，41(7)：261-265．

[7] 呂婉琪，鐘 誠，唐印滸，等．Hadoop分布式架構(gòu)下大數(shù)據(jù)集的并行挖掘[J]．計算機(jī)技術(shù)與發(fā)展，2014，24(1)：22-25.

[8] 張晨陽，馬志強(qiáng)，劉利民，等．Hadoop下基于粗糙集與貝葉斯的氣象數(shù)據(jù)挖掘研究[J]．計算機(jī)應(yīng)用與軟件，2015，32(4)：72-76.

[9] 梁 瑜．基于Hadoop平臺的醫(yī)保數(shù)據(jù)挖掘[D]．沈陽:東北大學(xué),2012.

[10] 郭 健，任永功．云計算環(huán)境下的關(guān)聯(lián)挖掘在圖書銷售中的研究[J]．計算機(jī)應(yīng)用與軟件，2014，31(11)：50-53.

[11]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.

[12]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[C]//Proceedingsofthe6thconferenceonsymposiumonoperatingsystemsdesign&implementation.Berkeley,CA,USA:USENIXAssociation,2004.

Flight String Compilation Algorithm Based on MapReduce Frame

ZHANG Kang,YU Ying,WANG Wei-jie

(Institute of Electromechanical Engineering and Automation,Shanghai University,Shanghai 200072,China)

A simple algorithm without distribution is proposed to solve the small scale flight string compilation problem and tested on stand-alone operation platform.However,with the rapid development of civil aviation enterprises and the rising number of flights,the simple algorithm has been unable to meet the requirement of practical production.Two new distributed flight string compilation algorithms based on MapReduce frame are proposed.The first one is extended from the simple algorithm to solve the large scale flight string compilation problem.And the second is made further improvements on the basis of the former where the processes of Map and Reduce are simplified and the iteration is deleted.A Hadoop platform is constructed to verify these algorithms.Results shows that compared to the simple algorithm and the first distributed algorithm,the second improved algorithm could effectively improve the efficiency of compiling flight string with large scale flights.

MapReduce framework;Hadoop platform;flight string compilation;big data

2016-04-16

2016-08-10

時間：2017-02-17

上海市2015年度“科技創(chuàng)新行動計劃”高新技術(shù)領(lǐng)域項目(15511109700)

張 康(1991-)，男，碩士研究生，研究方向為項目調(diào)度；喻 瑛，副教授，通訊作者，研究方向為不確定理論及其應(yīng)用、項目優(yōu)化調(diào)度、可靠性研究。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1623.020.html

TP305

A

1673-629X(2017)03-0142-05

10.3969/j.issn.1673-629X.2017.03.029