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

黃玉文

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

0 引言

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

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

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

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

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

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

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

2.2 交叉和變異的自適應性

1）交叉操作

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

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

2）變異操作

變異操作采用如下形式：

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

2.3 接受算子的退火處理

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

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

2.4 算法的實現(xiàn)

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

（1）設置初始參數(shù),包括種群規(guī)模M,最大遺傳代數(shù)Tmax,退火初始溫度T0,溫度下降系數(shù)κ,最小新解接受次數(shù)Nmin,最大內循環(huán)次數(shù)Cmax,隨機產生初始種群Gi（1，2，…，n）。設定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ōu)個體。對種群中的每一個染色體Gi（1，2，…，n），求得對應的目標函數(shù)值fi；若染色體對應的是不可行解，則屬于其目標函數(shù)一個很大的整數(shù)。并采用如下方法進行適應度拉伸公式中f′為拉伸后的適應度值。

（3）選擇操作。

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

（4）交叉操作。按照式(2)、式(3)進行自適應交叉操作。

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

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

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

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

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

3 結論

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

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

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

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

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

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