物流配送路徑優(yōu)化問(wèn)題的模型及改進(jìn)混合算法

摘要：在建立帶有時(shí)間窗的物流配送路徑優(yōu)化問(wèn)題數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求解該問(wèn)題的遺傳模擬退火混合算法。該混合算法利用了遺傳算法較強(qiáng)的全局搜索能力和模擬退火算法較好的局部搜索能力，克服了兩種算法各自在尋優(yōu)方面的不足，使其在全局最優(yōu)搜索和計(jì)算速度方面都有了很大的提高。最后經(jīng)仿真試驗(yàn)證實(shí)了混合算法解決物流配送路徑優(yōu)化問(wèn)題的優(yōu)越性。

關(guān)鍵詞：物流配送；數(shù)學(xué)模型；遺傳算法；模擬退火算法；時(shí)間窗

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-3100(2008)04-0026-05

Abstract: The thesis constructs the mathematical model of optimizing distribution routing problem with time window， and designs the hybrid algorithm of Genetic and Simulated Annealing Algorithm. The hybrid algorithm， which overcomes the disadvantages of the two algorithms in global search， adopts the advantages of both algorithms to solve the combinatorial and optimizing problem. The hybrid algorithm improves the GB search and computation speed greatly. Finally， simulated test proves the superiority of the hybrid algorithm.

Key words: logistics distribution; mathematical model; genetic algorithm; simulated annealing algorithm; time window

0引言

物流配送是指按用戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)、經(jīng)濟(jì)、有效地送給收貨人。配送路徑的選擇是否合理對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本有很大的影響。物流配送路徑的優(yōu)化問(wèn)題是一個(gè)典型的NP完全問(wèn)題，很難用全局搜索算法求出最優(yōu)解，因此尋求一種有效的算法求出其接近最優(yōu)解或滿意解有重要的理論和實(shí)踐意義。

遺傳算法（Genetic Algorithm，GA）和模擬退火算法（Simulated Annealing Algorithm，SA）在解決復(fù)雜優(yōu)化問(wèn)題時(shí)顯示出良好的特性。GA有較強(qiáng)的全局搜索能力，但實(shí)際應(yīng)用中容易出現(xiàn)早熟收斂（premature convergence）現(xiàn)象，且在進(jìn)化后期搜索效率較低。SA具有很好的局部搜索能力，但對(duì)參數(shù)的依賴性較強(qiáng)。因此考慮到兩種算法在實(shí)際應(yīng)用中的特點(diǎn)，本文在對(duì)GA改進(jìn)的基礎(chǔ)上，采用與SA算法相結(jié)合的混合算法，最后的仿真試驗(yàn)說(shuō)明了混合算法解決物流配送優(yōu)化問(wèn)題的優(yōu)越性。

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

物流配送問(wèn)題的描述：從配送中心將一定的貨物用一定的貨車向多個(gè)需求點(diǎn)運(yùn)送，每個(gè)需求點(diǎn)的位置和需求量確定，安排合理的貨車運(yùn)輸路徑使運(yùn)距最短（即表示目標(biāo)函數(shù)運(yùn)價(jià)最低），并且滿足：（1）每條路線所運(yùn)送貨物總和不能超過(guò)貨車載重量；（2）每輛貨車都要在規(guī)定的時(shí)間內(nèi)準(zhǔn)時(shí)送達(dá)貨物；（3）每輛貨車從配送中心出發(fā)，在規(guī)定時(shí)間內(nèi)最后返回配送中心。

其中（1）是目標(biāo)函數(shù)，方程（2）規(guī)定了路徑數(shù)限制，（3）確保貨車的出發(fā)地和返回地都是物流中心，（4）和（5）確保每個(gè)需求點(diǎn)只被一輛貨車送貨一次，（6）表示每條路線所運(yùn)送的貨物總和不能超過(guò)貨車載重量，（7）貨車運(yùn)輸?shù)臅r(shí)間約束，（8）—（10）定義了車流路徑的時(shí)間窗。

2SA算法及其實(shí)現(xiàn)

模擬退火算法是用于解決組合優(yōu)化問(wèn)題的，是基于物理中固態(tài)物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性，通過(guò)設(shè)定初溫和初態(tài)，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中通過(guò)鄰域函數(shù)進(jìn)行隨機(jī)搜索，最終得到全局最優(yōu)。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火算法實(shí)現(xiàn)步驟如下：

（1）初始化：初始溫度T，初始解狀態(tài)S，每個(gè)T值的迭代次數(shù)為L(zhǎng)；

（2）對(duì)k=1，2，…L，做第（3）至第6步；

（3）對(duì)當(dāng)前狀態(tài)S隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解S'；

（4）計(jì)算增量Δt=CS'-CS，其中CS為評(píng)價(jià)函數(shù)；

（5）若Δt<0，則接受S'作為新的當(dāng)前解，否則以概率exp-ΔtT接受S'作為新的當(dāng)前解；

（6）如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止；

（7）T逐漸減少，且T→0，然后轉(zhuǎn)到第（2）步。

