1、統(tǒng)計(jì)與決策2007年8月(理論版另設(shè)交易費(fèi)用率為0.0075。本文利用Matlab 語(yǔ)言編程計(jì)算出最優(yōu)解,舉例如下:在給定VaR 的置信水平t=0.99,即k=2.33時(shí)(1期望收益率為0.15,置信水平為0.7的機(jī)會(huì)約束問(wèn)題,最優(yōu)解為0.3028,0.7190,0.1365,-0.4003,0.2346,最優(yōu)解的均值為0.1696,標(biāo)準(zhǔn)差為0.0248,VaR 為-0.1043。(2期望收益率為0.15,置信水平為0.8的機(jī)會(huì)約束問(wèn)題,最優(yōu)解為0.2946,0.7351,0.1601,-0.4556,0.2346,最優(yōu)解的均值為0.1717,標(biāo)準(zhǔn)差為0.0259,VaR 為-0.104。(3

2、期望收益率為0.20,置信水平為0.9的機(jī)會(huì)約束問(wèn)題,無(wú)最優(yōu)解。參考文獻(xiàn):1榮喜民,武丹丹,張奎廷.基于均值-VaR 的投資組合最優(yōu)化J.數(shù)理統(tǒng)計(jì)與管理,2005,25(5:96-103.2韓其恒,唐萬(wàn)生,李光泉.機(jī)會(huì)約束下的投資組合問(wèn)題J.系統(tǒng)工程學(xué)報(bào),2002,17(1:87-91.3郭丹,徐偉,雷佑銘.機(jī)會(huì)約束下的均值-VaR 組合投資問(wèn)題J.系統(tǒng)工程學(xué)報(bào),2005,20(3:256-260.4郭福華,彭大衡,吳健雄.機(jī)會(huì)約束下的均值-VaR 投資組合模型研究J.中國(guó)管理科學(xué),2004,12(1:28-34.6劉慶偉,彭大衡.投資機(jī)會(huì)與VaR 約束下的投資組合分析J.經(jīng)濟(jì)數(shù)學(xué),2002,

3、19:85-89.8歐陽(yáng)光中,李敬湖.證券組合與投資分析M.北京:高等教育出版社,1997.9郭存之,董青春.國(guó)內(nèi)證券投資組合模型研究J.北京航空航天大學(xué)學(xué)報(bào),2000,13(3,19-23.10沈忠環(huán),楊勇.含交易費(fèi)用的證券投資組合決策J.統(tǒng)計(jì)與決策,2002,4,25-25.(責(zé)任編輯/亦民摘要:車(chē)輛路徑優(yōu)化研究是一個(gè)既有理論和實(shí)踐意義又富有挑戰(zhàn)性的課題。針對(duì)該NP 難問(wèn)題,提出了一種改進(jìn)遺傳算法。該算法采用了一種新的編碼方式,使得染色體中的每一個(gè)基因能代表三層含義;采用了一種與爬山法相結(jié)合的混合進(jìn)化策略。通過(guò)性能比較可以看出,在同等計(jì)算量情況下,改進(jìn)遺傳算法的優(yōu)勢(shì)明顯。關(guān)鍵詞:改進(jìn)遺傳算

4、法;車(chē)輛路徑優(yōu)化;混合進(jìn)化;中圖分類(lèi)號(hào):O212文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1002-6487(200708-0163-03基于改進(jìn)遺傳算法的車(chē)輛路徑優(yōu)化研究孔志周1,2,官東2(1.湖南大學(xué)統(tǒng)計(jì)學(xué)院,長(zhǎng)沙410079;2.中南大學(xué)信息科學(xué)與工程學(xué)院,長(zhǎng)沙4100830引言隨著電子商務(wù)的進(jìn)一步推廣與應(yīng)用,物流的重要性對(duì)電子商務(wù)活動(dòng)的影響日益明顯。B2C 的物流支持要靠配送來(lái)提供,B2B 的物流業(yè)務(wù)會(huì)逐漸外包,其供貨方式也是配送制。沒(méi)有配送,電子商務(wù)物流就無(wú)法實(shí)現(xiàn),電子商務(wù)也就無(wú)法實(shí)現(xiàn),電子商務(wù)的命運(yùn)與配送業(yè)聯(lián)在了一起。在配送中心地址已經(jīng)確定的情況下,管理人員如何采取有效的配送策略,在滿(mǎn)足需求點(diǎn)所要

5、求需求量的前提下合理安排車(chē)輛路徑,是物流配送優(yōu)化的又一個(gè)重要方面,迫切需要對(duì)其開(kāi)展研究。車(chē)輛路徑問(wèn)題的模型及其算法復(fù)雜,曾被Savelsbergh 證明是NP 難問(wèn)題。啟發(fā)式隨機(jī)搜索方法(random heuristicsearch ,RHS 是目前關(guān)于復(fù)雜優(yōu)化問(wèn)題求解的一類(lèi)有效方法,不需要或需要很少的關(guān)于問(wèn)題的先驗(yàn)信息,該類(lèi)方法具有很強(qiáng)的魯棒性,即能適應(yīng)不同領(lǐng)域的優(yōu)化問(wèn)題求解,并在大多數(shù)情況下都能得到比較滿(mǎn)意的解。RHS 一般統(tǒng)稱(chēng)為弱方法(weak methods 。遺傳算法就是一種典型的弱方法,與其它搜索算法相比,具有獨(dú)特的算法形式和運(yùn)行機(jī)理,在復(fù)雜優(yōu)化問(wèn)題求解中有著比較顯著的優(yōu)勢(shì)。1車(chē)輛

6、路徑優(yōu)化問(wèn)題假定配送中心最多可用K 輛車(chē)對(duì)q 個(gè)貨物需求點(diǎn)進(jìn)行運(yùn)輸配送,每部車(chē)輛的載重量為b k (k=1,2,K,每個(gè)需求點(diǎn)的需求量為d i (i=1,2,q,需求點(diǎn)i 到需求點(diǎn)j 的運(yùn)距為c ij ,設(shè)nk 為第k 輛車(chē)所包含的需求點(diǎn)數(shù)(若nk=0表示未啟用第k 輛車(chē),用集合Rk 表示第k 條路徑,其中的元素rki 表示需求點(diǎn)rki 在路徑k 中的順序?yàn)閕 (不包含配送中心,令r k0=rk(n k +1=0表示配送中心,則有如下表示的車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型。基金項(xiàng)目:國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(60234030;國(guó)防科工委項(xiàng)目(A1420060159;國(guó)家統(tǒng)計(jì)局重點(diǎn)項(xiàng)目(2006B1916

7、3統(tǒng)計(jì)與決策2007年8月(理論版目標(biāo)函數(shù):min U=Kk =1!n ki =1!c rk(i-1rki+Kk =1!c rknk rk(nk+1sign(n k -1(1約束條件:n ki =1!dr kib k k=1,2,K(20n k qk=1,2,K(3Kk =1!n k=q(4R k =>r ki |r ki >1,2,q ,i=1,2,n k (5R k1R k2=!%k 1k 2(6其中:sign(n k -1=1n k1其(它(7式(2保證每條路徑上的各需求點(diǎn)的總需求量不超過(guò)此條路徑的配送車(chē)容量;式(3表明每條路徑服務(wù)的需求點(diǎn)數(shù)不超過(guò)總需求點(diǎn)數(shù);式(4要求每個(gè)需

8、求點(diǎn)都得到車(chē)輛的配送服務(wù);式(5表示每條路徑需求點(diǎn)的組成情況;式(6則限制每個(gè)需求點(diǎn)的需求僅能由一個(gè)車(chē)輛來(lái)完成。2改進(jìn)遺傳算法基本遺傳算法的相關(guān)原理可參看文獻(xiàn)1。求解車(chē)輛路徑問(wèn)題的關(guān)鍵是合理確定車(chē)輛與各需求點(diǎn)的關(guān)系,在滿(mǎn)足車(chē)輛載重量、時(shí)間和各需求點(diǎn)需求量的約束條件下使得總費(fèi)用最小。下面對(duì)基本遺傳算法進(jìn)行改進(jìn)來(lái)構(gòu)造車(chē)輛路徑問(wèn)題優(yōu)化的求解方法,具體實(shí)現(xiàn)步驟如下:2.1編碼方案染色體(或個(gè)體由1到x 的整數(shù)排列串構(gòu)成,其中x 為車(chē)輛數(shù)K 與需求點(diǎn)數(shù)q 的乘積。可以將其記為:g=(w 1,w 2,w j ,w x (8其中:w j >1,2,x ,w j1w j2%j1j2,j1,j2>1

9、,2,x 。染色體中的元素wj 可以表示三個(gè)方面的含義:對(duì)應(yīng)需求點(diǎn)的編號(hào)為:m=w j -w j -1q*q (9(其中表示取整,下同對(duì)應(yīng)的路徑編號(hào)為:w j -1q+,+1(10確定需求點(diǎn)m 是否由車(chē)輛k 配送以及確定需求點(diǎn)m在路徑k 中的順序?yàn)閖 。2.2初始種群的產(chǎn)生在滿(mǎn)足編碼方案的前提下,隨機(jī)產(chǎn)生L 個(gè)個(gè)體,構(gòu)成初始種群。將其記為:G 0=>g 0,g 1,g L (11此時(shí)代數(shù)為0。2.3可行化過(guò)程將染色體的編碼向量映射為滿(mǎn)足全部約束條件的可行解稱(chēng)為可行化。對(duì)于一般車(chē)輛路徑問(wèn)題,其過(guò)程如下:需求點(diǎn)的需求條件滿(mǎn)足的標(biāo)志變量為d zm =0(其中m=1,2,.,q ;令路徑k 中的

10、需求點(diǎn)數(shù)目n k =0;設(shè)汽車(chē)的載重量為b k ,令b k '=b k ;路徑k 所包含的需求點(diǎn)R k =!;路徑k 中除去配送中心后的第i 個(gè)位置的需求點(diǎn)號(hào)為r ki =0,即此時(shí)所有路徑皆未形成。(其中k=1,2,.,K ;i =1,2,.,q 。令j=1;m=w j -w j -1q ,q (12第j 次確定需求點(diǎn)m 和路徑k 間的關(guān)系,其中:k=w j-1q ,+1(13判斷d zm 是否等于0,若等于0,表明需求點(diǎn)m 的需求尚未滿(mǎn)足,轉(zhuǎn)繼續(xù)判斷,否則轉(zhuǎn)執(zhí)行。判斷需求點(diǎn)m 的需求量d m 是否小于或等于k 車(chē)輛所剩余的載重量b k ',若成立,令d zm =1,b k

11、'=b k -d m ,n k =n k +1,r kn k=m ,R k =R k >m ,然后轉(zhuǎn)執(zhí)行;若不成立,直接轉(zhuǎn)執(zhí)行。j=j+1,判斷j 是否等于K ×q+1,若不相等,轉(zhuǎn)重復(fù)上述過(guò)程;若相等,則表明該染色體中的K ×q 個(gè)元素已經(jīng)判斷完畢,此時(shí)檢查是否所有d zm =1成立。若成立,說(shuō)明在滿(mǎn)足各約束條件的情況下,所有的需求點(diǎn)均分配了一個(gè)路徑,構(gòu)成路徑集合RT=>R 1,R 2,R k ,即為染色體所對(duì)應(yīng)的原車(chē)輛問(wèn)題的一個(gè)可行解;若不成立,說(shuō)明此染色體表示的路徑分配方案不滿(mǎn)足約束,為原車(chē)輛路徑問(wèn)題的一個(gè)不可行解。2.4性能評(píng)價(jià)對(duì)當(dāng)前代種群中的每

12、一個(gè)染色體g t (t=1,2,.,L ,應(yīng)用上述的可行化過(guò)程,求得對(duì)應(yīng)可行解U t =K k =1!n ki =1!c rk(i-1rki+Kk =1!c rknk rk(nk+1sign(n k -1(14RT i 代入目標(biāo)函數(shù):即可求得其目標(biāo)值。若染色體對(duì)應(yīng)的為非可行解,則賦予目標(biāo)函數(shù)一個(gè)很大的整數(shù)U t =M ,將目標(biāo)值的倒數(shù)定義為對(duì)應(yīng)于染色體g t 的適應(yīng)值f t ,用其作為個(gè)體的性能評(píng)價(jià)指標(biāo),指導(dǎo)個(gè)體的進(jìn)化和競(jìng)爭(zhēng),其值越大代表該個(gè)體的性能越優(yōu),即對(duì)應(yīng)的解越接近最優(yōu)解。2.5判斷及爬山搜索判斷迭代的代數(shù)是否達(dá)到某一預(yù)定值,若是,停止進(jìn)化,選性能最好的個(gè)體進(jìn)行爬山搜索,以取得最優(yōu)結(jié)果;

13、否則,繼續(xù)執(zhí)行步驟(6。其中,爬山搜索的過(guò)程是:對(duì)個(gè)體的每一位基因,分別在1x 取值并填入該位置,為保證染色體中無(wú)相同基因,則用該基因位的原值去代替該基因新值原來(lái)所在的位置,求得其對(duì)應(yīng)的適應(yīng)值,最大適應(yīng)度的染色體所對(duì)應(yīng)的路徑集合即為車(chē)輛路徑問(wèn)題的全局最優(yōu)解(或滿(mǎn)意解。2.6自然選擇將當(dāng)前代種群的L 個(gè)染色體按適應(yīng)值f t 由大到小排列,重排后的染色體g 1的性能最優(yōu),采用式(5.6和式(5.7計(jì)算當(dāng)前代中L 個(gè)染色體的選擇概率。用輪盤(pán)賭法選擇兩個(gè)個(gè)體,然后執(zhí)行步驟(7;2.7染色體的交叉重組對(duì)于步驟(6中所選擇的兩個(gè)個(gè)體,按照交叉率p c 進(jìn)行交叉重組,交叉規(guī)則采用第四章介紹的PMX 法,其中

14、交叉點(diǎn)是隨機(jī)選取的,對(duì)交叉成功所產(chǎn)生的個(gè)體應(yīng)用步驟(3所述164方法對(duì)其進(jìn)行可行性分析,按照步驟(4對(duì)求得其對(duì)應(yīng)的適應(yīng)值,并與其父?jìng)€(gè)體進(jìn)行比較,選擇四者中性能最好的兩個(gè)個(gè)體,然后執(zhí)行步驟(8;2.8染色體的變異對(duì)步驟(7中產(chǎn)生的兩個(gè)染色體,以變異率p m對(duì)其基因進(jìn)行變異操作。對(duì)于要變異的基因,這里采用的變異策略是:首先將其值保存,然后重新分別在1取值并填入該位置,為保證染色體中無(wú)相同基因,則用所保存的值去代替該基因新值原來(lái)所在的位置,最后對(duì)所產(chǎn)生的個(gè)體應(yīng)用步驟(3所述方法對(duì)其進(jìn)行可行性分析,求得其對(duì)應(yīng)的適應(yīng)值,保留適應(yīng)度最大的個(gè)體。這種變異具有局部爬山能力,可使染色體改良到它的局部極點(diǎn)。執(zhí)行步

15、驟(9。2.9循環(huán)將當(dāng)前代已執(zhí)行遺傳操作的染色體數(shù)目加2,判斷其是否小于種群大小,若小于,則返回步驟(6循環(huán);否則,將當(dāng)前代種群的最優(yōu)個(gè)體g1復(fù)制到下一代,這樣可保證最優(yōu)者生存,然后返回步驟(5循環(huán)。3實(shí)證分析3.1車(chē)輛路徑問(wèn)題實(shí)例的描述現(xiàn)有8個(gè)貨物需求點(diǎn)和一個(gè)為這些需求點(diǎn)提供貨物的配送中心,各需求點(diǎn)對(duì)配送中心的需求量如表1所示,配送中心只有兩輛汽車(chē)用于各需求點(diǎn)的貨物配送,每輛車(chē)的載重量皆為8000千克,已知配送中心及各需求點(diǎn)的距離如表2 (其中0表示配送中心,要求合理確定車(chē)輛和各需求點(diǎn)間的關(guān)系,在滿(mǎn)足車(chē)輛載重量和各需求點(diǎn)需求的約束條件下,安排車(chē)輛的行駛路徑,使總運(yùn)行費(fèi)用最少,即總運(yùn)輸里程最小

16、。3.2車(chē)輛路徑問(wèn)題實(shí)例的結(jié)果為更好地了解采用改進(jìn)遺傳算法求解一般車(chē)輛路徑問(wèn)題的輸出結(jié)果,給出當(dāng)每代的種群大小為30,最大進(jìn)化代數(shù)為100,交叉率為0.80,變異率為0.05時(shí)。在實(shí)際的調(diào)試過(guò)程中,衡量參數(shù)設(shè)置恰當(dāng)與否,要依據(jù)多次運(yùn)行的收斂情況和解的質(zhì)量來(lái)判斷。需要指出的是,在實(shí)際運(yùn)行的輸出結(jié)果中,相鄰兩代的同序號(hào)染色體在同一行輸出。3.3性能比較為了驗(yàn)證改進(jìn)遺傳算法的有效性,在GA群體進(jìn)化的不同階段,當(dāng)前最優(yōu)解質(zhì)量提高的程度不同。在早期階段,由于群體中大量有效低階模式的存在,在交叉算子的作用下,低階模式重組為較高階模式的概率較大,當(dāng)前最優(yōu)解的質(zhì)量改善的速度較快。隨著群體多樣性的逐漸降低,群體

17、中包含的低階模式數(shù)量不斷減少,高階模式數(shù)量不斷增加,個(gè)體之間的相似性隨之提高,有效基因的重組成功概率顯著降低,從而群體中當(dāng)前最優(yōu)解改善的速度大大下降。在GA進(jìn)化的后期,個(gè)體交叉產(chǎn)生大量的品質(zhì)無(wú)改善的子個(gè)體,所以GA計(jì)算資源利用率很低。從某種程度上講,GA的宏觀探索能力大于局部求精能力。因此,根據(jù)實(shí)際問(wèn)題求解要求,將局部搜索方法與GA結(jié)合起來(lái),可以促進(jìn)GA進(jìn)化后期計(jì)算效率的提高。在以上車(chē)輛路徑優(yōu)化問(wèn)題的求解中,將GA與爬山法相結(jié)合,并為了驗(yàn)證其有效性,與與無(wú)爬山能力的遺傳算法進(jìn)行了比較。在實(shí)驗(yàn)中,群體規(guī)模n=30,群體進(jìn)化的最大代數(shù)為T(mén)= 100,染色體編碼長(zhǎng)度L=40,p c=0.75,p m

18、=0.02。其實(shí)驗(yàn)結(jié)果如圖1所示。需要說(shuō)明的是,圖1中的適應(yīng)值進(jìn)行了歸一化處理。可以看出,GA在進(jìn)化后期最佳個(gè)體的質(zhì)量改善非常緩慢。采用GA與具有局部搜索能力的爬山法相結(jié)合后,當(dāng)前最佳個(gè)體適應(yīng)值迅速提高,在同等計(jì)算量情況下,效果比較顯著。參考文獻(xiàn):1王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)M.西安:西安交通大學(xué)出版社,2002.2李軍.車(chē)輛調(diào)度問(wèn)題的分派啟發(fā)式算法J.系統(tǒng)工程理論與實(shí)踐, 1999,(1.3李志威,張旭梅.基于動(dòng)態(tài)掃描和螞蟻算法的物流配送網(wǎng)絡(luò)優(yōu)化研究J.管理工程學(xué)報(bào),2006,(4.4張得志?謝如鶴?羅榮武等.物流配送網(wǎng)絡(luò)優(yōu)化模型及其求解算法J.武漢理工大學(xué)學(xué)報(bào),2006,(4.(責(zé)任編輯/亦民需求點(diǎn)需求量1100022000310004200051000640007200082000表1需求點(diǎn)對(duì)配送中心的需求量表(千克需求點(diǎn)123456788012015018040020032016018013080200100150220200212013015020020015015