MapReduce求解物流配送單源最短路徑研究

1、MapReduce求解物流配送單源最短路徑研究摘要:針對(duì)物流配送路線優(yōu)化，提出了將配送路線問(wèn)題分解成若干可并行操作的子問(wèn)題的云計(jì)算模式。詳細(xì)論述了基于標(biāo)色法的MapReduce廣度優(yōu)先算法并行化模型、節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)、算法流程和偽代碼程序，并通過(guò)將該算法應(yīng)用于快遞公司的實(shí)際配送，驗(yàn)證了該算法的可行性。關(guān)鍵詞:物流配送；MapReduce；并行計(jì)算；最短路徑隨著電子商務(wù)的普及，人們網(wǎng)上購(gòu)物的習(xí)慣逐漸形成。截止2012年11月30日，阿里巴巴集團(tuán)旗下淘寶和天貓2012年總交易額已經(jīng)突破一萬(wàn)億。綜合淘寶和天貓的交易數(shù)據(jù)來(lái)看，以快遞員為主體的中國(guó)物流配送業(yè)對(duì)電子商務(wù)發(fā)展的促進(jìn)起到了巨大作用。同時(shí)傳統(tǒng)郵政擔(dān)

2、負(fù)的包裹配送業(yè)務(wù)比重也逐漸地傾斜于第三方物流配送公司。目前我國(guó)物流配送運(yùn)輸成本占整個(gè)物流成本的35%50%左右1。由于網(wǎng)購(gòu)物品用戶分布在城市的不同地方,為了控制配送運(yùn)輸成本，改善配送秩序，需要優(yōu)化配送路線。優(yōu)化配送路線的求解有串行算法和并行算法。串行算法主要表現(xiàn)在基于算法本身以及其優(yōu)化組合的方法，例如CLARKG和WRIGHTJ的節(jié)約算法、GILLETTBE和MILLERLR的掃描算法、Christofides等人的k度中心樹(shù)和相關(guān)算法、Gendrean的禁忌搜索方法、LAWRENCEJ的遺傳算法、Dijkstra算法、Nordbeck提出的橢圓限制搜索區(qū)域改進(jìn)算法2。隨著計(jì)算數(shù)據(jù)的海量化以及

3、摩爾定律的失效(晶體管電路已經(jīng)接近了其物理改進(jìn)的極限)，串行算法本身的改進(jìn)和組合已不能適應(yīng)需求。計(jì)算機(jī)科學(xué)領(lǐng)域出現(xiàn)了另一類并行最短路徑分析算法設(shè)計(jì)，目前關(guān)于并行最短路徑分析算法設(shè)計(jì)有基于MPI的主從Dijkstra并行算法3、MPI+open-MP混合算法4、社區(qū)分析的最短路徑LC-2q并行算法5等。本文針對(duì)物流及時(shí)配送和成本控制需求，提出基于標(biāo)色法的MapReduce廣度優(yōu)先算法并行化模型，并應(yīng)用于配送線路優(yōu)化問(wèn)題。由于MapReduce本身封裝了數(shù)據(jù)分割、負(fù)載均衡、容錯(cuò)處理等細(xì)節(jié)，用戶只需要將實(shí)際應(yīng)用問(wèn)題分解成若干可并行操作的子問(wèn)題，有效降低了求解難度，為解決物流配送運(yùn)輸路徑優(yōu)化問(wèn)題提供了

4、技術(shù)支持。1MapReduce算法描述信息技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展為云計(jì)算的產(chǎn)生提供了條件。MapReduce并行編程模型是云計(jì)算的核心技術(shù)之一。MapReduce是Google實(shí)驗(yàn)室提出的一個(gè)分布式并行編程模型或框架,主要用來(lái)處理和產(chǎn)生海量數(shù)據(jù)的并行編程模式，2004年DEANJ和GHEMAWATS第一次發(fā)表了這一新型分布式并行編程模型6。用戶不必關(guān)注MapReduce如何進(jìn)行數(shù)據(jù)分割、負(fù)載均衡、容錯(cuò)處理等細(xì)節(jié)，只需要將實(shí)際應(yīng)用問(wèn)題分解成若干可并行操作的子問(wèn)題，這種分解思路遵守主從架構(gòu)模型。Mapreduce框架的主要程序分為Master、Map和Reduce。在Hadoop中，MapReduc

