物流配送路徑優化問題的模型及改進混合算法

摘要：在建立帶有時間窗的物流配送路徑優化問題數學模型的基礎上，構造了求解該問題的遺傳模擬退火混合算法。該混合算法利用了遺傳算法較強的全局搜索能力和模擬退火算法較好的局部搜索能力，克服了兩種算法各自在尋優方面的不足，使其在全局最優搜索和計算速度方面都有了很大的提高。最后經仿真試驗證實了混合算法解決物流配送路徑優化問題的優越性。

關鍵詞：物流配送；數學模型；遺傳算法；模擬退火算法；時間窗

中圖分類號：F224文獻標識碼：A

文章編號：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引言

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

遺傳算法（Genetic Algorithm，GA）和模擬退火算法（Simulated Annealing Algorithm，SA）在解決復雜優化問題時顯示出良好的特性。GA有較強的全局搜索能力，但實際應用中容易出現早熟收斂（premature convergence）現象，且在進化后期搜索效率較低。SA具有很好的局部搜索能力，但對參數的依賴性較強。因此考慮到兩種算法在實際應用中的特點，本文在對GA改進的基礎上，采用與SA算法相結合的混合算法，最后的仿真試驗說明了混合算法解決物流配送優化問題的優越性。

1物流配送路徑優化問題的數學模型

物流配送問題的描述：從配送中心將一定的貨物用一定的貨車向多個需求點運送，每個需求點的位置和需求量確定，安排合理的貨車運輸路徑使運距最短（即表示目標函數運價最低），并且滿足：（1）每條路線所運送貨物總和不能超過貨車載重量；（2）每輛貨車都要在規定的時間內準時送達貨物；（3）每輛貨車從配送中心出發，在規定時間內最后返回配送中心。

其中（1）是目標函數，方程（2）規定了路徑數限制，（3）確保貨車的出發地和返回地都是物流中心，（4）和（5）確保每個需求點只被一輛貨車送貨一次，（6）表示每條路線所運送的貨物總和不能超過貨車載重量，（7）貨車運輸的時間約束，（8）—（10）定義了車流路徑的時間窗。

2SA算法及其實現

模擬退火算法是用于解決組合優化問題的，是基于物理中固態物質的退火過程與一般組合優化問題之間的相似性，通過設定初溫和初態，伴隨溫度的不斷下降，結合概率突跳特性在解空間中通過鄰域函數進行隨機搜索，最終得到全局最優。模擬退火算法可以分解為解空間、目標函數和初始解三部分。模擬退火算法實現步驟如下：

（1）初始化：初始溫度T，初始解狀態S，每個T值的迭代次數為L；

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

（3）對當前狀態S隨機擾動產生一個新解S'；

（4）計算增量Δt=CS'-CS，其中CS為評價函數；

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

（6）如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接受時終止；

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

以上步驟稱為Metropolis過程[4]，按照一定的退火方案逐步降低溫度，重復Metropolis過程，就構成了SA優化算法。當系統溫度足夠低時，就認為達到了全局最優狀態。SA在解決組合優化問題中取得很好的效果，能解決傳統的優化方法難于解決的某些問題。

3GA算法及其實現

遺傳算法是美國Michigan大學John Holland教授根據生物進化論和遺傳學的思想提出的一種全局啟發式優化算法，它利用遺傳算子（選擇、交叉和變異）促進解集合類似生物種群在自然界中自然選擇、優勝劣汰、不斷進化，最終收斂于最優狀態。遺傳算法的實現步驟為：

（1）對求解空間進行編碼、初始化；

（4）應用遺傳算子產生新一代群體popi+1；

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

GA通過選擇復制和遺傳因子的作用，使優化群體不斷進化，最終收斂于最優狀態。選擇復制適應度函數值大的個體有較大的復制概率，它能加快算法的收斂速度。交叉算子通過對兩個父代進行基因交換而搜索出更優的個體。變異操使進化群體產生多樣性，避免算法陷入局部最優。然而實踐證明，遺傳算法往往會表現出早熟現象、局部尋優能力較差等不足，將遺傳算法與其它算法相結合有助于彌補它的不足之處，并能夠加快尋優速度。

4GA和SA混合算法及其實現

4.1算法分析

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

4.2算法步驟

GA和SA混合算法的基本思想：從通過PFIH方法[6]產生的初始種群中開始全局最優解的搜索過程，先通過選擇、交叉、變異等遺傳操作來產生一組新的個體，然后再獨立地對種群中的個體進行模擬退火過程，以其結果作為下一代種群中的個體。經過反復的迭代直到滿足某個終止條件為止。算法實現的步驟如下：

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

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

4.3算法描述

（1）染色體的編碼

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

（2）初始種群的產生

（4）適應度函數

（5）選擇算子

（6）交叉和變異算子

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

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

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

=。

（7）新個體的復制策略及終止規則

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

6結束語

算法中，當貨車數過小時，找不到可行解，當貨車數過大時，得到的方案不經濟，通過適當的調整貨車數使方案達到滿意的結果。混合算法結合了遺傳算法和模擬退火算法各自優點，即利用了GA的全局搜索能力和SA的局部搜索能力，使混合算法在全局尋優和計算效率方面都有了很大的提高。經試驗證明，混合算法在解決帶有時間窗的物流配送路徑優化問題上保持了良好的性能，當需求點較少時得到了最優解，當需求點較多時得到了滿意解。

參考文獻：

[1] 郎茂祥. 基于遺傳算法的物流配送路徑優化問題的研究[J]. 中國公路學報，2002(3):76-79.

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

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

[4] 王素云，李軍. 基于遺傳算法的物流配送車輛優化調度[J]. 商場現代化，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.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。