劉睿瓊 張文麗 侯愛華

（1.西安理工大學(xué)高等技術(shù)學(xué)院 西安 710082）（2.陜西理工大學(xué)物電學(xué)院 漢中 723000）

1 引言

遺傳算法屬于隨機(jī)搜索算法，其來源于生物界自然選擇和自然遺傳機(jī)制，在各類工程優(yōu)化問題中得到了廣泛應(yīng)用。在車輛調(diào)度領(lǐng)域，遺傳算法應(yīng)用已經(jīng)很多，但多采用標(biāo)準(zhǔn)遺傳算法［1］。遺傳算法是以點集到點集的方式進(jìn)行搜索，相對于點到點的搜索方法能以更大的概率搜索到全局最優(yōu)解，但在實踐應(yīng)用過程中遺傳算法往往容易產(chǎn)生早熟［2］，而得不到全局最優(yōu)解，因此需要對其進(jìn)行改進(jìn)。模擬退火算法不僅接收使目標(biāo)函數(shù)變好的解，還在一定程度上接收使目標(biāo)函數(shù)變差的解，克服了遺傳算法局部搜索能力較差、易出現(xiàn)早熟現(xiàn)象的缺點。因此，如果能夠使用模擬退火算法對種群進(jìn)行優(yōu)化，能夠有效提高遺傳算法的運行效率和準(zhǔn)確性。

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

本文主要討論單配送中心有時間窗約束車輛調(diào)度（VRPTW）問題［3］。設(shè) N 表示為客戶總數(shù)，編號分別為1，2，…，N；編號0表示配送中心。D=(dij)為歷程矩陣。配送中心的車輛數(shù)為K，q為車輛的容積。gi表示第i個客戶的需求量。[ai，bi]為客戶i的時間窗，即送貨時間不能早于ai，且不能晚于bi，否則就要追加一定的時間窗懲罰值。ti為車輛到達(dá)客戶i的時間。此外，對于客戶i，j(i≠j)、車輛k定義如下兩個變量：xijk和 yik

根據(jù)以上假設(shè)，有時間窗約束車輛調(diào)度問題的數(shù)學(xué)模型可表示為

約束條件如下：

在上述表達(dá)式中，式（1）為目標(biāo)函數(shù)，時間窗懲罰函數(shù)將在后面討論；式（2）表示每個客戶的貨物只由一輛車配送；式（3）～（4）表示變量之間的約束關(guān)系；式（5）～（7）保證了車輛始于配送中心，不重復(fù)的經(jīng)過客戶后，最終又回到配送中心；式（8）表示一輛車的任務(wù)量不大于其容量；式（9）表示交貨時間窗約束。

3 融合了模擬退火的改進(jìn)遺傳算法的實現(xiàn)

融合模擬退火的遺傳算法是在基本遺傳算法運算流程的基礎(chǔ)上，融入了模擬退火算法，針對選擇運算、交叉運算和變異運算產(chǎn)生的新種群，使用模擬退貨算法逐一進(jìn)行優(yōu)化，改善遺傳算法的局部搜索能力。整個算法的執(zhí)行過程如圖1所示。

圖1 融合模擬退火的遺傳算法流程圖

3.1 遺傳算法的實現(xiàn)

3.1.1 染色體編碼

本文采用自然數(shù)編碼［4～5］，使用自然數(shù)對每個客戶進(jìn)行編碼，以客戶點作為基因，按訪問的先后次序組成的染色體對應(yīng)問題的解。例如，若問題的解路線為

路線1：0—2—5—6—0

路線2：0—1—7—3—8—0

路線3：0—4—9—0

去除配送點編號0，然后將車輛路線的客戶點首尾順序連接起來，那么，上例中的染色體編碼應(yīng)該為256173849。解碼只是編碼的逆向操作，按順序依次將基因位表示的節(jié)點插入到路線中。當(dāng)某一個結(jié)點加入后不滿足時間或者體積約束時，就新增一條路線且把此點插入［6］。

3.1.2 適應(yīng)度函數(shù)

在實際的車輛調(diào)度配送問題中，運行成本主要由兩部分組成。一部分是車輛在配送過程的行駛成本，如果車速一定的情況下，這一部分與距離成正比；另一部分是違反客戶配送時間要求（即時間約束窗口）的懲罰成本，這一部分與貨物配送至客戶的時間相關(guān)。本文中對于時間窗約束的懲罰函數(shù)［7］形式如下：

其中：si為客戶 pi的時間窗懲罰函數(shù)，M 為一個足夠大的正整數(shù)，α1、α2、β1、β2為常數(shù)。綜合配送車輛的行駛成本和時間窗懲罰成本，配送過程中的總成本可用如下函數(shù)表示：

3.1.3 選擇算子

本文采用比例選擇算子。為了使適應(yīng)度最好的個體盡可能地保留下來，我們在遺傳算法中還使用了最優(yōu)保留策略。

2）對于第i個個體，計算從第1個到第i個個體的累計相對適應(yīng)度

3）產(chǎn)生［0，1］內(nèi)均勻分布的隨機(jī)數(shù) r，當(dāng)P(i-1)＜r≤Pi時選擇此個體i；

3.1.4 交叉算子

