動(dòng)態(tài)自適應(yīng)混合智能算法在VRP問題中的應(yīng)用

1、物流技術(shù)2010年 第3期物流工程與管理第 32 卷 總第 189 期LOGISTICS ENGINEERING AND MANAGEMENT doi:10.3969/j.issn.1674-4993.2010.03.024動(dòng)態(tài)自適應(yīng)混合智能算法在VRP問題中的應(yīng)用張磊，鮑福光，彭 揚(yáng)(浙江工商大學(xué)，浙江杭州310018 )【摘 要】貨物配置和車輛路徑安排是個(gè)典型的NP難題。文中在建立 VRP問題數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求解該問題的混合智能算法。在如何確定車輛數(shù)的問題上提岀一種新的算法思路一一動(dòng)態(tài)自適應(yīng)確定車輛數(shù)；同時(shí)文 中提岀了一種新的編碼思維，將車輛信息引入染色體中；在遺傳算法終止后，利用

2、模擬退火對(duì)每一輛車的路線分別 進(jìn)行優(yōu)化。最后，對(duì)具體案例進(jìn)行仿真實(shí)驗(yàn)，證明了文中算法是有效的。【關(guān)鍵詞】VRP問題；新式編碼；動(dòng)態(tài)自適應(yīng)；混合智能算法【中圖分類號(hào)】TP35【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】 1674-4993 (2010) 03-0058-03Application of Dynamic Self-Adaptive mixed intellige ZHANG Lei, BAO Fu-guang, PENG Yang(Zhejiang Gongshang University, Hangzhou 310018, China )【Abstract 】Cargo configuratio

3、n and vehicle routing arrangement is a NP. This issue of theestablishment of VRP based on the mathematical model is constructed for solving the problem of hybridintelligent algorithm. In the issue of how to determine the number of vehicles, we put forward a newalgorithm - Dynamic Adaptive determine

4、the number of vehicles; simultaneously, this paper presents a newcoding ideas, the vehicle information pull into the chromosome; in the end of genetic algorithm, usingsimulated annealing line for each car separately optimized. Finally, the simulation of specific cases proves that this algorithm is e

5、ffective.【Key words】 VRP; New coding; Dynamic Adaptive; Hybrid intelligent algorithm© 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/'/ki.iidt© 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/&

6、#39;/ki.iidt1引言隨著物流技術(shù)和應(yīng)用的發(fā)展，物流配送過程中的車輛路徑優(yōu)化問題（Vehicle Routing Problem VRP）成為一個(gè)研究的熱點(diǎn)。它是一個(gè) NP難題，不能得到解析解，通常只能通 過各種啟發(fā)式算法得到近似解。啟發(fā)式算法求解該問題就成為人們研究的一個(gè)重要方向，并出現(xiàn)了多種啟發(fā)式算法，如Clarke和Wright提出的節(jié)約法1，Gillett和Miller提出的掃描法等，雖然這些算法 為求解配送路徑優(yōu)化問題提供了有效的方法，但也存在一定 的問題，如節(jié)約法雖然具有運(yùn)算速度快的優(yōu)點(diǎn)，但也有組合 點(diǎn)零亂、邊緣點(diǎn)難以組合的問題，掃描法為非漸進(jìn)優(yōu)化等。遺傳算法是

7、J.Holland 教授模擬達(dá)爾文生物進(jìn)化論的自然選 擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型2，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，目前已廣泛應(yīng)用于各 種優(yōu)化或控制領(lǐng)域。本文將采用混合智能算法去解決VRP問題：遺傳算法先從整體方面出發(fā)，安排總體路徑；最后經(jīng)過模擬退火進(jìn) 一步優(yōu)化每一輛車的路徑。在引入遺傳算法時(shí)的難點(diǎn)有：?jiǎn)栴}是一個(gè)動(dòng)態(tài)的問題，當(dāng)各個(gè)需求點(diǎn)變化時(shí)，需要的車輛數(shù)就在時(shí)時(shí)變動(dòng)， 如何確定車輛數(shù)。如何將車輛數(shù)加入到編碼之中，從而在 編碼中體現(xiàn)更多的實(shí)際有效信息。如何進(jìn)行有效的交叉， 適合新式編碼。2假設(shè)與數(shù)學(xué)模型假定配送中心最多可以用 m輛車對(duì)n個(gè)商店進(jìn)行運(yùn)輸配 送，每個(gè)車輛載重

