基于加權(quán)Voronoi圖的連續(xù)型物流節(jié)點(diǎn)布局優(yōu)化＊

王 偉 封學(xué)軍

（河海大學(xué)港口海岸與近海工程學(xué)院水運(yùn)規(guī)劃與物流工程研究所1） 南京 210098）（長(zhǎng)沙理工大學(xué)公路工程省部共建教育部重點(diǎn)實(shí)驗(yàn)室2） 長(zhǎng)沙 410004）

國(guó)內(nèi)外學(xué)者采用調(diào)查法、雷利法則、引力模型、需求勢(shì)能理論、系統(tǒng)建模等方法［1－4］研究了物流節(jié)點(diǎn)的合理服務(wù)范圍劃分；相關(guān)學(xué)者還基于物流節(jié)點(diǎn)服務(wù)范圍的分析，基于重心法、鮑姆爾－沃爾夫法、雙層規(guī)劃、混合整數(shù)規(guī)劃、圖論等方法構(gòu)建了物流節(jié)點(diǎn)布局優(yōu)化模型［5－6］，系統(tǒng)地研究了物流節(jié)點(diǎn)數(shù)量、選址、規(guī)模的綜合優(yōu)化問題.現(xiàn)有的研究雖能概要性確定物流節(jié)點(diǎn)服務(wù)范圍，但未能綜合反映物流節(jié)點(diǎn)對(duì)服務(wù)區(qū)域的吸引，難以滿足動(dòng)態(tài)性、系統(tǒng)性的要求，且只是粗略的劃分，在一定程度上限制了物流節(jié)點(diǎn)布局優(yōu)化研究的深度和準(zhǔn)確性.

本文采用引力模型來確定物流節(jié)點(diǎn)對(duì)區(qū)域空間的吸引力，引入加權(quán)Voronoi圖來實(shí)現(xiàn)物流系統(tǒng)空間服務(wù)范圍的動(dòng)態(tài)精確劃分，在此基礎(chǔ)上，構(gòu)建連續(xù)型物流節(jié)點(diǎn)布局優(yōu)化模型，提出模型的高效求解算法.

1 加權(quán)Voronoi圖

加權(quán)Voronoi圖［7］的定義如下：

設(shè)P＝（P1，P2，…，Pn），3≤n＜∞為二維歐氏空間上的一個(gè)控制點(diǎn)集；λi（i＝1，2，…，n）是給定的n個(gè)正實(shí)數(shù)，則

將平面分成n部分，由V（pi，λi）（i＝1，2，…，n）確定的對(duì)平面的分割稱為點(diǎn)上加權(quán)的Voronoi圖，稱λi為pi的權(quán)重.

加權(quán)Voronoi圖的生成可采用離散生成算法，此方法無需復(fù)雜的計(jì)算，容易實(shí)現(xiàn)［8］.同時(shí)，考慮到物流節(jié)點(diǎn)存在多層級(jí)情況，假設(shè)物流節(jié)點(diǎn)的競(jìng)爭(zhēng)只存在于同級(jí)別的節(jié)點(diǎn)之間，對(duì)于多層級(jí)物流節(jié)點(diǎn)服務(wù)范圍的劃分可以轉(zhuǎn)化為多個(gè)單層級(jí)內(nèi)物流節(jié)點(diǎn)服務(wù)范圍劃分問題，通過多次離散生成法來實(shí)現(xiàn).

2 物流節(jié)點(diǎn)服務(wù)范圍劃分的引力模型

