以正向變異的遺傳算法提高求解VRP問題效率

胡中棟，謝金偉，涂燕瓊

（江西理工大學 信息工程學院，江西 贛州341000）

0 引 言

車輛路徑問題因其較難求得最優解的特點吸引了無數研究者的關注。許多研究者提出了不同的方法來求解車輛路徑問題，潘立軍等［1］使用了插入檢測法，文獻 ［2］提出了改進變鄰域搜索算法求，而文獻 ［3］則使用了多目標禁忌搜索算法來求解車輛路徑問題。目前主要的方法是仿生學算法，蟻群算法和粒子群算法［4－8］也是目前較為有效的方法。遺傳算法因其高效的搜索能力成為了解決車輛路徑問題最有效的方法之一。遺傳算法是一類借鑒生物界的進化規律演化而來的隨機化搜索方法。雖然遺傳算法能夠較有效的求解車輛路徑問題，但也存在搜索較慢等問題。特別是遺傳算法解決車輛路徑問題存在交叉操作時易破壞原來較好的基因片段［9］，從而降低收斂速度。因此，本文提出正向變異的遺傳算法來加速求解車輛路徑問題的收斂速度。

1 車輛路徑問題描述

已知車的總數量為M（m ＝1，2，…，M），每輛車的容量為w。共有N 個客戶，第i個客戶所需貨物量為pi（i＝1，2，…，N），且pi≤w。客戶的集合設為V ＝｛1，2，…，N｝。cij為i客戶點到j（j＝1，2，…，N）客戶點之間的距離

車輛路徑問題數學模型［10］如下所示

2 正向變異遺傳算法基本思想與設計

2.1 基本思想

由于遺傳算法求解車輛路徑問題時難以找到理想的編碼方式，使得交叉操作容易破壞好的基因連接［9］。針對難以保留優秀基因而導致的算法收斂速度較慢的問題，通過對算法的深入分析以及大量的實驗檢驗，提出正向變異的遺傳算法來加快算法的收斂速度。

本文提出的正向變異遺傳算法是在進行變異操作之前先將基因連接分類，一類為較差連接，一類為較優連接。正向變異的方法是破壞較差連接而保留較優連接。經正向變異后，生成新的較優連接更多。通過多次進化，優秀的染色體將越來越多，從而保證了進化的方向性。

2.2 理論基礎

定理1變異對于遺傳算法的重要性，在沒有變異的情況下，遺傳算法基本無搜索能力。

由以上理論可知，遺傳算法在開始階段快速進化，尋找最優模式，到進化后期次優解所占比例逐漸增大，易形成早熟問題。本文通過正向變異的遺傳算法，在算法早期加快進化速度 （通過增加個體適應度實現），在算法后期在保持進化速度的同時，使得種群中的個體保持一定的變化，以加速收斂速度。

2.3 算法設計

遺傳算法解決問題步驟通常包含編碼、選擇、交叉和變異。針對車輛路徑問題的具體做法如下：

（1）編碼采用客戶序號 （序號是自然數1～L，L 為客戶數）的十進制編碼方法。這種表示方法是直接產生L 個1～L間的互不重復的自然數的排列，該客戶排列就構成一個解，并對應一種配送路徑方案。設客戶排列 （染色體）為41287635，設兩輛車可以完成配送，每輛車為4個客戶配送貨物，則配送路線為第一輛車：0→4→1→2→8→0，第二輛車：0→7→6→3→5→0 （其中0表示起始點）。

（2）適應度計算方法采用某條染色體的配送方后案中要經過的客戶點 （或起始點）之間的路徑長度之和的倒數為其個體的適應值，設個體的適應值為fi＝1／z（z為車輛所需行走路程的總和）。

（4）交叉采用順序交叉法，開始選擇一個匹配區域，設兩父代個體及其匹配區域 （設第3到第5基因位，如A中的 ‘128’）為：A＝34｜128｜765、B＝52｜847｜613；將兩父代的匹配區域移動到對方的末尾得到A’＝34｜128｜765847、B’＝52｜847｜613128；去除原染色體中與A’和B ‘相同的數字得到新一代的染色體A’’＝31265847、B’’＝54763128。

當Ci＞Li時，則將i基因位處的客戶移動到染色體末端，將i基因位標記為0，然后到i＋2基因位處繼續比較。當Ci＜＝Li時不進行任何操作，直接到i＋1基因位處進行比較。重復以上操作直到染色體的最后一個客戶，最后將標記為0的地方去掉，將客戶 （基因）順序向前平移，得到新的染色體。

下面對變異的正向性進行分析：假設任一客戶到其他客戶之間的距離符合標準正態分布，單輛車來完成所有任務，f ［i］表示i基因位的客戶與i－1基因位處客戶的連接。由標準正態分布的特點可知，Pm為正態分布的路徑長度的期望，則隨機兩個客戶間的距離有50%的概率大于Pm，有50%的概率小于Pm。若以Pm來作為標準，則如果比Pm大就認定為較差連接，比Pm小則認定為較優連接。可假設新形成的連接有50%是較優的，50%是較差的。本算法雖然會少量增加單代進化需要的時間，卻能較大幅度減少收斂的代數和收斂時間。