8、為 6 （i =1，2，3， m），每個(gè)商店的 需求量為di （i =1，2，n），商店商店j的運(yùn)輸成本 為cj，商店i至應(yīng)送中心的成本為 c0或c0i （ i, j = 1， 2，n），車輛的載重能力可以滿足任意一個(gè)商店的要求。 忽略體積因素，在滿足各商店配送需求且不超載的情況下， 如何安排每輛車的行駛路徑，使總的運(yùn)輸成本最低。弓I入如 下變量：Vik為0-1變量，值為1時(shí)，表示第k輛車訪問需求點(diǎn)i， 值為 0 時(shí)，表示其他情況（i = 1,2,., n; k =1,2,., m）；Rk為0-1變量，值為1時(shí)，表示第k輛車經(jīng)過點(diǎn)i直接© 1 94-201 I China Acade

9、mic Journal Electronic Publijihing House. All rights reserved, http:/'/ki.iidt© 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/'/ki.iidt【收稿日期】2010-02-20【作者簡(jiǎn)介】 張磊（1988-），男，寧波人，浙江工商大學(xué)信息學(xué)院物流管理專業(yè)，本科生，研究方向：供應(yīng)鏈物流系統(tǒng)工程。彭 揚(yáng)（1972-，男，六安人，浙江工商

10、大學(xué)信息學(xué)院，博士，副教授，研究方向：供應(yīng)鏈物流系統(tǒng)工程商務(wù)智能。© 1 94-201 I China Academic Journal Electronic Publijihing House. All rights reserved, http:/'/ki.iidt59張 磊等：動(dòng)態(tài)自適應(yīng)混合智能算法在VRP問題中的應(yīng)用19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal Ek

11、ctronic Publishing Huuse. Al rights reserved, ki net到點(diǎn)j , 值為 0 時(shí)，表示其他情況(i, j =1,2,.,n;k = 1,2,.,m)；建立數(shù)學(xué)模型:m n nm i n刀刀刀C ij R j kk = 1 j = 0 i = 0J = 1, V i = 1,2. .ff(2)£尺啪= I朮=12 “(3)JUw送兒* =工£ =r；1Vu=l,2h.,ff,Vk* = L.2.(4)Yjji J,=1,2,.(5)t'/J,j' = 0,L2-.JF(0)陷丘12./訛=1»2”.阿(

12、了)P *= ,2,.jj;Jt= 1,2,.,ffl(g)G,(9)£ > Dj = I.2k>0.k =1 J,(10)m >0.n>0(11)其中，式 （1）表示目標(biāo)函數(shù)整個(gè)配送過程中運(yùn)輸成本的最 小化；式 （2）表示某個(gè)需求點(diǎn)有且僅有一輛車訪問；式 各運(yùn)輸車輛均從配送中心岀發(fā)，經(jīng)過需求點(diǎn)后，最后要回到 配送中心；式 （4）表示每個(gè)需求點(diǎn)都有一輛車經(jīng)過；式 車輛的裝載量大于其所訪問的需求點(diǎn)的需求量，即不岀現(xiàn)超 載情況發(fā)生；式（6）表示點(diǎn)到j(luò)點(diǎn)的運(yùn)輸費(fèi)用與j點(diǎn)到i點(diǎn)的 運(yùn)輸費(fèi)用相等；式（7）（8）（9）（1和）（11）均為變量的取值范圍。3 VRP問題的混

13、合智能算法的構(gòu)造Step1 :動(dòng)態(tài)自適應(yīng)確定車輛數(shù)假設(shè)有n個(gè)配送點(diǎn)，各個(gè)配送點(diǎn)i （ i =1， 2，n） 的配送量為di （ i =1，2,，n），車限重為b。n常規(guī)車輛數(shù)的算法為：車輛數(shù)=Hdi/b。這是非科學(xué)的計(jì)算方法，也是不符合實(shí)際的，因?yàn)樨浳锊豢煞指?，得出?車輛數(shù)可能因?yàn)檫^小而無(wú)法得到可行解。本文米用一種新思維 動(dòng)態(tài)自適應(yīng)車輛數(shù)確定法。具 體實(shí)現(xiàn)是將所有的客戶點(diǎn)隨機(jī)排序，從頭依次將各客戶點(diǎn)的 貨物量逐步累加，在超過車輛滿載量之前為一車，直至所有 的貨物裝完為止，累加并記錄該條染色體的車輛數(shù)。通過一 個(gè)大種群的染色體算岀其中記錄的最少車輛數(shù)作為本模型所 要的車輛數(shù)。此方法避免了貨物被

