涂 偉,李清泉,,方志祥

1.深圳大學(xué)土木工程學(xué)院空間信息智能感知與服務(wù)深圳市重點實驗室,廣東深圳 518060;2.深圳大學(xué)海岸帶地理環(huán)境監(jiān)測國家測繪地理信息局重點實驗室,廣東深圳 518060;3.武漢大學(xué)測繪遙感信息工程國家重點實驗室,湖北武漢 430079

基于網(wǎng)絡(luò)Voronoi圖的大規(guī)模多倉庫物流配送路徑優(yōu)化

涂 偉1,2,李清泉1,2,3,方志祥3

1.深圳大學(xué)土木工程學(xué)院空間信息智能感知與服務(wù)深圳市重點實驗室,廣東深圳 518060;2.深圳大學(xué)海岸帶地理環(huán)境監(jiān)測國家測繪地理信息局重點實驗室,廣東深圳 518060;3.武漢大學(xué)測繪遙感信息工程國家重點實驗室,湖北武漢 430079

由于存在多約束和多個優(yōu)化目標(biāo),物流配送決策非常困難。本文針對城市多倉庫物流配送問題,提出基于網(wǎng)絡(luò)Voronoi圖的空間啟發(fā)式優(yōu)化方法。從空間角度將多倉庫物流配送優(yōu)化分解為區(qū)域分割和路徑優(yōu)化兩個空間子問題?；诰W(wǎng)絡(luò)Voronoi覆蓋進(jìn)行服務(wù)區(qū)域初始劃分,顧及倉庫容量差異,進(jìn)行區(qū)域邊界修正,并創(chuàng)建初始解。路徑優(yōu)化將局部搜索范圍限定在網(wǎng)絡(luò)K近鄰內(nèi),只搜索最有可能的空間鄰域,迭代改進(jìn)解的質(zhì)量。該算法最小化路徑數(shù)量和路徑長度。利用深圳市的大規(guī)模多倉庫物流配送問題測試算法性能。試驗結(jié)果表明:本文方法能夠在15 min內(nèi)求解6400個客戶點的大規(guī)模物流配送問題,解的質(zhì)量優(yōu)于Arc GIS約10.8%,計算時間約為其21.2%。

物流;啟發(fā)式優(yōu)化;網(wǎng)絡(luò)Voronoi圖;多倉庫車輛路徑問題

1 引 言

空間輔助決策廣泛應(yīng)用于物流中的倉庫選址、路徑優(yōu)化和物流監(jiān)控等活動中[1]?；诘乩硇畔⒓夹g(shù)的物流配送決策支持系統(tǒng)集成交通網(wǎng)絡(luò)、倉庫和客戶信息,顧及容量、距離等附加約束,進(jìn)行配送路線優(yōu)化,設(shè)計最小費用的運輸方案,輔助進(jìn)行物流運營決策,提高物流效率,降低物流費用[2-4],其核心是高效地進(jìn)行物流配送優(yōu)化。

物流配送通常建模為車輛路徑問題,其解空間搜索范圍隨客戶點數(shù)量增加呈階乘性擴大,計算時間隨之急劇增長,具有典型的NP難(nondeterministic polynomial hard)特性[5],求解非常困難[6]。準(zhǔn)確性方法只能求解不超過100個客戶點的物流配送問題[7]。啟發(fā)式方法能夠在4 h內(nèi)獲得3000個客戶點物流配送問題的近似最優(yōu)解[8]。因此需要研究更加高效的大規(guī)模物流配送優(yōu)化方法。

在城市物流中,通常有多個倉庫共同配送貨物,滿足多個客戶的預(yù)訂需求,一般建模為多倉庫物流配送優(yōu)化問題。從空間角度看,該問題包含兩個空間相關(guān)的子問題:區(qū)域劃分和路徑優(yōu)化。前者劃分每個倉庫的服務(wù)覆蓋區(qū)域,建立倉庫-客戶之間的服務(wù)關(guān)系,協(xié)調(diào)倉庫之間的競爭與合作,是多倉庫物流配送優(yōu)化的關(guān)鍵。直接劃分方法把客戶點剛性地分配給最近的倉庫[9-10]。較為復(fù)雜的劃分方法顧及倉庫-客戶服務(wù)關(guān)系的不確定性,依據(jù)概率將客戶分配到某個鄰近的倉庫[11]。這些方法在歐式空間下建立固定的倉庫-客戶服務(wù)關(guān)系,將多倉庫物流配送進(jìn)行分解,然后進(jìn)行路徑優(yōu)化。由于忽略了交通網(wǎng)絡(luò)限制和倉庫間的協(xié)作,設(shè)計的配送方案和現(xiàn)實情況存在偏差,其質(zhì)量有待改善。路徑優(yōu)化可改變多條配送路線的片段,迭代地改善配送方案,如:變鄰域搜索啟發(fā)式[11]、遺傳優(yōu)化[9]和蟻群優(yōu)化[12]等。傳統(tǒng)路徑優(yōu)化方法遍歷解空間,計算時間較長?？臻g優(yōu)化策略能夠有效提高優(yōu)化速度,如基于空間聚類的客戶點分組[13]、基于Voronoi鄰域的搜索空間精簡策略[14]和長邊引導(dǎo)優(yōu)化[15]。這些策略縮小局部搜索的空間范圍,優(yōu)化效率較高,但通常針對單倉庫物流配送,需要和區(qū)域劃分相配合。

