MGASA算法求解物流中貨物最佳運(yùn)輸路線

摘要:本文首先描述了在物流系統(tǒng)中，貨物運(yùn)輸中的實(shí)際情況，對(duì)運(yùn)輸?shù)某杀尽r(shí)間限制加以描述，并建立了數(shù)學(xué)模型。然后在對(duì)遺傳算法和模擬退火算法進(jìn)行分析對(duì)比的基礎(chǔ)上，討論了它們各自的優(yōu)缺點(diǎn)，并將模擬退火算法和遺傳算法相結(jié)合，構(gòu)造混合遺傳模擬退火算法。克服了單一遺傳算法的不足，增強(qiáng)了其優(yōu)化行為，并提高了優(yōu)化的效率。在物流最佳運(yùn)輸路線問(wèn)題上，混合遺傳模擬退火算法表現(xiàn)出計(jì)算速度快，準(zhǔn)確度高的特性。

關(guān)鍵詞:最優(yōu)路徑 遺傳算法 模擬退火算法 混合遺傳模擬退火算法

0 引言

隨著我國(guó)經(jīng)濟(jì)建設(shè)的發(fā)展，我國(guó)的交通越來(lái)越便利，從一個(gè)城市到另一個(gè)城市，我們有各種交通工具盒路徑可供選擇，雖然便利了出行，但同時(shí)也給當(dāng)前的物流公司設(shè)置了難題。那就是如何在各種交通工具、運(yùn)輸路徑中選擇，才能在保證及時(shí)的前提小盡量減少成本，已使利潤(rùn)最大化。這也是本文所要研究的內(nèi)容。

1 最優(yōu)路徑查詢問(wèn)題的數(shù)學(xué)模型

我們首先將問(wèn)題抽象，假定我國(guó)交通地圖上的每個(gè)城市為一個(gè)節(jié)點(diǎn)，城市與城市之間連線標(biāo)識(shí)兩個(gè)城市之間的一種交通運(yùn)輸方式。當(dāng)然如果A地與B地之間有多種運(yùn)輸方式那么將會(huì)有多條連線。每種運(yùn)輸方式都有他的時(shí)間消耗值與運(yùn)輸成本。如圖所示。

對(duì)于沒(méi)有直接運(yùn)輸方式可達(dá)的兩個(gè)城市，我們也假定有一種運(yùn)輸方式，置其運(yùn)輸成本和運(yùn)輸時(shí)間為無(wú)窮大。這樣，從我們的網(wǎng)絡(luò)圖上，任意連個(gè)點(diǎn)之間都有連接，那么我們尋求A到B路徑的時(shí)候就可以隨機(jī)生成，例如A-B，或A-C-B，或A-D-B，或A-D-E-B等等，然后我們只要計(jì)算他們的時(shí)間、成本，找出滿足時(shí)間限制的最低成本的運(yùn)輸路徑即可。各個(gè)節(jié)點(diǎn)以及他們之間的運(yùn)輸成本和時(shí)間成本我們將存儲(chǔ)在兩個(gè)三維維數(shù)組中。

運(yùn)輸成本Costs[i][j][k]標(biāo)識(shí)節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的第k中運(yùn)輸方式的運(yùn)輸成本，Time[i][j][k]標(biāo)識(shí)節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的地k中運(yùn)輸方式的時(shí)間成本。在實(shí)際中Costs[j][i][k]標(biāo)識(shí)雖然是同一條路段的同一種運(yùn)輸方式，但是由于運(yùn)輸方向的不同，其成本也可能存在很大的差異。

生成路徑步驟:

隨機(jī)生成0=

For I 從0 到 CountT

begin

隨機(jī)獲得一個(gè)不再tempPathT，且不等于S和E的節(jié)點(diǎn)tempT

tempPathT=tempPathT+tempt

end

