基于混合遺傳算法的大規(guī)模VRP問題算法研究

冉崇善　張妍

摘要：物流配送的車輛路徑問題（VRP）是近年來物流領(lǐng)域中的研究熱點(diǎn)，該問題屬于NP難題，較難得到最優(yōu)解和滿意解。在建立了車輛路徑問題數(shù)學(xué)模型的基礎(chǔ)上，該問題被分解為兩個(gè)階段進(jìn)行研究，分別為利用基于基地啟發(fā)式分區(qū)算法進(jìn)行區(qū)域劃分和利用改進(jìn)的遺傳算法來確定具體的一條配送線路的先后次序。通過此改進(jìn)的混合遺傳算法最終得到優(yōu)化配送路徑。仿真計(jì)算結(jié)果表明，在大規(guī)模車輛路徑問題中改進(jìn)后的算法相比于傳統(tǒng)的遺傳算法最優(yōu)解的質(zhì)量得到一定提高。

關(guān)鍵詞： 物流配送；大規(guī)模；車輛路徑；分區(qū)算法； 遺傳算法

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）18-0182-03

Research on Large Scale VRP Problem Based on Hybrid Genetic Algorithm

RAN Chong-shan，ZHANG Yan

（Shaanxi University of Science & Technology， Xian 710021， China）

Abstract：The vehicle routing problem （VRP） is a research hotspot in the logistics field in recent years. The problem is a NP problem， and it is difficult to obtain the optimal solution and the satisfactory solution. On the basis of the mathematical model of vehicle routing problem， the problem is decomposed into two stages were studied， namely the use of the base heuristic partitioning algorithm for region partition and the improved genetic algorithm to determine the sequence of specific a distribution line. Through this improved hybrid genetic algorithm to optimize the distribution path. The simulation results show that the improved algorithm can improve the quality of the optimal solution compared to the traditional genetic algorithm in the large-scale vehicle routing problem.

Key words：logistics distribution； large-scale； Vehicle routing； Partitioning algorithm； logistics distribution

1 引言

隨著物流產(chǎn)業(yè)的迅猛發(fā)展、物流配送點(diǎn)大規(guī)模的增加，車輛路徑問題的解決方案成為了目前研究的一個(gè)重點(diǎn)。解決車輛路徑問題的算法很多，比較常用的有旅行商法、動(dòng)態(tài)規(guī)劃法、分區(qū)配送算法[1]、蟻群算法、粒子群算法、遺傳算法等。新改進(jìn)的混合遺傳算法是在傳統(tǒng)遺傳算法的基礎(chǔ)上采用精華模型和比例選擇相結(jié)合的選擇策略，構(gòu)造了一種用于求解大規(guī)模車輛路徑問題的混合遺傳算法。在于文獻(xiàn)[1]提出的改進(jìn)遺傳算法進(jìn)行對比后，可知此改進(jìn)遺傳算法具有較強(qiáng)的全局搜索能力和較快的收斂速度。

2 物流配送車輛路徑優(yōu)化問題的數(shù)學(xué)模型

物流配送車輛路徑優(yōu)化問題的數(shù)學(xué)模型可以描述為：從配送中心用多輛汽車向多個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的位置和需求量一定，每輛汽車的載重量一定，要求合理安排汽車行駛路線，使總運(yùn)距最短，并滿足以下條件：

1）每條配送路徑上各需求點(diǎn)的需求量之和不超過汽車載重量；

2）每條配送路徑的長度不超過汽車一次配送的最大行駛距離；

3）每個(gè)需求點(diǎn)的需求必須滿足，且只能由一輛汽車送貨。

設(shè)配送中心擁有K臺(tái)容量為q的車輛，i個(gè)客戶的需求量為g，且gi≤q，i=1，2，…，i，將配送中心編號(hào)為0，配送中心和客戶用i（i=0，1，...，i）表示，且有