從空間角度來看,多倉庫物流配送優(yōu)化是一個與空間要素緊密相關(guān)的優(yōu)化問題?？臻g特性常用于設(shè)計啟發(fā)式策略,快速高效地求解空間要素相關(guān)的優(yōu)化問題,如:設(shè)計地理多叉樹劃分策略,并行優(yōu)化大區(qū)域的空間資源配置[16];為保持避難所服務(wù)區(qū)域的連續(xù)性,設(shè)計基于空間鄰近替換策略,進(jìn)行避難所分配[17]。相關(guān)研究的啟示是:根據(jù)優(yōu)化問題的空間特性設(shè)計啟發(fā)式優(yōu)化方法。

Voronoi圖根據(jù)設(shè)施的空間分布,將連續(xù)空間劃分為相應(yīng)的勢力范圍,常用于商業(yè)設(shè)施的服務(wù)區(qū)域劃分[18],適合多倉庫物流配送優(yōu)化問題。顧及交通網(wǎng)絡(luò)的限制,基于網(wǎng)絡(luò)的Voronoi圖更適合表達(dá)多倉庫的服務(wù)區(qū)域競爭與合作[19-22]。針對多倉庫物流配送,本文提出基于網(wǎng)絡(luò)Voronoi圖的啟發(fā)式優(yōu)化方法,進(jìn)行多倉庫服務(wù)區(qū)域劃分與修正,并將路徑優(yōu)化過程限制在鄰近的客戶點內(nèi),快速設(shè)計大規(guī)模多倉庫物流路線,在短時間內(nèi)提供高質(zhì)量的配送方案,減少物流費用,提高物流效率。

2 多倉庫物流配送路徑優(yōu)化

多倉庫物流配送有多個倉庫和客戶點。每個客戶均有一個非負(fù)的需求qj(j為客戶點編號)。每個倉庫的容量為Ci,存儲客戶訂購的貨物。每個客戶點均無時間要求。多個倉庫之間互相合作,共同服務(wù)于這些客戶。物流車輛從某個倉庫出發(fā),服務(wù)于一定數(shù)量的客戶點,并最終返回該倉庫。配送方案設(shè)計若干車輛的行駛路徑,以最少的耗費訪問所有的客戶,滿足其需求。配送耗費通常以車輛數(shù)量、運輸耗費(總運輸距離或總運輸時間)等指標(biāo)度量。因此,多倉庫物流配送路徑優(yōu)化的數(shù)學(xué)模型如下

式中,I為倉庫數(shù)量;R為車輛數(shù)量;i為倉庫編號,r為車輛編號。xir是0－1二進(jìn)制變量,若車輛r從是從倉庫i出發(fā),并最終返回該倉庫,則xir＝1;否則,xir＝0。Lr是車輛r訪問其服務(wù)的客戶點的耗費,通常為運輸距離或運輸時間,本文中以運輸距離度量。優(yōu)化目標(biāo)F的第1項為車輛數(shù)量,第2項為運輸耗費。K為一個極大常數(shù),從而首先優(yōu)化車輛數(shù)量。多倉庫物流配送優(yōu)化有以下6個約束:

(1)客戶需求不可分割。一個客戶只能由一輛車服務(wù)一次,j為客戶點編號,r、r′為車輛編號

(2)每輛車最多只能使用一次

區(qū)域劃分是多倉庫物流配送優(yōu)化的關(guān)鍵。該過程決定每個倉庫所服務(wù)的客戶需求及其位置,直接限制路徑優(yōu)化的方向。適應(yīng)于道路網(wǎng)絡(luò)上的受限制運動,網(wǎng)絡(luò)Voronoi圖顧及道路通行規(guī)則,更加適合表達(dá)依賴于道路網(wǎng)絡(luò)的商業(yè)設(shè)施之間的空間競爭[19-20]。本文基于網(wǎng)絡(luò)Voronoi圖進(jìn)行多倉庫服務(wù)區(qū)域的初始劃分,將其劃分為每個倉庫的占優(yōu)服務(wù)空間。在倉庫容量有限的情況下,貨物儲量不一定完全滿足其Voronoi覆蓋內(nèi)的客戶需求,初始劃分需要進(jìn)一步修正。通過縮小儲量不足的倉庫的服務(wù)區(qū)域,擴大儲量豐富的倉庫的服務(wù)區(qū)域,進(jìn)行多個倉庫之間的協(xié)作,從而滿足客戶需求?；诰W(wǎng)絡(luò)Voronoi圖的區(qū)域劃分及其修正過程如圖1所示。

圖1 服務(wù)區(qū)域及其修正Fig.1 Service area and its refinement

