基于捕食搜索策略混合遺傳算法的車輛路徑問題研究

林 濤，武孟賢，軒倩倩，徐慶國，江 沖

(1 河北工業(yè)大學 控制科學與工程學院,天津 300130;2 河北工業(yè)大學 計算機科學與軟件學院,天津 300401)

基于捕食搜索策略混合遺傳算法的車輛路徑問題研究

林 濤1,2，武孟賢1,*，軒倩倩1，徐慶國1，江 沖1

(1 河北工業(yè)大學 控制科學與工程學院,天津 300130;2 河北工業(yè)大學 計算機科學與軟件學院,天津 300401)

在分析研究車輛路徑問題的基礎(chǔ)上，將其轉(zhuǎn)換為經(jīng)典TSP優(yōu)化問題進行求解并建立數(shù)學模型,針對遺傳算法在求解車輛路徑問題時搜索效率低，容易陷入局部最優(yōu)的缺點，提出了一種改進的遺傳算法.改進算法引用自適應(yīng)鄰域法進行種群初始化；基于捕食搜索策略動態(tài)自適應(yīng)調(diào)整遺傳參數(shù)，在加快尋優(yōu)速度的同時防止陷入局部最優(yōu)；交叉前后的種群分別實施精英個體保留策略，交叉變異之后引進進化逆轉(zhuǎn)操作，繼承父代較優(yōu)和較多的信息.實驗結(jié)果表明：改進遺傳算法搜索效率高、計算結(jié)果較為穩(wěn)定；求解車輛路徑最優(yōu)問題較其它算法具有較好的性能.

車輛路徑問題；遺傳算法；自適應(yīng)鄰域法；捕食搜索算法

作為物流運輸配送系統(tǒng)的核心問題，車輛路徑問題(VRP)主要研究車輛從配送中心到各客戶點配送最后返回配送中心的滿足約束條件的最優(yōu)車輛使用方案以及最優(yōu)車輛路線方案[1].該問題是一個典型的NP-hard(NP難)問題，自提出以來一直受到眾多專家和學者的關(guān)注，在理論研究和現(xiàn)實應(yīng)用上均取得了豐碩的研究成果.神經(jīng)網(wǎng)絡(luò)、模擬退火、遺傳算法、蟻群算法、粒子群算法等智能算法都已實現(xiàn)了對該NP難題的求解[2].

近年來，隨著我國電子商務(wù)行業(yè)的高速發(fā)展，使得物流配送業(yè)務(wù)大量增加，企業(yè)的配送車輛數(shù)目迅猛增多.不合理的配送路線不僅增加了企業(yè)的配送成本,同時還影響了城市的交通和環(huán)境[3].求解最優(yōu)路徑時許多算法的搜索效率和解的質(zhì)量不高，所以許多學者為了使算法同時兼顧時間和效率的要求，繼續(xù)對啟發(fā)式智能算法進行了優(yōu)化改進[4].文獻[5]將貪婪算法引入到遺傳算法來初始化種群，采用基于貪婪算法的啟發(fā)式交叉算子來求解旅行商問題；文獻[6]將偵察特性引用到蟻群優(yōu)化算法來提高算法的有效性和適用性.文獻[7]基于K-means算法提出了一種新的初始種群策略來改善遺傳算法求解組合優(yōu)化問題.

為了更好地實現(xiàn)對VRP問題的求解，本文將其轉(zhuǎn)換為經(jīng)典TSP優(yōu)化問題進行求解并建立數(shù)學模型.由于遺傳算法是求解TSP優(yōu)化問題的強大搜索方法，本文基于該數(shù)學模型對遺傳算法進行改進來提高算法的尋優(yōu)性能.

1 VRP問題描述及模型

一般的車輛路徑問題可以描述為：配送中心和客戶點用i,j表示；車輛用k表示，最多擁有m輛；配送中心編號為0，客戶點集合N0=1,2,3,…,n}；其中客戶需求量為gi(i=1,2,3,…,n)，車輛的載重量為qk(k=1,2,3,…,m)，配送車輛最后都返回配送中心；求滿足需求的最小成本的車輛路徑R=(c0,c1,c2,…,cn).

為了得到合理的車輛使用和路線方案，本文對所需要的車輛數(shù)目進行預估，按照下面的公式(1)來確定車輛數(shù)m：

(1)

其中,?」表示括號內(nèi)數(shù)字的向下取整；qmin表示最小載重量車輛的載重量；0<α<1，它是卸車復雜程度和約束多少估計的參數(shù).可以根據(jù)實際情況調(diào)整α的大小.

對VRP問題建立數(shù)學模型如下.

定義決策變量：

目標函數(shù)：

(2)

約束條件:

(3)

(4)

(5)

(6)

