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

黃玉文

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

0 引言

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

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

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

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

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

在遺傳算法運(yùn)算前期，由于染色體的差異較大，輪盤(pán)賭選擇容易使遺傳算法進(jìn)入局部最優(yōu)；進(jìn)化后期，染色體的個(gè)體差異性較小，輪盤(pá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）交叉操作

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

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

2）變異操作

變異操作采用如下形式：

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

2.3 接受算子的退火處理

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

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

2.4 算法的實(shí)現(xiàn)

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

（1）設(shè)置初始參數(shù),包括種群規(guī)模M,最大遺傳代數(shù)Tmax,退火初始溫度T0,溫度下降系數(shù)κ,最小新解接受次數(shù)Nmin,最大內(nèi)循環(huán)次數(shù)Cmax,隨機(jī)產(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í)間懲罰系數(shù)c和d的值。

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

（3）選擇操作。

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

［3］孫國(guó)華.帶時(shí)間窗的開(kāi)放式滿(mǎn)載車(chē)輛路徑問(wèn)題建模及其求解算法[J].系統(tǒng)工程理論與實(shí)踐,2012,8：56-60.

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

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