傅　勉，王世貴，王丹丹

（1.安徽新華學(xué)院a.商學(xué)院；b.大學(xué)生素質(zhì)教育研究中心，合肥 230088；2.陸軍炮兵防空兵學(xué)院，合肥 230031）

0　引言

物流配送路徑優(yōu)化問題是物流配送業(yè)務(wù)中的優(yōu)化決策問題之一，目前多采用遺傳算法[1]、模擬退火算法[2]、蝙蝠算法[3]、智能水滴算法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]、蟻群算法[6]等啟發(fā)式算法求解，但上述算法單獨(dú)使用均存在早熟收斂，求解質(zhì)量不高。為此，文章嘗試將全局求解質(zhì)量高的遺傳算法與局部求解質(zhì)量高的模擬退火算法相結(jié)合，對(duì)遺傳算法求出的解進(jìn)行多次模擬退火尋優(yōu)，構(gòu)造一種混合遺傳算法。

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

假設(shè)已知情況如下：從配送中心向若干個(gè)客戶送貨，假設(shè)K表示最大車輛數(shù)；Qk（k=1,2,…,K）表示汽車的載重量；Dk表示車輛的最大行駛距離；L表示顧客配送數(shù)；qi表示每個(gè)顧客的需求量；dij表示配送點(diǎn)i到j(luò)的運(yùn)距；d0i表示配送中心到各配送點(diǎn)的距離；nk表示第k輛車服務(wù)的客戶數(shù)量；Rk表示第k條行駛路線；rki表示服務(wù)點(diǎn)rki在第k條路線的次序是i。求最優(yōu)的車輛配送路線，使配送路徑最短。

要求：1）每條線路上的總配送量不得超過車輛最大載重量；2）每條線路的總距離不能超過車輛行駛距離的臨界值；3）各個(gè)顧客的需求只能被一輛車服務(wù)。因此，建立配送模型如下：

2　混合遺傳算法構(gòu)造

混合遺傳算法主要是將模擬退火引入到遺傳算法的交叉操作中，使得遺傳算法不僅能夠接收優(yōu)良解，還能接收劣質(zhì)解，避免陷入“早熟”解中，以增強(qiáng)遺傳算法的局部求解效率。

2.1　算法實(shí)現(xiàn)步驟

具體實(shí)現(xiàn)步驟如下∶

1）確定種群大小n，交叉概率Pc，變異概率Pm，初始溫度T0；

2）對(duì)個(gè)體進(jìn)行編碼，用隨機(jī)法產(chǎn)生L個(gè)個(gè)體，計(jì)算個(gè)體的適應(yīng)度；

3）對(duì)個(gè)體進(jìn)行選擇操作；

4）對(duì)個(gè)體分別進(jìn)行交叉操作和模擬退火操作；

5）變異操作；

6）降溫，T=T0*θk，θ為一個(gè)[0,1]之間的常數(shù)，k為迭代次數(shù)；

7）判斷個(gè)體是否達(dá)到進(jìn)化代數(shù)G，若達(dá)到則終止運(yùn)算，否則轉(zhuǎn)步驟3。

2.2　混合遺傳算法的構(gòu)造

1）編碼。采用0、1、2、3、4，…，N的自然數(shù)編碼。

2）適應(yīng)度函數(shù)。對(duì)于某個(gè)個(gè)體，設(shè)其對(duì)應(yīng)的配送路徑條數(shù)與車輛總臺(tái)數(shù)之差為M，取適應(yīng)度值為Z，α為對(duì)每條不可行路徑的懲罰權(quán)重，則適應(yīng)度F為：

3）選擇算子。采用最佳個(gè)體保留方法。

4）交叉算子。采用類似OX法的交叉方法。

5）模擬退火算法。假設(shè)交叉前的父代是f1、f2，交叉后產(chǎn)生的子代c1、c2，計(jì)算父代和子代的適應(yīng)度分別是F(fi),F(ci)，i=1,2，然后進(jìn)行模擬退火操作，如果子代F(ci)大于父代F(fi)，則用子代ci代替父代 fi，否則，以概率 exp((F(ci)-F(fi)/T)接受子代 ci，其中T為當(dāng)前溫度；

6）變異算子。為了保持群體內(nèi)個(gè)體的多樣化，使個(gè)體在排列順序上有較大變化，采用了連續(xù)多次對(duì)換的變異方法。

3　仿真實(shí)驗(yàn)

實(shí)驗(yàn)1：配送中心需要對(duì)6個(gè)客戶進(jìn)行配送服務(wù)，假設(shè)有2輛車，一輛的載重量是8 t，一輛是7 t，車輛最大行駛距離都是60 km，具體數(shù)據(jù)見文獻(xiàn)[1]，求最短配送距離。

本文在MATLAB 2017下編制了程序，群體規(guī)模設(shè)置為40，代數(shù)設(shè)置為36代，交叉率為0.75，變異率為0.09，懲罰權(quán)重為300 km，模擬退火的降溫函數(shù)為T=T0*0.9k，其中T0為初始溫度，K為遺傳代數(shù)，初始溫度T0取為2 000。求解結(jié)果見表1。

表1　實(shí)驗(yàn)1計(jì)算結(jié)果

由表1可以看出：進(jìn)行了10次求解，第1、5、9次都求出了最優(yōu)解。

為了便于比較，本文還使用標(biāo)準(zhǔn)遺傳算法進(jìn)行了400次求解，2種算法求解結(jié)果見表2，顯然，從解的質(zhì)量和求解效率上混合遺傳算法都優(yōu)于遺傳算法。將2種情況下的結(jié)果進(jìn)行對(duì)比分析，如圖1所示。

表2　兩種算法計(jì)算結(jié)果比較

圖1　遺傳算法和混合遺傳算法比較

實(shí)驗(yàn)2：某物流中心需要配送30個(gè)顧客，共有6臺(tái)車輛，其最大載重量都是8 t，最大行駛距離是60 km。具體數(shù)據(jù)見文獻(xiàn)[1]，求最短配送距離。

求解時(shí)采用了以下參數(shù)：群體規(guī)模設(shè)置為70，代數(shù)設(shè)置為360，交叉率為0.95，變異率為0.08，懲罰權(quán)重為600 km，模擬退火算法參數(shù)同上。對(duì)實(shí)驗(yàn)2隨機(jī)求解10次，得到的計(jì)算結(jié)果見表3。

表3　實(shí)驗(yàn)2計(jì)算結(jié)果

表4　兩種算法計(jì)算結(jié)果比較

從表3可以看出，采用混合遺傳算法求解的10個(gè)解質(zhì)量都很優(yōu)良，求解效率也很好。

為了便于比較，本文還使用標(biāo)準(zhǔn)遺傳算法進(jìn)行了10 000次求解，2種算法求解結(jié)果見表4，顯然，從解的質(zhì)量和求解效率上混合遺傳算法都優(yōu)于遺傳算法。

4　結(jié)語

本文針對(duì)遺傳算法局部尋優(yōu)能力的不足，對(duì)其求得的解進(jìn)行模擬退火局部尋優(yōu)，構(gòu)造了混合遺傳算法，取得了很好的計(jì)算結(jié)果。目前還有很多的算法都有很強(qiáng)的局部搜索能力，如蟻群算法、離散Hopfield網(wǎng)絡(luò)等。將遺傳算法與這些局部搜索能力很強(qiáng)的算法相結(jié)合將是遺傳算法發(fā)展的重要方向。