(7)

(8)

上述模型中，cij可以是從客戶點i到j(luò)的距離、費用、時間等；K表示所有車輛的集合，N0表示所有客戶的集合.式(3)約束使用車輛數(shù)小于車輛總數(shù)；式(4)約束車輛行駛路線都是環(huán)線；式(5)約束每條服務(wù)路線上的需求總量小于車輛載重；式(6)約束所有客戶點都能被配送；式(7)和式(8)約束一個客戶點僅被一輛車配送.

2 改進的遺傳算法

遺傳算法是一種求解組合優(yōu)化問題的強大搜索方法，它是根據(jù)適應(yīng)度值按照“優(yōu)勝劣汰”的自然規(guī)則來逐代全局遍歷的尋優(yōu)方法[8].標準遺傳算法包括種群初始化，計算種群中個體適應(yīng)度，選擇操作，交叉操作，變異操作，終止條件判斷等基本操作.標準遺傳算法的搜索效率和優(yōu)化精度不高，且容易陷入局部最優(yōu)，所以遺傳算法需要不斷改進來滿足時間和效率的同時，使得尋優(yōu)結(jié)果更接近最優(yōu).

2.1 基于自適應(yīng)鄰域法生成初始種群

初始種群常常影響遺傳算法解的質(zhì)量和算法的效率；復雜組合優(yōu)化問題使用隨機方法生成的初始種群，搜索空間大、時間長，且容易出現(xiàn)早熟收斂.為了克服這些問題，本文引用一種初始化種群策略來改善遺傳算法，采用自適應(yīng)鄰域法生成遺傳算法的初始種群.自適應(yīng)鄰域法是從一個點出發(fā)，隨機選取比其最近點稍遠的鄰域范圍內(nèi)的點作為下一點并作為當前點，繼續(xù)搜索添加未加入的點，直至遍歷完所有的點，由此得到初步優(yōu)化的個體.實驗結(jié)果得出，自適應(yīng)鄰域算法生成的初始種群即不失隨機性，又提高了初始種群的質(zhì)量，可以改善算法的收斂速度.

2.2 基于捕食搜索策略的自適應(yīng)參數(shù)

標準遺傳算法采用固定的交叉概率Pc和變異概率Pm，限制了算法的搜索性能.許多專家學者研究自適應(yīng)的遺傳概率Pc和Pm，可以在種群進化過程中自動調(diào)整遺傳概率的大小.交叉算子和變異算子分別決定算法的全局和局部搜索能力，因此Pc和Pm的選擇關(guān)系到遺傳算法的搜索效率和群體多樣性.

為了合理的選擇Pc和Pm，本文引入平衡全局搜索能力和局部尋優(yōu)能力的捕食搜索策略[9]，運用捕食搜索策略改進遺傳算法，形成自適應(yīng)的遺傳算法.根據(jù)種群進化代數(shù)和適應(yīng)度值的變化，動態(tài)自適應(yīng)調(diào)整Pc和Pm的值.進化過程類似于動物的捕食過程，先進行全局搜索，即選擇較大Pc的和較小的Pm，一旦發(fā)現(xiàn)較好的解，則改為集中的局部搜尋，即選擇較小Pc的和較大的Pm，希望得到更好的解來提高群體的多樣性.如果最優(yōu)解得不到改善，則放棄局部搜索繼續(xù)進行全局搜索.Pc1和Pm1隨著進化代數(shù)動態(tài)改變：

其中：i代表進化代數(shù)；總進化代數(shù)為M.

實際應(yīng)用中，結(jié)合進化代數(shù)、適應(yīng)度值的變化來動態(tài)調(diào)整參數(shù)Pc和Pm.全局最優(yōu)的適應(yīng)度值為gbest，局部最優(yōu)(當代最優(yōu))的適應(yīng)度值為fbest，根據(jù)兩者的比值g=fbest/gbest來調(diào)整遺傳參數(shù)，其中Pc2和Pm2為實際問題設(shè)定的遺傳參數(shù)，k的取值根據(jù)實際情況選定，k的取值越小局部搜索的次數(shù)越多.

2.3 精英策略

采用精英策略和輪盤賭選擇法來進行選擇操作，選擇適應(yīng)度值最高的個體復制到交叉配對的父代群體中.當父代執(zhí)行完交叉變異算子之后，使用精英策略，用父代中的精英個體替換子代中適應(yīng)度最低的個體，使得父代的好的個體不至于隨著進化操作而丟失.

2.4 進化逆轉(zhuǎn)操作

