敖成敏

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

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

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

0 引言

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

1 快遞車輛路徑模型

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

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

2 算法的求解

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

2.1 混合遺傳操作

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

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

遺傳操作分為選擇、交叉、變異三個(gè)操作環(huán)節(jié)。其中，選擇操作有多種選擇方法，本文選取加權(quán)隨機(jī)（輪盤賭）配對(duì)，對(duì)染色體進(jìn)行選擇;交叉操作，交叉運(yùn)算本文采用的是等長(zhǎng)度的染色體編碼，且是小數(shù)編碼，采用單點(diǎn)交叉策略;變異操作中為保持局部隨機(jī)搜索能力和保持群體的多樣性，避免出現(xiàn)未成熟就收斂的情況，本文對(duì)染色體第一段編碼采用單點(diǎ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)個(gè)體交叉變異概率的變化對(duì)最優(yōu)解的影響，本文設(shè)定局部搜索次數(shù)為50;最優(yōu)個(gè)體交叉概率為0.5、0.6、0.7、0.8、0.9以及最優(yōu)個(gè)體變異概率為0.1、0.2、0.3、0.4、0.5兩兩組合對(duì)三類測(cè)試數(shù)據(jù)集進(jìn)行25組實(shí)驗(yàn)，每組實(shí)驗(yàn)運(yùn)行算法10次取平均值。通過(guò)對(duì)三類數(shù)據(jù)集的分析，發(fā)現(xiàn)整體上，最優(yōu)解受最優(yōu)個(gè)體變異概率的影響不顯著，隨最優(yōu)個(gè)體交叉概率的增加而減小。并且，當(dāng)最優(yōu)個(gè)體交叉概率趨近0.6，變異概率趨近0.3時(shí)，算法會(huì)取得最優(yōu)解。

4 結(jié)論

通過(guò)對(duì)物流路徑優(yōu)化問(wèn)題進(jìn)行深入的研究發(fā)現(xiàn)，本文將遺傳算法與局部搜索算法相混合，得到了一種求解車輛路徑問(wèn)題的高效算法——混合遺傳算法。最后引用實(shí)例對(duì)比分析求解結(jié)果，說(shuō)明了混合遺傳算法擁有尋找最優(yōu)解的能力，并且在運(yùn)算效率方面都能表現(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]周蓉，沈維蕾，劉明周，等.帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的混合離散粒子群優(yōu)化算法[J].中國(guó)機(jī)械工程，2016，27（04）：494-502.

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