基于聚類分析和種子進(jìn)化算法的車輛路徑優(yōu)化算法

冀德剛，魏俊萍，賈 鸝

（1.河北農(nóng)業(yè)大學(xué) 理學(xué)院，河北 保定 071001；2.保定市科學(xué)技術(shù)信息研究所，河北 保定 071000）

1 引言

物流優(yōu)化方案[1-6]是一個(gè)涉及多方面、多系統(tǒng)的組合優(yōu)化方案，包含客戶系統(tǒng)、倉儲(chǔ)系統(tǒng)、運(yùn)輸系統(tǒng)等諸多方面的優(yōu)化。而運(yùn)輸系統(tǒng)優(yōu)化是物流運(yùn)輸配送過程中的重要環(huán)節(jié)，也是控制物流營運(yùn)成本的核心內(nèi)容[7-12]。如果配送車輛路徑合理，不但能夠減少送貨時(shí)間，降低物流成本，同時(shí)還能夠使客戶達(dá)到較高的滿意度，實(shí)現(xiàn)物流管理科學(xué)化的目標(biāo)，因此本文只討論車輛路徑優(yōu)化問題。

2 VRP模型

為了描述問題方便，定義如下變量：M代表車輛總數(shù)，N代表客戶數(shù)量；Burk代表配送車輛k的最大限載量；Vonk代表配送車輛k的最大裝載容積；Carijk代表車輛k從i客戶到j(luò)客戶的配送基礎(chǔ)費(fèi)用（i=1,2,...,N；j=1,2,...,N；k=1,2,...,M）；λTL代表運(yùn)輸延時(shí)調(diào)整系數(shù)（λTL∈[1,+∞]）；CuWi代表客戶i的貨重；CuVi代表客戶i的貨物體積。

目標(biāo)函數(shù)表示車輛的總費(fèi)用等于每輛配送車的總費(fèi)用乘以懲罰因子，懲罰因子隨著運(yùn)輸時(shí)間的增長而不斷增大，具體大小需要預(yù)先設(shè)定。懲罰因子較大時(shí)，該目標(biāo)函數(shù)轉(zhuǎn)化為帶時(shí)間窗路徑優(yōu)化函數(shù)（本文沒有考慮帶時(shí)間窗路徑優(yōu)化的問題，故在數(shù)值計(jì)算時(shí)λTL=1）。

約束條件：

其中式（4）、（5）保證每個(gè)客戶的貨物都得到配送；式（6）保證每個(gè)客戶只由一輛車送達(dá)貨物；式（7）保證一條線路上的所有客戶貨物總重不超過配送車輛最大載重量；式（8）保證一條線路上的所有客戶貨物總體積不超過配送車輛最大載容量；式（9）、（10）為約束條件。

3 車輛路徑優(yōu)化算法設(shè)計(jì)思路

基于物流運(yùn)輸?shù)膶?shí)際情況，考慮到物流系統(tǒng)優(yōu)化的諸多要求，把整個(gè)優(yōu)化過程分成兩個(gè)階段：

（1）分割區(qū)域：考慮到在物流配送中一個(gè)特定區(qū)域只能由一臺(tái)車來完成，因此對(duì)于一個(gè)具體的城市，有必要對(duì)整個(gè)區(qū)域進(jìn)行劃分。首先把每一個(gè)指定的客戶看成一個(gè)二維的點(diǎn)，把區(qū)域內(nèi)的公路看成線，這樣通過點(diǎn)與線就可以把整個(gè)區(qū)域組成一個(gè)連通網(wǎng)，把每兩點(diǎn)間公路距離定義為兩點(diǎn)間距離。其次通過k-means聚類，把近距點(diǎn)劃為同一區(qū)域，這樣就完成了整個(gè)區(qū)域的劃分。

