基于混合遺傳算法的物流路徑優(yōu)化方法研究

申艷光，張玲玉，劉永紅

(1.河北工程大學(xué) 信息與電氣工程學(xué)院，河北 邯鄲 056038；2.中電建建筑集團(tuán)有限公司，北京 100000)

0 引 言

隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流企業(yè)在物流配送中如何合理調(diào)度運(yùn)輸車輛，優(yōu)化運(yùn)輸線路，減少運(yùn)輸距離，已經(jīng)成為物流管理的一個(gè)關(guān)鍵問題，直接影響和決定著物流企業(yè)在社會(huì)中的競(jìng)爭(zhēng)。目前國(guó)內(nèi)各地物流企業(yè)在選擇物流配送路線時(shí)，主要依據(jù)經(jīng)驗(yàn)選擇配送路線，往往達(dá)不到行駛距離最短，調(diào)用車輛次數(shù)最少的效果。因此如何選擇最優(yōu)物流配送車輛路徑，及時(shí)將貨物送到客戶手中，成為物流研究領(lǐng)域中的熱點(diǎn)問題[1]。

通過研究物流配送路徑優(yōu)化問題，發(fā)現(xiàn)車輛路徑問題是一個(gè)NP(non-deterministic polynomial，非確定性多項(xiàng)式)完全問題。在20世紀(jì)60年代初，車輛路徑問題一直是配送和物流領(lǐng)域的一個(gè)重要問題[2]。現(xiàn)在關(guān)于車輛路徑問題的算法有很多種，主要包括人工蜂群算法[3-6]、禁忌搜索法[7]、遺傳算法[8-10]、啟發(fā)式算法、蟻群算法[11]等。其中遺傳算法是求解此類NP完全問題的一種有效的全局搜索算法,但在求解車輛路徑問題時(shí)存在早熟和局部搜索能力不足的問題。因此尋求合理的方法，提高算法的效率，增強(qiáng)算法對(duì)配送車輛調(diào)度的優(yōu)化性能，成為相關(guān)學(xué)者分析的重點(diǎn)[12]。

遺傳算法(genetic algorithm，GA)是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種全局優(yōu)化搜索算法[13]。為了提高遺傳算法的局部搜索能力和早熟現(xiàn)象，以往的算法忽略了在物流配送途中可能存在的一些客觀因素，比如車輛行駛路線、在配送過程中給車輛加油或修車額外行駛距離和使用車輛數(shù)量等。因此，針對(duì)物流配送路徑中存在的問題，文中提出一種結(jié)合K-means算法與改進(jìn)遺傳算法的混合遺傳算法。首先，通過K-means算法對(duì)客戶的位置坐標(biāo)進(jìn)行聚類分析，得到局部配送中心及其配送范圍內(nèi)的客戶點(diǎn)，然后利用改進(jìn)遺傳算法使目標(biāo)函數(shù)最小，優(yōu)化配送路線。

1 物流配送路徑優(yōu)化數(shù)學(xué)模型

1.1 問題描述

物流配送車輛的調(diào)度問題描述如下：已知每個(gè)客戶的位置坐標(biāo)和需求量，車輛的最大行駛距離，在滿足目標(biāo)函數(shù)最小和多個(gè)約束條件的前提下，要求每輛車從配送中心出發(fā)，用k(1≤k≤K，K為最大允許的車輛數(shù))輛車分別走不同的配送路線，把貨物送到客戶指定的送貨地點(diǎn)，使得每個(gè)客戶有且僅有一輛車進(jìn)行一次配送，完成配送任務(wù)后返回配送中心。所以物流配送路徑問題的關(guān)鍵是如何優(yōu)化配送路線和分配車輛的行駛路線，使得總運(yùn)輸距離最短。

1.2 模型假設(shè)和模型符號(hào)

在對(duì)物流配送路徑優(yōu)化問題進(jìn)行建模時(shí)，需要遵循以下假設(shè)條件：