路徑優(yōu)化設(shè)計性質(zhì)良好的搜索策略,在計算強度和解的質(zhì)量之間取得均衡?？臻g鄰域精簡策略將搜索區(qū)域限定在一定的空間范圍內(nèi),如平面K近鄰[6]、平面K環(huán)Voronoi鄰居[16]。由于只搜索小部分解空間,效率較高,適合大規(guī)模多倉庫物流配送優(yōu)化。顧及交通網(wǎng)絡(luò)約束,本文將局部搜索范圍限制在網(wǎng)絡(luò)K近鄰,保持解的質(zhì)量和計算效率之間的平衡。

3 基于網(wǎng)絡(luò)Voronoi圖的大規(guī)模多倉庫物流配送路徑優(yōu)化

基于網(wǎng)絡(luò)Voronoi圖的多倉庫物流配送優(yōu)化設(shè)計協(xié)調(diào)處理區(qū)域劃分和路徑優(yōu)化兩個過程。區(qū)域劃分過程基于網(wǎng)絡(luò)Voronoi圖進(jìn)行初始分割,修正區(qū)域邊界,并進(jìn)行倉庫-客戶服務(wù)關(guān)系調(diào)整?；诳臻g鄰近性,路徑優(yōu)化過程將局部搜索范圍限定在網(wǎng)絡(luò)K近鄰內(nèi),從而提高優(yōu)化效率。

算法流程如圖2所示,分為兩個階段:創(chuàng)建階段和改善階段。創(chuàng)建階段進(jìn)行服務(wù)區(qū)域初始劃分并修正,創(chuàng)建初始解。改善階段依次進(jìn)行服務(wù)關(guān)系調(diào)整和倉庫內(nèi)部的路徑優(yōu)化,迭代改進(jìn)解的質(zhì)量,最終輸出發(fā)現(xiàn)的最好解。

圖2 大規(guī)模多倉庫物流配送優(yōu)化方法流程Fig.2 The flow chart of large scale multi-depot logistics routing optimization

3.1 區(qū)域初始劃分及修正

區(qū)域劃分將服務(wù)范圍分割為各倉庫的服務(wù)空間,該過程首先創(chuàng)建倉庫的網(wǎng)絡(luò)Voronoi面域覆蓋,無縫地進(jìn)行服務(wù)區(qū)域初始劃分?？紤]到倉庫貨物儲量的差異,調(diào)整倉庫服務(wù)區(qū)域大小。

調(diào)整過程計算每個倉庫的Voronoi面域內(nèi)的客戶需求總和TDi,并與倉庫貨物儲量Ci相比較,如果Ci＜TDi,則進(jìn)行區(qū)域邊界修正。修正步驟搜索倉庫i的鄰近且貨物富余的倉庫j(Cj＞TDj),將共同邊界VEij向i移動,縮小倉庫i的覆蓋范圍,從而減少其服務(wù)的需求。移動距離d逐步增大,直至式(8)成立,其中Area(VEij,d)表示i和j的共同邊界VEij向倉庫i移動距離d所覆蓋的區(qū)域,TDArea(VEij,d)為覆蓋區(qū)域內(nèi)的客戶需求之和

3.2 初始解創(chuàng)建方法

服務(wù)區(qū)域劃分后,每個客戶被分配給其所在的倉庫。多倉庫物流配送被分割為多個單倉庫物流配送問題。初始解創(chuàng)建過程逐個倉庫進(jìn)行。

本文采用隨機插入法[24]生成每個倉庫服務(wù)區(qū)域內(nèi)的車輛路徑,該方法能夠充分利用車輛容量,使用較少車輛,且計算時間較短,適合大規(guī)模物流配送優(yōu)化。隨機插入法首先創(chuàng)建一條空的初始路徑。然后,每次隨機選擇倉庫內(nèi)一個未服務(wù)的節(jié)點j,依據(jù)插入費用最小的準(zhǔn)則,插入到順次服務(wù)的點對(a,b)中。若未找到可行的插入位置,則創(chuàng)建一條新的路徑,將節(jié)點j作為初始服務(wù)節(jié)點。插入費用按照式(9)計算,λ為[0.5,1.5]內(nèi)的隨機數(shù)

插入操作時需要滿足容量約束(式(3))和距離約束(式(4))。插入節(jié)點操作反復(fù)進(jìn)行,直到該倉庫所服務(wù)的客戶點均被安排插入到路徑中的合適位置。

3.3 服務(wù)關(guān)系調(diào)整

商業(yè)設(shè)施在Voronoi邊界附近存在空間競爭與合作。文獻(xiàn)[22]指出多個商業(yè)設(shè)施在服務(wù)區(qū)域邊界存在侵入、互侵與鄰域等競爭形態(tài)。本文將區(qū)域邊界的鄰近范圍定義為動態(tài)區(qū)域,其大小由到邊界的距離α定義。為了協(xié)調(diào)相鄰倉庫間的合作,服務(wù)關(guān)系調(diào)整過程利用移動節(jié)點和交換節(jié)點兩個操作在動態(tài)區(qū)域內(nèi)改變倉庫-客戶的服務(wù)關(guān)系。