物流節(jié)點(diǎn)服務(wù)范圍的劃分要考慮到內(nèi)外部環(huán)境中的諸多因素，物流節(jié)點(diǎn)服務(wù)范圍的確定與節(jié)點(diǎn)的層級(jí)、功能、規(guī)模、服務(wù)對(duì)象緊密關(guān)聯(lián)，提出如下假設(shè)：物流節(jié)點(diǎn)的功能是一致的；只考慮同層級(jí)物流節(jié)點(diǎn)之間的競(jìng)爭(zhēng)；物流節(jié)點(diǎn)對(duì)服務(wù)區(qū)域的吸引力也存在“規(guī)模效應(yīng)”和“遞遠(yuǎn)遞減”的現(xiàn)象.構(gòu)建物流節(jié)點(diǎn)的吸引力模型來解決物流節(jié)點(diǎn)服務(wù)范圍劃分的問題［9］，設(shè)有n個(gè)物流節(jié)點(diǎn)（同一層級(jí)），s個(gè)需求點(diǎn)（可將區(qū)域物流系統(tǒng)服務(wù)區(qū)域劃分為若干個(gè)小區(qū)），則物流節(jié)點(diǎn)i對(duì)需求點(diǎn)j的吸引力為

式中：mi為物流節(jié)點(diǎn)或其所在區(qū)域的“質(zhì)量”，即物流節(jié)點(diǎn)的競(jìng)爭(zhēng)力，這里選擇物流節(jié)點(diǎn)規(guī)模、區(qū)位交通條件、技術(shù)作業(yè)水平及效率和所在區(qū)域的經(jīng)濟(jì)總量4個(gè)因素來確定物流節(jié)點(diǎn)綜合競(jìng)爭(zhēng)力

其中：si，qi，ei，gi分別為物流節(jié)點(diǎn)i的規(guī)模、區(qū)位交通條件、技術(shù)作業(yè)水平、所在區(qū)域的經(jīng)濟(jì)總量，Si，Qi，Ei，Gi分別為其歸一化后的值；b1，b2，b3，b4為權(quán)重系數(shù)，b1＋b2＋b3＋b4＝1，可采用 AHP法確定.

dij為需求點(diǎn)j到物流節(jié)點(diǎn)i的廣義費(fèi)用，這里取運(yùn)輸里程、運(yùn)輸時(shí)間和運(yùn)輸費(fèi)用3個(gè)主要因子構(gòu)建路權(quán)函數(shù)，dij＝a1Lij＋a2Tij＋a3Fij＝其中：lij，tij，fij分別為需求點(diǎn)j到物流節(jié)點(diǎn)i的運(yùn)輸里程、運(yùn)輸時(shí)間、運(yùn)輸費(fèi)用，Lij，Tij，F(xiàn)ij分別為其歸一化后的值；a1，a2，a3為權(quán)重系數(shù)，a1＋a2＋a3＝1，可采用AHP法確定；

k為引力系數(shù)；θ為引力衰減指數(shù)，以［1，2］為宜.

同時(shí)，考慮到物流節(jié)點(diǎn)作業(yè)能力限制等條件，對(duì)物流節(jié)點(diǎn)服務(wù)范圍劃分可采用多次劃分的方式，即當(dāng)物流節(jié)點(diǎn)i飽和度大于1時(shí)，對(duì)需求點(diǎn)j到物流節(jié)點(diǎn) 的廣義費(fèi)用進(jìn)行動(dòng)態(tài)調(diào)整，進(jìn)行動(dòng)態(tài)劃分.

3 物流節(jié)點(diǎn)布局優(yōu)化

物流節(jié)點(diǎn)布局優(yōu)化問題可描述為：在規(guī)劃目標(biāo)年負(fù)荷分布已知的情況下，以最小的投資和年物流運(yùn)行費(fèi)用為目標(biāo)函數(shù)，確定物流節(jié)點(diǎn)的數(shù)量、位置、容量以及物流節(jié)點(diǎn)的服務(wù)范圍.優(yōu)化流程如下：首先，根據(jù)目標(biāo)年物流總需求、已有物流節(jié)點(diǎn)供給容量以及候選物流節(jié)點(diǎn)規(guī)模與類型確定新建物流節(jié)點(diǎn)的最大個(gè)數(shù)nmax和最小個(gè)數(shù)nmin，利用整數(shù)規(guī)劃技術(shù)得到新建物流節(jié)點(diǎn)的容量組合；在確定了新建節(jié)點(diǎn)的個(gè)數(shù)及容量組合之后，采用最大空心圓策略產(chǎn)生新建節(jié)點(diǎn)初始選址方案，基于加權(quán)Voronoi圖和最大空心圓策略，結(jié)合模擬退火算法實(shí)現(xiàn)新建物流節(jié)點(diǎn)的選址、規(guī)模與布局的方案優(yōu)化［10－12］.

