融合模擬退火的遺傳算法在車輛調(diào)度中的應(yīng)用?

劉睿瓊 張文麗 侯愛華

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

1 引言

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

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為車輛到達客戶i的時間。此外，對于客戶i，j(i≠j)、車輛k定義如下兩個變量：xijk和 yik

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

約束條件如下：

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

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

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

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

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

3.1.1 染色體編碼

本文采用自然數(shù)編碼［4～5］，使用自然數(shù)對每個客戶進行編碼，以客戶點作為基因，按訪問的先后次序組成的染色體對應(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é)點插入到路線中。當某一個結(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)均勻分布的隨機數(shù) r，當P(i-1)＜r≤Pi時選擇此個體i；

3.1.4 交叉算子

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

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

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

3.1.5 變異算子

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

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

3.2.1 冷卻進度表

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

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

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

2）停止準則。當連續(xù)若干次降溫后目標函數(shù)無改進或者接受率小于給定足夠小的正數(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ù)

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

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

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

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

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

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

5 結(jié)語

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