(1)每輛車都要從配送中心出發(fā)進(jìn)行貨物運(yùn)輸，完成任務(wù)后返回配送中心；

(2)每輛車只能分配一條運(yùn)輸路線，而且每個(gè)客戶只能被訪問一次；

(3)已知每個(gè)客戶配送地址的坐標(biāo)；

(4)已知每個(gè)客戶點(diǎn)的需求量；

(5)每輛車的行駛距離不得超過其規(guī)定的最大行駛距離；

(6)必須滿足每個(gè)客戶的配送需求。

基于以上假設(shè)，建立物流配送路徑優(yōu)化模型，與之相關(guān)的數(shù)學(xué)模型符號(hào)的含義如下：

K：表示配送中心的總車輛數(shù)(k=1,2,…,K)；

Pi：表示每個(gè)客戶(k=1,2,…,K)；

N：表示這一區(qū)域內(nèi)需要服務(wù)的客戶數(shù)量；

Xij：表示決策變量，表示從客戶i到客戶j的次數(shù)；

dij：表示客戶i與客戶j之間的距離；

d1o：表示車輛從配送中心到第1個(gè)客戶點(diǎn)的距離；

So：表示車輛在行駛過程中額外行走的路程(例如配送過程中加油、修車行駛路程)；

dno：表示車輛送貨完畢返回配送中心的距離；

Xik：表示車輛從客戶i行駛到客戶k；

L：表示可以行駛的最大距離；

Xko：表示k點(diǎn)到原點(diǎn)的距離；

Q：表示每臺(tái)車的最大載重量；

qi：表示每個(gè)客戶的需求量。

1.3 建立模型

由以上問題描述和假設(shè)條件，建立了物流配送路徑優(yōu)化數(shù)學(xué)模型。模型以最少運(yùn)輸距離為目標(biāo)函數(shù)，確定最優(yōu)的車輛配送路線來求解數(shù)學(xué)模型，其目標(biāo)函數(shù)和約束條件如下所示：

目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

(5)

(6)

約束條件：

目標(biāo)函數(shù)(1)：表示計(jì)算可行駛最短路徑的目標(biāo)函數(shù)；

約束條件(2)：表示計(jì)算預(yù)留車輛數(shù)量；

約束條件(3-4)：表示每個(gè)客戶被訪問有且僅有一次；

約束條件(5)：表示車輛在配送過程中行駛一次的距離不能超過其規(guī)定的行駛距離L；

約束條件(6)：xij是模型的決策變量。

2 優(yōu)化物流配送路徑的混合遺傳算法

由于傳統(tǒng)遺傳算法存在局部搜索能力不足和早熟的缺點(diǎn)，于是首先通過K-means算法對(duì)客戶的位置坐標(biāo)進(jìn)行聚類分析，得到局部配送中心及其配送范圍內(nèi)的客戶點(diǎn)，然后利用改進(jìn)遺傳算法的選擇、交叉、變異操作對(duì)物流路徑進(jìn)行優(yōu)化。

2.1 K-means算法

K-means算法以k為參數(shù)，把n個(gè)對(duì)象分成k個(gè)簇，以使簇內(nèi)具有較高的相似度，而簇間具有較低的相似度，相似度根據(jù)一個(gè)簇中對(duì)象的平均值來計(jì)算。定義準(zhǔn)則如下：

(7)

其中，E為所有對(duì)象的誤差平方和；x為給定的對(duì)象屬于Ci的平均值。

該準(zhǔn)則函數(shù)試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。

計(jì)算步驟如下：

(1)任意選擇k對(duì)象，然后將每個(gè)數(shù)據(jù)對(duì)象作為聚類中心；

(2)將剩下的數(shù)據(jù)對(duì)象劃分到和各個(gè)數(shù)據(jù)對(duì)象本身距離最近的聚類中心，根據(jù)式(8)：

DS(Ca,Cb)=min{d(x,y)|x∈Ca,y∈Cb}

(8)

