Map Reduce求解物流配送單源最短路徑研究*

鈕 亮,張寶友

(中國計量學院經濟與管理學院,浙江 杭州 310018)

隨著電子商務的普及，人們網上購物的習慣逐漸形成。截止2012年11月30日，阿里巴巴集團旗下淘寶和天貓2012年總交易額已經突破一萬億。綜合淘寶和天貓的交易數據來看，以快遞員為主體的中國物流配送業對電子商務發展的促進起到了巨大作用。同時傳統郵政擔負的包裹配送業務比重也逐漸地傾斜于第三方物流配送公司。目前我國物流配送運輸成本占整個物流成本的35%～50%左右[1]。由于網購物品用戶分布在城市的不同地方,為了控制配送運輸成本，改善配送秩序，需要優化配送路線。優化配送路線的求解有串行算法和并行算法。串行算法主要表現在基于算法本身以及其優化組合的方法,例如CLARK G和WRIGHT J的節約算法、GILLETT B E和 MILLER L R的掃描算法、Christofides等人的k度中心樹和相關算法、Gendrean的禁忌搜索方法、LAWRENCE J的遺傳算法、Dijkstra算法、Nordbeck提出的橢圓限制搜索區域改進算法[2]。隨著計算數據的海量化以及摩爾定律的失效(晶體管電路已經接近了其物理改進的極限)，串行算法本身的改進和組合已不能適應需求。計算機科學領域出現了另一類并行最短路徑分析算法設計，目前關于并行最短路徑分析算法設計有基于MPI的主從Dijkstra并行算法[3]、MPI+open-MP混合算法[4]、社區分析的最短路徑LC-2q并行算法[5]等。

本文針對物流及時配送和成本控制需求，提出基于標色法的MapReduce廣度優先算法并行化模型，并應用于配送線路優化問題。由于MapReduce本身封裝了數據分割、負載均衡、容錯處理等細節，用戶只需要將實際應用問題分解成若干可并行操作的子問題，有效降低了求解難度，為解決物流配送運輸路徑優化問題提供了技術支持。

1 Map Reduce算法描述

信息技術和網絡技術的發展為云計算的產生提供了條件。MapReduce并行編程模型是云計算的核心技術之一。MapReduce是Google實驗室提出的一個分布式并行編程模型或框架,主要用來處理和產生海量數據的并行編程模式，2004年 DEAN J和GHEMAWAT S第一次發表了這一新型分布式并行編程模型[6]。用戶不必關注MapReduce如何進行數據分割、負載均衡、容錯處理等細節，只需要將實際應用問題分解成若干可并行操作的子問題，這種分解思路遵守主從架構模型。Mapreduce框架的主要程序分為 Master、Map和 Reduce。在 Hadoop中，MapReduce由一個主節點(Jobtracker,屬于 Master)和從節點(Tasktracker,屬于 Map和 Reduce)組成[7]。

1.1 基于標色法的Map Reduce廣度優先算法模型

給定一個帶權有向圖,用 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}為權值集。一般向圖的權值表示節點與節點之間的幾何長度,記為 w(ni,nj)=dij，dij表示節點 ni到節點 nj的距離。最短路徑計算就是計算從起始點ni到終止點nj的最短幾何長度之和為最小。在有向圖起始點和終止點的最短路徑計算中，MapReduce采用的是廣度優先算法。MapReduce計算最短路徑用鄰接表來表示圖，在鄰接表中每一行數據構成Map和Reduce的一個數據內容。Map和 Reduce的(key，value)中 key為 N，value值為與這個節點鄰接的所有節點的 AdjacentList。在用標色法求解最短路徑時，AdjacentList節點的信息包括源點到頂點的距離distance(除到本身的距離為0外，其余初始值皆為無窮大)；節點的顏色 color(其值可分別取 0、1、2，0表示未處理的頂點，1表示等待處理的頂點，2表示已處理的頂點，源點的初始值為1，其余頂點皆為 0)；被訪問頂點和邊的權值記為N和W。頂點的數據結構如表1所示。

表1 頂點的數據結構

1.2 Map Reduce求解步驟

(1)Master對輸入文件按行 (每行代表圖中的一個頂點)進行自動切分,并將數據作為輸入分發到每個Map任 務(keyin,valuein)， 即 輸 入[(ID,＜Distance;color;pnodes and weight＞)]；