以上步驟稱為Metropolis過(guò)程[4]，按照一定的退火方案逐步降低溫度，重復(fù)Metropolis過(guò)程，就構(gòu)成了SA優(yōu)化算法。當(dāng)系統(tǒng)溫度足夠低時(shí)，就認(rèn)為達(dá)到了全局最優(yōu)狀態(tài)。SA在解決組合優(yōu)化問(wèn)題中取得很好的效果，能解決傳統(tǒng)的優(yōu)化方法難于解決的某些問(wèn)題。

3GA算法及其實(shí)現(xiàn)

遺傳算法是美國(guó)Michigan大學(xué)John Holland教授根據(jù)生物進(jìn)化論和遺傳學(xué)的思想提出的一種全局啟發(fā)式優(yōu)化算法，它利用遺傳算子（選擇、交叉和變異）促進(jìn)解集合類似生物種群在自然界中自然選擇、優(yōu)勝劣汰、不斷進(jìn)化，最終收斂于最優(yōu)狀態(tài)。遺傳算法的實(shí)現(xiàn)步驟為：

（1）對(duì)求解空間進(jìn)行編碼、初始化；

（4）應(yīng)用遺傳算子產(chǎn)生新一代群體popi+1；

（5）判斷終止條件，不滿足返回（3）。

GA通過(guò)選擇復(fù)制和遺傳因子的作用，使優(yōu)化群體不斷進(jìn)化，最終收斂于最優(yōu)狀態(tài)。選擇復(fù)制適應(yīng)度函數(shù)值大的個(gè)體有較大的復(fù)制概率，它能加快算法的收斂速度。交叉算子通過(guò)對(duì)兩個(gè)父代進(jìn)行基因交換而搜索出更優(yōu)的個(gè)體。變異操使進(jìn)化群體產(chǎn)生多樣性，避免算法陷入局部最優(yōu)。然而實(shí)踐證明，遺傳算法往往會(huì)表現(xiàn)出早熟現(xiàn)象、局部尋優(yōu)能力較差等不足，將遺傳算法與其它算法相結(jié)合有助于彌補(bǔ)它的不足之處，并能夠加快尋優(yōu)速度。

4GA和SA混合算法及其實(shí)現(xiàn)

4.1算法分析

遺傳算法較適合于傳統(tǒng)搜索方法所不能解決的復(fù)雜問(wèn)題和非線性問(wèn)題。然而，實(shí)際應(yīng)用中遺傳算法存在編碼、迭代次數(shù)、種群規(guī)模的限制，造成種群多樣性和選擇性壓力的調(diào)和沖突，即強(qiáng)選擇性壓力導(dǎo)致遺傳搜索過(guò)早收斂，強(qiáng)種群多樣性導(dǎo)致遺傳搜索效率低下，遺傳算法的改進(jìn)應(yīng)考慮到：（1）為了保證算法能全局收斂，必須保證種群的多樣性；（2）為了加快算法的收斂，必須使種群中個(gè)體盡快向最優(yōu)解聚集。理論上分析，GA和SA算法均屬于基于概率分布機(jī)制的優(yōu)化算法。將兩種算法進(jìn)行結(jié)合，有利于豐富優(yōu)化過(guò)程中的搜索行為，增強(qiáng)全局和局部意義下的搜索能力和效率。

4.2算法步驟

GA和SA混合算法的基本思想：從通過(guò)PFIH方法[6]產(chǎn)生的初始種群中開(kāi)始全局最優(yōu)解的搜索過(guò)程，先通過(guò)選擇、交叉、變異等遺傳操作來(lái)產(chǎn)生一組新的個(gè)體，然后再獨(dú)立地對(duì)種群中的個(gè)體進(jìn)行模擬退火過(guò)程，以其結(jié)果作為下一代種群中的個(gè)體。經(jīng)過(guò)反復(fù)的迭代直到滿足某個(gè)終止條件為止。算法實(shí)現(xiàn)的步驟如下：

Step8：判斷S'是否小于S，如果是，令S=S'，p=0，否則p=p+1；

Step9：判斷p是否大于或等于q，如果是，則以S作為最終解輸出，并停止計(jì)算。否則返回第（3）步。

4.3算法描述

（1）染色體的編碼

采用人工染色體字符串實(shí)體表示種群成員，解表示長(zhǎng)度為N的定長(zhǎng)整型字符串，N為網(wǎng)絡(luò)中的需求點(diǎn)數(shù)，染色體中的一個(gè)數(shù)字表示一個(gè)需求點(diǎn)，染色體基因的順序表示貨車行使的路徑和方向。例如含有8個(gè)需求點(diǎn)的配送網(wǎng)絡(luò)其編碼可以表示為47628531，表示的路徑為：路徑1，0→4→7→6→0；路徑2，0→2→8→5→3→1→0，其中，路徑k的最后一個(gè)需求點(diǎn)與路徑k+1的第一個(gè)需求點(diǎn)相連。解碼時(shí)將基因按順序插入新的路徑當(dāng)中，一般認(rèn)為路徑數(shù)最小化即是費(fèi)用最小化，即在約束條件下最大限度的利用每條路徑貨車的載重量。

（2）初始種群的產(chǎn)生

