文獻標識碼: A
文章編號： 0258-7998(2014)03-0123-03
隨著電子商務(wù)的普及，人們網(wǎng)上購物的習慣逐漸形成,。截止2012年11月30日,，阿里巴巴集團旗下淘寶和天貓2012年總交易額已經(jīng)突破一萬億。綜合淘寶和天貓的交易數(shù)據(jù)來看,，以快遞員為主體的中國物流配送業(yè)對電子商務(wù)發(fā)展的促進起到了巨大作用,。同時傳統(tǒng)郵政擔負的包裹配送業(yè)務(wù)比重也逐漸地傾斜于第三方物流配送公司。目前我國物流配送運輸成本占整個物流成本的35%~50%左右[1],。由于網(wǎng)購物品用戶分布在城市的不同地方,為了控制配送運輸成本,，改善配送秩序，需要優(yōu)化配送路線,。優(yōu)化配送路線的求解有串行算法和并行算法,。串行算法主要表現(xiàn)在基于算法本身以及其優(yōu)化組合的方法,例如CLARK G和WRIGHT J的節(jié)約算法、GILLETT B E和MILLER L R的掃描算法,、Christofides等人的k度中心樹和相關(guān)算法,、Gendrean的禁忌搜索方法、LAWRENCE J 的遺傳算法,、Dijkstra算法,、Nordbeck提出的橢圓限制搜索區(qū)域改進算法[2]。隨著計算數(shù)據(jù)的海量化以及摩爾定律的失效(晶體管電路已經(jīng)接近了其物理改進的極限),，串行算法本身的改進和組合已不能適應(yīng)需求,。計算機科學領(lǐng)域出現(xiàn)了另一類并行最短路徑分析算法設(shè)計，目前關(guān)于并行最短路徑分析算法設(shè)計有基于MPI的主從Dijkstra并行算法[3],、MPI+open-MP混合算法[4],、社區(qū)分析的最短路徑LC-2q并行算法[5]等。
本文針對物流及時配送和成本控制需求,，提出基于標色法的MapReduce廣度優(yōu)先算法并行化模型,，并應(yīng)用于配送線路優(yōu)化問題。由于MapReduce本身封裝了數(shù)據(jù)分割,、負載均衡,、容錯處理等細節(jié)，用戶只需要將實際應(yīng)用問題分解成若干可并行操作的子問題,，有效降低了求解難度,，為解決物流配送運輸路徑優(yōu)化問題提供了技術(shù)支持。
1 MapReduce算法描述
信息技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展為云計算的產(chǎn)生提供了條件,。MapReduce并行編程模型是云計算的核心技術(shù)之一,。MapReduce是Google 實驗室提出的一個分布式并行編程模型或框架, 主要用來處理和產(chǎn)生海量數(shù)據(jù)的并行編程模式,，2004 年DEAN J和GHEMAWAT S第一次發(fā)表了這一新型分布式并行編程模型[6]。用戶不必關(guān)注MapReduce 如何進行數(shù)據(jù)分割,、負載均衡,、容錯處理等細節(jié)，只需要將實際應(yīng)用問題分解成若干可并行操作的子問題,，這種分解思路遵守主從架構(gòu)模型,。Mapreduce框架的主要程序分為Master、Map和Reduce,。在Hadoop 中,，MapReduce由一個主節(jié)點(Jobtracker,屬于Master)和從節(jié)點(Tasktracker,屬于Map和Reduce)組成[7]。
1.1 基于標色法的MapReduce廣度優(yōu)先算法模型
給定一個帶權(quán)有向圖,用G=(N,，E,，W)模型來表示，其中N={ni∣i=1,2,，...,，m}為完全圖的點的集合；E={e(ni,nj)∣i≠j, ni,nj∈N}為弧段集,；W={w(ni,nj)∣i≠j,ni,nj∈N}為權(quán)值集,。一般向圖的權(quán)值表示節(jié)點與節(jié)點之間的幾何長度,記為w(ni,nj)=dij,，dij表示節(jié)點ni到節(jié)點nj的距離,。最短路徑計算就是計算從起始點ni到終止點nj的最短幾何長度之和為最小。在有向圖起始點和終止點的最短路徑計算中,，MapReduce采用的是廣度優(yōu)先算法,。MapReduce計算最短路徑用鄰接表來表示圖，在鄰接表中每一行數(shù)據(jù)構(gòu)成Map和Reduce的一個數(shù)據(jù)內(nèi)容,。Map和Reduce的(key,，value)中key為N，value值為與這個節(jié)點鄰接的所有節(jié)點的 AdjacentList,。在用標色法求解最短路徑時,，AdjacentList節(jié)點的信息包括源點到頂點的距離distance(除到本身的距離為0外，其余初始值皆為無窮大),；節(jié)點的顏色color(其值可分別取0,、1、2,，0表示未處理的頂點,，1表示等待處理的頂點，2表示已處理的頂點,，源點的初始值為1,，其余頂點皆為0)；被訪問頂點和邊的權(quán)值記為N和W。頂點的數(shù)據(jù)結(jié)構(gòu)如表1所示,。
1.2 MapReduce求解步驟
(1)Master對輸入文件按行(每行代表圖中的一個頂點)進行自動切分,并將數(shù)據(jù)作為輸入分發(fā)到每個Map任務(wù)(keyin,valuein),，即輸入[(ID,<Distance;color;pnodes and weight>)]；
(2)接收(keyin,valuein)對,，當valuein中的color的值為1時,，則處理當前頂點,產(chǎn)生臨時的{(keyout,valueout)│out=1...k}集；
(3)MapReduce對Map執(zhí)行過程輸出的臨時中間結(jié)果進行分組(Shuffle/sort),將相同的key值即ID號合并成同一組(key,，list(valuei)│i=1...m),并將其分發(fā)給空閑的Reduce,；
(4)Reduce接收(key，list(valuei)),對相同ID的value進行合并,，找到當前的最短路徑,；
(5)如果每次Reduce后，結(jié)果收斂,，則停止計算,；如果未收斂，則繼續(xù)發(fā)給下一輪的Map過程,，多次迭代計算直到color值全部為2,，得到最終的最短路徑，算法結(jié)束,。
MapReduce算法流程如圖1所示,。
1.3 MapReduce算法偽代碼
(1)MapReduce的第一次迭代偽代碼，Map部分為：
Map:<k1,v1> → list(<k2,v2>)
其中k1為節(jié)點的ID,；v1為該節(jié)點的距離,、邊、邊的權(quán)值,、顏色,；每一個輸入的<k1,v1>會輸出一批<k2,v2>,它們是計算的中間結(jié)果。
Begin
If( color(k1) = 1)
//如果k1的還需處理,，即k1的顏色為灰色
{
for ki (<k1,ki>in k1.edges)
//對所有k1指向的節(jié)點, 只處理所有標記為1的節(jié)點
If ( distance(k1) + weight(k1 ,ki) < distance(ki))
{
Set distance(distance(ki)) = distance(k1) + weight(k1,ki);
Set color(ki) = 1;
emit (ki, v1)
//將該記錄加入到鍵值對中,，將標記為1
的節(jié)點所關(guān)聯(lián)的節(jié)點加入中間結(jié)果。
}
Set color(k1) = 2;
//標記為1的節(jié)點被變更為2,，表示處理完畢
}
emit (k1, v1)
End
(2）Mapreduce的第一次迭代偽代碼,，Reduce部分
Reduce <k2,list(v2)> → <k3,v3>
//<k2,list(v2)>輸入的中間結(jié)果，其中l(wèi)ist(v2)表示
一批屬于同一個K2的value,。<k3,v3>為輸出結(jié)果
Begin
Set color(k2) =0;
Set distance(k2) = ∞;
vi∈ list(v2);
If( vi.color > k2.color)
//按照節(jié)點對計算中間結(jié)果進行合并
{
Set color(k2) = vi.color;
}
If {vi.distance < distance(k2))
//如果中間結(jié)果比原有結(jié)果小,，將節(jié)點標記為1
{
Set distance(k2) = vi.distance;
If(vi.color = 1),Set color(k2) = 1;
}
If vi.edges != null, Set Edges(k2) = vi.edges;
}
emit (k2, vi.)
End
2 案例分析
2.1 基本情況
韻達快遞浙江杭州西湖區(qū)文一路公司是民營韻達快運的子公司，為客戶提供快遞,、物流及電子商務(wù)等一系列門到門服務(wù),。企業(yè)的配送范圍為文一路,、文二路、教工路及學院路構(gòu)成的矩形區(qū)域,，該區(qū)域面積大約20 km2的范圍,。
隨著第三方物流公司的增多，物流配送競爭越來越激烈,。為了壓縮成本,，按照配送點情況優(yōu)化線路是節(jié)約成本的途徑之一,優(yōu)化后的單源配送線路線可以將途經(jīng)的配送點一并發(fā)送，形成一車多配的節(jié)約模式,。
2.2 問題提出及求解
公司某次接到為4個區(qū)域(西湖科技大廈,、節(jié)能工業(yè)園、高新大廈及華門公寓)配送貨物的任務(wù),，配送員決定分頭配送,，而如何組織好路線使得路程最短就可以歸結(jié)為單源最短路徑問題。為了計算方便,，設(shè)置配送中心點為n1,，被配送的4個地方分別設(shè)置西湖科技大廈為n2，節(jié)能工業(yè)園為n3,，高新大廈為n4,，華門公寓為n5。4個區(qū)域之間及其與配送中心的幾何路線長度取整數(shù)(km),。有向圖見圖2(a),其中幾何路線長度d1(n1,n2)=10,，d2(n1,n4)=5，d3(n2,n3)=1,，d4(n2,n4)= 2,，d5(n3,n5)=4,，d6(n4,n2)=3,，d7(n4,n3)=9，d8(n5,n1)=7,，d9(n5,n3)=6,。從配送中心n1出發(fā)選取怎樣的路線可以滿足到達n2、n3,、n4,、n5的長度是最短的。采用標色法的MapReduce廣度優(yōu)先算法計算,，依照偽代碼的計算邏輯計算出源點到其他各點的最短路徑,。通過4次迭代頂點到各點的最短路徑見圖2(f),其中加粗的圓圈表示被訪問過的頂點，color值為2,，圈內(nèi)的數(shù)值為其與n1的最短路徑長度;color值為0,，虛線圈為未訪問的頂點,，圈內(nèi)值為∞;color值為1，虛線圈為待訪問的頂點,，圈內(nèi)值為標注值,。MapReduce第一次迭代驗算數(shù)據(jù)如表2所示,其余幾次迭代過程格式與此類似。
如果從配送點n1到節(jié)能工業(yè)園n3進行配送,，配送的最優(yōu)路線就是配送點n1→高新大廈n4→西湖科技大廈n2→節(jié)能工業(yè)園n3,。優(yōu)化后的長度為n1→n4→n2→n3=9。相比其他配送路線選擇,，如
n1→n2→n3=11,，n1→n2→n4→n3=21，n1→n2→n4→n5→n3=20,，n1→n2→n4→n5→n3=20,，n1→n4→n3=14，n1→n4→n5→n3=13,，優(yōu)化后的路線長度更短,。在選擇這樣的配送路線后，途中高新大廈n4和西湖科技大廈n2的一些貨物也可以一并被配送,，這樣就滿足了一車多配的情況,，達到了節(jié)約成本的目的。
本文將MapReduce并行編程模式引入了物流配送最短路徑查詢,，用戶不必關(guān)注MapReduce 如何進行數(shù)據(jù)分割,、負載均衡、容錯處理等細節(jié),，只需將實際應(yīng)用問題分解成若干可并行操作的子問題,，即可解決配送線路優(yōu)化問題，簡化了算法設(shè)計,。為優(yōu)化配送,、節(jié)約成本、提高配送系統(tǒng)的運行效率提供了技術(shù)參考,。
參考文獻
[1] 劉榮華,，孫皓，趙娟．基于供應(yīng)鏈的運輸決策研究[J].中國海洋大學學報,，2007(1):63－65．
[2] ZHAN F B. Three fastest shortest path algorithms on real road networks[J]. Journal of Geographic Information and Decision Analysis, 1997,1(1):69-82.
[3] 盧照.基于城市路網(wǎng)最短路徑并行搜索算法的研究[D].陜西：陜西師范大學,，2010.
[4] 楊慶芳，劉東,，楊兆生.基于MPI+openMP混合編程模型的城市路網(wǎng)最短路徑并行算法[J].吉林大學學報(工學版),，2011,41(6)：1581-1584.
[5] 馬明全,周明全,耿國華,等.基于社區(qū)分析的最短路徑計算[J].計算機應(yīng)用與軟件,2009,25(4):177-181.
[6] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[J]. Communications of the ACM,2005,51(1):107-113.
[7] 劉曉群，鄒 欣,，范 虹.基于并行云計算模式的建筑結(jié)構(gòu)設(shè)計[J].電子技術(shù)應(yīng)用,，2011,37(10)：123-125.