遺傳算子在VRP中的應用綜述

郝友文，劉 燁

（天津工業大學 管理學院；天津 300387）

物流業與一個國家的經濟發展水平是正相關關系，經濟發展程度越高，對物流業的依賴程度也會越高。而近些年來無論是我國經濟發展的規模、速度、樣式，還是從社會物流總費用占GDP的比重在我國與發達國家之間存在巨大差距的形勢來看，提高物流業發展速度和水平都已是迫在眉睫。

運輸費用在我國物流總費用中所占的比重是最大的，而車輛路徑問題（VRP）無論是在提高顧客滿意度方面還是在縮減物流成本方面都在物流運輸中起著最為重要的作用。這也就是VRP近些年來成為管理科學、交通運輸、物流管理等學科研究的一個熱點的原因所在。

鑒于傳統的精確算法在求解VRP時，在求解效率、速度、求解規模等方面所表現出的不足，啟發式算法成為目前解決VRP時最為合適的算法。國內外學者們在解決VRP時用到的啟發式算法有遺傳算法、禁忌搜索算法等等，這些算法相較傳統精確算法在求解效率、求解速度、求解問題規模等方面，均表現出了更優越的性能，而應用最為廣泛的當屬遺傳算法。本文在國內外采用遺傳算法解決VRP的研究成果基礎上，對遺傳算法的三種算子選擇算子、交叉算子和變異算子在VRP中的不同應用情況進行了較為全面的綜述。

一、選擇算子

選擇又稱復制，就是從種群中選擇生命力強（適應度高）的個體來產生新群體的過程。選擇算子的好壞會直接影響到遺傳算法的計算結果。好的選擇算子能夠提高全局的收斂性和計算效率，避免有用遺傳信息的丟失，而不好的選擇算子就會導致遺傳進化停滯不前，產生早熟問題和喪失遺傳的多樣性。

姜大立等人在解決帶軟時間窗的物流配送中心車輛路徑問題時采用了比例選擇算子［1］（輪盤賭選擇算子），該算子是一種隨機回訪式采樣方法，旋轉輪盤賭pop-size（種群規模）次，每次旋轉選一個進入下一代種群。曹［2］在求解物流配送VRP時運用了精華模型和比例選擇相結合的選擇策略（即最佳染色體保留及輪盤賭選擇法相結合的選擇策略）。具體來說就是，將每代種群種群的pop_size個個體按照它們的適應度大小進行排序，把適應度最大的個體直接復制到下一代的種群中，剩余的pop_size-1個個體按照輪盤賭選擇的策略選擇若干進入到下一代。肖天國［3］在求解帶軟時間窗的開放式車輛路徑問題時，采用了基于排序法的輪盤賭選擇法和最佳保留策略相結合的選擇算子。基于排序的輪盤賭選擇法的中心思想就是：為了使得選擇個體時所產生的隨機數字能夠更均勻的分布在選擇區間內（此區間一般是［0，1］ ），就先把該區間劃分成大小相等的若干個子區間，之后再隨機產生該選擇數，該法有利于保持種群的多樣性。最佳保留策略有利于遺傳算法能夠依概率收斂到全局最優解。但是最佳保留策略在具體的實施過程中會有一些差異，而這些差異一般體現在：哪個或哪幾個染色體不參與交叉運算和變異運算、哪個染色體取代哪個染色體等方面，詳細情況在此不作贅述。占書芳［4］在求解帶軟時間窗車輛路徑問題時，運用了精英策略（即最佳保留策略）和隨機聯賽選擇機制的混合法來作為選擇個體的依據。隨機聯賽選擇機制的基本思想就是，每次選取聯賽規模（一般取2）個個體進行適應度值的比較，取適應度最大的一個個體來作為遺傳到下一代群體中的對象。該方法的操作過程較為簡單，只有個體適應度間的大小比較運算而無個體適應度間的算術運算。隨機聯賽選擇機制的意義還在于較優的個體就會有較大的優先權來產生自己的后代。范月林等［5］在解決帶時間窗的車輛路徑問題時，采用了基于基因庫的跨世代精英選擇算子。基本做法是：建立世代基因庫以用來存儲遺傳進化過程中適應度相對較高的精英染色體，設置好基因庫的大小（比如20）并將庫中的染色體按適應度大小排好序，每次更新基因庫時將新染色體插入庫中并剔除掉庫中適應度最小的染色體，這樣整個基因庫的平均適應度就會越來越高，在染色體的選擇過程中要把基因庫的染色體與其他普通染色體混合，用于進一步的進化。周艷聰［6］在解決物流配送路徑優化問題時，采用了小生境選擇機制與最優個體保留、輪盤賭選擇相結合的策略。該策略主要是用于擺脫以適應度為引導的選擇機制所產生的“近親繁殖”現象，用在交叉前兩個父本的選擇上，通過設置一個閥值來避免相似個體間的交配與再出現情況。經過試驗也驗證了，在該選擇策略的配合下，的確能夠提高算法的收斂速度、增強種群的多樣性以及全局尋優能力。

二、交叉算子