（4）適應(yīng)度函數(shù)

（5）選擇算子

（6）交叉和變異算子

由于傳統(tǒng)的單點(diǎn)或雙點(diǎn)交叉操作只適用于無(wú)序的染色體基因序列或變長(zhǎng)的染色體基因序列，而物流配送路徑問(wèn)題的染色體編碼是定長(zhǎng)有序的，且每條染色體中的整數(shù)基因只出現(xiàn)一次，為了避免經(jīng)交叉操作后出現(xiàn)不合格后代（即染色體中出現(xiàn)重復(fù)的整數(shù)基因），本文采用PMX[7]（Permutation Crossover）交叉方法，即在染色體編碼中隨機(jī)選擇兩個(gè)交叉點(diǎn)，然后交換兩點(diǎn)之間的染色體基因，例如：若父代基因序列為：

Parent1 h k c e f d b l a i g j

Parent2 a b c d e f g h I j k l

交叉后的后代基因序列為：

Offspring1 i g c d e f b l a j k h

Offspring2 l k c e f d g h I a b j

變異操作是交叉操作的重要補(bǔ)充，變異操作使父代種群產(chǎn)生隨機(jī)的、無(wú)關(guān)聯(lián)的性狀，是維持種群多樣性的重要手段。考慮到本算法編碼的特點(diǎn)，本文采用INV[3]作為變異算子，這有利于算法的小范圍遷移，并可以在染色體中引入小幅度變化，增加了種群的多樣性。變異概率的選擇是變異算子的關(guān)鍵，概率太大使算法收斂過(guò)快，陷入局部最優(yōu)；而概率太小使算法收斂過(guò)慢，影響計(jì)算速度。本文采用一種獨(dú)特的適應(yīng)性變異概率計(jì)算方法，即：s

=。

（7）新個(gè)體的復(fù)制策略及終止規(guī)則

根據(jù)本文的混合算法及以上參數(shù)設(shè)定編制了各個(gè)算法的計(jì)算機(jī)程序，GA算法求得的解分布較為均勻，而改進(jìn)的遺傳模擬退火算法在模擬中都找到了最優(yōu)解，SA算法的運(yùn)行時(shí)間較長(zhǎng)，但求得的最優(yōu)解強(qiáng)于GA算法最優(yōu)解，而GA算法求得的解的變化幅度較小，各種算法性能比較如表3所示。說(shuō)明SA算法在局部搜索的能力較GA算法強(qiáng)，而GA算法全局搜索能力較SA算法強(qiáng)。改進(jìn)的遺傳模擬退火算法保持了很高的性能，獲得了明顯優(yōu)于其它兩種方法的解，算法求得的最優(yōu)路徑如表4所示，說(shuō)明混合算法較快的收斂并得到比較滿意的解。

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

算法中，當(dāng)貨車數(shù)過(guò)小時(shí)，找不到可行解，當(dāng)貨車數(shù)過(guò)大時(shí)，得到的方案不經(jīng)濟(jì)，通過(guò)適當(dāng)?shù)恼{(diào)整貨車數(shù)使方案達(dá)到滿意的結(jié)果。混合算法結(jié)合了遺傳算法和模擬退火算法各自優(yōu)點(diǎn)，即利用了GA的全局搜索能力和SA的局部搜索能力，使混合算法在全局尋優(yōu)和計(jì)算效率方面都有了很大的提高。經(jīng)試驗(yàn)證明，混合算法在解決帶有時(shí)間窗的物流配送路徑優(yōu)化問(wèn)題上保持了良好的性能，當(dāng)需求點(diǎn)較少時(shí)得到了最優(yōu)解，當(dāng)需求點(diǎn)較多時(shí)得到了滿意解。

參考文獻(xiàn)：

[1] 郎茂祥. 基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題的研究[J]. 中國(guó)公路學(xué)報(bào)，2002(3):76-79.

[2] 趙瑛琪. 一種求解車輛路徑問(wèn)題的雙目標(biāo)遺傳算法[J]. 湖南工程學(xué)院學(xué)報(bào)，2006，16(2):49-51.

[3] 劉懷春，劉懷亮，李秀煥，等. 改進(jìn)的遺傳模擬退火算法及其在組合優(yōu)化中的應(yīng)用研究[J]. 現(xiàn)代計(jì)算機(jī)，2004(1):14-16，41.

[4] 王素云，李軍. 基于遺傳算法的物流配送車輛優(yōu)化調(diào)度[J]. 商場(chǎng)現(xiàn)代化，2006(28):119-120.

[5]K. C. Tan， L. H. Lee， Q. L. Zhu， K. Qu. Heuristic Methods for Vehicle Routing Problem with Time Window[J]. Artificial Intelligence in Engineering， 2000(12):15.

[6]Solomon MM. Algorithms for Vehicle Routing and Scheduling Problem with Time Window constraints[J]. Oper Res， 1987，35(2):54-66.

[7]Oliver IM， Smith DJ， Holland JRC. A study of permutation crossover operations on the traveling salesman problem[C] // In: Proceedings of the fourth International Conference on Genetic Algorithm， 1991.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。