Bramel和Simchi-Levi提出了基于基地啟發(fā)式分區(qū)算法[2]，本文借助其算法思想，將它分解成一個(gè)分派問題（Pl）和一個(gè)單車線路優(yōu)化問題（P2）。

P1：

且滿足如下約束條件：

Pl中，zk表示車輛k所能服務(wù)的客戶集合，滿即足yki=1的客戶集合，f（zk）表示在zk中滿足約束條件的客戶最優(yōu)旅行線路的長度，由p2確定。

且滿足如下約束條件：

前兩個(gè)等式描述了兩個(gè)變量之間的關(guān)系，對于客戶i，只有兩個(gè)客戶與i相連；第三個(gè)等式消除了子回環(huán)，表示沒有任何子回路解產(chǎn)生。

3 算法原理及改進(jìn)

3.1算法原理

針對大規(guī)模車輛問題，本文首先用基于基地啟發(fā)式分區(qū)算法進(jìn)行區(qū)域劃分，求解P1模型，然后運(yùn)用最近鄰算法計(jì)算各區(qū)域內(nèi)的配送車輛的行駛路徑的初始解，最后運(yùn)用混合遺傳算法對初始解進(jìn)行優(yōu)化，求解P2模型。

在實(shí)際的配送中，一般優(yōu)先考慮離配送中心最遠(yuǎn)的點(diǎn)。我們利用地理信息系統(tǒng)和電子地圖，可以確定在配送區(qū)域內(nèi)任意兩個(gè)網(wǎng)點(diǎn)之間的最短距離，且可以確定任一網(wǎng)點(diǎn)的左右兩個(gè)關(guān)鍵節(jié)點(diǎn)，具體的求解思路是：

（1） 用改進(jìn)的基地啟發(fā)式算法每次都優(yōu)先考慮離配送中心和己確定的基地集合最遠(yuǎn)的點(diǎn)[3]。基地，綜合考慮客戶的需求及車輛容量，從基地開始運(yùn)用廣度優(yōu)先遍歷算法，依次尋找最近的關(guān)鍵節(jié)點(diǎn)，由關(guān)鍵節(jié)點(diǎn)形成關(guān)鍵群；

（2） 關(guān)鍵群為中心擴(kuò)展并形成配送線路，當(dāng)達(dá)到預(yù)定的工作量時(shí)停止擴(kuò)展；

（3） 未在線路上的網(wǎng)點(diǎn)進(jìn)行聚類，直到所有的網(wǎng)點(diǎn)都在線路上。

基地啟發(fā)式分區(qū)算法流程圖如圖1所示。

一個(gè)區(qū)域內(nèi)單車線路優(yōu)化算法的基本思路為：①利用最近鄰算法確定初始可行解，并生成一個(gè)初始路徑集合；②運(yùn)用遺傳算法優(yōu)化初始可行解，再對由遺傳算法確定的個(gè)體實(shí)施多次鄰域操作。

3.2算法改進(jìn)

3.2.1選擇算子改進(jìn)

本文采用精華模型和比例選擇相結(jié)合的選擇策略[4-5]，該策略保證最優(yōu)個(gè)體生存到下一代，適應(yīng)度較大的個(gè)體以較大概率進(jìn)入下一代。其基本思路是對每代種群中的k個(gè)染色體按適應(yīng)值函數(shù)值進(jìn)行排序，其中適應(yīng)值函數(shù)值最大的染色體復(fù)制并直接進(jìn)入下一代，其余的k-1個(gè)染色體由輪盤賭選擇法或比例選擇法確定。

3.2.2交叉算子改進(jìn)