（2）優(yōu)化方法：使用智能算法對(duì)每個(gè)區(qū)域中的配貨路線進(jìn)行優(yōu)化，最終形成最優(yōu)配送方案。具體優(yōu)化時(shí)，先讓優(yōu)化個(gè)體在局部區(qū)域深度搜索后，再進(jìn)行聚類分組之間的二次優(yōu)化，搜尋全局最優(yōu)值。

兩階段法的設(shè)計(jì)從實(shí)際的物流配送出發(fā)，同時(shí)在不同區(qū)域分別確定局部最優(yōu)解，然后不同區(qū)域間再次優(yōu)化，很大程度上降低了算法的輸入量，使算法的求解速度有效提高。

4 基于聚類和種子進(jìn)化算法的復(fù)合算法

4.1 K-means聚類

K-means算法原理：首先從樣本數(shù)據(jù)中隨機(jī)選取K個(gè)點(diǎn)作為初始聚類中心；其次計(jì)算每一個(gè)樣本到聚類中心的距離（本文使用歐氏距離），把距離每個(gè)中心最近的樣本點(diǎn)歸為該中心所在的類。接下來計(jì)算新形成的每一個(gè)類中所有樣本數(shù)據(jù)的平均值作為新的聚類中心，直到相鄰兩次的聚類中心不再發(fā)生變化，此時(shí)K-means聚類結(jié)束[13]。

4.2 種子進(jìn)化算法(SOA：Seed Optim ization Algorithm)

種子進(jìn)化算法思想源于豆科植物種子的傳播規(guī)律。它的整體思路如下：首先把待優(yōu)化的車輛運(yùn)輸區(qū)域看成土地，那么最優(yōu)值就應(yīng)該在土地最肥沃的區(qū)域取得。在這種思想下，可以用目標(biāo)函數(shù)值來確定每個(gè)區(qū)域土地的肥沃程度。土地貧瘠，則目標(biāo)函數(shù)值低，土地肥沃，則目標(biāo)函數(shù)值高。顯然如果經(jīng)過傳播后的種子所落區(qū)域是肥沃土地，那么它生長和傳播的機(jī)會(huì)就會(huì)很大；否則，傳播的可能性就很小。經(jīng)過反復(fù)搜索，植株會(huì)在最肥沃的土地上被找到，此時(shí)優(yōu)化問題的目標(biāo)函數(shù)就取得最優(yōu)值。這樣反復(fù)執(zhí)行的過程經(jīng)過抽象最終形成一種進(jìn)化算法-種子進(jìn)化算法。種子進(jìn)化算法中散射現(xiàn)象是最核心的部分，整個(gè)算法中的搜索機(jī)制由散射來完成[14]。

4.3 車輛路徑選擇的復(fù)合優(yōu)化算法

基于聚類和種子進(jìn)化的車輛路徑選擇的復(fù)合優(yōu)化算法（KMSOA:K-Means Seed Optimization Algorithm）設(shè)計(jì)分為兩個(gè)階段：（1）聚類；（2）優(yōu)化算法求解。其流程圖如圖1、2所示。

圖1 種子進(jìn)化算法流程圖

圖2 父種選擇流程

KMSOA算法首先把物流運(yùn)輸?shù)膮^(qū)域利用K-means算法進(jìn)行區(qū)域劃分，然后計(jì)算每個(gè)父種對(duì)應(yīng)的適應(yīng)度函數(shù)值，依賴父種的適應(yīng)度函數(shù)值來完成父種的選擇和傳播，如果滿足終止條件則結(jié)束，否則生成下一代新的父種，然后再次進(jìn)行區(qū)域劃分，反復(fù)迭代執(zhí)行。

5 數(shù)值實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文算法的可行性及有效性，實(shí)驗(yàn)中采用與文獻(xiàn)[15]相同的數(shù)據(jù)(見表1)，以便進(jìn)行比較。

表1 實(shí)驗(yàn)數(shù)據(jù)

5.2 實(shí)驗(yàn)說明

距離：所有點(diǎn)之間只考慮直線距離，其他情況不予考慮，距離函數(shù)采用歐式距離：