交叉算子在進化過程中可以保持種群的多樣性，但是它不利于子代繼承父代較多的信息，特別是進化后期交叉操作對父代較優(yōu)基因的破壞較大，使得父代的一些優(yōu)良基因難以被繼承.本文對發(fā)生交叉、變異操作之后的個體使用進化逆轉(zhuǎn)操作，可以繼承父代較多的信息，使得搜索最優(yōu)解的能力變強.“進化”指逆轉(zhuǎn)操作后可以提高適應(yīng)度值的個體才接受逆轉(zhuǎn).

逆轉(zhuǎn)操作如下：隨機的選擇染色體中的兩個位置a和b，對選中位置之間基因?qū)嵤┠孓D(zhuǎn)，如a=3,b=7

5 2 |3 8 9 6 7 |4 1

逆轉(zhuǎn)后為：

5 2 |7 6 9 8 3 |4 1

2.5 改進遺傳算法求解VRP問題

基于上述改進分析，本文設(shè)計的改進遺傳算法求解VRP問題步驟如下.

Step 1：確定編碼方式，基于自適應(yīng)鄰域算法生成初始種群.求解VRP問題通常采用客戶點序列編碼方式生成染色體，并設(shè)置算法運行的參數(shù).

Step 2：計算種群中個體的適應(yīng)度值.較大的適應(yīng)度值代表較優(yōu)的路徑，適應(yīng)函數(shù)一般選用Fitness(i)=D/f(Ri).常數(shù)D保證適應(yīng)度值不會太小.

Step 4：終止條件.判斷進化代數(shù)是否達到最大代數(shù)，達到則停止迭代，得到的最優(yōu)個體被認為是最優(yōu)路徑；否則進化代數(shù)加1，轉(zhuǎn)Step 2循環(huán)操作.

Step 5：最優(yōu)個體(染色體)分割得到最優(yōu)車輛使用方案和最優(yōu)路線方案.

3 實驗分析

根據(jù)上述改進遺傳算法求解車輛路徑問題的步驟，設(shè)計算法的基本流程如圖1所示.

圖1 改進遺傳算法流程圖Fig.1 Improved genetic algorithm flow chart

3.1 實驗結(jié)果分析

為了驗證改進算法的性能，采用Matlab對其進行仿真實驗.根據(jù)某物流公司實際業(yè)務(wù)情況其擁有一個配送中心，配送車輛的載重量相同，隨機抽取該公司的一次配送訂單數(shù)據(jù)，該訂單共擁有13個客戶點，為方便計算將各客戶點實際地理位置按照一定比例縮小到xy坐標系下.配送中心與客戶點的位置坐標如表1所示，客戶點0即配送中心.本實例中使用相同載重量車輛，車輛載重量為10t；改進算法參數(shù)設(shè)置為：初始種群大小為100，最大迭代次數(shù)為200， K=1.5Pc max=0.95Pc min=0.4Pm max=0.1Pm min=0.01.

表1 配送中心與客戶點坐標

預估使用4輛配送車輛，通過使用本文方法運行10次，得到14個坐標點TSP問題的最優(yōu)解為：12→6→11→5→4→3→2→13→1→0→9→8→10→7→12，總距離：29.3405.根據(jù)車輛載重解碼可以得到4條最優(yōu)配送路線：

路徑1：0→9→8→10→11→4→0

路徑2：0→7→12→6→0

路徑3：0→5→3→13→0

路徑4：0→2→1→0

實驗計算結(jié)果如表2所示.

表2 實驗結(jié)果

從表2中實驗結(jié)果可以看出，本文方法計算效率高，結(jié)果較為穩(wěn)定，能夠較好的解決其它算法搜索效率低的問題.

3.2 改進算法性能分析

采用標準遺傳算法(GA)、自適應(yīng)遺傳算法(AGA)、蟻群算法(ACA)、混合粒子群算法(HPSO)對本文示例進行仿真，迭代200次得到的結(jié)果如表3所示.

表3 各種算法計算結(jié)果

各算法程序仿真的優(yōu)化過程與改進遺傳算法的仿真過程比較如圖2～5所示.

圖2 標準遺傳算法與本文改進算法的迭代曲線Fig.2 The iterative curve of standard GA and improved GA

圖3 自適應(yīng)遺傳算法與本文改進算法的迭代曲線Fig.3 The iterative curve of adaptive GA and improved GA

圖4 蟻群算法與本文改進算法的迭代曲線Fig.4 The iterative curve of ACA and improved GA

圖5 混合粒子群與本文改進算法的迭代曲線Fig.5 The iterative curve of HPSO and improved GA

由表3可見，本文所改進算法求解配送VRP問題時在最優(yōu)距離、迭代次數(shù)、時間上優(yōu)于其它算法.遺傳算法、蟻群算法、混合粒子群算法雖然可以在短時間內(nèi)找到較優(yōu)路線，但是容易陷入局部最優(yōu).通過圖2～5比較還發(fā)現(xiàn)，本文的改進遺傳算法能夠加快進化初期的尋優(yōu)速度，減少迭代次數(shù)，可以在更短的時間內(nèi)找到最優(yōu)解，而且計算結(jié)果較為穩(wěn)定.