3.1 確定初始方案

基于Voronoi圖最大空心圓定位策略的基礎(chǔ)上，給出根據(jù)已有節(jié)點(diǎn)及負(fù)荷分布情況產(chǎn)生新建物流節(jié)點(diǎn)初始選址的方法，具體步驟如下.

步驟1以已有物流節(jié)點(diǎn)位置為頂點(diǎn)，產(chǎn)生Voronoi圖.

步驟2求出各節(jié)點(diǎn)對(duì)應(yīng)的最大空心圓.

步驟3根據(jù)規(guī)劃目標(biāo)年負(fù)荷分布情況及負(fù)荷密度來確定閾值常數(shù)ε（ε是2個(gè)新建節(jié)點(diǎn)間距離的最小允許值），比較節(jié)點(diǎn)qi與qj（i≠j；j＝1，2，…，r）間的距離dij；若dij≤ε，再比較qi與qj對(duì)應(yīng)的最大空心圓的半徑，將半徑較小的最大空心圓所對(duì)應(yīng)的節(jié)點(diǎn)刪去.

步驟4若新建節(jié)點(diǎn)個(gè)數(shù)為n，取半徑較大的前n個(gè)最大空心圓所對(duì)應(yīng)的節(jié)點(diǎn)作為新建節(jié)點(diǎn)初始選址.

3.2 方案分析及評(píng)價(jià)

評(píng)價(jià)函數(shù)如下

式中：Ccost為年物流成本；Si為第i個(gè)新規(guī)劃物流節(jié)點(diǎn)的規(guī)模；f（Si）為第i個(gè)新規(guī)劃物流節(jié)點(diǎn)的投資；u（Si）為第i個(gè)新規(guī)劃物流節(jié)點(diǎn)的年運(yùn)行費(fèi)用；wij為第i個(gè)物流節(jié)點(diǎn)至第j個(gè)需求點(diǎn)之間的單位運(yùn)輸費(fèi)用；lij為第i個(gè)物流節(jié)點(diǎn)至第j個(gè)需求點(diǎn)之間的運(yùn)輸距離；pij為第i個(gè)物流節(jié)點(diǎn)與第j個(gè)需求點(diǎn)間的需求量；r0為貼現(xiàn)率；α為折算系數(shù).

3.3 方案優(yōu)化步驟

結(jié)合加權(quán)Voronoi圖與進(jìn)化策略算法進(jìn)行多物流節(jié)點(diǎn)選址與規(guī)模優(yōu)化的具體步驟如下.

步驟1以已有節(jié)點(diǎn)選址和新建節(jié)點(diǎn)初始選址為頂點(diǎn)構(gòu)造加權(quán)Voronoi圖，初始權(quán)重取1.

步驟2在新建物流節(jié)點(diǎn)對(duì)應(yīng)的V曲邊形中，基于模擬退火算法以總物流費(fèi)用最小為準(zhǔn)則對(duì)新建節(jié)點(diǎn)選址及其規(guī)模進(jìn)行優(yōu)化.算法步驟如下.

（1）初始化.

（2）生成初始方案S，步驟如下.

①采用Voronoi規(guī)則確定各物流節(jié)點(diǎn)的位置.

②根據(jù)Voronoi規(guī)則劃分的物流節(jié)點(diǎn)服務(wù)范圍需求點(diǎn)的總需求作為節(jié)點(diǎn)的規(guī)模.

③反復(fù)進(jìn)行②直到各物流節(jié)點(diǎn)前后兩次迭代生成的規(guī)模相差不大時(shí)終止，輸出初始方案.

（3）對(duì)k＝1，2，…，L做第（4）至第（7）步.

（4）生成一個(gè)新的解S′，步驟如下.