其中，Ca和Cb是兩個(gè)簇，它們分別包含m和h個(gè)元素。設(shè)元素x∈Ca，y∈Cb，這兩個(gè)元素間的距離用簇間距離表示，記為D(Ca,Cb)。

(3)重新計(jì)算每個(gè)聚類中心中數(shù)據(jù)對(duì)象的均值，得到新的聚類中心，均值計(jì)算公式為：

(9)

其中，Ci為一個(gè)聚類，x為Ci內(nèi)的一個(gè)數(shù)據(jù)對(duì)象，即x∈Ci；nk為第k個(gè)聚類中的數(shù)據(jù)對(duì)象。

(4)重復(fù)步驟(2)到(3)，直到每個(gè)聚類中的數(shù)據(jù)對(duì)象不再發(fā)生變化或者目標(biāo)函數(shù)收斂時(shí)結(jié)束。

2.2 改進(jìn)遺傳算法

2.2.1 編碼設(shè)計(jì)

這里采用序號(hào)編碼的方式。假設(shè)隨機(jī)產(chǎn)生一個(gè)序列(1，2，3，4，7，6，5，9，8)，設(shè)生成的斷點(diǎn)矩陣為(2，5，7)，則首先在序列的第2、第5及第7位加“0”，序列變?yōu)?1，2，0，3，4，7，0，6，5，0，9，8)，再在新序列的首末位加“0”，則染色體為(0，1，2，0，3，4，7，0，6，5，0，9，8，0)。其中，0表示配送中心，序號(hào)表示客戶編號(hào)，此序列表示配送方案由4條路線組成。車輛1的路線為(0，1，2，0)，經(jīng)過客戶后回到配送中心，為子路徑1；同理，車輛2的路線為(0，3，4，7，0)，為子路徑2；車輛3的路線為(0，6，5，0)，為子路徑3；車輛4的路線為(0，9，8，0)，為子路徑4，如圖1所示。圖1很直觀地給出了子路徑及客戶順序。此染色體結(jié)構(gòu)能夠很清晰地表

圖1 染色體結(jié)構(gòu)

達(dá)車輛路徑問題的解空間[14]。

通過編碼重復(fù)染色體生成的過程，一直達(dá)到種群規(guī)模M，即初始種群。

2.2.2 適應(yīng)度函數(shù)設(shè)計(jì)

通過適應(yīng)度函數(shù)選擇優(yōu)秀的染色體，因此設(shè)計(jì)的適應(yīng)度函數(shù)為：

(10)

其中，fitness(xi)為第i個(gè)個(gè)體的適應(yīng)度；x0為初始種群中最優(yōu)染色體的運(yùn)輸距離；xi為當(dāng)前染色體所對(duì)應(yīng)的運(yùn)輸距離。

然后利用適應(yīng)度函數(shù)計(jì)算適應(yīng)度值，按從小到大進(jìn)行排序，最后進(jìn)入選擇操作。

2.2.3 選擇操作

采用精英保留模型的錦標(biāo)賽選擇策略，產(chǎn)生一個(gè)新的染色體。錦標(biāo)賽選擇策略是一種基于適應(yīng)度的選擇方法，隨機(jī)從染色體中選擇一組個(gè)體(n個(gè))稱為比賽集。這里設(shè)置的大小為4，選擇一個(gè)隨機(jī)數(shù)r(介于0和1之間)。當(dāng)r小于0.8時(shí)，在比賽集中設(shè)置個(gè)體的優(yōu)勝劣汰，然后選擇一個(gè)用于復(fù)制。否則，任何染色體選擇從比賽集復(fù)制，被精英保留模型選中，以確保最好的個(gè)體進(jìn)入下一代。

2.2.4 交叉操作

