黃玉文

（菏澤學(xué)院計算機與信息工程系，山東 菏澤274015）

0 引言

當(dāng)前,隨著電子商務(wù)的快速興起，物流業(yè)在市場經(jīng)濟(jì)中占有越來越重要的地位，引起國家的高度重視和越來越多的企業(yè)的關(guān)注。正確和高效的安排多配送中心車輛路徑調(diào)度有利于提高配送速度，有利于企業(yè)節(jié)約成本，提高物流配送企業(yè)的經(jīng)濟(jì)效率和顧客服務(wù)水平。近年來,物流配送在國家的經(jīng)濟(jì)建設(shè)中扮演越來越重要的作用，如何提高物流配送效率和降低物流成本成為一個熱門研究課題[1]。多配送中心配送能夠滿足更廣闊的地理范圍內(nèi)的顧客服務(wù)需求，配送車輛可以從多個配送中心出發(fā)去完成運輸任務(wù),達(dá)到提高車輛利用率、減少總的運輸距離、節(jié)約運輸成本,更快滿足顧客需要的目的。車輛路徑問題（Vehicle Routing Problem）在多配送中心物流調(diào)度中占有一個非常重要的環(huán)節(jié)，這個問題的有效解決，可以提高物流調(diào)度的科學(xué)化水平，降低運輸成本，提高經(jīng)濟(jì)效益[2]。同時物流配送車輛調(diào)度問題作為一個NP難題，隨著客戶數(shù)量的增加，可選的配送路徑方案數(shù)量將以指數(shù)速度急劇增長[3]。因此，用啟發(fā)式算法求解該問題就成為人們研究的一個重要方向，本文提出了一種基于 優(yōu)化遺傳算法的多配送中心車輛路徑方案。

1 優(yōu)化遺傳算法思想

遺傳算法不依賴初始解，可以對問題參數(shù)的編碼組進(jìn)行計算，并且算法具有強大的搜索能力，故很多研究者把遺傳算法應(yīng)用到解決多配送中心的調(diào)度問題中。遺傳算法強調(diào)的是兩代之間的進(jìn)化關(guān)系，其交叉有可能錯過最好解，因而局部搜索能力較弱，所以即使是在最優(yōu)解附近，而要達(dá)到這個最優(yōu)解，卻花費較大的代價。遺傳算法在最優(yōu)路徑搜索過程中容易陷入局部最優(yōu)，搜索效率比較低下，而模擬退火算法容易脫離局部最優(yōu)[4]。因此，考慮將模擬退火算法的思想引入遺傳算法，有效地緩解了遺傳算法的選擇壓力。退火遺傳算法是集合了遺傳算法和模擬退火算法各自的優(yōu)點，具有較好的全局搜索和局部搜索能力，本文把遺傳算法和模擬退火策略相結(jié)合以解決多配送中心車輛調(diào)度問題[5]。

2 基于優(yōu)化遺傳算法的的多配送中心車輛路徑算法

2.1 適應(yīng)函數(shù)的退火拉伸

在遺傳算法運算前期，由于染色體的差異較大，輪盤賭選擇容易使遺傳算法進(jìn)入局部最優(yōu)；進(jìn)化后期，染色體的個體差異性較小，輪盤賭選擇容易使遺傳算法進(jìn)入終止?fàn)顟B(tài)。故變換適應(yīng)度函數(shù)為：

式中：f′（X）為適應(yīng)度函數(shù)變換后的值，fmax（X）適應(yīng)度函數(shù)的最大值，T代表退火溫度，T0代表初始溫度，g代表遺傳代數(shù)，R為略小于1的正數(shù)，本文取0.99。

2.2 交叉和變異的自適應(yīng)性

1）交叉操作

遺傳算法通過交叉操作能夠產(chǎn)生下一代新個體，由于遺傳算法在運算過程中容易陷入局部最優(yōu)，交叉操作通過產(chǎn)生的新個體和上一代個體的差異性較大，使遺傳算法具有較強的全局搜索能力。本文采用如下的交叉操作方式：

在上式中，A′和B′分別為上一代個體A和B產(chǎn)生的新一代個體，α和β分別是[0，r]上的隨機數(shù)，交叉系數(shù)r的取值范圍為[0，1]。L和R代表尋優(yōu)參數(shù)的范圍，如進(jìn)行交叉操作后超過了尋優(yōu)參數(shù)范圍，則重新進(jìn)行交叉操作。

2）變異操作

變異操作采用如下形式：

