基于MapReduce框架的航班串編制算法
2017-03-29 05:00:18王偉杰
計算機技術與發(fā)展 2017年3期
張 康，喻 瑛，王偉杰
(上海大學 機電工程與自動化學院，上海 200072)
基于MapReduce框架的航班串編制算法
張 康，喻 瑛，王偉杰
(上海大學 機電工程與自動化學院，上海 200072)
為解決小規(guī)模航班串編制問題，提出一種簡單的非分布式算法，并在單機運行平臺進行測試。然而，隨著民航企業(yè)的迅速發(fā)展，航班數(shù)量不斷增加，非分布式的航班串編制算法已經(jīng)無法滿足實際生產(chǎn)需求。為解決大規(guī)模航班串編制問題，提出另外兩種基于MapReduce框架的分布式航班串編制算法。第一種算法將簡單的非分布式算法擴展到MapReduce框架，解決大規(guī)模航班串編制問題；第二種算法在第一種算法的基礎上進一步改進，優(yōu)化Map和Reduce的處理流程，刪除第一種算法中的迭代過程，充分發(fā)揮MapReduce框架的批處理優(yōu)勢。搭建Hadoop平臺進行驗證，實驗結果表明，提出的兩種分布式算法中，第二種算法即改進后的分布式算法，較之簡單的非分布式算法和第一種分布式算法，能夠有效提高大規(guī)模航班串編制效率。
MapReduce框架；Hadoop平臺；航班串編制；大數(shù)據(jù)
0 引 言
飛機排班是民航企業(yè)制定生產(chǎn)計劃的一項基本內容，排班人員根據(jù)航班計劃和飛機維修計劃以及商務部提供的航班連線信息、航站信息、飛機本身信息等，給出飛機調度決策，為每個運營航班指定一架具體執(zhí)行的飛機。2010年以來，隨著中國經(jīng)濟的快速發(fā)展，在市場需求旺盛和人民幣持續(xù)升值的雙重利好下，中國民航經(jīng)歷了新一輪的發(fā)展高峰。單就2015/2016年冬春航季，根據(jù)中國民航排定的航班計劃，在國內航班方面，國內39家航空公司每周共安排的航班數(shù)量高達54 956班次，比2014/2015年冬春航季增長6.2%。
航班串編制[1-2]是飛機排班的核心工作。隨著航班規(guī)模逐年擴大，民航企業(yè)傳統(tǒng)上使用的非分布式航班串編制的方法已經(jīng)無法滿足實際生產(chǎn)需求，從而需要一種更高效的計算機技術處理大規(guī)模航班串編制問題。近年來，Hadoop分布式計算平臺在處理大規(guī)模數(shù)據(jù)問題上表現(xiàn)出了顯著優(yōu)勢，吸引了產(chǎn)業(yè)界、政府和學術界的廣泛關注。
Hadoop[3-5]是Apache軟件基金會旗下的一個開源分布式計算平臺，已成為大數(shù)據(jù)分析的主流框架。針對Hadoop的研究與應用的相關工作正在積極展開。文獻[6]探討了蟻群算法的幾種并行方式與適用場景以及結合MapReduce編程框架的可行性。文獻[7]利用MapReduce并行編程模式，提出了一種基于Hadoop平臺的高效、可擴展并行挖掘算法，節(jié)省了因大數(shù)據(jù)挖掘過程中產(chǎn)生的大量數(shù)據(jù)通信、中間數(shù)據(jù)以及執(zhí)行大量交集操作而產(chǎn)生的時間耗費。文獻[8]給出了基于MapReduce的計算等價類的數(shù)據(jù)約簡算法與樸素貝葉斯分類算法，實現(xiàn)了氣象數(shù)據(jù)挖掘研究。文獻[9]利用Hadoop平臺對醫(yī)保數(shù)據(jù)進行挖掘，利用MapReduce編程方法實現(xiàn)并行挖掘，基于Hadoop平臺的醫(yī)保數(shù)據(jù)挖掘。文獻[10]基于列存儲數(shù)據(jù)庫Hbase的存儲模型，提出了一種MapReduce框架下的分布式關聯(lián)規(guī)則挖掘算法(MCM-Apriori算法)，并進一步將改進MCM-Apriori算法應用于基于Hadoop云平臺的網(wǎng)上圖書銷售系統(tǒng)。
文中研究了基于MapReduce框架的航班串編制問題，提出一種簡單非分布式算法，并與兩種分布式算法進行對比。搭建一主兩從Hadoop平臺，分別進行不同規(guī)模的航班串編制，比較三種算法的性能。
1 相關理論
1.1 航班串編制數(shù)學模型
作如下定義(以下所有定義的變量均考慮的是一個排班周期內，規(guī)定一天為一個排班周期)：
U為航班集合，ui為U中第i個航班；
Q0為航班串集合；
Qui為以航班ui為起始航班的航班串，Qui∈Q0；
qk為航班串中的第k個航班；
taqk為航班qk的到港時間；
tdqk為航班qk的離港時間；
aaqk為航班qk的到港機場；
daqk為航班qk的離港機場；
t0為完成一次過站作業(yè)所需的最短時間。
航班串編制數(shù)學模型可以描述為：
(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負責的是大規(guī)模數(shù)據(jù)的存儲，MapReduce負責數(shù)據(jù)的并行計算。Hadoop基于主從式架構，通過Namenode、Datanode、Jobtracker和Tasktracker管理，主要特性是移動計算，而不是移動數(shù)據(jù)。計算前，Namenode分析程序需要的數(shù)據(jù)存儲在集群中的哪些Datanode節(jié)點；Jobtracker將MapReduce計算任務分配給這些節(jié)點上的Tasktracker；Tasktracker啟動Map程序，開啟計算任務；經(jīng)過Combiner、Shuffle等過程，在Reduce階段生成計算結果[11]。
1.3 MapReduce框架
MapReduce[11-12]分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細節(jié)的情況下開發(fā)并行應用程序。作為一種海量數(shù)據(jù)處理的并行編程模型，MapReduce將分布式編程分為Map(映射)和Reduce(歸約)兩個階段，Map函數(shù)負責分塊數(shù)據(jù)的處理，Reduce函數(shù)負責對分塊數(shù)據(jù)處理的中間結果進行歸約。
MapReduce框架運行應用程序的過程如下：
(1)輸入文件被分成固定大小(默認為64 MB，用戶可以調整)的M個分片(split)。Master節(jié)點會盡量將任務分配到離輸入分片較近的節(jié)點上執(zhí)行，以減少網(wǎng)絡通信量。
(2)在Map階段，MapReduce模型以一組(key1,value1)作為Map函數(shù)的數(shù)據(jù)輸入，經(jīng)過映射，聚合所有具有相同的key值的中間結果，產(chǎn)生一組中間結果list(key2,value2)，中間結果存儲在本地磁盤上。
(3)在Reduce階段，所有Map中輸出的數(shù)據(jù)經(jīng)過分區(qū)、混洗、排序后都傳入到Reduce函數(shù)，函數(shù)把具有相同key值的中間結果進行合并產(chǎn)生結果(key2,list(value2))，最終生成輸出文件。
2 航班串編制算法
文中提出的三種航班串編制算法如下：
算法1：不使用MapReduce框架的簡單算法。
算法2：基于MapReduce框架對算法1進行擴展。
算法3：在算法2的基礎上進行改進。
使用的原始航班數(shù)據(jù)中包括航班號、離港機場、到港機場、離港時間和到港時間等航班信息。為方便起見，使用表1中的形式。其中，離港時間“0725”，表示該航班的離港時間為7點25分。
航班銜接需要考慮兩個約束關系。約束1為機場銜接約束，即同一航班串中的前一航班的到港機場必須是下一航班的離港機場。約束2為過站時間約束，即同一航班串中的后一航班的離港時間與前一航班的到港時間之差必須大于等于飛機完成一次過站操作的時間。
表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中的航班依次調用遞歸函數(shù)generate。generate中，依次判斷航班集合中的航班是否屬于該航班的后續(xù)航班集合；如果是，則將搜索到的航班加入以該航班為起始航班的航班串中，同時，將搜索到的航班標記為當前航班，繼續(xù)調用遞歸函數(shù)generate；直至搜索完航班集合中的航班。
算法1的具體步驟如下：
(1)i=1；
(2)調用子函數(shù)followFlightSet(ui,U)，生成ui的后續(xù)航班集合Fui；
(3)i=i+1；
(4)如果i≤n+1，轉到(2)；
(5)i=1；
(6)q=ui，j=1，U'=U；
(7)調用子函數(shù)generate(Qui,q,j,U')，生成以航班ui為起始航班的航班串Qui；
(8)i=i+1；
(9)如果i≤n+1，轉到(6)；
(10)輸出航班串集合；
(11)算法結束。
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ù)進行處理，生成如表2所示的數(shù)據(jù)形式，即生成各個航班的后續(xù)航班集合。
表2 預處理后的航班數(shù)據(jù)
2.1.2generate函數(shù)的偽代碼
輸入?yún)?shù)：q為待處理航班串Qui中的當前尾航班；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中的當前尾航班
j=1;
U'=U;
generate(Qui,q,j,U'); //繼續(xù)調用generate函數(shù)
else//如果航班uj不是Qui中的航班，繼續(xù)判斷下一個航班
j=j+1;
endif
endwhile
end
2.2 算法2
算法2使用MapReduce框架對算法1進行擴展。將算法1的步驟進行拆分，算法1中生成各個航班的后續(xù)航班集合的步驟，在算法2中的預處理中實現(xiàn)；算法1中生成航班串的步驟，在算法2的Reduce函數(shù)中實現(xiàn)。
(1)Main函數(shù)。
算法2的Main函數(shù)包含四個步驟。第一步，對原始航班數(shù)據(jù)進行預處理，生成各航班的后續(xù)航班集合；第二步，分配Map函數(shù)；第三步，分配Reduce函數(shù)；第四步，輸出航班串。
(2)Map函數(shù)。
Map函數(shù)，輸入格式為
(3)Reduce函數(shù)。
Reduce函數(shù)，輸入數(shù)據(jù)為MapReduce框架對Map階段輸出的中間結果進行分區(qū)、混洗、排序后的數(shù)據(jù)，即鍵相同的值的集合。Reduce函數(shù)的輸入格式為
具體步驟如下：
(1)i=1；
(2)q=ui，j=1，U'=U；
(3)調用子函數(shù)generate(Qui,q,j,U')，生成以航班ui為起始航班的航班串Qui；
(4)i=i+1；
(5)如果i≤n+1，則轉到(2)，否則，進入下一步；
(6)Reduce函數(shù)輸出航班串集合；
(7)結束。
2.3 算法3
算法3在算法2的基礎上進一步改進，去除算法2中的遞歸等操作，簡化Reduce函數(shù)，降低運算時間。
(1)Main函數(shù)。
Main函數(shù)中，首先對原始航班數(shù)據(jù)進行預處理，初始flag=0。然后，判斷標記flag，如果flag==1，則需要繼續(xù)分配Map和Reduce函數(shù)；否則，不需要分配新的Map和Reduce函數(shù)。具體步驟如圖1所示。
(2)Map函數(shù)。
Map函數(shù)，輸入格式為
(3)Reduce函數(shù)。
Reduce函數(shù)，輸入數(shù)據(jù)為MapReduce框架對Map階段輸出的中間結果進行分區(qū)、混洗、排序后的數(shù)據(jù)，即鍵相同的值的集合。Reduce函數(shù)的輸入格式為
圖1 算法3的流程圖
3 算例分析
文中搭建的Hadoop集群，主節(jié)點(Namenode)命名為master，從節(jié)點(Datanode)分別命名為node1和node2，如圖2所示。三臺計算機內存均為2G，使用的Linux版本為Ubuntu-14.04.2desktop，Java版本為jdk-6u45-linux-x64，Hadoop版本為hadoop-2.6.0。
圖2 一主兩從Hadoop架構
分別實現(xiàn)三種航班串編制算法，測試相同航班數(shù)量下的運行時間。然后，逐步擴大航班規(guī)模，測試三種算法的運行時間。實驗結果如表3所示。
從表3可知，算法1只適用于處理航班數(shù)量低于3 000時的航班串編制問題，當航班規(guī)模為4 000時，編制航班串的運算時間大于9個小時，是實際生產(chǎn)中無法接受的。算法2中，由于Reduce函數(shù)邏輯復雜，當航班數(shù)量為4 000時，消耗的時間為8 530 844ms，雖然少于算法1，但是遠高于算法3。當航班數(shù)量小于1 000時，算法3的運算時間大于算法1和算法2；當航班數(shù)量大于2 000時，算法3的運算時間小于算法1和算法2；尤其當航班數(shù)量大于4 000時，算法3的運算時間遠小于算法1和算法2。由此說明算法3在航班數(shù)量較大時，運算時間少，運行效率高。
表3 不同算法的運行時間 ms
4 結束語
文中提出了三種航班串編制算法。算法1為不使用分布式框架的簡單算法，編制小規(guī)模航班串的效率高于算法2和算法3，但是不適用于編制大規(guī)模航班串。算法2在算法1的基礎上進行擴展，使用分布式MapReduce框架，將算法1的步驟拆分，利用了其處理大數(shù)據(jù)的特點，編制大規(guī)模航班串的效率高于算法1。算法3對算法2進行改進，去除了遞歸過程，簡化了Map和Reduce階段的流程，編制大規(guī)模航班串的效率遠高于算法1和算法2。算法3充分發(fā)揮了MapReduce框架批處理和大數(shù)據(jù)處理的優(yōu)勢，做到了揚長避短，提高了大規(guī)模航班串的編制效率，為民航企業(yè)進行航班串編制提供了一種切實可行的方案。
[1] 李耀華，譚 娜，郝貴和．飛機排班航班串編制模型及算法研究[J]．系統(tǒng)仿真學報，2008，20(3)：612-615．
[2] 付維方，張偉剛，孫春林.航班排班中航班串生成與篩選問題的算法與實現(xiàn)[J].中國民航學院學報，2006，24(5)：4-6.
[3]WhiteT．Hadoop權威指南[M]．周敏奇，王曉玲，金澈清，等，譯．第2版.北京：清華大學出版社，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] 王詔遠，李天瑞，易修文．基于MapReduce的蟻群優(yōu)化算法實現(xiàn)方法[J]．計算機科學，2014，41(7)：261-265．
[7] 呂婉琪，鐘 誠，唐印滸，等．Hadoop分布式架構下大數(shù)據(jù)集的并行挖掘[J]．計算機技術與發(fā)展，2014，24(1)：22-25.
[8] 張晨陽，馬志強，劉利民，等．Hadoop下基于粗糙集與貝葉斯的氣象數(shù)據(jù)挖掘研究[J]．計算機應用與軟件，2015，32(4)：72-76.
[9] 梁 瑜．基于Hadoop平臺的醫(yī)保數(shù)據(jù)挖掘[D]．沈陽:東北大學,2012.
[10] 郭 健，任永功．云計算環(huán)境下的關聯(lián)挖掘在圖書銷售中的研究[J]．計算機應用與軟件，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)新行動計劃”高新技術領域項目(15511109700)
張 康(1991-)，男，碩士研究生，研究方向為項目調度；喻 瑛，副教授，通訊作者，研究方向為不確定理論及其應用、項目優(yōu)化調度、可靠性研究。
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