選擇操作產(chǎn)生的新種群，除第一條染色體外，另外N-1條染色體要根據(jù)交叉概率pc(pc取值在0～1之間)進(jìn)行交叉配對(duì)[15]。這里采用雙切點(diǎn)交叉遺傳，在傳統(tǒng)遺傳算法中多采用單點(diǎn)交叉遺傳，單點(diǎn)交叉遺傳使得父代雙方很多染色體發(fā)生交換，在交換過程中有時(shí)會(huì)破壞種群中優(yōu)秀的染色體；而雙切點(diǎn)交叉遺傳與單點(diǎn)交叉遺傳相比，父代雙方很少有染色體發(fā)生交換，有利于保留優(yōu)秀的染色體。例如對(duì)下面兩個(gè)個(gè)體使用雙切點(diǎn)交叉的方法，切點(diǎn)分別在第2個(gè)位置和第5個(gè)位置：

↓切點(diǎn)1 ↓切點(diǎn)2

染色體1：1 0 7 6 9 8 3 2

染色體2：0 1 9 8 7 4 2 3

則通過多點(diǎn)交叉之后，兩個(gè)染色體個(gè)體分別變?yōu)椋?/p>

染色體1：1 0 9 6 7 8 3 2

染色體2：0 1 7 8 9 4 2 3

即只交換了兩個(gè)切點(diǎn)之間的部分。

2.2.5 變異操作

采用k-交換變異操作，通過對(duì)初始可行路線交換k條邊/弧，對(duì)初始可行解進(jìn)行逐步改進(jìn)，直到不能改進(jìn)為止。一般2-交換和3-交換技術(shù)運(yùn)用較多，即在每代種群中隨機(jī)地以變異概率pm選擇染色體上的兩個(gè)點(diǎn)或三個(gè)點(diǎn)，并執(zhí)行2-交換和3-交換變異操作。

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)數(shù)據(jù)來源于《中國(guó)所有城市坐標(biāo)表》，以河北省15個(gè)城市坐標(biāo)作為測(cè)試數(shù)據(jù)，為了使描述簡(jiǎn)單準(zhǔn)確，進(jìn)行了相應(yīng)的原始數(shù)據(jù)處理，見表1。

表1 各個(gè)客戶之間的位置坐標(biāo)和需求量

3.2 參數(shù)設(shè)定

根據(jù)K-means算法與改進(jìn)遺傳算法二者結(jié)合的混合遺傳算法、改進(jìn)遺傳算法和傳統(tǒng)遺傳算法利用Matlab對(duì)表1的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行編程得出實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)中算法的初始參數(shù)設(shè)置為：初始配送中心編號(hào)為0，首先根據(jù)K-means算法，設(shè)k=3計(jì)算出聚類中心點(diǎn)，即局部配送中心以及客戶的分配范圍，然后利用改進(jìn)遺傳算法優(yōu)化配送路線；設(shè)車輛的數(shù)量由式(2)計(jì)算，得出K=4，車輛的載量Q=20 m3，每次配送車輛最大行駛距離L=100 km,額外行駛路程So=80 km，種群大小M=100,交叉概率pc=0.7，變異概率pm=0.05。

3.3 實(shí)驗(yàn)結(jié)果

圖2和圖3為傳統(tǒng)遺傳算法和改進(jìn)遺傳算法的配送路徑。

圖2 傳統(tǒng)遺傳算法配送路徑

圖3 改進(jìn)遺傳算法配送路徑

從圖2可以看出，傳統(tǒng)遺傳算法在物流配送路徑中配送路線有若干條交叉線，可以判斷這不是一個(gè)最優(yōu)解。圖3中改進(jìn)的遺傳算法在物流配送路徑中配送路線相比圖2交叉線明顯減少。而圖4比圖2、圖3更能達(dá)到目標(biāo)函數(shù)的最少運(yùn)輸距離。

圖4 混合遺傳算法配送路徑

從表2可以看出每臺(tái)車輛分別在傳統(tǒng)遺傳算法和改進(jìn)遺傳算法、K-means算法與改進(jìn)遺傳算法相結(jié)合的混合遺傳算法下物流配送路徑的路線及運(yùn)輸距離，說明混合遺傳算法所求得的最優(yōu)配送路線使目標(biāo)函數(shù)值達(dá)到最小并解決了早熟現(xiàn)象。基于表2中的最優(yōu)配送路線，相對(duì)應(yīng)的貨物配送量見表3。