PathS-E=S+tempPathT+E，至此，路徑已經(jīng)生成完畢，下一步就是隨機(jī)選擇路徑上兩個(gè)節(jié)點(diǎn)之間的路徑，設(shè)置起始運(yùn)輸?shù)钠鋵?shí)城市節(jié)點(diǎn)為S，目的地節(jié)點(diǎn)為E，中間節(jié)點(diǎn)為T(mén)，按照離S節(jié)點(diǎn)的深度分為T(mén)1，T2，T3……，那么構(gòu)成一條的從S到E的一條完整的路徑我們就可以表示為: PathS-E=S-T1-T2-……Tn-E。從S-T1兩節(jié)點(diǎn)之間我們隨機(jī)選擇第r中運(yùn)輸方式，那么從S-T1的運(yùn)輸成本CostS-T1通過(guò)查詢Costs[i][j][k]可以獲得，并且標(biāo)識(shí)為P0Cost，從S-T1的時(shí)間成本TimeS-T1通過(guò)查詢Time[i][j][k]可以獲得，并且標(biāo)識(shí)為P0Time，那么以此類推，從S到E的總的運(yùn)輸成本可以標(biāo)識(shí)為PCost=P0Cost+P1Cost+……+PnCost，其時(shí)間總成本可以標(biāo)識(shí)為PTime=P0Time+P1Time+……+PnTime。

假定約束為貨物必須在N天抵達(dá)

目標(biāo)min∑Cost[i][j][k]

約束∑Time[i][j][k]<=N

2 算法分析

模擬退火算法是模擬對(duì)固體退火的過(guò)程，采用Meteropolis接受準(zhǔn)則，并用一組稱為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似最優(yōu)解。模擬退火算法能以一定的概率接收目標(biāo)函數(shù)值不太好的狀態(tài)。即算法不但往好的方向走也可向差的方向走;這使得算法即便落入局部最優(yōu)的陷阱中，理論上經(jīng)過(guò)足夠長(zhǎng)的時(shí)間后也可跳出來(lái)從而收斂到全局最優(yōu)解。模擬退火算法的主要缺點(diǎn)是為得到一個(gè)好的近似最優(yōu)解，需要進(jìn)行反復(fù)迭代運(yùn)算，當(dāng)問(wèn)題的規(guī)模很大時(shí)缺乏可行的解決途徑。

遺傳算法(Genetic Algorithms， GA)的優(yōu)點(diǎn)是:不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性、導(dǎo)數(shù)存在和單峰的假設(shè)，并且具有內(nèi)在的并行性，收斂速度快。遺傳算法在搜索的初期，由于優(yōu)良個(gè)體急劇增加使種群失去多樣性，容易造成程序陷入局部，達(dá)不到全局最優(yōu)解的現(xiàn)象。遺傳算法的另一個(gè)缺陷是“GA欺騙”問(wèn)題，即在GA的搜索過(guò)程中，有可能搜索到最優(yōu)解然后又發(fā)散出去的現(xiàn)象。

本文將模擬退火算法和遺傳算法結(jié)合來(lái)構(gòu)造一種混合遺傳模擬退火算法(Mixed Genetic-Simulated Annealing Algorithms， MGASA)。把遺傳算法運(yùn)行早期也作為模擬退火算法的初期，給適應(yīng)度添加一個(gè)系數(shù)λ，使λ與模擬退火的溫度成一定程度的反比關(guān)系，取λ=exp -(fj-fi)tk」，由于模擬退火算法早期溫度比較高，λ較小，這樣就使個(gè)體適應(yīng)度差異縮小，避免初期個(gè)別好的個(gè)體的后代充斥整個(gè)種群，導(dǎo)致早熟;在遺傳算法后期，模擬退火的溫度也在不斷的下降，從而使得λ的值不斷增大，使適應(yīng)度相近的個(gè)體適應(yīng)度差異放大，從而使得優(yōu)秀大額個(gè)體優(yōu)勢(shì)更明顯。從而避免了由于遺傳算法后期適應(yīng)度趨向一致，優(yōu)秀的個(gè)體在產(chǎn)生后代時(shí)，優(yōu)勢(shì)不明顯，使整個(gè)種群進(jìn)化停滯不前。在遺傳算法中種群的選取時(shí)，以模擬退火的接受概率Aij(tk)=min{1，exp(-)}接受或拒絕群體鄰域的某一狀態(tài)是否作為新種群的一員。另在遺傳算法基因發(fā)生變異時(shí)，發(fā)生變異的概率也是選取了模擬退火的接受概率。

3 求解最低運(yùn)輸成本的混合遺傳模擬退火算法