KMSOA算法說明：

（1）聚類中K的取值：2到可調(diào)度的最多可用車量數(shù)。

（2）把優(yōu)化目標(biāo)函數(shù)定義為適應(yīng)度函數(shù)，即式（3），懲罰因子λTL=1，不考慮時(shí)間窗，其中任意兩點(diǎn)間的車輛配送費(fèi)用即為兩點(diǎn)間的歐氏距離。

（3）父種類別個(gè)數(shù)取20。

（4）距離限定標(biāo)準(zhǔn)：避免父類選擇為種子的集中分布，距離的限定標(biāo)準(zhǔn)采用每兩個(gè)種子之間距離的30%。

（5）算法執(zhí)行最大次數(shù)取50次。

5.3 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證文中給定復(fù)合算法的有效性，把文中結(jié)果和文獻(xiàn)[15]提出的混合遺傳算法做比較，獨(dú)立運(yùn)行9次，結(jié)果見表2與表3。

表2 混合遺傳算法求解結(jié)果

表3 KMSOA求解結(jié)果

表2、表3展示了在相同條件下混合遺傳算法與本算法的對(duì)比，本文提出的KMSOA算法無論從平均值還是迭代次數(shù)來看，均優(yōu)于混合遺傳算法。實(shí)驗(yàn)數(shù)據(jù)再次說明文中給出算法能夠降低算法的輸入量，提高收斂速度，對(duì)物流運(yùn)輸中運(yùn)輸路徑優(yōu)化問題具有一定的可行性和有效性。

[1]F Alffedo,T Montan,R Galv.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33:595-619.

[2]朱志勇,刁洪祥.基于改進(jìn)遺傳算法的車輛路徑問題研究[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2011,33(3):115-118.

[3]何未雨.物流配送最佳路徑的最差-最優(yōu)蟻群算法實(shí)現(xiàn)[J]甘肅科技縱橫,2011,40(5):104-106.

[4]BOmbuki,B JRoss,E Hanshar.Multi-Objective Genetic Algorithms for Vehicle Routing Problem with TimeWindows[J].Applied Intelligence,2006,(24):17-30.

[5]姜貴山,姬長虹.周期性車輛路徑問題在物流中的應(yīng)用：案例研究[J].科學(xué)技術(shù)與工程,2010,10(11):2 694-2 697.

[6]E Taniguchi,N Ando.An Experimental Analysis on Probabilistic Vehicle Routing and Scheduling with ITS[J].Journal of the Eastern Asia Society for Transportation Studies,2005,(6):3 052-3 06l.

[7]G Alvarenga.A Hybrid Approach for the Dynamic Vehicle Routing Problem with Time Windows[A].Proceedings ofthe Fifth International Conference on Hybrid Intelligent Systems[C].2005.

[8]J Y Potvin,Y Xu,I Benyahia.Vehicle routing and scheduling with dynamic travel times[J].Computers&Operations Research,2006,33:1 129-1 137.

[9]宋遠(yuǎn)卓.物流配送中心搬運(yùn)設(shè)備配置研究[D].成都:西南交通大學(xué),2008.

[10]呂勇.蟻群優(yōu)化算法及在網(wǎng)絡(luò)路由中的應(yīng)用研究[D].杭州:浙江大學(xué),2006.

[11]李晨.基于免疫遺傳算法的物流配送VRP問題研究[D].天津:天津理工大學(xué),2009.

[12]胡田田.車輛路徑問題的知識(shí)表示支持系統(tǒng)研究[D].大連:大連理工大學(xué),2006.

[13]張建輝.K-means聚類算法研究及應(yīng)用[D].武漢:武漢理工大學(xué),2007.

[14]張曉明,王儒敬,宋良圖.一種新的進(jìn)化算法—種子優(yōu)化算法[J].模式識(shí)別與人工智能,2008,21(5):677-681.

[15]郎茂祥,胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué),2002,10(5):51-56.