遺傳算法的改進(jìn)算法在物流配送當(dāng)中的應(yīng)用

富文軍，王文發(fā)，王詩瑤，李曉英

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

隨著社會(huì)的進(jìn)步，運(yùn)輸行業(yè)的發(fā)展，城市物流這種活動(dòng)頻繁、運(yùn)輸節(jié)點(diǎn)多、運(yùn)輸批量小、頻率高的配送方式應(yīng)運(yùn)而生。在物流配送過程中，存在很多優(yōu)化策略問題，本文討論的物流配送過程中的路徑優(yōu)化問題就是其中之一。目前對(duì)這類的解決方法主要有:Floyd算法、模擬退火算法、節(jié)約法、蟻群算法、禁忌搜索算法等。其中，廉晚祥、徐國(guó)平、柳林、蔡良偉、郎茂祥、劉敏等人就曾利用遺傳算法的相關(guān)思想解決過路徑優(yōu)化類的問題［1－7］。但由于該方法計(jì)算量大、效率低，在實(shí)際中難于維護(hù)，特別是對(duì)一些規(guī)模較大的物流配送更是如此。作者嘗試將遺傳算法進(jìn)行改進(jìn)，把模擬退火的思想融入到遺傳算法當(dāng)中，以求達(dá)到更好的效果。經(jīng)過反復(fù)測(cè)試，該方法比單純使用遺傳算法有較大的改進(jìn)。

1 數(shù)學(xué)模型

物流配送的路徑優(yōu)化問題可以描述為:從配送中心用多輛車向各客戶所在的物流點(diǎn)進(jìn)行配貨，各個(gè)物流點(diǎn)和貨物的需求量是固定的，每輛汽車的載重量一定，要求合理安排汽車行駛路線，使得總運(yùn)距最小。

基于上述要求，作如下的約定:

該城市一共有L個(gè)配送點(diǎn)，需要通過k輛汽車來進(jìn)行配送，每輛車載重限制為b，每個(gè)配送點(diǎn)的需求量為gi，任意兩個(gè)配送點(diǎn)i到j(luò)的距離為dij，nk為車輛k所滿足的配送點(diǎn)數(shù)目，rki表示在車輛k所行駛的路徑中配送點(diǎn)的順序i，rk0=0表示物流中心，用集合Rk表示第k輛車所行駛的路徑。

車輛路徑問題的數(shù)學(xué)模型為:配送中所需車輛數(shù)進(jìn)行確定

上述模型中，式(1)為目標(biāo)函數(shù);式(2)到式(7)為約束條件，其中式(2)為每輛汽車所行駛路線上所有客戶的載重量之和不超過汽車本身的載重量;式(3)為每條路徑配送點(diǎn)的組成;式(4)為每個(gè)配送點(diǎn)只能由一輛汽車進(jìn)行配送;式(5)表示一輛車的配送點(diǎn)數(shù)目不超過總配送點(diǎn)數(shù);式(6)表示所有車輛所行駛配送點(diǎn)數(shù)目總和即為總配送點(diǎn)數(shù);式(7)為標(biāo)志變量，用來查看當(dāng)前所選車輛是否用于配送。

2 遺傳算法的改進(jìn)算法

針對(duì)一般遺傳算法收斂速度方面的不足，作者在變異過程中將模擬退火算法與之結(jié)合，從而構(gòu)造出如下的路徑優(yōu)化問題中遺傳算法的改進(jìn)算法:

1)構(gòu)造染色體，產(chǎn)生初始種群

首先確定染色體的編碼方式，由于遺傳算法不能直接處理解空間的數(shù)據(jù)，所以必須通過編碼使他們形成基因數(shù)串的結(jié)構(gòu)。此問題中我們采用的是自然數(shù)編碼。隨機(jī)產(chǎn)生一組種群大小為N，染色體中基因個(gè)數(shù)為L(zhǎng)(L為互不重復(fù)的自然數(shù))的初始群體。

2)適應(yīng)度計(jì)算

3)選擇操作

本文采用如下最佳個(gè)體保留與賭輪選擇相結(jié)合的選擇策略［7］:將每代群體中的N個(gè)個(gè)體按適應(yīng)度由大到小排列，排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下一代，并排在第一位;下一代群體的另N－1個(gè)個(gè)體需要根據(jù)前代群體的N個(gè)個(gè)體的適應(yīng)度，采用賭輪選擇法產(chǎn)生，具體地說，就是首先計(jì)算上代群體中所有個(gè)體適應(yīng)度的總和∑fj，再計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例fi/∑fi(j=1，2，…，N)，以此作為其被選擇的概率。上述選擇方法既可保證最優(yōu)個(gè)體生存至下一代，又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代。