14、迫分割現(xiàn)象的發(fā)生，同時(shí) 也避免了同批貨物分次到達(dá)同一個(gè)目的地的情形。Step2 :新的編碼方式本文采用自然數(shù)編碼方法，構(gòu)造配送路線優(yōu)化問題的解 向量的染色體結(jié)構(gòu)。但如何將車輛數(shù)體現(xiàn)在編碼中并且能發(fā) 揮應(yīng)有的效果則是當(dāng)前最大的難題。本文將采取一種新的編碼思維方式，假設(shè)問題是1個(gè)配送中心、n個(gè)配送點(diǎn)的分配選擇與路徑優(yōu)化問題，本文自然 數(shù)編碼的染色體長(zhǎng)度將不再是常規(guī)思維下的1+n，而是n+m-1（車輛數(shù)由step1中算出），多出白m-2個(gè)點(diǎn)，稱之為“虛擬配送中心” ，m-1個(gè)配送中心分散在染色體中間將染色 體分割成m段，每一段則為每輛車的路徑。本文稱這種新型 的編碼思維方式為：“分割染色體法”。這種

15、編碼的創(chuàng)新為我 們整個(gè)算法的實(shí)現(xiàn)奠定了基礎(chǔ)，同時(shí)可以與下面的交叉建立 一個(gè)良好的銜接。Step3 :初始化群體隨機(jī)產(chǎn)生N條染色體組成初始群體，并淘汰不符合約束的 染色體，對(duì)每一條染色體，分別計(jì)算它們的函數(shù)適應(yīng)度值，并 按適應(yīng)度值排序。由于約束條件的限制，隨機(jī)產(chǎn)生的染色體將 會(huì)有很大一部分不符合條件，所以一般將初始群體取為3N。Step4 :適應(yīng)度的計(jì)算對(duì)于某個(gè)個(gè)體所對(duì)應(yīng)的配送路徑方案，要判定其優(yōu)劣，一是要看其是否滿足配送的約束條件；二是要計(jì)算其目標(biāo)函 數(shù)值（即各條配送路徑的長(zhǎng)度之和）。本文根據(jù)配送路徑優(yōu)化 問題的特點(diǎn)所確定的編碼方法，能夠知道每輛車所行走的路 線，對(duì)各條路徑逐一進(jìn)行判斷，看其是

16、否滿足約束條件（是 否超載），若不滿足，則將該條路徑定為不可行路徑，目標(biāo)函 數(shù)值加一個(gè)絕對(duì)大的懲罰數(shù)。（3）St表示：選擇選擇采用輪盤賭3的方法進(jìn)行，選擇得到的個(gè)體進(jìn)入下一步交表示變異。在每代種群中，以一定的交叉概率對(duì)個(gè)體 進(jìn)行交叉重組，在此交叉概率中采用自適應(yīng)概率。這樣，可 以有效加強(qiáng)優(yōu)秀個(gè)體的遺傳能力，保護(hù)其進(jìn)入下一代；對(duì)于 適應(yīng)度低于平均值的個(gè)體，采用較大的交叉概率，增大弱勢(shì) 個(gè)體的淘汰率。但是同時(shí)，又保證了在進(jìn)化初期優(yōu)秀個(gè)體不 會(huì)占有完全的主導(dǎo)地位，降低了局部最優(yōu)解的岀現(xiàn)概率。Step6 :有效交叉標(biāo)準(zhǔn)遺傳算法的交叉只是簡(jiǎn)單的隨機(jī)交換。結(jié)合VRP問題的實(shí)際情況以及新式編碼，本文采用能與

17、新式編碼良好結(jié) 合的劉海交叉，交叉的過程也是一種擇優(yōu)的過程，即交叉 的同時(shí)，也在擇優(yōu)。應(yīng)用這種交叉法的優(yōu)點(diǎn)在于：能跳出局部最優(yōu)解，繼續(xù)尋找問題的全局最優(yōu)解；收斂速度非常快，具有較強(qiáng)的全局搜索能力。能夠保證得到的子代染色體一定是可行的且比 其父代染色體更加優(yōu)異，交叉本身就是一次擇優(yōu)。Step7 :引入模擬退火實(shí)現(xiàn)每一輛車的自優(yōu)化U 別一!整味 両工昭”L ：處送供圖1算法整體流程圖在遺傳算法結(jié)束時(shí)，利用模擬退火實(shí)現(xiàn)解的更優(yōu)，因?yàn)?0物流工程與管理32卷染色體被分割后的每一段并不可能在遺傳算法下都實(shí)現(xiàn)最優(yōu)，而通過模擬退火可以實(shí)現(xiàn)局部（也就是每一小段染色體） 都能得到最優(yōu)路徑（每一輛車各自走的都是最

