資源描述：
《并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第47卷第2期大連理工大學(xué)學(xué)報(bào)VOl.47,NO.22OO7年3月JOurnalOfDalianUniversityOfTechnOlOgyMar.2OO7=================================================================文章編號(hào):1OOO-86O8(2OO7DO2-O211-O4并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用于濱1,2,楊忠振2,程春田1(1.大連理工大學(xué)土木水利學(xué)院,遼寧大連116O24;2.大連海事大學(xué)交通規(guī)劃研究所,遼寧大連116O26D摘要:針對實(shí)用有效的
2、公交線網(wǎng)優(yōu)化模型很少的現(xiàn)狀,提出了一個(gè)以直達(dá)客流密度最大為目標(biāo)的公交線網(wǎng)優(yōu)化模型.該模型以換乘次數(shù)最少~單位長度運(yùn)送客流量最大為優(yōu)化目標(biāo),線路長度~非直線系數(shù)等作為約束條件.為求解該模型,并綜合考慮優(yōu)化質(zhì)量和通信開銷,采用了基于粗粒度模型的并行蟻群算法.數(shù)值實(shí)驗(yàn)驗(yàn)證了模型及算法的合理有效.關(guān)鍵詞:公交線網(wǎng)優(yōu)化;直達(dá)客流密度;蟻群算法;粗粒度中圖分類號(hào):U491.1文獻(xiàn)標(biāo)識(shí)碼:AO引言展到解決不均衡的TSP~@AP和job-shop調(diào)度問題中.為了克服在Ant-@中可能出現(xiàn)的停滯現(xiàn)城市公交線網(wǎng)設(shè)置得是否合理直接影響居民象,SttZl
3、e等[5]提出了max-min蟻群算法,稱做出行所需的時(shí)間~換乘次數(shù)以及系統(tǒng)運(yùn)行成本.MMAS.它對基本螞蟻算法(ASD進(jìn)行了3點(diǎn)改因此,國內(nèi)外許多學(xué)者對公交線網(wǎng)的優(yōu)化作了大進(jìn):D為了更加充分地進(jìn)行尋優(yōu),各路徑信息素量的研究.例如Ceder等[1]將三階段法(出行分初值設(shè)為最大值Z一次循環(huán)后只有修改最max,@配~規(guī)劃路徑和發(fā)車間隔D引入到公交線網(wǎng)設(shè)計(jì)短路徑的螞蟻才進(jìn)行信息素增加,@為了避免算中;~asselstro"[2]提出了一個(gè)兩階段同時(shí)優(yōu)化路m法過早收斂于非全局最優(yōu)解,將各路徑的信息素線和頻率的方法;王煒等[3]提出一個(gè)以
4、直達(dá)乘客濃度限制在[Z等[6]提出了min,Zmax].Gambardella量最大為目標(biāo)的逐條布設(shè)~優(yōu)化成網(wǎng)'的方法一種被稱做~AS-@AP的蟻群算法,這個(gè)算法主等.本文以整體線網(wǎng)為研究對象,以出行者對公要的不同在于它直接修改解決方案.Botee等[7]交的需求為依據(jù),方便居民出行為目的,并兼顧公對參數(shù)n~o~B~0的選擇進(jìn)行了深入的研究,用遺交企業(yè)的經(jīng)營效益,建立一個(gè)以直達(dá)客流密度(單傳算法求參數(shù)的最優(yōu)組合.吳慶洪等[8]提出了具位長度運(yùn)送的乘客數(shù)D最大為目標(biāo)的公交線網(wǎng)優(yōu)有變異特征的蟻群算法,在基本蟻群算法中引入化模型.變異機(jī)
5、制,充分利用了2-交換法簡潔高效的特由于網(wǎng)絡(luò)設(shè)計(jì)問題是一個(gè)NP-hard問題,使點(diǎn).陳崚等[9]提出了一種基于分布均勻度的自適用傳統(tǒng)的算法很難求解.大量的研究表明,模擬應(yīng)蟻群算法,該算法根據(jù)優(yōu)化過程中解分布均勻生物的啟發(fā)式算法非常適合這種超大規(guī)模的優(yōu)化度,自適應(yīng)地調(diào)整路徑選擇概率的確定策略和信問題.蟻群算法就是利用群集智能解決組合優(yōu)化息量更新策略.問題的典型例子.蟻群算法是受自然界中蟻群找蟻群算法研究的歷史比較短,如面對規(guī)模較尋食物的行為啟發(fā)而提出的一種基于種群的模擬大的實(shí)際問題它的搜索效率不高,因此還存在許進(jìn)化算法.它屬于隨機(jī)搜
6、索算法,是由Dorigo多有待改進(jìn)的地方.本文通過借鑒比較成熟算法等[4]提出的一種新型的優(yōu)化算法.比較有代表性(并行遺傳算法等D的經(jīng)驗(yàn),充分發(fā)揮蟻群算法的的蟻群算法的研究有Dorigo等[4]的研究,他們用內(nèi)在并行性,開發(fā)并行蟻群算法來提高算法的求蟻群算法解決TSP問題,然后進(jìn)一步把該方法擴(kuò)解質(zhì)量和搜索效率,從而求解公交線網(wǎng)優(yōu)化模型.收稿日期:2OO5-O6-1O;修回日期:2OO6-12-2O.基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(5O479O55;5O278O11D.作者簡介:于濱(1977-D,男,博士生,E-mail:mi
7、nlfishyahoo.com.cn.212大連理工大學(xué)學(xué)報(bào)第47卷1公交線網(wǎng)優(yōu)化模型2算法設(shè)計(jì)以直達(dá)客流密度(單位長度運(yùn)送的乘客數(shù))蟻群算法在優(yōu)化公交網(wǎng)絡(luò)時(shí),首先初始化各最大為目標(biāo)的公交線網(wǎng)優(yōu)化模型如下,邊的信息素分布,然后從起點(diǎn)釋放出P只螞蟻,出發(fā)尋找終點(diǎn).在每一步中,每只螞蟻移動(dòng)一次,到PzjIzjzENjEN達(dá)下一節(jié)點(diǎn).螞蟻從相鄰的~在該循環(huán)中沒有被maxDOd=AghlghIgh其訪問過的~且該路段含有一定的信息素的節(jié)點(diǎn)gENhENLmin{LOd{Lmax中,按照轉(zhuǎn)移規(guī)則求得每一點(diǎn)的轉(zhuǎn)移概率,來選擇Sum下一節(jié)點(diǎn).當(dāng)所
8、有螞蟻都找到終點(diǎn),則一次循環(huán)@Od>@mingII結(jié)束,每條邊上的信息素按更新策略更新.這樣Od{gmaxbnn重復(fù)循環(huán),直到所有的線路都布設(shè)完畢或者循環(huán)Od{bmaxklkl次數(shù)達(dá)到限值為止.S..<@Od<@max(1)Vlgh>0.5km2.