移動節(jié)點[8]將一個節(jié)點插入其他倉庫服務(wù)節(jié)點的前面,如圖3(a)所示,路徑長度增加值為ΔC＝(dac＋dib＋dbj)－(dab＋dbc＋dij)。交換節(jié)點[8]互換兩個節(jié)點的位置,如圖3(b)所示,路徑長度增加值ΔC＝(daj＋dib＋dbk＋djc)－(dab＋dbc＋dij＋djk)。移動節(jié)點和交換節(jié)點均包含兩個操作參數(shù):b和j。操作時首先選擇動態(tài)區(qū)域內(nèi)的一個節(jié)點作為參數(shù)b,分析其網(wǎng)絡(luò)K近鄰且由其他倉庫服務(wù)的客戶點j,然后選擇目標(biāo)函數(shù)增加值最小的節(jié)點進(jìn)行。

圖3 局部搜索算子Fig.3 Local search operator

服務(wù)關(guān)系調(diào)整利用上述兩個算子,對動態(tài)區(qū)域內(nèi)的節(jié)點逐個分析,在滿足約束式(4)—(6)下,執(zhí)行那些減少目標(biāo)函數(shù)值的操作,從而加速路徑優(yōu)化過程。

3.4 路徑優(yōu)化過程

路徑優(yōu)化過程對每個倉庫內(nèi)的路徑進(jìn)行局部搜索,調(diào)整路徑內(nèi)或路徑間節(jié)點訪問順序,改善路徑的質(zhì)量。本文將局部搜索的空間范圍限制在客戶點的同一倉庫服務(wù)的網(wǎng)絡(luò)K近鄰內(nèi),利用有限的計算能力只搜索那些最應(yīng)該被搜索的客戶節(jié)點。

本文采用3個典型的局部搜索操作[23](local search operation,LSO)搜索鄰域解,包括移動節(jié)點、交換節(jié)點和交換片段。移動節(jié)點和交換節(jié)點操作如3.3節(jié)所述。交換片段操作[21]互換兩條路徑的尾部片段,如圖3(c)所示,路徑長度增加值為:ΔC＝(daj＋dibc)－(dab＋dij)。

局部搜索過程通常落入局部最優(yōu)解。模擬退火啟發(fā)式模仿固體的冷卻過程,逐漸降低溫度,最終收斂于一個穩(wěn)定狀態(tài)。該策略能夠接受一定程度的較差解,避免過早陷入局部最優(yōu),計算簡單,容易實現(xiàn)。本文采用閾值接受準(zhǔn)則接受較差解[6],如式(10)所示,其中f(s′)為鄰域解的目標(biāo)函數(shù)值,f(s)為當(dāng)前最好解的目標(biāo)函數(shù)值

局部搜索的操作過程如下:①隨機選擇一個局部搜索算子LSO;②隨機選擇一個客戶點b;③利用LSO分析客戶點b的同一倉庫服務(wù)的網(wǎng)絡(luò)K近鄰,找出目標(biāo)函數(shù)增加最小的節(jié)點j;④利用閾值接受準(zhǔn)則進(jìn)行判斷,執(zhí)行那些接受的局部操作。

每次迭代時,對于每個倉庫,路徑優(yōu)化過程執(zhí)行上述局部搜索操作3×N次(N為該倉庫服務(wù)節(jié)點數(shù)量),平均每個局部搜索算子對每個節(jié)點執(zhí)行一次。

3.5 時間復(fù)雜度

為了分析算法的時間復(fù)雜度,假設(shè)道路網(wǎng)絡(luò)的結(jié)構(gòu)不變,即節(jié)點、路段和拓?fù)洳蛔?倉庫點數(shù)量I,客戶點數(shù)量J,局部搜索的網(wǎng)絡(luò)Voronoi鄰近為K,動態(tài)區(qū)域的寬度為α。建立倉庫網(wǎng)絡(luò)Voronoi圖的時間為T(I,J)1＝O(I)[24]?？蛻酎c初始分配及調(diào)整的時間為T(I,J)2＝O(IJ)。初始解遍歷客戶點進(jìn)行插入操作,計算時間為T(I,J)3＝O(J)。服務(wù)關(guān)系調(diào)整的時間為T(I, J)4＝O(JαIK)。路徑優(yōu)化過程的時間為T(I, J)5＝O(IK)。本文優(yōu)化的計算總時間為T(I, J)1到T(I,J)5之和。由于多次迭代,T(I, J)1、T(I,J)2、T(I,J)3?T(I,J)4、T(I,J)5,即優(yōu)化計算主要集中在服務(wù)關(guān)系調(diào)整與路徑優(yōu)化。綜上所述,本文方法的時間復(fù)雜度為O(I＋I(xiàn)J＋J＋JαIK＋I(xiàn)K),是客戶點數(shù)量I的線性階函數(shù),也是倉庫點數(shù)量J的線性階函數(shù)。

4 試驗與比較

4.1 試驗數(shù)據(jù)與試驗環(huán)境