由正向變異的方法可知若i基因位要變異則f ［i］必為較差連接。這樣就有4種情況。設圖1中標注為五角星的線為較差連接，沒有標記的為較優連接，圖1中省略未畫出的都為較優連接。

情況1 （圖1）：若染色體中有且僅有最后一個連接f ［N］為較差連接時，這時正向變異的方法無法改變染色體的連接，染色體保持不變。

圖1 染色體正向變異情況1

情況2 （圖2）：若染色體中有不止一個較差連接且f［N］為較差連接，N 基因位需要變異。此時，第N－1基因位與N 基因位之間的新連接是由之前N 基因位變異產生的，其余兩個新連接是由其它變異造成的。

圖2 染色體正向變異情況2

情況3 （圖3）：若i基因位需要變異，且f［i＋1］為較優連接，此時，將破壞一個優秀連接和一個較差連接。這時將生成兩個新連接，這兩個連接都是有一半的概率變優，所以在這種情況下，染色體的優秀連接總數不變。

圖3 染色體正向變異情況3

情況4 （圖4）：若i基因位需要變異，且f［i＋1］為較差連接，此時將破壞兩個較差連接。這時將生成兩個新連接，這兩個連接都是有一半的概率變優，所以在這種情況下，染色體的優秀連接數增加一倍。這時染色體變的更優了。

圖4 染色體正向變異情況4

設任一染色體的N 個連接中有p 個是優秀連接，q個是較差連接。較差連接中有r個連接被打破時其后是優秀連接或者沒有連接，有t個連接被打破時其后是較差連接。根據事實有N ＝p＋q，q＝r＋2t，p＜＝N，q＜＝N，r＜＝q，2t＜＝q，r＜＝p（最后一個基因位N 不需變異），r－1＜＝p（最后一個基因位N 須變異），其中p，q，r，t均大于等于0。設染色體中的優秀連接數為BEST，變異開始前BEST ＝p。

綜合以上4種情況，變異后則有

由式 （7）與t＞＝0可知，在任何情況下新增的優秀連接數為BEST－p ＞＝0，所以變異是向正向進行的。

3 仿真實驗

實驗環境：i5cpu 筆記本電腦，8 G 內存。在虛擬機（VMware）中安裝2 G 內存、單核CPU 的ubuntu12.04系統。用C語言編寫程序，數據分析與作圖在R 語言軟件平臺進行。

設vi代表客戶i，Qi表示vi對貨物的需求量，v0為起始點，則各客戶對貨物的需求量見表1。

表1 各客戶對貨物的需求量

各個客戶間的距離見表2。

表2 各個客戶間的距離

本實驗取客戶數為8，初始隨機產生數目為100 的種群，交叉長度為4，交叉概率為0.8，進化代數為200，變異概率如表3 和表4 所示，每輛車的最大載重量設為10，且車的數量不限。采用傳統遺傳算法與改進的正向變異遺傳算法求解，在成功求解的概率都為98%以上的情況下，比較成功求解所用計算的平均代數和平均所用時間。實驗的數據均為運行程序10000次的平均結果。經過計算得到最優染色體對應的最大適應度值為0.024155，其對應的染色體有多個，例如染色體A ＝8 1 6 4 7 3 5 2，染色體A 所對應的方案為最優的車輛調度方案的一種，根據車的容量及每個客戶點的需求貨物量可以推算出對應的調度方案為：第一輛車0→8→1→6→4→7→0，第二輛車：0→3→5→2→0 （其中0表示起始點）。

表3 變異概率平均成功代數比較

表4 不同變異概率運行時間

設變異概率為P。未改進成功求解所需代數為GO，預先求得最大適應度值0.024155，在預定的200代進化過程中，若第K 代的最大適應度值為0.024155，則稱成功求解所需的進化代數為K，若程序運行10000次，則有10000個不同的K 值，其平均值既為GO，又因為求解的成功率大于98%，則10000次的成功求解所需代數的平均數有較高的參考價值。改進后成功求解所需代數為GN。未改進成功求解所需時間為TO，假設進化200代所需時間為t，K 為成功求解所需的代數，且t和K 的值為10000次運算的平均結果，則成功求解平均所需的時間即為t＊（K／200）。改進后成功求解所需時間為TN。表3為不同變異概率和平均得到最優結果所用計算代數的關系，表4為變異概率與平均得到最優結果所用時間關系（為了避免統計過小數參數誤差，將運行時間擴大100倍）。由于表格寬度的限制，在表1與表2中省略了P ＝0.1，0.3，0.5，0.7，0.9時的計算結果。

用R 軟件對數據進行回歸分析，得到了回歸參數極為顯著 （三顆星）的回歸方程