表2 傳統(tǒng)遺傳算法、改進(jìn)遺傳算法和混合遺傳算法配送路線比較

續(xù)表2

表3 最優(yōu)車輛調(diào)度狀態(tài)下的需求分配

注：q表示對(duì)對(duì)應(yīng)節(jié)點(diǎn)客戶的需求進(jìn)行配送，后面的數(shù)字均表示相應(yīng)的配送量。

4 結(jié)束語

考慮到實(shí)際車輛在配送過程中的應(yīng)用，文中建立了減少運(yùn)輸距離的物流配送路徑最優(yōu)化的數(shù)學(xué)模型，提出了一種K-means算法與改進(jìn)遺傳算法相結(jié)合的混合遺傳算法，并通過仿真實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)遺傳算法和改進(jìn)遺傳算法相比，該算法解決了早熟現(xiàn)象，優(yōu)化了物流配送路徑，從而加快了配送速度，提高了服務(wù)質(zhì)量，縮短了配送距離。在未來的工作中，力圖將該算法推廣到更復(fù)雜的物流配送當(dāng)中，通過仿真實(shí)驗(yàn)進(jìn)一步優(yōu)化該算法的性能。

[1] 吳潔明.物流配送車輛路徑優(yōu)化問題的仿真研究[J].計(jì)算機(jī)仿真,2011,28(7):357-360.

[2] BELL J E,MCMULLEN P R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engineering Informatics,2004,18(1):41-48.

[3] AKAY B,KARABOGA D.A modified artificial bee colony algorithm imization[J].Information Sciences,2012,192(1):120-142.

[4] IRANI R,NASIMI R.Application of artificial bee colony-based neural network int bottom hole pressure prediction in underbalanced drilling[J].Journal of Petroleum Science and Engineering,2011,78(1):6-12.

[5] KARABOGA D,QZTRUK C.A novel clusteringapproach:artificial bee colony (ABC) algorithm[J].Applied Soft Computing,2011,11(1):652-657.

[6] MANDAL S K,CHAN F T,TIWARL M.Leak detection of pipeline:an integrated approach of rough set theory and artificial bee colony trained SVM[J].Expert Systems with Applications,2012,39(3):3071-3080.

[7] 鞏 固,胡曉婷,衛(wèi)開夏,等.物流配送車輛路徑問題的優(yōu)化研究[J].計(jì)算機(jī)工程與科學(xué),2011,33(5):106-111.

[8] 雷建平,沈成武,聞驥駿.貨郎擔(dān)問題與單親遺傳算法[J].武漢理工大學(xué)學(xué)報(bào),2003,25(6):80-83.

[9] 周春光,周國(guó)芹,程彥峰,等.一種克服遺傳算法收斂于局部極小的方法[J].小型微型計(jì)算機(jī)系統(tǒng),1997,18(3):46-49.

[10] 李向陽.遺傳算法求解VRP問題[J].計(jì)算機(jī)工程與設(shè)計(jì),2004,25(2):271-273.

[11] 陳衛(wèi)東,王 佳.基于混合蟻群算法的物流配送路徑優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(14):3383-3385.

[12] 彭其華.一種車輛路徑優(yōu)化調(diào)度算法的研究與仿真[J].計(jì)算機(jī)仿真,2014,31(5):143-146.

[13] HOLLAND J H.Adaptation in natural and artificial systems[M]//Adaptation in natural and artificial systems.Cambridge,MA,USA:MIT Press,1975.

[14] 葛顯龍,辜羽潔,譚柏川.基于第三方帶軟時(shí)間窗約束的車輛路徑問題研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32(3):689-693.

[15] 易榮貴,羅大庸.基于遺傳算法的物流配送路徑優(yōu)化問題研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(6):13-15.