交叉是指以較大的概率從群體中選擇兩個個體，交換兩個個體的某個或某些基因位，從而形成兩個新個體的過程。它在遺傳算法中起著關鍵作用，是產生新個體的主要方法，也是遺傳算法區別于其他進化運算的重要特征。交叉算子的設計和實現與具體問題密切相關，主要涉及到交叉點的位置和如何交換部分基因等。交叉算子的設計一定要與編碼的設計一同考慮，而國內外學者在VRP上一般都采用了自然數編碼方式。以下便綜述了遺傳算法在VRP的應用中交叉算子的設計情況：

對于VRP，由于虛擬節點基因（配送中心）“0”的存在，普通的交叉算子很容易會產生一些不可行解。為了提高遺傳算法的收斂速度，保留好雙親的優良染色體序列，楊愛梅［7］在其論文中采用了2—交叉算子。為了不丟失優良基因，在交叉操作過程中保留一部分優良的父代個體的優良基因段，鐘石泉［8］在其論文中運用了改進的最大保留交叉算子。曹［7］運用遺傳算法解決帶時間窗的同時取送貨車輛路徑問題時設計了前置交叉算子，該交叉算子的引入能夠解決即使選取的雙親染色體序列相同的情形，進而繼續搜索問題的優化解、跳出局部最優、克服“早熟”現象。受生成最小代價樹的普萊姆算法的啟發，羅勇等［9］等人提出了基于最小代價樹的交叉算子。關麗霞［10］根據帶時間窗和同時取送貨的車輛路徑問題的特點以及啟發式交叉方法求解的角度，運用了以基于路程最優的啟發式交叉方法為主，單親遺傳作為交叉方法為輔的策略來實現交叉操作。啟發式交叉算子的應用會使交叉操作后產生不同于父代的新個體，但同時也會使較優的個體大量繁殖以致于后續參與交叉的父本的基因相似度太高甚至完全一樣，而單親遺傳操作利用一個閥值的操作便巧妙地解決了這個問題。汪秋云等［11］在求解帶軟時間窗車輛路徑問題時采用的是多點交叉算子。針對傳統交叉算子（如：部分匹配交叉（PMX）、順序交叉（OX）、循環交叉（CX）等）效率較低、適用性受限等不足之處，Oguz［12］在結合了PMX、OX和OBX等算子思想的基礎上提出了交叉算子A。謝秉磊等［13］在用遺傳算法解決有時間窗的非滿載車輛調度問題時運用了最大保留交叉。Soojung Jung［14］等人在解決帶時間窗車輛路徑問題時采用了部分匹配交叉算子。帶軟時間窗的車輛路徑問題（VRPSTW）是一類基于次序的組合優化問題，該問題模型的目標函數一般要考慮到路程和時間兩方面的因素，因此運用遺傳算法解決VRPSTW問題時所運用的交叉算子也要考慮這兩個因素。占書芳［4］在應用并行遺傳算法解決VRPSTW時采用了合并交叉方法與啟發式交叉方法的混合策略來實現交叉操作，該混合策略在其文中表現效果較好。Heung-Suk Hwang［15］在求解帶時間約束的車輛路徑問題時，對傳統的重組交叉做了改進提出了2-邊緣重組交叉算子，該交叉算子是利用一個邊緣表作為鄰接表來巡回對雙親染色體序列基因進行挑選形成子代基因序列的。對于多節點周期性的車輛路徑問題，Vidal T［16］等人為實現對整個解空間的廣度搜索和對優化解的進一步精煉提出了插入周期交叉算子（PIX），該交叉算子在進化過程各代間能夠傳遞良好的基因序列，對節點、路線、路網的組合聯系以及解決周期性路線問題方面都能發揮很好的效果。

三、變異算子

遺傳算法中的變異是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成新個體的過程。變異運算是產生新個體的輔助方法，但也是不可或缺的一個環節。它與交叉算子的配合可實現對整個解空間的局部搜索和全局搜索；它與選擇算子和交叉算子的配合可避免由選擇和交叉運算而造成的某些信息丟失，確保遺傳算法的有效性。變異算子在遺傳算法中的意義有，可改善遺傳算法的局部搜索能力、維持群體的多樣性以及防止早熟現象的產生。具體針對于遺傳算法在VRP中的應用，研究者們所采用的變異算子也有許多種類。