由式 （8）和式 （10）可知，編碼問題所導致的交叉問題［9］使得求解的效率是與變異概率正相關的，變異的概率越大，求解的效率越高。由式 （9）、式 （11）與圖5、圖6可以看出正向變異對問題的求解有很大的提高，求解最優結果所需的代數和時間都有較大幅度的降低。

4 結束語

本文提出了正向變異的遺傳算法，該方法有效的利用了遺傳算法的變異過程。在其原有的防止搜索到局部最優解功能的基礎上進一步優化了搜索的方向性，本方法有效的提高了遺傳算法車輛路徑問題的求解效率，同時也為遺傳算法解決其它問題提供了思路。經過8客戶數不同變異概率情況下問題求解效率的分析和同條件下多點成功率的分析，可以驗證正向變異的遺傳算法在求解VRP問題時的效率有了較大幅度的提高。

圖5 平均求解成功所需代數

圖6 平均求解成功所需時間

［1］PAN Lijun，FU Zhuo.Insertion detection method for vehicle routing problem with time windows［J］.Systems Engineering－Theory ＆ Practice，2012，32 （2）：319－322 （in Chinese）.［潘立軍，符卓.求解帶時間窗車輛路徑問題的插入檢測法［J］.系統工程理論與實踐，2012，32 （2）：319－322.］

［2］WANG Renmin，BI Yingzhou，LIU Aning，et al.Improved variable neighbourhood search algorithm for DVRP ［J］.Computer Engineering and Applications，2014，50 （2）：237－241（in Chinese）.［王仁民，閉應洲，劉阿寧，等.改進變鄰域搜索算法求解動態車輛路徑問題 ［J］.計算機工程與應用，2014，50 （2）：237－241.］

［3］WANG Jun，LI Bo.Multi－objective tabu search algorithm for vehicle routing problem with fuzzy due－time［J］.Computer Integrated Manufacturing Systems，2011，17 （4）：858－866 （in Chinese）.［王君，李波.帶模糊預約時間的車輛路徑問題的多目標禁忌搜索算法 ［J］.計算機集成制造系統，2011，17（4）：858－866.］

［4］CHEN Yingxin.Study on VRP based on improved ant colony optimization ［J］.Application Research of Computers，2012，29 （6）：2031－2034 （in Chinese）.［陳迎欣.基于改進蟻群算法的車輛路徑優化問題研究 ［J］.計算機應用研究，2012，29（6）：2031－2034.］

［5］HE Xiaofeng，MA Liang.Quantum－inspired ant colony algorithm for vehicle routing problem with time windows［J］.Systems Engineering－Theory ＆ Practice，2013，33 （5）：1255－1261 （in Chinese）.［何小鋒，馬良.帶時間窗車輛路徑問題的量子蟻群算法 ［J］.系統工程理論與實踐，2013，33 （5）：1255－1261.］

［6］LIU Xia，YANG Chao.Min－max vehicle routing problem based on ant colony algorithm ［J］.Journal of PLA University of Science and Technology（Natural Science Edition），2012，13（3）：336－341 （in Chinese）.［劉霞，楊超.最小－最大車輛路徑問題的蟻群算法 ［J］.解放軍理工大學學報 （自然科學版），2012，13 （3）：336－341.］

［7］WANG Tiejun，WU Kaijun.Study on multi－depot vehicle routing problem with time windows based on particle swarm optimization ［J］.Systems Engineering Theory ＆ Practice，2012，48 （27）：27－30 （in Chinese）. ［王鐵君，鄔開俊.帶時間窗的多車場車輛路徑優化的粒子群算法 ［J］.計算機工程與應用，2012，48 （27）：27－30.］

［8］LI Ning，ZHOU Tong，SUN Debao，et al.Particle swarm optimization for vehicle routing problem with time windows［J］.Systems Engineering－Theory ＆Practice，2004，24 （4）：130－135 （in Chinese）.［李寧，鄒彤，孫德寶，等.帶時間窗車輛路徑問題的粒子群算法 ［J］.系統工程理論與實踐，2004，24 （4）：130－135.］

［9］WU Kaijun，WANG Tiejun.Vehicle routing problem algorithm based on improved differential evolution ［J］.Computer Engineering and Applications，2013，49 （13）：17－20 （in Chinese）.［鄔開俊，王鐵君.基于改進差分進化的車輛路徑優化算法 ［J］.計算機工程與應用，2013，49 （13）：17－20.］

［10］ZHANG Ruifeng，WANG Tongsan.New genetic algorithm for vehicle routing problem ［J］.Journal of Hubei University（Natural Science Edition），2012，34 （2）：239－242 （in Chinese）.［張瑞鋒，汪同三.新型遺傳算法求解車輛路徑問題研究 ［J］.湖北大學學報 （自然科學版），2012，34 （2）：239－242.］

［11］WANG Xiaobo，LI Yijun.Study on multi－type vehicles and single centre vehicle routing problem with backhauls［J］.Journal of Systems Engineering，2010，25 （5）：629－636 （in Chinese）.［王曉博，李一軍.多車型單配送中心混合裝卸車輛路徑問題研究［J］.系統工程學報，2010，25 （5）：629－636.］