①任去掉一個(gè)規(guī)劃節(jié)點(diǎn)，對(duì)其位置重新按照Voronoi圖的原則選擇最佳位置采用Voronoi規(guī)則確定物流節(jié)點(diǎn)的位置.

②根據(jù)Voronoi規(guī)則劃分的物流節(jié)點(diǎn)服務(wù)范圍需求點(diǎn)的總需求作為節(jié)點(diǎn)的規(guī)模.

③反復(fù)進(jìn)行②直到各物流節(jié)點(diǎn)前后兩次迭代生成的規(guī)模相差不大時(shí)終止，得到新的解S′.

（5）計(jì)算增量Δt＝C（S′）－C（S）.

（6）若Δt＜0則接受S′作為新的當(dāng)前解，否則以概率exp（－Δt／T）接受S′作為新的當(dāng)前解.

（7）若滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序.終止條件取為連續(xù)若干個(gè)新解都沒有被接受時(shí)或迭代次數(shù)達(dá)到預(yù)計(jì)次數(shù)時(shí)終止算法.

（8）T逐漸減少，且T趨于0，然后轉(zhuǎn)第（2）步.

對(duì)于物流節(jié)點(diǎn)需求超過物流節(jié)點(diǎn)供給能力限制時(shí)采用懲罰函數(shù)法進(jìn)行處理，對(duì)于在可行范圍之外的方案進(jìn)行懲罰.

步驟3再以優(yōu)化得到的新建節(jié)點(diǎn)站址和已有節(jié)點(diǎn)站址構(gòu)造加權(quán)Voronoi圖，并計(jì)算各物流節(jié)點(diǎn)的需求量和負(fù)載強(qiáng)度.

步驟4如果新建節(jié)點(diǎn)選址變動(dòng)距離和小于閾值，則結(jié)束迭代.

步驟5否則，返回步驟2.

4 實(shí)證分析

以區(qū)域物流節(jié)點(diǎn)布局優(yōu)化為例進(jìn)行實(shí)證分析，假設(shè)規(guī)劃區(qū)域?yàn)?40×360的矩形，規(guī)劃區(qū)域內(nèi)的每個(gè)方格作為一個(gè)物流需求點(diǎn)，假設(shè)其物流需求量是均勻分布的，各物流節(jié)點(diǎn)與需求點(diǎn)間的廣義費(fèi)用采用物流節(jié)點(diǎn)與各網(wǎng)格需求點(diǎn)間的歐式距離來表示。設(shè)已有物流節(jié)點(diǎn)為10個(gè)，其位置見表1，各節(jié)點(diǎn)規(guī)模服從［100，200］的均勻分布，由計(jì)算機(jī)隨機(jī)生成，規(guī)劃節(jié)點(diǎn)為40個(gè)。通過在Delphi和SQL Server2000平臺(tái)下編寫了多級(jí)物流節(jié)點(diǎn)布局優(yōu)化系統(tǒng)，在實(shí)驗(yàn)過程中，根據(jù)調(diào)查情況調(diào)整系統(tǒng)參數(shù)。

表1 已有物流節(jié)點(diǎn)地理位置

1）假設(shè)規(guī)劃物流節(jié)點(diǎn)的規(guī)模保持在100，不考慮規(guī)劃節(jié)點(diǎn)規(guī)模優(yōu)化，重力模型參數(shù)θ分別取1和2，現(xiàn)有節(jié)點(diǎn)的服務(wù)區(qū)域劃分結(jié)果如圖1所示，生成如圖2所示的初始方案，其目標(biāo)函數(shù)值為126 4762（θ取1）和179 575.5（θ取2）；優(yōu)化參數(shù)為溫度T＝100；Markov鏈長(zhǎng)度取50，迭代次數(shù)為30次，溫度衰減系數(shù)0.95，優(yōu)化運(yùn)行過程見圖3.當(dāng)20次迭代后趨于最優(yōu)解，其目標(biāo)函數(shù)值為1271 155（θ取1）和179 908.7（θ取2），最終解見圖4.

圖1 已有物流節(jié)點(diǎn)服務(wù)區(qū)域劃分結(jié)果

