涂 偉,李清泉,,方志祥

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

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

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

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

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

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

1 引 言

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

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

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

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

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

2 多倉(cāng)庫(kù)物流配送路徑優(yōu)化

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

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

(1)客戶需求不可分割。一個(gè)客戶只能由一輛車(chē)服務(wù)一次,j為客戶點(diǎn)編號(hào),r、r′為車(chē)輛編號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 時(shí)間復(fù)雜度

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

4 試驗(yàn)與比較

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

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

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

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

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

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

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

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

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

表2 大規(guī)模多倉(cāng)庫(kù)物流配送問(wèn)題實(shí)例計(jì)算結(jié)果Tab.2 The result of large scale multi-depot logistics distribution instances

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

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

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

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

圖5 多倉(cāng)庫(kù)物流配送方案示例Fig.5 An example of multi-depot logistic distribution

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

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

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

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

4.4 算法比較

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

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

表4 多倉(cāng)庫(kù)物流配送問(wèn)題的計(jì)算結(jié)果比較Tab.4 The comparison of results of the proposed algorithm and the ArcGIS

5 結(jié) 論

由于存在多約束和多優(yōu)化目標(biāo),大規(guī)模多倉(cāng)庫(kù)物流配送優(yōu)化十分困難。本文提出了基于網(wǎng)絡(luò)Voronoi圖的大規(guī)模多倉(cāng)庫(kù)物流配送路徑優(yōu)化新方法。該方法利用倉(cāng)庫(kù)的網(wǎng)絡(luò)Voronoi圖對(duì)服務(wù)區(qū)域進(jìn)行初始劃分,顧及倉(cāng)庫(kù)容量差異修正區(qū)域邊界,并調(diào)整邊界鄰近區(qū)域的倉(cāng)庫(kù)-客戶服務(wù)關(guān)系,將局部搜索限定在網(wǎng)絡(luò)K近鄰內(nèi),充分利用有限的計(jì)算能力,在短時(shí)間內(nèi)提供高質(zhì)量的物流配送方案。利用深圳市的大規(guī)模多倉(cāng)庫(kù)物流配送優(yōu)化實(shí)例進(jìn)行驗(yàn)證,結(jié)果表明:該算法解的質(zhì)量?jī)?yōu)于ArcGIS 10約為10.8%,計(jì)算時(shí)間約為其21.2%。本文方法可廣泛用于電子商務(wù)、快遞配送和城市垃圾收集中的方案設(shè)計(jì),提高物流效率,減少物流費(fèi)用。后續(xù)研究可以考慮倉(cāng)庫(kù)的重要程度,利用帶權(quán)網(wǎng)絡(luò)Voronoi圖進(jìn)行物流配送優(yōu)化;顧及客戶點(diǎn)的時(shí)間要求,優(yōu)化附帶時(shí)間窗的多倉(cāng)庫(kù)物流配送問(wèn)題。同時(shí),本文的空間啟發(fā)式優(yōu)化思想可以進(jìn)一步拓展至其他空間相關(guān)優(yōu)化問(wèn)題,利用空間特性、空間結(jié)構(gòu)和空間規(guī)律等,發(fā)展高效率的優(yōu)化機(jī)制,應(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.(史亞容,萬(wàn)迪昉,李雙燕,等.基于GIS的物流配送路線規(guī)劃研究[J].系統(tǒng)工程理論與實(shí)踐,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ī)模車(chē)輛路徑問(wèn)題的啟發(fā)式算法[J].武漢大學(xué)學(xué)報(bào):信息科學(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.(趙元,張新長(zhǎng),康停軍.并行蟻群算法及其在區(qū)位選址中的應(yīng)用[J].測(cè)繪學(xué)報(bào),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].測(cè)繪學(xué)報(bào),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é)報(bào),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].測(cè)繪學(xué)報(bào),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.(艾廷華,禹文豪.水流擴(kuò)展思想的網(wǎng)絡(luò)空間Voronoi圖生成[J].測(cè)繪學(xué)報(bào),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ìng)爭(zhēng)分析模型研究[J].測(cè)繪學(xué)報(bào),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].測(cè)繪學(xué)報(bào), 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

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

2013-12-17

涂偉(1984—),男,博士,主要研究方向?yàn)闀r(shí)空數(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ī)模多倉(cāng)庫(kù)物流配送路徑優(yōu)化[J].測(cè)繪學(xué)報(bào),2014,43(10):1075-1082.)

10.13485/j.cnki.11-2089.2014.0153

修回日期:2014-03-12