5、e由一個(gè)主節(jié)點(diǎn)(Jobtracker,屬于Master)和從節(jié)點(diǎn)(Tasktracker,屬于Map和Reduce)組成7。1.1基于標(biāo)色法的MapReduce廣度優(yōu)先算法模型給定一個(gè)帶權(quán)有向圖,用G=(N，E，W)模型來(lái)表示，其中N=ni|i=l,2,.，m為完全圖的點(diǎn)的集合；E=e(ni,nj)|i≠j,ni,nj∈N為弧段集；W=w(ni,nj)|i≠j,ni,nj∈N為權(quán)值集。一般向圖的權(quán)值表示節(jié)點(diǎn)與節(jié)點(diǎn)之間的幾何長(zhǎng)度,記為w(ni,nj)=dij，dij表示節(jié)點(diǎn)ni到節(jié)點(diǎn)nj的距離。最短路徑計(jì)算就是計(jì)算從起始點(diǎn)ni到終止點(diǎn)nj的最短幾何長(zhǎng)度之和為最小。

6、在有向圖起始點(diǎn)和終止點(diǎn)的最短路徑計(jì)算中，MapReduce采用的是廣度優(yōu)先算法。MapReduce計(jì)算最短路徑用鄰接表來(lái)表示圖，在鄰接表中每一行數(shù)據(jù)構(gòu)成Map和Reduce的一個(gè)數(shù)據(jù)內(nèi)容。Map和Reduce的(key,value)中key為N，value值為與這個(gè)節(jié)點(diǎn)鄰接的所有節(jié)點(diǎn)的AdjacentList。在用標(biāo)色法求解最短路徑時(shí)，AdjacentList節(jié)點(diǎn)的信息包括源點(diǎn)到頂點(diǎn)的距離distance(除到本身的距離為0外，其余初始值皆為無(wú)窮大)；節(jié)點(diǎn)的顏色color(其值可分別取0、1、2，0表示未處理的頂點(diǎn)，1表示等待處理的頂點(diǎn)，2表示已處理的頂點(diǎn)，源點(diǎn)的初始值為1,其余頂點(diǎn)皆為0);

7、被訪問(wèn)頂點(diǎn)和邊的權(quán)值記為N和W。頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如表1所示。1.2 MapReduce求解步驟(l)Master對(duì)輸入文件按行(每行代表圖中的一個(gè)頂點(diǎn))進(jìn)行自動(dòng)切分,并將數(shù)據(jù)作為輸入分發(fā)到每個(gè)Map任務(wù)(keyin,valuein)，即輸入(ID，<Distance;color;pnodesandweight>)；(2)接收(keyin,valuein)對(duì)，當(dāng)valuein中的color的值為1時(shí)，則處理當(dāng)前頂點(diǎn),產(chǎn)生臨時(shí)的(keyout,valueout)|out=l.k集；(3)MapReduce對(duì)Map執(zhí)行過(guò)程輸出的臨時(shí)中間結(jié)果進(jìn)行分組(Shuffle/sort),將相同的ke