圖2 初始方案物流節(jié)點(diǎn)服務(wù)區(qū)域劃分結(jié)果

2）考慮規(guī)劃節(jié)點(diǎn)規(guī)模的優(yōu)化，重力模型參數(shù)θ分別取1和2，則生成如圖5所示的初始方案，其目標(biāo)函數(shù)值為224 488.2（θ＝1）和227 459.3（θ＝2）；優(yōu)化參數(shù)為溫度T＝100；Markov鏈長(zhǎng)度取50，迭代次數(shù)為30次，溫度衰減系數(shù)0.95，優(yōu)化運(yùn)行過程見圖6.當(dāng)θ＝1時(shí)，4次迭代后趨于最優(yōu)解，其目標(biāo)函數(shù)值為266 022.3；當(dāng)θ＝2時(shí)，12次迭代后趨于最優(yōu)解，其目標(biāo)函數(shù)值為261 239.7.

圖3 規(guī)模保持不變情況下的優(yōu)化過程圖

圖4 規(guī)模保持不變情況下迭代20次以后的優(yōu)化方案

圖5 加入規(guī)模優(yōu)化后的初始方案物流節(jié)點(diǎn)服務(wù)區(qū)域劃分結(jié)果

圖6 加入規(guī)模優(yōu)化后的優(yōu)化過程圖

通過上述優(yōu)化實(shí)例可以看出：

1）與已有的定量劃分方法相比，將GIS技術(shù)中的加權(quán)Voronoi圖和引力模型相結(jié)合，可以實(shí)現(xiàn)由多個(gè)物流節(jié)點(diǎn)構(gòu)成的區(qū)域物流系統(tǒng)動(dòng)態(tài)服務(wù)范圍的精確劃分，可以通過多層區(qū)域物流體系反映不同等級(jí)物流節(jié)點(diǎn)服務(wù)范圍的層次關(guān)系，對(duì)于區(qū)域物流系統(tǒng)空間服務(wù)范圍的劃分，可以基于不同物流節(jié)點(diǎn)的功能或者貨種的競(jìng)爭(zhēng)力、廣義費(fèi)用等因子，對(duì)其進(jìn)行動(dòng)態(tài)劃分，此方法可用于任意復(fù)雜區(qū)域物流系統(tǒng)的動(dòng)態(tài)服務(wù)范圍劃分，具有較強(qiáng)的實(shí)際價(jià)值.

2）當(dāng)不考慮規(guī)模優(yōu)化時(shí)，物流節(jié)點(diǎn)布局方案中節(jié)點(diǎn)布局較為均勻，層次性不明顯；當(dāng)考慮規(guī)模因素時(shí)，物流節(jié)點(diǎn)布局優(yōu)化方案中的物流節(jié)點(diǎn)呈不均勻布置，物流節(jié)點(diǎn)的層次性較為明顯.通過重力模型參數(shù)θ的取值不同，可以看出當(dāng)θ取［1，2］時(shí)，θ的值越大，表明物流節(jié)點(diǎn)規(guī)模對(duì)其服務(wù)范圍和布局優(yōu)化的影響越大.通過不同參數(shù)條件下SA優(yōu)化過程對(duì)比表明，Markov鏈越長(zhǎng)，解質(zhì)越好但計(jì)算時(shí)間越長(zhǎng)；較小的溫度衰減系數(shù)r可以明顯加速算法的進(jìn)程，但增加了算法陷入局部最優(yōu)解的可能性.

3）在區(qū)域物流節(jié)點(diǎn)布局規(guī)劃中，考慮到物流需求不是均勻分布的，可以對(duì)需求點(diǎn)對(duì)應(yīng)的方格定義一個(gè)需求屬性值來表達(dá)對(duì)應(yīng)需求點(diǎn)的物流需求量，同時(shí)，考慮到物流節(jié)點(diǎn)的輻射范圍受到節(jié)點(diǎn)到需求點(diǎn)廣義費(fèi)用的影響，在實(shí)際應(yīng)用中可以在GIS系統(tǒng)中表達(dá)區(qū)域物流網(wǎng)絡(luò)，分析各需求點(diǎn)到物流節(jié)點(diǎn)的實(shí)際運(yùn)輸距離、運(yùn)輸時(shí)間以及物流費(fèi)用來綜合表達(dá)各物流節(jié)點(diǎn)的引力模型，將更具有實(shí)際意義和應(yīng)用價(jià)值.