本文設(shè)計(jì)了一種新的前置交叉算子。現(xiàn)用9個(gè)頂點(diǎn)為例來說明其原理，圖2所示。設(shè)p1={1 2 3 | 4 5 6 | 7 | 8 9}，p2={4 5 2 | 1 8 7 6 | 9 3}，其中“|”表示交叉點(diǎn)。子個(gè)體確定的方法為取p2中的兩個(gè)交叉點(diǎn)中間的點(diǎn)放在子代C1的開始處，得C1={1 8 7 6 X X X X X}，對C中未確定位置的X，在p1中找到暫時(shí)沒有在C1中出現(xiàn)的離6最近的點(diǎn)3，將3放在6的后面，從左到右將p1中未出現(xiàn)的點(diǎn)移到C1中，最后C1為{1 8 7 6 3 4 5 9 2}。交叉點(diǎn)位置為：C1=2、C2=7。

給定兩個(gè)相同的染色體，經(jīng)過新的交叉算子仍可以產(chǎn)生不同于父體的新個(gè)體，如p1=p2={4 5 2 | 1 8 7 6 | 9 3}，則經(jīng)過新的前置交叉算子后兩個(gè)子代為{1 8 7 6 3 4 5 2 9}，不同于其父代染色體。這說明由于前置交叉算子的引入，即使個(gè)體都相同，仍能夠進(jìn)行迭代進(jìn)化，跳出局部最優(yōu)解，從而繼續(xù)尋找問題的最優(yōu)解，克服了早熟收斂的缺點(diǎn)。

4實(shí)驗(yàn)結(jié)果

為了驗(yàn)證混合算法的有效性，通過選用TSPLIB中的Oliver30和att48作為仿真算例，以驗(yàn)證本文提出的算法性能，并與基本遺傳算法求解Oliver30和att48TSP進(jìn)行比較。

基本遺傳算法采用文獻(xiàn)[6]中的程序和參數(shù)，GA的參數(shù)為：染色體N=30，Pc=0.2，Pm=0.5，迭代次數(shù)為100。對算法預(yù)測20次，，結(jié)果如表1、表2所示。

從表1及表 2可以看出，采用本文提出的混合算法求解Oliver30和att48，其最優(yōu)解的質(zhì)量均有明顯的提高。

5 結(jié)論

考慮第三方物流企業(yè)擁有完成配送服務(wù)的所有車輛的情形，即在車場封閉條件下研究大規(guī)模的車輛路徑問題，從理論上進(jìn)行深入的研究，構(gòu)造求解此問題的混合遺傳算法，分兩階段對問題進(jìn)行了求解，第一階段先采用基于基地啟發(fā)式分區(qū)算法，將零售網(wǎng)點(diǎn)進(jìn)行區(qū)域劃分，第二階段利用優(yōu)化算法，主要是最近鄰算法，遺傳算法，和鄰域搜索算法，來確定具體的一條配送線路的先后次序，并通過選用TSPLIB中的Oliver30和att48作為仿真算例，以驗(yàn)證本文提出的算法性能。實(shí)驗(yàn)結(jié)果表明，本文提出的混合遺傳算法在求解大規(guī)模車輛路徑問題中求解效果相對較好。

參考文獻(xiàn)：

[1] 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué)，2012，10（5）：52-56.

[2] Bramel J，Simehi-Levi D.A location based heuristicb for general routing Problems.Operation Research，1995，（43）： 649-660.

[3] 陶波，朱玉琴.改進(jìn)的動(dòng)態(tài)規(guī)劃法在車輛最短路徑問題中的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)，2011，23（1）：24-27.

[4] 李妍峰，李軍，高自友.大規(guī)模鄰域搜索算法求解時(shí)變車輛調(diào)度問題[J].管理科學(xué)學(xué)報(bào)，2012，15（1）：22-32.

[5] 代桂平，王 勇，侯亞榮.基于遺傳算法的TSP問題求解算法及其系統(tǒng)[J].微計(jì)算機(jī)信息，2010，26（1）：15-19.

[6] 羅上遠(yuǎn)，徐天亮，陳代芬.零售業(yè)庫存分布模型及分區(qū)配送算法研究[J].物流技術(shù)，2000（5）：22-25.