利用深圳市的導(dǎo)航電子地圖,模擬生成多倉庫物流配送問題,測試算法性能。深圳市的交通網(wǎng)絡(luò)數(shù)據(jù)共有115 904條邊,84 113個節(jié)點。每條邊依據(jù)實際通行規(guī)則設(shè)置為單向通行和雙向通行?？蛻酎c數(shù)據(jù)源于地圖中的商業(yè)類興趣點,客戶點需求qj為0～100間的隨機數(shù)。根據(jù)深圳市的土地利用規(guī)劃,設(shè)置合理的倉庫位置。從而模擬生成多倉庫物流配送問題。共設(shè)計了8個不同規(guī)模的物流配送問題?？蛻酎c規(guī)模從1600到6400不等,倉庫數(shù)量為2～8個。所有車輛均具有相同的容量Q＝2000,最大行駛距離為L＝500 km。每個問題實例的具體參數(shù)如表1所示。實例SZ1—SZ4中客戶位置、倉庫位置、需求大小和SZ5—SZ8中完全相同。特別的,SZ1—SZ4中貨物儲量充足,SZ5—SZ8中部分倉庫的貨物儲量不充足。在試驗中,以網(wǎng)絡(luò)距離度量運輸耗費,最小化使用車輛數(shù)量和路徑總長度。

試驗環(huán)境為臺式PC,內(nèi)存為4 GB,CPU為Intel Core i7-3700＠3.40 GHZ,操作系統(tǒng)環(huán)境為64位Windows 7。本文算法采用C＋＋語言實現(xiàn),為單線程執(zhí)行模式。

表1 多倉庫物流配送問題實例的參數(shù)明細(xì)Tab.1 Details of multi-depot logistics distribution instances

算法性能以解的質(zhì)量和計算效率度量。高質(zhì)量的解要求盡量使用最少的車輛,同時路徑總長度盡可能少。計算效率以計算時間作為參考指標(biāo),時間越少,效率越高。

4.2 試驗結(jié)果與分析

經(jīng)過多次試驗,設(shè)定了本文算法執(zhí)行時的動態(tài)區(qū)域大小α＝500 m,優(yōu)化最大迭代次數(shù)Imax＝2000,網(wǎng)絡(luò)K近鄰K＝30。每個問題實例運行算法3次,記錄最好解的車輛數(shù)量、路徑總長度和計算時間。

表2統(tǒng)計8個多倉庫物流配送問題的計算結(jié)果。由表可知,本文算法在較快時間內(nèi)生成了初始解。從解的質(zhì)量上看,相對于初始解,經(jīng)過服務(wù)關(guān)系調(diào)整和路徑優(yōu)化后,解的質(zhì)量得到了明顯提升。初始解生成時間較短,在規(guī)模最大的實例SZ8上,本文算法在82.4 s內(nèi)生成了初始解。在使用車輛數(shù)量上,初始解的路徑數(shù)量已經(jīng)較少,實例SZ1、SZ2、SZ5、SZ6的初始方案和最終方案一致。在SZ3、SZ4、SZ7、SZ8上,最終方案使用的車輛數(shù)量均有所減少。8個實例使用的車輛數(shù)量和從820減少到810,略高于理論上的最小值(808)。在路徑長度上,最終方案的路徑總長度約為初始方案的24.1%。和貨物充足的問題SZ1—SZ4比較,SZ5—SZ8的算法性能大致相同。綜上所述,基于網(wǎng)絡(luò)Voronoi圖的啟發(fā)式優(yōu)化方法能夠大幅度改善初始解的質(zhì)量。

在計算效率上,本文算法在867.8 s內(nèi)給出了6400個客戶點的實例SZ8的解,用時較少。計算時間隨客戶點數(shù)量增長較為緩慢。如表2所示,以實例SZ1為基準(zhǔn),SZ4的客戶點增長了4倍,其計算時間約增長了7.2倍,增長速度略高于線性增長,和理論分析結(jié)果基本一致。

表2 大規(guī)模多倉庫物流配送問題實例計算結(jié)果Tab.2 The result of large scale multi-depot logistics distribution instances

圖4以多倉庫物流配送實例SZ6為例,給出了其總路徑長度的迭代曲線。雖然初始解的總路徑長度較大,本文的優(yōu)化算法仍然能夠較快地收斂到一個高質(zhì)量的解。

圖4 總路徑長度迭代曲線(SZ6)Fig.4 The iterated curve of total routes length

圖5給出了SZ2和SZ6物流配送路線方案。由圖5(a)可知,不同倉庫服務(wù)區(qū)域的節(jié)點基本上位于對應(yīng)的網(wǎng)絡(luò)Voronoi區(qū)域內(nèi)。在圖5(b)中,本文方法顧及貨物儲量的不足,進(jìn)行區(qū)域邊界調(diào)整,服務(wù)范圍相應(yīng)減小。在服務(wù)區(qū)域邊緣,不同倉庫出發(fā)的車輛配送路徑相互重疊或交叉,進(jìn)行協(xié)作,減少了總路徑長度。因此,基于網(wǎng)絡(luò)Voronoi圖的空間啟發(fā)式策略引導(dǎo)多個倉庫在動態(tài)服務(wù)區(qū)域相互配合,協(xié)同完成物流配送任務(wù)。