8、y值即ID號(hào)合并成同一組(key,list(valuei)|i=l.m),并將其分發(fā)給空閑的Reduce；(4)Reduce接收(key,list(valuei),對(duì)相同ID的value進(jìn)行合并，找到當(dāng)前的最短路徑；(5)如果每次Reduce后，結(jié)果收斂，則停止計(jì)算；如果未收斂，則繼續(xù)發(fā)給下一輪的Map過(guò)程，多次迭代計(jì)算直到color值全部為2,得到最終的最短路徑，算法結(jié)束。MapReduce算法流程。1.3 MapReduce算法偽代碼(1)MapReduce的第一次迭代偽代碼，Map部分為：Map:<kl,vl>→list(<k2,v2>)其中k1為節(jié)點(diǎn)的

9、ID；vl為該節(jié)點(diǎn)的距離、邊、邊的權(quán)值、顏色；每一個(gè)輸入的<k1,v1>會(huì)輸出一批<k2,v2>,它們是計(jì)算的中間結(jié)果。BeginIf(color(k1)=1)/如果k1的還需處理，即k1的顏色為灰色forki(<k1,ki>ink1.edges)/對(duì)所有k1指向的節(jié)點(diǎn),只處理所有標(biāo)記為1的節(jié)點(diǎn)If(distance(k1)+weight(k1,ki)<distance(ki)Setdistance(distance(ki)=distance(k1)+weight(k1,ki);Setcolor(ki)=1;emit(ki,v1)/將/該記錄加入到鍵值

10、對(duì)中，將標(biāo)記為1的節(jié)點(diǎn)所關(guān)聯(lián)的節(jié)點(diǎn)加入中間結(jié)果。Setcolor(k1)=2;/標(biāo)記為1的節(jié)點(diǎn)被變更為2，表示處理完畢emit(k1,v1)End(2)Mapreduce的第一次迭代偽代碼，Reduce部分Reduce<k2,list(v2)>→<k3,v3>/<k2,list(v2)>輸入的中間結(jié)果，其中l(wèi)ist(v2)表示一批屬于同一個(gè)K2的value。<k3,v3>為輸出結(jié)果BeginSetcolor(k2)=0;Setdistance(k2)=∞vi∈list(v2);If(vi.color>k2.c

11、olor)/按照節(jié)點(diǎn)對(duì)計(jì)算中間結(jié)果進(jìn)行合并Setcolor(k2)=vi.color;Ifvi.distance<distance(k2)/如果中間結(jié)果比原有結(jié)果小，將節(jié)點(diǎn)標(biāo)記為1Setdistance(k2)=vi.distance;If(vi.color=1),Setcolor(k2)=1;Ifvi.edges!=null,SetEdges(k2)=vi.edges;emit(k2,vi.)End2案例分析2.1基本情況韻達(dá)快遞浙江杭州西湖區(qū)文一路公司是民營(yíng)韻達(dá)快運(yùn)的子公司，為客戶提供快遞、物流及電子商務(wù)等一系列門到門服務(wù)。企業(yè)的配送范圍為文一路、文二路、教工路及學(xué)院路構(gòu)成的矩形區(qū)域

12、，該區(qū)域面積大約20km2的范圍。隨著第三方物流公司的增多，物流配送競(jìng)爭(zhēng)越來(lái)越激烈。為了壓縮成本，按照配送點(diǎn)情況優(yōu)化線路是節(jié)約成本的途徑之一,優(yōu)化后的單源配送線路線可以將途經(jīng)的配送點(diǎn)一并發(fā)送，形成一車多配的節(jié)約模式。2.2問(wèn)題提出及求解公司某次接到為4個(gè)區(qū)域(西湖科技大廈、節(jié)能工業(yè)園、高新大廈及華門公寓)配送貨物的任務(wù)，配送員決定分頭配送，而如何組織好路線使得路程最短就可以歸結(jié)為單源最短路徑問(wèn)題。為了計(jì)算方便，設(shè)置配送中心點(diǎn)為n1,被配送的4個(gè)地方分別設(shè)置西湖科技大廈為n2,節(jié)能工業(yè)園為n3,高新大廈為n4,華門公寓為n5。4個(gè)區(qū)域之間及其與配送中心的幾何路線長(zhǎng)度取整數(shù)(km)。有向圖見(jiàn)圖2(

13、a),其中幾何路線長(zhǎng)度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ā)選取怎樣的路線可以滿足到達(dá)n2、n3、n4、n5的長(zhǎng)度是最短的。采用標(biāo)色法的MapReduce廣度優(yōu)先算法計(jì)算，依照偽代碼的計(jì)算邏輯計(jì)算出源點(diǎn)到其他各點(diǎn)的最短路徑。通過(guò)4次迭代頂點(diǎn)到各點(diǎn)的最短路徑見(jiàn)圖2(f),其中加粗的圓圈表示被訪問(wèn)過(guò)的頂點(diǎn)，color值為2,圈內(nèi)的數(shù)值為其與n1的最短路徑長(zhǎng)度;color值為0,虛線圈為未訪問(wèn)的頂點(diǎn)，圈內(nèi)

14、值為∞color值為1,虛線圈為待訪問(wèn)的頂點(diǎn)，圈內(nèi)值為標(biāo)注值。MapReduce第一次迭代驗(yàn)算數(shù)據(jù)如表2所示，其余幾次迭代過(guò)程格式與此類似。如果從配送點(diǎn)n1到節(jié)能工業(yè)園n3進(jìn)行配送，配送的最優(yōu)路線就是配送點(diǎn)nl→高新大廈n4→西湖科技大廈n2→節(jié)能工業(yè)園n3。優(yōu)化后的長(zhǎng)度為nl→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，nl→n4→n3=14,nl→n4→n5→n3=1