4)交叉操作

交叉規(guī)則采用部分匹配交叉。選擇操作產(chǎn)生的新種群，除第一條染色體外，另N－1條染色體要根據(jù)交叉概率Pc進(jìn)行交叉配對(duì)。本文采用了一種改進(jìn)的兩點(diǎn)交叉法，例如:隨機(jī)在染色體G1、G2中選擇一個(gè)交配區(qū)域，交換G1、G2的交配區(qū)域，且G1交配區(qū)域前面的數(shù)與G2交配區(qū)域后面的數(shù)交換，G1交配區(qū)域后面的數(shù)與G2交配區(qū)域前面的數(shù)交換。相對(duì)于別的交叉法，這種方法既能產(chǎn)生一定程度的變異效果，又能保持種群內(nèi)個(gè)體的多樣性。

5)變異操作

我們?cè)谌旧w的變異中對(duì)遺傳算法進(jìn)行了改進(jìn)，加入了模擬退火算法的思想。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。染色體上的某一段基因會(huì)以一定的概率來決定是否接受變異。

初始化各變量，Pm為變異概率，T0是退火初始溫度，α是溫度冷卻參數(shù)。

對(duì)于一個(gè)已產(chǎn)生的初始化種群，對(duì)它實(shí)行變異交叉操作，產(chǎn)生新的群體:計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)函數(shù)值fh。隨機(jī)選取兩個(gè)個(gè)體進(jìn)行交叉操作，產(chǎn)生兩個(gè)新個(gè)體，計(jì)算它們的適應(yīng)度函數(shù)值fi，fj，若exp(－|fi－fj|/Tk)＞random(0，1)，則接收新解。通過該方法決定是否接收變異后的解，直到滿足收斂條件則進(jìn)化過程結(jié)束;若不滿足，則Tk+1=α*Tk，對(duì)交叉后的個(gè)體繼續(xù)實(shí)行變異操作。

3 測(cè)試

有八個(gè)配送點(diǎn)和一個(gè)配送中心的配送系統(tǒng)，各配送點(diǎn)對(duì)配送中心的需求為gi(i=1，2，…，8)(單位為t)，每輛車的容量皆為8 t，已知配送中心與各配送點(diǎn)間的距離如表1(其中0為配送中心)，要求合理安排車輛行駛路線，使得總運(yùn)輸路程最小。

表1 配送中心與各配送點(diǎn)的距離

為了評(píng)價(jià)該算法的好壞，我們又對(duì)通常的遺傳算法進(jìn)行了計(jì)算，結(jié)果為71.5。通過與普通的遺傳算法進(jìn)行對(duì)比，可以看到，改進(jìn)遺傳算法的計(jì)算結(jié)果優(yōu)于普通的遺傳算法。

通過對(duì)上述模型的研究以及計(jì)算，結(jié)果表明，將改進(jìn)后的遺傳算法應(yīng)用到城市物流的配送當(dāng)中，得到較好的結(jié)果，證明了改進(jìn)后遺傳算法的可行性和有效性。算法將交叉和變異后的個(gè)體實(shí)施接受策略，不但增強(qiáng)了進(jìn)化算法的全局收斂性，并且加快了算法的收斂速度。

［1］廖潔君，陳燕.城市物流中多目標(biāo)配送模型［J］.大連海事大學(xué)學(xué)報(bào)，2004，30(4):82 －85.

［2］李軍.車輛調(diào)度問題的分派啟發(fā)式算法［J］.系統(tǒng)工程理論與實(shí)踐，1999，(1):27－33.

［3］廉晚祥，朱參世.改進(jìn)遺傳算法在應(yīng)急救援物資運(yùn)輸中的應(yīng)用［J］.中國(guó)安全科學(xué)學(xué)報(bào)，2013，23(5):172－176.

［4］徐國(guó)平，葉效鋒.基于模擬退火遺傳算法的車輛路徑問題研究［J］.工業(yè)控制計(jì)算機(jī)，2004，17(6):49－50.

［5］柳林，朱建榮.基于遺傳算法的物流配送路徑優(yōu)化問題的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2005，(27):227－229.

［6］蔡良偉，李霞.遺傳算法交叉操作的改進(jìn)［J］.系統(tǒng)工程與電子技術(shù)，2006，28(6):925 －928.

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