綜上所述,基于網(wǎng)絡(luò)Voronoi圖的啟發(fā)式優(yōu)化方法能夠在15 min內(nèi)提供6400個客戶點的大規(guī)模多倉庫物流配送方案。

圖5 多倉庫物流配送方案示例Fig.5 An example of multi-depot logistic distribution

4.3 動態(tài)區(qū)域

為了分析動態(tài)區(qū)域的效果,本文設(shè)計4種策略,分別是:無動態(tài)區(qū)域(S1,α＝0),即是剛性的網(wǎng)絡(luò)Voronoi劃分,倉庫之間無路徑協(xié)作;窄動態(tài)區(qū)域(S2,α＝200);一般動態(tài)區(qū)域(S3,α＝500);寬動態(tài)區(qū)域(S4,α＝1000)。以SZ6為例,進(jìn)行多倉庫物流配送優(yōu)化,記錄優(yōu)化方案的路徑長度和計算時間。

計算結(jié)果如表3所示。由表可知,4種策略的路徑數(shù)量均相同。在路徑長度上,無動態(tài)區(qū)域策略S1劣于動態(tài)區(qū)域策略(S2、S3、S4)。動態(tài)區(qū)域大小對優(yōu)化方案也有影響。與策略S2和S4相比,S3的路徑總長度為3 157.755 km,質(zhì)量最好。試驗結(jié)果表明:恰當(dāng)?shù)膭討B(tài)區(qū)域策略能夠協(xié)調(diào)多個倉庫之間的競爭與合作關(guān)系,進(jìn)一步提高解的質(zhì)量。在計算效率上,隨著動態(tài)區(qū)域的擴大,計算時間有所增長,但增長幅度不大。

表3 不同α值下最優(yōu)方案(SZ6)的路徑長度Tab.3 Results of settings of the parameterα

4.4 算法比較

為了驗證算法性能,將本文算法計算結(jié)果和其他算法進(jìn)行比較。比較指標(biāo)為路徑數(shù)量、路徑長度和計算時間?？紤]到算法的可獲得性,比較算法為ArcGIS10中的Network Analyst模塊。利用該模塊計算4.1節(jié)中多倉庫物流配送實例。試驗時ArcGIS10運行于和本文算法相同的計算平臺。對于SZ5—SZ8,根據(jù)倉庫貨物儲量的差異,需要人工預(yù)先設(shè)計各倉庫的車輛配置方案。

試驗結(jié)果如表4所示。由表可知,本文算法的解顯著優(yōu)于ArcGIS的解。在解的質(zhì)量上, ArcGIS的解的車輛數(shù)量為812條,略高于本文算法。然而,在路徑長度指標(biāo)上,ArcGIS解的路徑長度和最少高于本文算法約9.1%(SZ3),最多高于本文算法約11.4%(SZ7),平均高于本文算法約10.8%。因此,ArcGIS的計算結(jié)果顯著劣于本文算法。在計算時間上,ArcGIS的計算時間約為本文算法的4.72倍(2 204.3/466.7)。本文算法的配送方案質(zhì)量優(yōu)于ArcGIS 10,計算時間更少,算法性能顯著優(yōu)于ArcGIS。

表4 多倉庫物流配送問題的計算結(jié)果比較Tab.4 The comparison of results of the proposed algorithm and the ArcGIS

5 結(jié) 論

由于存在多約束和多優(yōu)化目標(biāo),大規(guī)模多倉庫物流配送優(yōu)化十分困難。本文提出了基于網(wǎng)絡(luò)Voronoi圖的大規(guī)模多倉庫物流配送路徑優(yōu)化新方法。該方法利用倉庫的網(wǎng)絡(luò)Voronoi圖對服務(wù)區(qū)域進(jìn)行初始劃分,顧及倉庫容量差異修正區(qū)域邊界,并調(diào)整邊界鄰近區(qū)域的倉庫-客戶服務(wù)關(guān)系,將局部搜索限定在網(wǎng)絡(luò)K近鄰內(nèi),充分利用有限的計算能力,在短時間內(nèi)提供高質(zhì)量的物流配送方案。利用深圳市的大規(guī)模多倉庫物流配送優(yōu)化實例進(jìn)行驗證,結(jié)果表明:該算法解的質(zhì)量優(yōu)于ArcGIS 10約為10.8%,計算時間約為其21.2%。本文方法可廣泛用于電子商務(wù)、快遞配送和城市垃圾收集中的方案設(shè)計,提高物流效率,減少物流費用。后續(xù)研究可以考慮倉庫的重要程度,利用帶權(quán)網(wǎng)絡(luò)Voronoi圖進(jìn)行物流配送優(yōu)化;顧及客戶點的時間要求,優(yōu)化附帶時間窗的多倉庫物流配送問題。同時,本文的空間啟發(fā)式優(yōu)化思想可以進(jìn)一步拓展至其他空間相關(guān)優(yōu)化問題,利用空間特性、空間結(jié)構(gòu)和空間規(guī)律等,發(fā)展高效率的優(yōu)化機制,應(yīng)用于設(shè)施選址、應(yīng)急疏散、資源調(diào)度等。

