亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2014-12-07 06:19:10張寶友
        電子技術(shù)應(yīng)用 2014年3期
        關(guān)鍵詞:物流配送大廈頂點

        鈕 亮,張寶友

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

        隨著電子商務(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 Map Reduce算法描述

        信息技術(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 基于標色法的Map Reduce廣度優(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 頂點的數(shù)據(jù)結(jié)構(gòu)

        1.2 Map Reduce求解步驟

        (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 MapReduce算法流程

        1.3 Map Reduce算法偽代碼

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

        Map:<k1,v1> → list(<k2,v2>)

        其中k1為節(jié)點的ID;v1為該節(jié)點的距離、邊、邊的權(quán)值、顏色;每一個輸入的<k1,v1>會輸出一批<k2,v2>,它們是計算的中間結(jié)果。

        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é)約成本的目的。

        圖2 標色法的MapReduce廣度優(yōu)先算法應(yīng)用

        表2 MapReduce第一次迭代驗算

        本文將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.

        猜你喜歡
        物流配送大廈頂點
        山西將打造高效農(nóng)村快遞物流配送體系
        過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應(yīng)用(下)
        基于精益生產(chǎn)的SPS物流配送應(yīng)用研究
        影子大廈
        文苑(2020年12期)2020-04-13 00:54:16
        基于Flexsim的飲品物流配送中心仿真優(yōu)化研究
        關(guān)于頂點染色的一個猜想
        山東科學(2018年6期)2018-12-20 11:08:58
        直企物流配送四步走
        電梯
        故事大王(2018年3期)2018-05-03 09:55:52
        冰淇淋大廈
        旋轉(zhuǎn)大廈
        蜜桃传媒免费观看视频| 欧美在线三级艳情网站| 国产精品大屁股1区二区三区| 美女露屁股无内裤视频| 性色av色香蕉一区二区蜜桃| 一区二区三区视频| 国产成人无码区免费网站| AV无码专区亚洲AVL在线观看 | 精品一区二区三区国产av| 日韩国产人妻一区二区三区| 1000部夫妻午夜免费| 成年男人裸j照无遮挡无码| 色男色女午夜福利影院| 成人免费看aa片| 国产主播一区二区三区在线观看 | 男女男在线精品网站免费观看 | 二区视频在线免费观看| 东北老女人高潮大喊舒服死了| 国产乱子伦露脸在线| 国产精品女同一区二区久| 看女人毛茸茸下面视频| 久久久精品人妻无码专区不卡| 在线精品国内视频秒播| 亚洲无av高清一区不卡| 精品国产yw在线观看| 全球av集中精品导航福利| 男人阁久久| 91国产自拍精品视频| 台湾佬中文偷拍亚洲综合| 日本精品一区二区三区在线观看| 亚洲精品无码久久久影院相关影片| 波多野结衣一区| 97激情在线视频五月天视频| 成年丰满熟妇午夜免费视频 | 亚洲中文久久精品无码ww16| 极品人妻少妇一区二区| 少妇免费av一区二区三区久久 | 久久精品噜噜噜成人| 久久精品国产亚洲AV无码不| 成人黄色片久久久大全| 国产国产人免费人成免费视频|