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

敖成敏

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

關(guān)鍵詞：混合遺傳算法;配送分區(qū);局部搜索算法;快遞物流配送

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

0 引言

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

1 快遞車輛路徑模型

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

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

2 算法的求解

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

2.1 混合遺傳操作

混合遺傳操作包括局部搜索操作和遺傳操作兩個環(huán)節(jié)。

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

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

3 算例分析

3.1 算法有效性

圖3.1給出了最優(yōu)解隨遺傳算法迭代次數(shù)的變化圖。由圖3.1可知，當(dāng)?shù)螖?shù)達(dá)到500代左右，達(dá)到最優(yōu)解收斂狀態(tài)。

3.2 算法敏感性

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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