[1] QI Minyao.Research on the Logistics Oriented Spatial Information Service and Its Key Technical Issues[D].Beijing:Institute of Remote Sensing Applications,Chinese Academy of Sciences,2006.(戚銘堯.面向物流的空間信息服務(wù)及其關(guān)鍵技術(shù)研究[D].北京:中科院遙感應(yīng)用研究所,2006.)

[2] REPOUSSISP P,PARAKEVOPOULOS D,ZOBOLAS G,et al.A Web-based Decision Support System for Waste Lube Oils Collection and Recycling[J].European Journal of Operational Research,2009,195(3):676-700.

[3] SANTOS L,COUTINHO-RODRIGUES J,ANTUNES C H.A Web Spatial Decision Support System for Vehicle Routing Using Google Maps[J].Decision Support Systems,2011,51(1):1-9.

[4] SANTOS L,COUTINHO R J,CURRENT J R.Implementing a Multi-vehicle Multi-route Spatial Decision Support System for Efficient Trash Collection in Portugal [J].Transportation Research Part A:Policy and Practice, 2008,42(6):922-934.

[5] LAPORTE G.Fifty Years of Vehicle Routing[J].Transportation Science,2009,43(4):408-416.

[6] LI Feiyue,GOLDEN B,WASIL E.Very Large-scale Vehicle Routing:New Test Problems,Algorithms,and Results [J].Computers and Operations Research,2005,32(5): 1165-1179.

[7] TOTH P,DANIELE V.The Vehicle Routing Problem[M].Philadelphia:Society for Industrial and Applied Mathematics,2002.

[8] ZACHARIADIS E E,KIRANOUDIS C T.A Strategy for Reducing the Computational Complexity of Local Searchbased Methods for the Vehicle Routing Problem[J].Computers and Operations Research,2010,37(12): 2089-2105.

[9] HO W,HO G T S,JI P,et al.A Hybrid Genetic Algorithm for the Multi-depot Vehicle Routing Problem[J].Engineering Applications of Artificial Intelligence,2008, 21(4):548-557.

[10] CORDEAU J F,GENDREAU M,LAPORTE G.A Tabu Search Heuristic for Periodic and Multi-depot Vehicle Routing Problems[J].Networks,1997,30(2):105-119.

[11] KUO,Y,WANG C C.A Variable Neighborhood Search for the Multi-depot Vehicle Routing Problem with Loading Cost[J].Expert Systems with Applications,2012,39, 6949-6954.

[12] YU B,YANG Z Z,XIE J X.A Parallel Improved Ant Colony Optimization for Multi-depot Vehicle Routing Problem [J].Journal of the Operational Research Society,2010, 62,183-188.

[13] SHI Yarong,WAN Difang,LI Shuangyan,et al.Research of Vehicle Routing Problem Based on GIS[J].System Engineering-Theory and Practice,2009,29(10):76-85.(史亞容,萬迪昉,李雙燕,等.基于GIS的物流配送路線規(guī)劃研究[J].系統(tǒng)工程理論與實踐,2009,29(10):76-85.)

[14] FANG Zhixiang,TU Wei,LI Qingquan,et al.A Voronoi Neighborhood-based Search Heuristic for Distance/ Capacity Constrained Very Large Vehicle Routing Problems[J].International Journal of Geographical Information Science,2013,27(4):741-764.