5 結(jié)束語

對(duì)物流節(jié)點(diǎn)空間服務(wù)進(jìn)行合理劃分能促進(jìn)物流節(jié)點(diǎn)及其服務(wù)范圍內(nèi)相關(guān)產(chǎn)業(yè)的和諧發(fā)展并帶動(dòng)區(qū)域經(jīng)濟(jì)的發(fā)展.基于GIS技術(shù)中的加權(quán)Voronoi圖實(shí)現(xiàn)物流節(jié)點(diǎn)動(dòng)態(tài)服務(wù)范圍的劃分，將加權(quán)Voronoi圖與引力模型相結(jié)合，充分地考慮了影響物流節(jié)點(diǎn)服務(wù)范圍的眾多因素，實(shí)現(xiàn)了物流節(jié)點(diǎn)服務(wù)范圍的精確劃分；在此基礎(chǔ)上，構(gòu)建連續(xù)型物流節(jié)點(diǎn)協(xié)調(diào)布局優(yōu)化模型，結(jié)合最大空心圓定位策略和模擬退火算法提出模型的高效求解算法，對(duì)解決連續(xù)型物流節(jié)點(diǎn)資源優(yōu)化配置是一種嘗試.從算例可以看出，本方法效率高，結(jié)果合理，特別是對(duì)于區(qū)域物流系統(tǒng)，該方法具有其特殊的優(yōu)勢(shì).

［1］湯宇卿.城市流通空間研究［M］.北京：高等教育出版社，2002.

［2］邱慧芳，郝生躍.基于引力模型的配送中心服務(wù)范圍研究［J］.物流技術(shù)，2010（2）：82－84.

［3］任冠星，王 轉(zhuǎn).需求勢(shì)能理論在多級(jí)物流網(wǎng)絡(luò)預(yù)選點(diǎn)中的應(yīng)用［J］.物流技術(shù)，2005（12）：34－36.

［4］張得志，謝如鶴，李雙艷.物流園區(qū)布局優(yōu)化模型及其求解算法研究［J］.武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2008，（6）：1 048－1 051.

［5］楊 勇.國(guó)內(nèi)物流中心選址研究方法綜述［J］.物流技術(shù)，2008（1）：34－36，43.

［6］黎青松，袁慶達(dá)，杜 文.一個(gè)結(jié)合庫(kù)存策略的物流選址模型［J］.西南交通大學(xué)學(xué)報(bào)，2000，35（3）：315－318.

［7］梁 婷.區(qū)域物流中心分工布局規(guī)劃［D］.長(zhǎng)沙：中南大學(xué)交通運(yùn)輸工程學(xué)院，2007.

［8］秦 進(jìn)，史 峰，繆立新，等.考慮隨機(jī)需求和庫(kù)存決策的多商品物流網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化模型與算法［J］.系統(tǒng)工程理論與實(shí)踐，2009，29（4）：176－183.

［9］Kobayashi K，Sugihara K.Crystal voronoi diagram and its applications［J］.Future Generation Computer Systems，2002，18（5）：681－692.

［10］趙志輝，李 平，黃曉芹.加權(quán)Voronoi圖的離散生成［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24（1）：12－16.

［11］丁鵬飛，王遠(yuǎn)飛.基于Relly法則與加權(quán)Voronoi圖的連鎖超市商圈分析［J］.上海商學(xué)院學(xué)報(bào)，2005，6（4）：135－139.

［12］葛少云，李 慧，劉 洪.基于加權(quán)Voronoi圖的變電站優(yōu)化規(guī)劃［J］.電力系統(tǒng)自動(dòng)化，2007，31（3）：29－34.