18、優(yōu)），從而在不 改變每輛車的貨物分配選擇條件下，只改變了路徑順序，從 而實(shí)現(xiàn)整體解的進(jìn)一步優(yōu)化。4實(shí)例驗(yàn)證本文根據(jù)上述混合智能算法編制了 MATLAB程序，并 對(duì)文獻(xiàn)5列岀的一個(gè)某配送中心對(duì) 13個(gè)需求點(diǎn)進(jìn)行送貨的物流配送路徑優(yōu)化問題實(shí)例進(jìn)行了實(shí)驗(yàn)計(jì)算，文獻(xiàn)中采用節(jié) 約矩陣法得到解決方案5，得到的總行程是 176。汽車的載重量為200t。可以根據(jù)載重量和各點(diǎn)需求量，采用本文中的動(dòng)態(tài)自適應(yīng)車輛數(shù)確定法算岀，車輛數(shù)等于4輛圖2十次運(yùn)行結(jié)果比較圖算法，提出一種新的算法思路 動(dòng)態(tài)自適應(yīng)車輛數(shù)確定法， 使本文的模型更符合實(shí)際情況；同時(shí)本文提岀了一種新的編 碼思維方式，將車輛信息引入染色體中，進(jìn)行分割染色

19、體處 理，同時(shí)應(yīng)用與此編碼結(jié)合度較好的擇優(yōu)交叉方式，對(duì)解決 類似的組合優(yōu)化問題具有一定的參考價(jià)值。 本文在建立VRP問題的數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求 解該問題的遺傳算法與模擬退火結(jié)合的混合智能算法。實(shí)驗(yàn) 計(jì)算結(jié)果表明，此混合智能算法是一種性能優(yōu)良的啟發(fā)式搜 索方法，利用該方法可以方便有效地求得物流配送路徑優(yōu)化 問題的最優(yōu)解或滿意解。 文本的模型與算法能很好的應(yīng)用于有多家代理店的同 城速遞業(yè)務(wù)和具有多家連鎖店的大型企業(yè)的配送業(yè)務(wù)的貨物 配置與路徑優(yōu)化安排。參考文獻(xiàn)1陳曉偉，張悟移，耿繼武.節(jié)約法在配送路線選擇中的應(yīng)用J.昆明理工大學(xué)學(xué)報(bào)（理工版）,2003,（04）:140-1432陳國(guó)良，王煦

20、法，莊鎮(zhèn)泉，王東生.遺傳算法及其應(yīng)用M.19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net表1十次運(yùn)行結(jié)果比較表次數(shù)12345678910平均遺傳算法160178170165168164168167166161166.7混合智能算法159163160159162161161161160159160.1

21、19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net在表1中可以發(fā)現(xiàn)，運(yùn)用單獨(dú)遺傳算法10次運(yùn)行的平均值為166.7 ，而運(yùn)用混合智能算法10次運(yùn)行的平均值為 160.1 ，而且，幾乎每一次都有所改進(jìn)。其中1、4、，第6、10次不大于170屬于最優(yōu)值符合條件自動(dòng)停止。其中第1、4、10次的結(jié)果得到了最優(yōu)值 159，對(duì)比采用節(jié)約矩陣 法5得到的總行程176，有了較大的改進(jìn)。5結(jié)論VRP問題中，在如何確定車輛數(shù)的問題上，摒棄傳統(tǒng)北京：人民郵電出版社， 1996.3王小明.遺傳算

22、法一一理論、應(yīng)用與軟件實(shí)現(xiàn)M西安： 西安交通大學(xué)出版社， 2002:25-26.4劉海，郝志峰，林智勇.改進(jìn)遺傳交叉算子求解TSP問題J.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版）,2002,（12）:71-73.5美森尼爾，喬普瑞彼杯,梅因德爾著，李麗萍譯供應(yīng)連 管理-戰(zhàn)略、規(guī)劃與運(yùn)營(yíng)M.北京:社會(huì)科學(xué)文獻(xiàn)岀版社 2003,11.19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al rights reserved, ki net19Q4k2011 China Academic Jtsumal Ekctronic Publishing Huuse. Al right