3.1 模擬退火參數(shù)的選擇設(shè)定

在進(jìn)行模擬退火操作時(shí)，冷卻進(jìn)度表的選取是一個(gè)關(guān)鍵。他包括如下參數(shù):控制參數(shù)t的初值t0、控制參數(shù)t的衰減系數(shù)α、控制參數(shù)t的終值tf。其中控制參數(shù)t的初值t0由t0=Δf-inχ0，其中Δf-為適應(yīng)度的平均減小量，χ0為初始接受率。第k次迭代時(shí)的控制參數(shù)為:tk=αtk-1，α=0.91控制參數(shù)t的終值取tf=t020000。

3.2 初始化染色體，構(gòu)造初始種群

在尋徑問(wèn)題中采用自然編碼，用矢量Asign(a1，a2，…，an)表示染色體G，其中基因ai=1，2，…，n是路徑的編號(hào)，ai=j表示路徑i上選中j節(jié)點(diǎn)，同時(shí)取得相應(yīng)的代價(jià)值Value[g][i][j]，這樣就構(gòu)成了該問(wèn)題的一個(gè)可行解，用同樣的方法就可以產(chǎn)生一組染色體Gh(h=1，2，…，N)，N為種群大小。其中染色體各不相同，此為第一代種群。

3.3 評(píng)價(jià)個(gè)體適應(yīng)度函數(shù)

適應(yīng)函數(shù)采用目標(biāo)函數(shù)，以保證較優(yōu)的解有較大的生存機(jī)會(huì)。另采用加速適應(yīng)度函數(shù):λ=exp -(fj-fi)tk」，式中tk是當(dāng)前第k代的溫度，k是遺傳代數(shù)。

3.4 交叉與變異的方法

對(duì)當(dāng)前的種群進(jìn)行交配，采取雙親單子法，這使得一對(duì)雙親只有一個(gè)后代，根據(jù)優(yōu)勝劣汰的自然法則從后代中選一個(gè)好的。在具體交配時(shí)采用變化交配法(string-of-change crossover)。如:父代A為(0|1|1|0100)，父代B為(0|1|1|1001)，如果交配位選在1，2，3位進(jìn)行交配，子代的A與子代B與其父代完全相同。因此，應(yīng)該避開(kāi)這三個(gè)位置，可以此采用的方法是從頭開(kāi)始比較它們的基因，從不同的位置按照常規(guī)方法隨機(jī)選擇交配位。如本例，比較可得到0001101，其中0表示相同，1表示不同。交配位可在4，5，6中隨機(jī)選取。這樣可以避免常規(guī)交配方法可能造成的父親與子代的完全相同，以至于影響收斂速度和搜索范圍。

對(duì)于變異操作，從子代中隨即選擇一個(gè)基因以模擬退火的接受概率Aij(tk)=min{1，exp(-)}進(jìn)行變異的操作。

由于在交叉過(guò)程中丟掉了一半數(shù)目的染色體，因此本文采用2-opt法構(gòu)造染色體的鄰域，同樣以模擬退火的接受概率Aij(tk)=min{1，exp(-)}選擇新的染色體加入到種群中來(lái)，直至種群數(shù)目滿足所設(shè)定的初值。另外，在遺傳過(guò)程中，為了防止當(dāng)前最優(yōu)解的遺失，采取將上一代的最優(yōu)值強(qiáng)行遺傳到下一代的策略。

3.5 溫度修改以及算法終止準(zhǔn)則的設(shè)計(jì)

這里采用了閥值法作為溫度修改和算法終止兩準(zhǔn)則的設(shè)計(jì)，因?yàn)檫@樣可以適應(yīng)算法性能的動(dòng)態(tài)變化，較好地兼顧算法的優(yōu)化性能和時(shí)間性能。例如溫度的逐步下降本文采取的是等比例降溫法，tk=αxtk-1，其中α∈(0，1)，另外除了設(shè)定算法的終止溫度外我們還可以根據(jù)問(wèn)題求解的規(guī)模設(shè)定算法最大迭代次數(shù)。

4 試驗(yàn)及結(jié)果分析