(2)接收(keyin,valuein)對，當 valuein中的 color的值為1時，則處理當前頂點,產生臨時的{(keyout,valueout)│out=1...k}集；

(3)MapReduce對Map執行過程輸出的臨時中間結果進行分組(Shuffle/sort),將相同的key值即ID號合并成同一組(key，list(valuei)│i=1...m),并將其分發給空閑的Reduce；

(4)Reduce接收(key，list(valuei)),對相同 ID的 value進行合并，找到當前的最短路徑；

(5)如果每次Reduce后，結果收斂，則停止計算；如果未收斂，則繼續發給下一輪的Map過程，多次迭代計算直到color值全部為2，得到最終的最短路徑，算法結束。

MapReduce算法流程如圖1所示。

圖1 MapReduce算法流程

1.3 Map Reduce算法偽代碼

(1)MapReduce的第一次迭代偽代碼，Map部分為：

Map:＜k1,v1＞ → list(＜k2,v2＞)

其中k1為節點的ID；v1為該節點的距離、邊、邊的權值、顏色；每一個輸入的＜k1,v1＞會輸出一批＜k2,v2＞,它們是計算的中間結果。

2 案例分析

2.1 基本情況

韻達快遞浙江杭州西湖區文一路公司是民營韻達快運的子公司，為客戶提供快遞、物流及電子商務等一系列門到門服務。企業的配送范圍為文一路、文二路、教工路及學院路構成的矩形區域，該區域面積大約20 km2的范圍。

隨著第三方物流公司的增多，物流配送競爭越來越激烈。為了壓縮成本，按照配送點情況優化線路是節約成本的途徑之一,優化后的單源配送線路線可以將途經的配送點一并發送，形成一車多配的節約模式。

2.2 問題提出及求解

公司某次接到為4個區域 (西湖科技大廈、節能工業園、高新大廈及華門公寓)配送貨物的任務，配送員決定分頭配送，而如何組織好路線使得路程最短就可以歸結為單源最短路徑問題。為了計算方便，設置配送中心點為n1，被配送的4個地方分別設置西湖科技大廈為n2，節能工業園為 n3，高新大廈為 n4，華門公寓為 n5。4個區域之間及其與配送中心的幾何路線長度取整數(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出發選取怎樣的路線可 以 滿 足 到達 n2、n3、n4、n5的長度是最短的。采用標色法的MapReduce廣度優先算法計算，依照偽代碼的計算邏輯計算出源點到其他各點的最短路徑。通過4次迭代頂點到各點的最短路徑見圖2(f),其中加粗的圓圈表示被訪問過的頂點，color值為 2，圈內的數值為其與 n1的最短路徑長度;color值為0，虛線圈為未訪問的頂點，圈內值為 ∞;color值為1，虛線圈為待訪問的頂點，圈內值為標注值。MapReduce第一次迭代驗算數據如表2所示,其余幾次迭代過程格式與此類似。

如果從配送點n1到節能工業園n3進行配送，配送的最優路線就是配送點n1→高新大廈n4→西湖科技大廈n2→節能工業園n3。優化后的長度為 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，優化后的路線長度更短。在選擇這樣的配送路線后，途中高新大廈n4和西湖科技大廈n2的一些貨物也可以一并被配送，這樣就滿足了一車多配的情況，達到了節約成本的目的。

圖2 標色法的MapReduce廣度優先算法應用

表2 MapReduce第一次迭代驗算

本文將MapReduce并行編程模式引入了物流配送最短路徑查詢，用戶不必關注MapReduce如何進行數據分割、負載均衡、容錯處理等細節，只需將實際應用問題分解成若干可并行操作的子問題，即可解決配送線路優化問題，簡化了算法設計。為優化配送、節約成本、提高配送系統的運行效率提供了技術參考。

[1]劉榮華，孫皓，趙娟．基于供應鏈的運輸決策研究[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]盧照.基于城市路網最短路徑并行搜索算法的研究[D].陜西：陜西師范大學，2010.

[4]楊慶芳，劉東，楊兆生.基于 MPI+openMP混合編程模型的城市路網最短路徑并行算法[J].吉林大學學報(工學版)，2011,41(6)：1581-1584.

[5]馬明全,周明全,耿國華,等.基于社區分析的最短路徑計算[J].計算機應用與軟件,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]劉曉群，鄒 欣，范 虹.基于并行云計算模式的建筑結構設計[J].電子技術應用，2011,37(10)：123-125.