基于混合遺傳算法的快遞車輛路徑優化問題研究

敖成敏

摘 要：車輛路徑問題是物流配送過程中的關鍵環節，車輛路徑優化問題是一個典型的有約束的組合優化問題，屬于強NP問題。本文在建立車輛路徑模型的基礎上，運用分區算法，把大量的數據區域劃分成幾個不同的較小的數據區域，利用局部搜索算法和遺傳算法結合的新的混合遺傳算法來確定具體的快遞車輛的配送路徑。仿真實驗證明，該混合遺傳算法在尋找最優解上具有可行性，而且在運算效率方面有相應的提升。

關鍵詞：混合遺傳算法;配送分區;局部搜索算法;快遞物流配送

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

0 引言

Dantzig和Ramser[1]二十世紀六十年代在首次提出物流配送路徑優化問題后，很快便成為組合優化領域和運籌學的研究熱點以及前沿問題。Loannou G，Prastacos G[2]等人在建立帶時間窗的問題模型時，采用可得到更好解的啟發式算法求解車輛路徑問題。沈維蕾等[3]在建立數學模型的基礎上，建立混合快遞服務的配送模式。目前，國內外有許多研究車輛路徑規劃問題的智能優化算法，其中局部搜索算法簡單靈活，但容易陷入局部最優解。趙威，曾國輝等[4]以改進的局部搜索算法為基礎，融合蟻群算法中信息素因子和人工勢場算法中勢場因子，建立了啟發函數模型以提高尋優的目的性，并對搜索到的路徑用迭代法進行優化。故本文采用局部搜索算法和遺傳算法相融合的混合遺傳算法，從而解決傳統遺傳算法求解擁有大量數據的車輛路徑問題時會出現搜索效率低、收斂速度慢、早熟收斂等現象。

1 快遞車輛路徑模型

本文將優化目標設定為快遞車輛的行駛路徑最短。設為客戶總數;為客戶的需求量;為客戶與客戶之間的距離。當時，指位于配送中心，指客戶2與客戶3之間的距離;為車輛總數;為車輛的最大裝載量;為車輛的最大行駛距離;為車輛配送的客戶總數;當時，表示車輛不是配送車輛;為車輛參與配送客戶的集合;當時，;當時，，其中表示該客戶在車輛的配送路線中所處的位置為。

該模型中，目標函數（1）（2）敘述的車輛配送路徑優化目標是將配送車輛的行駛總路徑最短;約束條件（3）表示每個客戶點只能被遍歷一次;約束條件（4）敘述的是每條配送路徑的總需求量不超過配送車輛的最大裝載量;約束條件（5）表示的是每一條配送路徑的總遍歷長度不超過該車輛一次最大行駛距離;約束條件（6）（7）（8）規定了運輸配送路徑包含所有的客戶點。

2 算法的求解

混合遺傳算法的主要思想是：將每個算法的優勢有效的結合起來，從而高效率的求解車輛路徑優化問題，為物流配送中心提供具有參考價值的車輛調度方案。在面對大量又不盡相同的客戶數據時，首先采用分區算法對客戶數據初次區域分區;然后利用最近鄰算法得出各分區域內的配送車輛的行駛路徑的初始解;再運用遺傳算法和局部搜索算法融合形成的混合遺傳算法對初始解進行優化計算，從而求解出每輛快遞服務車輛的服務序列。

2.1 混合遺傳操作

混合遺傳操作包括局部搜索操作和遺傳操作兩個環節。

局部搜索操作的目的是進一步優化算法的求解能力。在算法過程中，任意選取個體基因串中兩個位置，交換該位置對應的基因，生成新的個體，若新的個體對應的最優值優于之前的個體，則以新個體取代舊個體，否則保留舊個體。

遺傳操作分為選擇、交叉、變異三個操作環節。其中，選擇操作有多種選擇方法，本文選取加權隨機（輪盤賭）配對，對染色體進行選擇;交叉操作，交叉運算本文采用的是等長度的染色體編碼，且是小數編碼，采用單點交叉策略;變異操作中為保持局部隨機搜索能力和保持群體的多樣性，避免出現未成熟就收斂的情況，本文對染色體第一段編碼采用單點變異。

3 算例分析

3.1 算法有效性

圖3.1給出了最優解隨遺傳算法迭代次數的變化圖。由圖3.1可知，當迭代次數達到500代左右，達到最優解收斂狀態。

3.2 算法敏感性

為分析混合遺傳算法中種群最優個體交叉變異概率的變化對最優解的影響，本文設定局部搜索次數為50;最優個體交叉概率為0.5、0.6、0.7、0.8、0.9以及最優個體變異概率為0.1、0.2、0.3、0.4、0.5兩兩組合對三類測試數據集進行25組實驗，每組實驗運行算法10次取平均值。通過對三類數據集的分析，發現整體上，最優解受最優個體變異概率的影響不顯著，隨最優個體交叉概率的增加而減小。并且，當最優個體交叉概率趨近0.6，變異概率趨近0.3時，算法會取得最優解。

4 結論

通過對物流路徑優化問題進行深入的研究發現，本文將遺傳算法與局部搜索算法相混合，得到了一種求解車輛路徑問題的高效算法——混合遺傳算法。最后引用實例對比分析求解結果，說明了混合遺傳算法擁有尋找最優解的能力，并且在運算效率方面都能表現出一定的提高。

參考文獻：

[1]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（01）：80-91

[2]Loannou G，Prastacos G.A greedy look-ahead heuristic for the vehicle routing problem with time windows[J].Journal of the Operational Research Society，2001，52（05）：523-537.

[3]周蓉，沈維蕾，劉明周，等.帶時間窗裝卸一體化車輛路徑問題的混合離散粒子群優化算法[J].中國機械工程，2016，27（04）：494-502.

[4]趙威，曾國輝，黃勃，等.基于改進局部搜索算法的三維空間路徑規劃研究[J].電子科技，2019（06）：58-63.