[15] T U Wei,LI Qingquan,FANG Zhixiang.A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J].Geomatics and Information Science of Wuhan University, 2013,38(3):307-310.(涂偉,李清泉,方志祥.一種大規(guī)模車輛路徑問題的啟發(fā)式算法[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2013,38(3):307-310.)

[16] ZHAO Yuan,ZHANG Xinchang,KANG Tingjun.A Parallel Ant Colony Optimization Algorithm for Site Location[J].Acta Geodaetica et Cartographica Sinica,2010,39(3): 322-327.(趙元,張新長,康停軍.并行蟻群算法及其在區(qū)位選址中的應(yīng)用[J].測繪學(xué)報,2010,39(3):322-327.)

[17] LIU Jiubao,TANG Xinming,LIU Zhengjun,et al.Research algorithm of Shelter Assignment Based on Capability Limitation and Optimization of the Travel Cost[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):489-494.(劉久保,唐新明,劉正軍,等.基于行程距離最優(yōu)及容量受限的避難所分配算法研究[J].測繪學(xué)報,2011, 40(4),489-494.)

[18] OKABE A,SATOH T,FURUTA T,et al.Generalized Network Voronoi Diagrams:Concepts,Computational Methods,and Applications[J].International Journal of Geographical Information Science,2008,22(9):965-994.

[19] XIE Shunping,FENG Xuezhi,WANG Jiechen,et al.Radiation Domain of Commercial Centers in Nanjing Based on Analysis of Road Network Weighted Voronoi Diagram[J].Acta Geographica Sinica,2009,64(12): 1467-1476.(謝順平,馮學(xué)智,王結(jié)臣,等.基于網(wǎng)絡(luò)加權(quán)Voronoi圖分析的南京市商業(yè)中心輻射域研究[J].地理學(xué)報,2009,64(12):1467-1476.)

[20] XIE Shunping,FENG Xuezhi,DU Jinkang.Maximal Covering Spatial Optimization Based on Network Voronoi Diagrams Heuristic and Swarm Intelligence[J].Acta Geodaetica et Cartographica Sinica,2011,40(6):778-883.(謝順平,馮學(xué)智,都金康.基于網(wǎng)絡(luò)Voronoi圖啟發(fā)式和群智能的最大覆蓋空間優(yōu)化[J].測繪學(xué)報,2011,40(6):778-883.)

[21] AI Tinghua,YU Wenhao.Algorithm for Constructing Network Voronoi Diagram Based on Flow Extension Ideas[J].Acta Geodaetica et Cartographica Sinica,2013,42(5):760-766.(艾廷華,禹文豪.水流擴展思想的網(wǎng)絡(luò)空間Voronoi圖生成[J].測繪學(xué)報,2013,42(5):760-766.)[22] ZHU Weining,MA Jinsong,HUANG Xinyuan,et al.A Study of GISSpatial Competition Analysis Model Based on Projective Weighted Voronoi Diagrams[J].Acta Geodaetica et Cartographica Sinica,2004,33(2):146-150.(朱渭寧,馬勁松,黃杏元,等.基于投影加權(quán)Voronoi圖的GIS空間競爭分析模型研究[J].測繪學(xué)報,2004,33(2):146-150.)

[23] MOLE R,JAMESON S.A Sequential Route-building Algorithm Employing a Generalized Savings Criterion[J].Operational Research Quarterly,1976,27(2):503-511.

[24] XIE Shunping,FENG Xuezhi,LU Wei.Algorithm for Constructing Voronoi Area Diagram Based on Road Network Analysis[J].Acta Geodaetica et Cartographica Sinica,2010,39(1):88-94.(謝順平,馮學(xué)智,魯偉.基于道路網(wǎng)絡(luò)分析的Voronoi面域圖構(gòu)建算法[J].測繪學(xué)報, 2010,39(1):88-94.)

(責(zé)任編輯:宋啟凡))

Large Scale Multi-depot Logistics Routing Optimization Based on Network Voronoi Diagram

TU Wei1,2,LI Qingquan1,2,3,FANG Zhixiang3
1.Shenzhen Key Laboratory of Spatial Smart Sensing and Services,College of Civil Engineering,Shenzhen University,Shenzhen 518060,China;2.Key Laboratory for Geo-Environment Monitoring of Coastal Zone of the National Administration of Surveying,Mapping and GeoInformation,Shenzhen University,Shenzhen 518060,China;3.State Key Laboratory of Information Engineering in Surveying,Mapping,and Remote Sensing,Wuhan University,Wuhan 430079,China

Due to multi-constraints and multi-objectives,the optimization for large scale multi-depot logistics routing problem is very difficult.A spatial heuristics algorithm is proposed based on the network Voronoi diagram.From the spatial perspective,two involved spatial issues in the multi-depot logistics routing problem are service area partition and routing optimization.By using of depots’network Voronoi diagram,service area is coarsely partitioned and refined according to the goods storage in each depot.For the routing optimization,the local search space is limited within the spatial neighbors of customers.The proposed heuristics minimizes the used vehicles number and the total routes length.An experiment on several large scale logistics distribution instances in Shenzhen,China was implemented to validate the performance of the proposed heuristics algorithm.Results indicated that it provided high quality solution for large scale instances with 6400 customers in no more than 15 minutes.The proposed heuristics algorithm could be widely used in e-commerce,express delivery,public utility in city to promote logistics efficiency.

logistics;heuristic;network Voronoi diagram;multi-depot vehicle routing problem

TU Wei(1984—),male,PhD,majors in spatial-temporal data modeling,analysis and optimization.

P208

A

1001-1595(2014)10-1075-08

國家自然科學(xué)基金(41401444;41231171;41371377);深圳市戰(zhàn)略性新興產(chǎn)業(yè)發(fā)展專項資金(JCYJ20121019111128765);深圳市基礎(chǔ)研究計劃(JCYJ20120817163755063);測繪遙感信息工程國家重點實驗室開放基金(13S02)

2013-12-17

涂偉(1984—),男,博士,主要研究方向為時空數(shù)據(jù)建模、分析與優(yōu)化。

E-mail:tuwei＠szu.edu.cn

TU Wei,LI Qingquan,FANG Zhixiang.Large Scale Multi-depot Logistics Routing Optimization Based on Network Voronoi Diagram[J].Acta Geodaetica et Cartographica Sinica,2014,43(10):1075-1082.(涂偉,李清泉,方志祥.基于網(wǎng)絡(luò)Voronoi圖的大規(guī)模多倉庫物流配送路徑優(yōu)化[J].測繪學(xué)報,2014,43(10):1075-1082.)

10.13485/j.cnki.11-2089.2014.0153

修回日期:2014-03-12