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

申艷光，張玲玉，劉永紅

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

0 引 言

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

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

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

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

1.1 問題描述

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

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

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

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

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

(3)已知每個客戶配送地址的坐標；

(4)已知每個客戶點的需求量；

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

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

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

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

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

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

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

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

d1o：表示車輛從配送中心到第1個客戶點的距離；

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

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

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

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

Xko：表示k點到原點的距離；

Q：表示每臺車的最大載重量；

qi：表示每個客戶的需求量。

1.3 建立模型

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

目標函數(shù)：

(1)

(2)

(3)

(4)

(5)

(6)

約束條件：

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

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

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

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

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

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

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

2.1 K-means算法

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

(7)

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

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

計算步驟如下：

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

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

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

(8)

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

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

(9)

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

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

2.2 改進遺傳算法

2.2.1 編碼設(shè)計

這里采用序號編碼的方式。假設(shè)隨機產(chǎn)生一個序列(1，2，3，4，7，6，5，9，8)，設(shè)生成的斷點矩陣為(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表示配送中心，序號表示客戶編號，此序列表示配送方案由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)

達車輛路徑問題的解空間[14]。

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

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

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

(10)

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

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

2.2.3 選擇操作

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

2.2.4 交叉操作

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

↓切點1 ↓切點2

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

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

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

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

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

即只交換了兩個切點之間的部分。

2.2.5 變異操作

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

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)來源于《中國所有城市坐標表》，以河北省15個城市坐標作為測試數(shù)據(jù)，為了使描述簡單準確，進行了相應(yīng)的原始數(shù)據(jù)處理，見表1。

表1 各個客戶之間的位置坐標和需求量

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

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

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

3.3 實驗結(jié)果

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

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

圖3 改進遺傳算法配送路徑

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

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

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

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

續(xù)表2

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

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

4 結(jié)束語

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

[1] 吳潔明.物流配送車輛路徑優(yōu)化問題的仿真研究[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].計算機工程與科學(xué),2011,33(5):106-111.

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

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

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

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

[12] 彭其華.一種車輛路徑優(yōu)化調(diào)度算法的研究與仿真[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] 葛顯龍,辜羽潔,譚柏川.基于第三方帶軟時間窗約束的車輛路徑問題研究[J].計算機應(yīng)用研究,2015,32(3):689-693.

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