由于本實驗所用數(shù)據(jù)為某公司產(chǎn)生的實際數(shù)據(jù)，而且是隨機抽取的結(jié)果，所以對該類實際問題具有一定的普遍應(yīng)用性.

4 結(jié)語

車輛路徑問題是一個難以求出其精確解的經(jīng)典NP難題，本文設(shè)計了一種改進的遺傳算法來對其進行求解.利用自適應(yīng)鄰域法的局部尋優(yōu)能力來改善算法的初始種群，加快尋優(yōu)速度；基于捕食搜索策略對遺傳概率進行動態(tài)自適應(yīng)調(diào)整，平衡算法的全局搜索能力和局部搜索能力.為了保持種群的多樣性，交叉前后分別實施輪盤賭策略選擇和精英策略保留，交叉變異操作之后實施進化逆轉(zhuǎn)操作.實驗結(jié)果表明，新算法的對問題的尋優(yōu)質(zhì)量和效率均優(yōu)于其它幾種智能優(yōu)化算法.后續(xù)對VRP問題的研究將會考慮更多的約束條件，同時加大種群規(guī)模來驗證算法的有效性.

[1] Kim G, Ong Y S, Heng C K, et al. City vehicle routing problem : a review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015(16):1-13.

[2] 羅 勇,陳治亞.基于改進遺傳算法的物流配送路徑優(yōu)化[J].系統(tǒng)工程,2012(08):118-122.

[3] 邵麗麗.蟻群優(yōu)化自適應(yīng)遺傳算法物流車輛調(diào)度實現(xiàn)[J].計算機測量與控制,2012(05):1423-1425+1441.

[4] 張小琴.聯(lián)合貝葉斯推理與遺傳算法的主題信息搜索策略[J].中南民族大學學報(自然科學版), 2014(02):89-92.

[5] 于瑩瑩,陳 燕,李桃迎. 改進的遺傳算法求解旅行商問題[J]. 控制與決策,2014(08):1483-1488.

[6] Gan R, Guo Q, Chang H, et al. Improved ant colony optimization algorithm for the traveling salesman problems[J]. Journal of Systems Engineering and Electronics, 2010, 21(2): 329-333..

[7] Deng Y, Liu Y, Zhou D. An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP[J]. Mathematical Problems in Engineering, 2015(03):1-6.

[8] Contrerasbolton C, Parada V. Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem.[J]. Plos One, 2015, 10(9).

[9] 王萍萍,陳進東,潘 豐.采用捕食搜索策略的遺傳算法改進[J].東南大學學報(自然科學版),2010(S1):223-227.

Hybrid Genetic Algorithm Based on Predatory Search Strategy for Vehicle Routing Problem

Lin Tao1,2, Wu Mengxian1, Xuan Qianqian1, Xu Qingguo1, Jiang Chong1

(1 Institute of Control Science and Engineering, Hebei University of Technology, Tianjin 300130,China;2 Institute of Computer Science and Software, Hebei University of Technology, Tianjin 300401,China)

On the basis of the analysis of the vehicle routing problem, it is transformed into the classical TSP optimization problem to solve and build a mathematical model. Standard genetic algorithm in solving the vehicle routing problem (VRP) is not efficient since it is easy to fall local optimum. To improve the efficiency of genetic algorithm, this paper presents an improved genetic algorithm. The proposed algorithm introduces the adaptive neighborhood method into population initialization. In order to improve the optimization speed and prevent the local optimum, the improved algorithm dynamic adaptive adjustment of genetic parameters based on predatory search strategy. Elite individual retention strategy is introduced to genetic operation and evolutionary reversal operation is used after crossover and mutation operation to propagate the better and more gene structure. The experimental results show that the improved genetic algorithm has high search efficiency and stable calculation results, and it has better performance than other algorithms in case of solving the vehicle routing problem.

vehicle routing problem; genetic algorithm; adaptive neighborhood method ; predatory search algorithm

2016-06-10 *通訊作者 武孟賢，研究方向：計算機網(wǎng)絡(luò)控制、人工智能，E-mail:724996875@qq.com

林 濤(1970-)，男，教授，博士,研究方向：計算機網(wǎng)絡(luò)控制理論、網(wǎng)絡(luò)管理與安全、嵌入式系統(tǒng)及網(wǎng)絡(luò)控制,E-mail: lintao@scse.hebut.edu.cn

天津市科技支撐項目( 14ZCDZGX00818)

TP399

A

1672-4321(2016)04-0106-05