郝友文,劉 燁
(天津工業(yè)大學(xué) 管理學(xué)院;天津 300387)
物流業(yè)與一個(gè)國(guó)家的經(jīng)濟(jì)發(fā)展水平是正相關(guān)關(guān)系,經(jīng)濟(jì)發(fā)展程度越高,對(duì)物流業(yè)的依賴程度也會(huì)越高。而近些年來無論是我國(guó)經(jīng)濟(jì)發(fā)展的規(guī)模、速度、樣式,還是從社會(huì)物流總費(fèi)用占GDP的比重在我國(guó)與發(fā)達(dá)國(guó)家之間存在巨大差距的形勢(shì)來看,提高物流業(yè)發(fā)展速度和水平都已是迫在眉睫。
運(yùn)輸費(fèi)用在我國(guó)物流總費(fèi)用中所占的比重是最大的,而車輛路徑問題(VRP)無論是在提高顧客滿意度方面還是在縮減物流成本方面都在物流運(yùn)輸中起著最為重要的作用。這也就是VRP近些年來成為管理科學(xué)、交通運(yùn)輸、物流管理等學(xué)科研究的一個(gè)熱點(diǎn)的原因所在。
鑒于傳統(tǒng)的精確算法在求解VRP時(shí),在求解效率、速度、求解規(guī)模等方面所表現(xiàn)出的不足,啟發(fā)式算法成為目前解決VRP時(shí)最為合適的算法。國(guó)內(nèi)外學(xué)者們?cè)诮鉀QVRP時(shí)用到的啟發(fā)式算法有遺傳算法、禁忌搜索算法等等,這些算法相較傳統(tǒng)精確算法在求解效率、求解速度、求解問題規(guī)模等方面,均表現(xiàn)出了更優(yōu)越的性能,而應(yīng)用最為廣泛的當(dāng)屬遺傳算法。本文在國(guó)內(nèi)外采用遺傳算法解決VRP的研究成果基礎(chǔ)上,對(duì)遺傳算法的三種算子選擇算子、交叉算子和變異算子在VRP中的不同應(yīng)用情況進(jìn)行了較為全面的綜述。
選擇又稱復(fù)制,就是從種群中選擇生命力強(qiáng)(適應(yīng)度高)的個(gè)體來產(chǎn)生新群體的過程。選擇算子的好壞會(huì)直接影響到遺傳算法的計(jì)算結(jié)果。好的選擇算子能夠提高全局的收斂性和計(jì)算效率,避免有用遺傳信息的丟失,而不好的選擇算子就會(huì)導(dǎo)致遺傳進(jìn)化停滯不前,產(chǎn)生早熟問題和喪失遺傳的多樣性。
姜大立等人在解決帶軟時(shí)間窗的物流配送中心車輛路徑問題時(shí)采用了比例選擇算子[1](輪盤賭選擇算子),該算子是一種隨機(jī)回訪式采樣方法,旋轉(zhuǎn)輪盤賭pop-size(種群規(guī)模)次,每次旋轉(zhuǎn)選一個(gè)進(jìn)入下一代種群。曹[2]在求解物流配送VRP時(shí)運(yùn)用了精華模型和比例選擇相結(jié)合的選擇策略(即最佳染色體保留及輪盤賭選擇法相結(jié)合的選擇策略)。具體來說就是,將每代種群種群的pop_size個(gè)個(gè)體按照它們的適應(yīng)度大小進(jìn)行排序,把適應(yīng)度最大的個(gè)體直接復(fù)制到下一代的種群中,剩余的pop_size-1個(gè)個(gè)體按照輪盤賭選擇的策略選擇若干進(jìn)入到下一代。肖天國(guó)[3]在求解帶軟時(shí)間窗的開放式車輛路徑問題時(shí),采用了基于排序法的輪盤賭選擇法和最佳保留策略相結(jié)合的選擇算子。基于排序的輪盤賭選擇法的中心思想就是:為了使得選擇個(gè)體時(shí)所產(chǎn)生的隨機(jī)數(shù)字能夠更均勻的分布在選擇區(qū)間內(nèi)(此區(qū)間一般是[0,1] ),就先把該區(qū)間劃分成大小相等的若干個(gè)子區(qū)間,之后再隨機(jī)產(chǎn)生該選擇數(shù),該法有利于保持種群的多樣性。最佳保留策略有利于遺傳算法能夠依概率收斂到全局最優(yōu)解。但是最佳保留策略在具體的實(shí)施過程中會(huì)有一些差異,而這些差異一般體現(xiàn)在:哪個(gè)或哪幾個(gè)染色體不參與交叉運(yùn)算和變異運(yùn)算、哪個(gè)染色體取代哪個(gè)染色體等方面,詳細(xì)情況在此不作贅述。占書芳[4]在求解帶軟時(shí)間窗車輛路徑問題時(shí),運(yùn)用了精英策略(即最佳保留策略)和隨機(jī)聯(lián)賽選擇機(jī)制的混合法來作為選擇個(gè)體的依據(jù)。隨機(jī)聯(lián)賽選擇機(jī)制的基本思想就是,每次選取聯(lián)賽規(guī)模(一般取2)個(gè)個(gè)體進(jìn)行適應(yīng)度值的比較,取適應(yīng)度最大的一個(gè)個(gè)體來作為遺傳到下一代群體中的對(duì)象。該方法的操作過程較為簡(jiǎn)單,只有個(gè)體適應(yīng)度間的大小比較運(yùn)算而無個(gè)體適應(yīng)度間的算術(shù)運(yùn)算。隨機(jī)聯(lián)賽選擇機(jī)制的意義還在于較優(yōu)的個(gè)體就會(huì)有較大的優(yōu)先權(quán)來產(chǎn)生自己的后代。范月林等[5]在解決帶時(shí)間窗的車輛路徑問題時(shí),采用了基于基因庫(kù)的跨世代精英選擇算子?;咀龇ㄊ牵航⑹来驇?kù)以用來存儲(chǔ)遺傳進(jìn)化過程中適應(yīng)度相對(duì)較高的精英染色體,設(shè)置好基因庫(kù)的大小(比如20)并將庫(kù)中的染色體按適應(yīng)度大小排好序,每次更新基因庫(kù)時(shí)將新染色體插入庫(kù)中并剔除掉庫(kù)中適應(yīng)度最小的染色體,這樣整個(gè)基因庫(kù)的平均適應(yīng)度就會(huì)越來越高,在染色體的選擇過程中要把基因庫(kù)的染色體與其他普通染色體混合,用于進(jìn)一步的進(jìn)化。周艷聰[6]在解決物流配送路徑優(yōu)化問題時(shí),采用了小生境選擇機(jī)制與最優(yōu)個(gè)體保留、輪盤賭選擇相結(jié)合的策略。該策略主要是用于擺脫以適應(yīng)度為引導(dǎo)的選擇機(jī)制所產(chǎn)生的“近親繁殖”現(xiàn)象,用在交叉前兩個(gè)父本的選擇上,通過設(shè)置一個(gè)閥值來避免相似個(gè)體間的交配與再出現(xiàn)情況。經(jīng)過試驗(yàn)也驗(yàn)證了,在該選擇策略的配合下,的確能夠提高算法的收斂速度、增強(qiáng)種群的多樣性以及全局尋優(yōu)能力。
交叉是指以較大的概率從群體中選擇兩個(gè)個(gè)體,交換兩個(gè)個(gè)體的某個(gè)或某些基因位,從而形成兩個(gè)新個(gè)體的過程。它在遺傳算法中起著關(guān)鍵作用,是產(chǎn)生新個(gè)體的主要方法,也是遺傳算法區(qū)別于其他進(jìn)化運(yùn)算的重要特征。交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與具體問題密切相關(guān),主要涉及到交叉點(diǎn)的位置和如何交換部分基因等。交叉算子的設(shè)計(jì)一定要與編碼的設(shè)計(jì)一同考慮,而國(guó)內(nèi)外學(xué)者在VRP上一般都采用了自然數(shù)編碼方式。以下便綜述了遺傳算法在VRP的應(yīng)用中交叉算子的設(shè)計(jì)情況:
對(duì)于VRP,由于虛擬節(jié)點(diǎn)基因(配送中心)“0”的存在,普通的交叉算子很容易會(huì)產(chǎn)生一些不可行解。為了提高遺傳算法的收斂速度,保留好雙親的優(yōu)良染色體序列,楊愛梅[7]在其論文中采用了2—交叉算子。為了不丟失優(yōu)良基因,在交叉操作過程中保留一部分優(yōu)良的父代個(gè)體的優(yōu)良基因段,鐘石泉[8]在其論文中運(yùn)用了改進(jìn)的最大保留交叉算子。曹[7]運(yùn)用遺傳算法解決帶時(shí)間窗的同時(shí)取送貨車輛路徑問題時(shí)設(shè)計(jì)了前置交叉算子,該交叉算子的引入能夠解決即使選取的雙親染色體序列相同的情形,進(jìn)而繼續(xù)搜索問題的優(yōu)化解、跳出局部最優(yōu)、克服“早熟”現(xiàn)象。受生成最小代價(jià)樹的普萊姆算法的啟發(fā),羅勇等[9]等人提出了基于最小代價(jià)樹的交叉算子。關(guān)麗霞[10]根據(jù)帶時(shí)間窗和同時(shí)取送貨的車輛路徑問題的特點(diǎn)以及啟發(fā)式交叉方法求解的角度,運(yùn)用了以基于路程最優(yōu)的啟發(fā)式交叉方法為主,單親遺傳作為交叉方法為輔的策略來實(shí)現(xiàn)交叉操作。啟發(fā)式交叉算子的應(yīng)用會(huì)使交叉操作后產(chǎn)生不同于父代的新個(gè)體,但同時(shí)也會(huì)使較優(yōu)的個(gè)體大量繁殖以致于后續(xù)參與交叉的父本的基因相似度太高甚至完全一樣,而單親遺傳操作利用一個(gè)閥值的操作便巧妙地解決了這個(gè)問題。汪秋云等[11]在求解帶軟時(shí)間窗車輛路徑問題時(shí)采用的是多點(diǎn)交叉算子。針對(duì)傳統(tǒng)交叉算子(如:部分匹配交叉(PMX)、順序交叉(OX)、循環(huán)交叉(CX)等)效率較低、適用性受限等不足之處,Oguz[12]在結(jié)合了PMX、OX和OBX等算子思想的基礎(chǔ)上提出了交叉算子A。謝秉磊等[13]在用遺傳算法解決有時(shí)間窗的非滿載車輛調(diào)度問題時(shí)運(yùn)用了最大保留交叉。Soojung Jung[14]等人在解決帶時(shí)間窗車輛路徑問題時(shí)采用了部分匹配交叉算子。帶軟時(shí)間窗的車輛路徑問題(VRPSTW)是一類基于次序的組合優(yōu)化問題,該問題模型的目標(biāo)函數(shù)一般要考慮到路程和時(shí)間兩方面的因素,因此運(yùn)用遺傳算法解決VRPSTW問題時(shí)所運(yùn)用的交叉算子也要考慮這兩個(gè)因素。占書芳[4]在應(yīng)用并行遺傳算法解決VRPSTW時(shí)采用了合并交叉方法與啟發(fā)式交叉方法的混合策略來實(shí)現(xiàn)交叉操作,該混合策略在其文中表現(xiàn)效果較好。Heung-Suk Hwang[15]在求解帶時(shí)間約束的車輛路徑問題時(shí),對(duì)傳統(tǒng)的重組交叉做了改進(jìn)提出了2-邊緣重組交叉算子,該交叉算子是利用一個(gè)邊緣表作為鄰接表來巡回對(duì)雙親染色體序列基因進(jìn)行挑選形成子代基因序列的。對(duì)于多節(jié)點(diǎn)周期性的車輛路徑問題,Vidal T[16]等人為實(shí)現(xiàn)對(duì)整個(gè)解空間的廣度搜索和對(duì)優(yōu)化解的進(jìn)一步精煉提出了插入周期交叉算子(PIX),該交叉算子在進(jìn)化過程各代間能夠傳遞良好的基因序列,對(duì)節(jié)點(diǎn)、路線、路網(wǎng)的組合聯(lián)系以及解決周期性路線問題方面都能發(fā)揮很好的效果。
遺傳算法中的變異是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換,從而形成新個(gè)體的過程。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法,但也是不可或缺的一個(gè)環(huán)節(jié)。它與交叉算子的配合可實(shí)現(xiàn)對(duì)整個(gè)解空間的局部搜索和全局搜索;它與選擇算子和交叉算子的配合可避免由選擇和交叉運(yùn)算而造成的某些信息丟失,確保遺傳算法的有效性。變異算子在遺傳算法中的意義有,可改善遺傳算法的局部搜索能力、維持群體的多樣性以及防止早熟現(xiàn)象的產(chǎn)生。具體針對(duì)于遺傳算法在VRP中的應(yīng)用,研究者們所采用的變異算子也有許多種類。
為保持群體內(nèi)個(gè)體的多樣化以及使個(gè)體在排列順序上有較大的變化,郎茂祥[17]采用了連續(xù)多次對(duì)換的變異技術(shù),變異操作是在變異概率Pm下進(jìn)行的,只要進(jìn)行變異操作,就會(huì)用隨機(jī)方式產(chǎn)生交換次數(shù)k,然后就對(duì)待變異操作的個(gè)體染色體序列進(jìn)行k次對(duì)換(基因?qū)Q的位置也是隨機(jī)的)。楊愛梅[7]采用的是互換變異算子,該變異的操作方式是在染色體序列中隨機(jī)選擇兩個(gè)不同位置上的基因,然后將這兩個(gè)基因的位置進(jìn)行相互交換。而鐘石泉等[18]雖然也采用了互換變異算子,但其又加入了判斷,即采用互換交叉操作后所得到的染色體序列,其適應(yīng)度與前代染色體的作比較,若有提高則接受,反之就會(huì)放棄,如此循環(huán)下去,直到交換后產(chǎn)生了相對(duì)最好的染色體為止,顯然加入該判斷后會(huì)大大加快遺傳算法的收斂速度。關(guān)麗霞[10]針對(duì)帶軟時(shí)間窗和同時(shí)取送貨的車輛路徑問題(VRPSPDTW)的具體特征,嘗試采用了倒位變異(即反轉(zhuǎn)變異)的變異算子,該變異是在染色體序列上隨機(jī)選取兩點(diǎn),然后將兩點(diǎn)間的子串反轉(zhuǎn)過來的過程。汪秋云等[11]在求解軟時(shí)間窗車輛路徑問題時(shí)采用的是多點(diǎn)換位法的變異操作,多點(diǎn)換位變異就是在變異概率發(fā)生時(shí)隨機(jī)選取兩個(gè)及以上基因,并任意交換它們的位置的操作過程。沈玲[19]運(yùn)用混合遺傳算法求解帶時(shí)間窗車輛路徑優(yōu)化問題時(shí)采用了k-交換變異。Gen M[20]等人在傳統(tǒng)的多點(diǎn)變異的基礎(chǔ)上做了改進(jìn)形成了局部爬山變異,該變異的設(shè)計(jì)如下:在染色體序列中隨機(jī)產(chǎn)生n個(gè)基因位(非0的基因位),這n個(gè)位置的基因任意交換位置會(huì)產(chǎn)生中組合,然后計(jì)算這種組合對(duì)應(yīng)染色體序列的適應(yīng)度值,將適應(yīng)度值最高的染色體留下來作為變異算子產(chǎn)生的結(jié)果,如此便使得變異算子具有了局部的爬山能力,該局部爬山變異算子會(huì)使種群向著更為有利的方向變異,顯然會(huì)加快算法的收斂速度。
綜上述,受附加條件、約束條件和現(xiàn)實(shí)條件的影響,VRP分為很多種類;遺傳算法自提出以來經(jīng)歷了40年的發(fā)展,目前已相當(dāng)成熟,遺傳算子在不同的環(huán)境下存在各種相應(yīng)的設(shè)計(jì)策略和方法。不同的策略和方法決定了各遺傳算子具有不同的性能和特征。針對(duì)這兩方面的情況,如何根據(jù)每一種具體的VRP,去選擇相適應(yīng)的遺傳算子現(xiàn)有方法,亦或是提出一種新的、相適應(yīng)的遺傳算子的新方法,才是能夠快而準(zhǔn)的尋找到VRP最優(yōu)解的關(guān)鍵。也是用遺傳算法求解VRP能相較目前研究成果革命性前進(jìn)一步的關(guān)鍵。
[1] 姜大立,楊西龍,杜文.車輛路徑問題的遺傳算法研究[J] .系統(tǒng)工程理論與實(shí)踐,1999,(6):43-44.
[2] 曹二保.物流配送車輛路徑問題模型及算法研究[D] .長(zhǎng)沙:湖南大學(xué),2008,92-95.
[3] 肖天國(guó).帶軟時(shí)間窗的開放式車輛路徑問題研究[D] .長(zhǎng)沙:中南大學(xué),2009,35-37.
[4] 占書芳.并行遺傳算法在帶軟時(shí)間窗車輛路徑問題中的應(yīng)用研究[D] .武漢:武漢理工大學(xué),2006,36-37.
[5] 范月林,周素萍.基于改進(jìn)遺傳算法的帶時(shí)間窗VRP問題研究[J] .電腦知識(shí)與技術(shù),2011,7(10):2412-2413.
[6] 周艷聰,孫曉晨,余偉翔.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化研究[J] .計(jì)算機(jī)工程與科學(xué),2012,34(10):119-121.
[7] 楊愛梅.帶軟時(shí)間窗的車輛路徑問題研究[D] .合肥:合肥工業(yè)大學(xué),2009,11-13.
[8] 鐘石泉.物流配送車輛調(diào)度智能優(yōu)化方法研究[D] .天津:天津大學(xué),2004,21-28.
[9] 羅勇,陳治亞.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化[J] .系統(tǒng)工程,2012,30(8):119-120.
[10] 關(guān)麗霞.帶軟時(shí)間窗和同時(shí)取送貨的車輛路徑問題研究[D] .中南大學(xué),2010.
[11] 汪秋云,蔣文保.帶軟時(shí)間窗車輛路徑問題的求解算法研究[J] .北京信息科技大學(xué)學(xué)報(bào),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] 謝秉磊,李軍,郭耀煌.有時(shí)間窗的非滿載車輛調(diào)度問題的遺傳算法[J] .系統(tǒng)工程學(xué)報(bào),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] 郎茂祥,胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J] .中國(guó)管理科學(xué),2002,10(5):51-54.
[18] 鐘石泉,王雪蓮.多車場(chǎng)集送一體化車輛調(diào)度問題及其遺傳算法研究[J] .西安電子科技大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版),2009,19(1):63-65.
[19] 沈玲.基于混合遺傳算法的帶時(shí)間窗車輛路徑優(yōu)化問題研究[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.
東南大學(xué)學(xué)報(bào)(哲學(xué)社會(huì)科學(xué)版)2015年2期