上式中，C為父個體，C′為變異操作產(chǎn)生的新個體，隨機數(shù)γ的范圍為(0,1)，變異系數(shù)k的取值范圍為(0,1]，隨機函數(shù)U(0,1)的值為0或1。

2.3 接受算子的退火處理

雜交和變異運算后的個體中的最優(yōu)解被保留，這故遺傳算法容易陷入局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。本文提出以Metropolis準(zhǔn)則保留個體，其保留概率為：

式中：fold為雜交(變異)前的父代個體適應(yīng)值，fnew為雜交(變異)后的子代個體適應(yīng)值，T為退火溫度。

2.4 算法的實現(xiàn)

將自適應(yīng)遺傳退火算法應(yīng)用到多配送中心車輛路徑優(yōu)化中，具體的實現(xiàn)步驟如下：

（1）設(shè)置初始參數(shù),包括種群規(guī)模M,最大遺傳代數(shù)Tmax,退火初始溫度T0,溫度下降系數(shù)κ,最小新解接受次數(shù)Nmin,最大內(nèi)循環(huán)次數(shù)Cmax,隨機產(chǎn)生初始種群Gi（1，2，…，n）。設(shè)定H、M、qi（i=1，2，…，M+H）、Qk（k=1，2…，K）、Dk（k=1，2…，K）、dij（i，j=1，2…，M，M+1，M+2，…，M+H）、時間懲罰系數(shù)c和d的值。

（2）計算種群中各個個體的適應(yīng)度值,記錄最優(yōu)個體。對種群中的每一個染色體Gi（1，2，…，n），求得對應(yīng)的目標(biāo)函數(shù)值fi；若染色體對應(yīng)的是不可行解，則屬于其目標(biāo)函數(shù)一個很大的整數(shù)。并采用如下方法進(jìn)行適應(yīng)度拉伸公式中f′為拉伸后的適應(yīng)度值。

（3）選擇操作。

采用輪盤選擇策略進(jìn)行個體選擇,進(jìn)行染色體的復(fù)制，具體過程如下：對各個染色體uk，計算適應(yīng)值fk;計算種群中n個染色體適應(yīng)值的和，對各染色體uk，計算選擇概率對各個染色體uk,計算適應(yīng)值。在區(qū)間[0，1]內(nèi)產(chǎn)生一個隨機數(shù)r，若r≤q1，則選擇第一個染色體r≤u1；否則選擇第k個染色體uk（k=1，2，…，n），使得qk-1≤r≤qk成立。將當(dāng)前群體中適應(yīng)度最高的個體結(jié)構(gòu)完整的復(fù)制到下一代群體中。

（4）交叉操作。按照式(2)、式(3)進(jìn)行自適應(yīng)交叉操作。

（5）執(zhí)行Metropolis準(zhǔn)則,對交叉后的算子進(jìn)行接收退火處理。

（6）變異操作。對個體的每個參數(shù)進(jìn)行自適應(yīng)變異操作。

（7）執(zhí)行Metropolis準(zhǔn)則,對變異后的算子進(jìn)行接收退火處理。

（8）刪除子代種群中的任意一個個體，并替換成步驟(2)記錄的最優(yōu)個體。

（9）如果當(dāng)前遺傳代數(shù)T?Tmax,則按進(jìn)行降溫,T=T+1,并返回步驟(2);否則結(jié)束整個優(yōu)化過程。

3 結(jié)論

本章對雜交率和變異率的個體進(jìn)行自適應(yīng)的接受，有利于提高遺傳算法的收斂性。對適應(yīng)值函數(shù)的退火拉伸，能夠使遺傳算法加快收斂速度，能夠更好的尋找多配送中心車輛路徑。

［1］葛顯龍,王旭,鄧?yán)?基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J].管理工程學(xué)報,2013,3：44-48.

［2］于濱,靳鵬歡,楊忠振.兩階段啟發(fā)式算法求解帶時間窗的多中心車輛路徑問題[J].系統(tǒng)工程理論與實踐,2012,8：32-37.

［3］孫國華.帶時間窗的開放式滿載車輛路徑問題建模及其求解算法[J].系統(tǒng)工程理論與實踐,2012,8：56-60.

［4］王君,李波.帶模糊預(yù)約時間的車輛路徑問題的多目標(biāo)禁忌搜索算法[J].計算機集成制造系統(tǒng),2011,4：41-42.

［5］王征,張俊,王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J].中國管理科學(xué),2011,02：67-71.