為保持群體內個體的多樣化以及使個體在排列順序上有較大的變化，郎茂祥［17］采用了連續多次對換的變異技術，變異操作是在變異概率Pm下進行的，只要進行變異操作，就會用隨機方式產生交換次數k，然后就對待變異操作的個體染色體序列進行k次對換（基因對換的位置也是隨機的）。楊愛梅［7］采用的是互換變異算子，該變異的操作方式是在染色體序列中隨機選擇兩個不同位置上的基因，然后將這兩個基因的位置進行相互交換。而鐘石泉等［18］雖然也采用了互換變異算子，但其又加入了判斷，即采用互換交叉操作后所得到的染色體序列，其適應度與前代染色體的作比較，若有提高則接受，反之就會放棄，如此循環下去，直到交換后產生了相對最好的染色體為止，顯然加入該判斷后會大大加快遺傳算法的收斂速度。關麗霞［10］針對帶軟時間窗和同時取送貨的車輛路徑問題（VRPSPDTW）的具體特征，嘗試采用了倒位變異（即反轉變異）的變異算子，該變異是在染色體序列上隨機選取兩點，然后將兩點間的子串反轉過來的過程。汪秋云等［11］在求解軟時間窗車輛路徑問題時采用的是多點換位法的變異操作，多點換位變異就是在變異概率發生時隨機選取兩個及以上基因，并任意交換它們的位置的操作過程。沈玲［19］運用混合遺傳算法求解帶時間窗車輛路徑優化問題時采用了k-交換變異。Gen M［20］等人在傳統的多點變異的基礎上做了改進形成了局部爬山變異，該變異的設計如下：在染色體序列中隨機產生n個基因位（非0的基因位），這n個位置的基因任意交換位置會產生中組合，然后計算這種組合對應染色體序列的適應度值，將適應度值最高的染色體留下來作為變異算子產生的結果，如此便使得變異算子具有了局部的爬山能力，該局部爬山變異算子會使種群向著更為有利的方向變異，顯然會加快算法的收斂速度。

四、結 語

綜上述，受附加條件、約束條件和現實條件的影響，VRP分為很多種類；遺傳算法自提出以來經歷了40年的發展，目前已相當成熟，遺傳算子在不同的環境下存在各種相應的設計策略和方法。不同的策略和方法決定了各遺傳算子具有不同的性能和特征。針對這兩方面的情況，如何根據每一種具體的VRP，去選擇相適應的遺傳算子現有方法，亦或是提出一種新的、相適應的遺傳算子的新方法，才是能夠快而準的尋找到VRP最優解的關鍵。也是用遺傳算法求解VRP能相較目前研究成果革命性前進一步的關鍵。

［1］ 姜大立，楊西龍，杜文.車輛路徑問題的遺傳算法研究［J］ .系統工程理論與實踐，1999，（6）：43-44.

［2］ 曹二保.物流配送車輛路徑問題模型及算法研究［D］ .長沙：湖南大學，2008，92-95.

［3］ 肖天國.帶軟時間窗的開放式車輛路徑問題研究［D］ .長沙：中南大學，2009，35-37.

［4］ 占書芳.并行遺傳算法在帶軟時間窗車輛路徑問題中的應用研究［D］ .武漢：武漢理工大學，2006，36-37.

［5］ 范月林，周素萍.基于改進遺傳算法的帶時間窗VRP問題研究［J］ .電腦知識與技術，2011，7（10）：2412-2413.

［6］ 周艷聰，孫曉晨，余偉翔.基于改進遺傳算法的物流配送路徑優化研究［J］ .計算機工程與科學，2012，34（10）：119-121.

［7］ 楊愛梅.帶軟時間窗的車輛路徑問題研究［D］ .合肥：合肥工業大學，2009，11-13.

［8］ 鐘石泉.物流配送車輛調度智能優化方法研究［D］ .天津：天津大學，2004，21-28.

［9］ 羅勇，陳治亞.基于改進遺傳算法的物流配送路徑優化［J］ .系統工程，2012，30（8）：119-120.

［10］ 關麗霞.帶軟時間窗和同時取送貨的車輛路徑問題研究［D］ .中南大學，2010.

［11］ 汪秋云，蔣文保.帶軟時間窗車輛路徑問題的求解算法研究［J］ .北京信息科技大學學報，2013，28（4）：57-62.

［12］ OGUZ，B Cheung.A Genetic Algorithm for Flow-shop Scheduling Problems with Multiprocessor Tasks［J］ .Proceed-ing of 8th Internation-al Workshop in Project Management and Scheduling，Spain，2002.

［13］ 謝秉磊，李軍，郭耀煌.有時間窗的非滿載車輛調度問題的遺傳算法［J］ .系統工程學報，2000，15（3）：291-294.

［14］ SOOJUNG JUNG.A genetic algorithm for the vehicle routing problemwith time dependent travel times［J］ .ProQuest Information and Learning，2000：66-68.

［15］ HEUNG-SUK HWANG.An improved model for vehicle routing problem with time constraint based on genetic algorithm［J］ .Computers&Ind-ustrial Engineering，2002：362-364.

［16］ VIDAL T，CRAINIC T G，GENDREAU M et al.A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems.Operations Research 2012；60（3）：611–624.

［17］ 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優化問題的研究［J］ .中國管理科學，2002，10（5）：51-54.

［18］ 鐘石泉，王雪蓮.多車場集送一體化車輛調度問題及其遺傳算法研究［J］ .西安電子科技大學學報（社會科學版），2009，19（1）：63-65.

［19］ 沈玲.基于混合遺傳算法的帶時間窗車輛路徑優化問題研究［J］ .物流工程與管理，2009，31（2）：80-81.

［20］ GEN M，CHENG R.Genetic Algorithms and Engineering Design［M］.New York：A Wiley-Interscience Publication，266-271.