測(cè)試問(wèn)題:共有30個(gè)節(jié)點(diǎn)的運(yùn)輸成本核算問(wèn)題，每級(jí)路徑上至少有兩種運(yùn)輸方式(高速、普通公路)。設(shè)定初始節(jié)點(diǎn)為Pstart，終止節(jié)點(diǎn)為Pend。以下是混合遺傳模擬退火算法與遺傳算法、模擬退火算法在求解最低運(yùn)輸成本的測(cè)試結(jié)果:

從測(cè)試結(jié)果可以看出混合遺傳模擬退火算法在搜優(yōu)率上較遺傳算法和模擬退伙算法有了較大的提高。另外本文所采用的混合遺傳模擬算法的還具有以下優(yōu)點(diǎn):①多點(diǎn)搜索消弱了SA算法對(duì)初值的依賴性，利用GA算法不影響平穩(wěn)分布的特性，提高了整個(gè)算法的魯棒性。②它是一種并行而且具有自動(dòng)保優(yōu)功能的算法，利用GA和SA各自不同的鄰域搜索結(jié)構(gòu)相結(jié)合，使得算法在解空間中的搜索能力所增強(qiáng)，優(yōu)化效率得到提高。③它具有GA算法的優(yōu)化時(shí)間性能和SA算法可以最終趨于全局最優(yōu)的優(yōu)點(diǎn)，克服了GA算法“過(guò)早收斂”問(wèn)題和SA算法優(yōu)化時(shí)間性能較差的缺點(diǎn)。

5 結(jié)束語(yǔ)

本文結(jié)合遺傳算法和模擬退火算法的優(yōu)缺點(diǎn)，將模擬退火的思想引入遺傳算法，將模擬退火的接受概率應(yīng)用于種群的選取以及變異操作，并采用適應(yīng)值拉伸的方法，極大地緩解了遺傳算法的選擇壓力。豐富和優(yōu)化了整個(gè)過(guò)程，增強(qiáng)了全局和局部意義下的搜索能力和效率。在實(shí)際問(wèn)題的求解中表現(xiàn)出一定的優(yōu)越性。今后我將繼續(xù)研究多貨物配貨運(yùn)輸問(wèn)題，已減少整個(gè)物流企業(yè)在一定時(shí)期內(nèi)的總運(yùn)輸成本、人工成本問(wèn)題。

參考文獻(xiàn):

[1]唐文武，施曉東.GIS中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算[J].中國(guó)圖象圖形學(xué)報(bào):A輯.

[2]黃德才，郭海東，沈良忠.基于JIT的多目標(biāo)并行多機(jī)調(diào)度問(wèn)題的混合遺傳算法[J].系統(tǒng)工程理論與實(shí)踐. 2004.24(3):58-62.

[3]陸鋒，盧冬梅，崔偉宏.交通網(wǎng)絡(luò)限制搜索區(qū)域時(shí)間最短路徑算法[J].中國(guó)圖形圖象學(xué)報(bào).1999，(10).

[4]陸鋒.最短路徑算法:分類體系與研究進(jìn)展[J].測(cè)繪學(xué)報(bào).

[5]李勇，曹廣益，朱新堅(jiān).一種基于單親遺傳算法的Petri網(wǎng)發(fā)射路徑求解算法[J].系統(tǒng)仿真學(xué)報(bào).2005，17(1):203-206.

[6]劉志剛，王建華，耿英三，歐陽(yáng)森.一種改進(jìn)的遺傳模擬退火算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2004.16(5):1099-1101.

[7]行文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法(第2版).清華大學(xué)出版社，2005，09.

[8]周明，孫數(shù)棟.遺傳算法原理及應(yīng)用.國(guó)防工業(yè)出版社.1997.

[9]陳國(guó)良，王煦法，莊鎮(zhèn).遺傳算法及其應(yīng)用.人民郵電出版社.2001.02.

[10]王立平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社.2002.

[11]許國(guó)平，葉效鋒，鮑立威.基于模擬退火遺傳算法的車(chē)輛路徑問(wèn)題研究[J].工業(yè)控制計(jì)算機(jī).2004.24(3):58-62.

[12]嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào).

[13]康立山.非數(shù)值并行算法(第一冊(cè))-模擬退火算法.科學(xué)出版社.2000.6