本文采用部分映射交叉算子［8］，整個交叉操作過程分為兩步。首先對父代基因串進(jìn)行雙點交叉操作；然后根據(jù)交叉區(qū)域內(nèi)各基因值的映射關(guān)系來修改交叉區(qū)域以外的基因位的基因值。

?根據(jù)如上的映射關(guān)系得

其中交叉交換點k1，k2是隨機(jī)選取的。

3.1.5 變異算子

本文采用倒位變異的方法作為變異算子［9］。倒位變異是指在父體中隨機(jī)的選擇兩個斷點，將斷點之間的基因逆序排列，從而產(chǎn)生一個新的個體。

3.2 模擬退火算法的實現(xiàn)

3.2.1 冷卻進(jìn)度表

冷卻進(jìn)度表是一組算法進(jìn)程的控制參數(shù)，用以逼近模擬退火算法的漸進(jìn)收斂性，可以使算法執(zhí)行一定時間后返回一個近似最優(yōu)解［10］。

1）控制參數(shù)初值t0。本文通過計算若干次隨機(jī)變換目標(biāo)函數(shù)平均增量的方法來確定t0［11］的值：，其中為計算若干次隨機(jī)變換目

標(biāo)函數(shù)平均增量。只要設(shè)定初始接受率 p0，就能求出相應(yīng)的t0值。

2）停止準(zhǔn)則。當(dāng)連續(xù)若干次降溫后目標(biāo)函數(shù)無改進(jìn)或者接受率小于給定足夠小的正數(shù)λ時停止算法。

3）控制參數(shù)衰減函數(shù)［12］。本文采用指數(shù)衰減策略，取tk=αtk-1其中α為一接近1的常數(shù)，一般取0.5～0.99之間，本文選取α=0.9。

4）馬爾科夫鏈長度。本文采用固定長度馬爾科夫鏈 Lk=20［13］。

3.2.2 狀態(tài)產(chǎn)生函數(shù)

文獻(xiàn)［14］給出一種新的方法——排序反轉(zhuǎn)并移位，即隨機(jī)在編碼串中產(chǎn)生三個斷點k1、k2、k3（k1＜k2＜k3），將k1和k2之間的編碼倒序排列并插入到k3之后。并證明了此方法求解旅行商問題相當(dāng)有效，本文采用此方法。

3.2.3 狀態(tài)接受函數(shù)

采用Metropolis準(zhǔn)則作為狀態(tài)接受函數(shù)［15］。即接受新解的概率為

Metropolis接受準(zhǔn)則的優(yōu)點是可以對優(yōu)化解以一定的概率來接受，盡可能避免陷入局部最優(yōu)更有可能最終獲得系統(tǒng)的全局或近似全局最優(yōu)解。

4 仿真結(jié)果分析

根據(jù)實際問題有這樣一個配送系統(tǒng)，系統(tǒng)中含有1個配送中心，編號為0；8個客戶，編號依次從1至8，配送中心車輛的容量最大為8t。已知每個客戶的貨運量：gi（單位：立方），卸貨時間為：si（單位：小時），每項任務(wù)時間窗[ai，bi]（單位：小時）見表1，客戶之間的距離見表2。合理安排行車路線，使總運輸距離最小。

表1 客戶的特征及要求

表2 客戶之間的距離

本文采用的算法的仿真參數(shù)取值如下：初始種群隨機(jī)產(chǎn)生，種群個體數(shù)為50；種群遺傳進(jìn)化的代數(shù)設(shè)為100；針對選擇的個體以 pc=0.8概率進(jìn)行交叉；交叉操作后的個體以 pm=0.1概率進(jìn)行變異；車輛按60公里/小時的固定速度行駛；馬爾科夫鏈長L=20；接受概率小于0.01或連續(xù)40次降溫?zé)o變化則停止；退火系統(tǒng)為α=0.9，p0=0.95。表3給出了融合了模擬退火的改進(jìn)遺傳算法和基本遺傳算法的多次仿真結(jié)果比較（總成本的單位：公里，行駛時間的單位：小時）。該問題的最優(yōu)解為：0-8-5-7-0，0-6-4-0，0-3-1-2-0，最 優(yōu) 距 離 為1092，行駛時間為33.5。

表3 融合了模擬退火的改進(jìn)遺傳算法和基本的遺傳算法結(jié)果比較

通過比較可以看出，融合了模擬退火的改進(jìn)遺傳算法和基本遺傳算法都能得到最優(yōu)解，但本文所使用算法的局部搜索能力得到了顯著提高，避免了出現(xiàn)早熟現(xiàn)象，將進(jìn)化代數(shù)由100降到了10，仍然能每次都得到1092km的最優(yōu)解。而且，融合了模擬退火的改進(jìn)遺傳算法的收斂速度明顯優(yōu)于遺傳算法。

5 結(jié)語

本文討論了有時間約束窗口的車輛調(diào)度系統(tǒng)的數(shù)學(xué)模型和遺傳算法的詳細(xì)實現(xiàn)過程，指出了遺傳算法具有局部搜索能力較差、易產(chǎn)生早熟現(xiàn)象的缺點，并在遺傳算法搜索過程中融入了模擬退火算法，針對選擇運算、交叉運算和變異運算產(chǎn)生的新種群，使用模擬退貨算法逐一進(jìn)行優(yōu)化，新算法兼顧了局部和全局兩方面，克服了遺傳算法的缺點，仿真結(jié)果證明是一套完善可行的優(yōu)化方法。