蟻群算法優(yōu)化車輛路徑問(wèn)題的研究

《蟻群算法優(yōu)化車輛路徑問(wèn)題的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、第27卷第2期貴州大學(xué)學(xué)報(bào)(自然科學(xué)版)V0l_27No．22010年4月JoumalofGuizhouUnive~ity(NaturalSciences)Apr．2010文章編號(hào)1000—5269(2010)02-0115—04蟻群算法優(yōu)化車輛路徑問(wèn)題的研究宋鴿，王子牛，劉磊(1．貴州大學(xué)計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州貴陽(yáng)550003；2．貴州大學(xué)信息化管理中心，貴州貴陽(yáng)550003；3．中鐵六局天津鐵路建設(shè)有限公司，天津300140)摘要：通過(guò)引入蟻群算法來(lái)解決物流中的車輛路徑問(wèn)題。針對(duì)具體實(shí)例運(yùn)用計(jì)算機(jī)編程得出系統(tǒng)的最優(yōu)解，并與優(yōu)化前進(jìn)行對(duì)比，指出優(yōu)化比率，從而減少物流配

2、送成本，提高效益。關(guān)鍵詞：物流配送；優(yōu)化；蟻群算法中圖分類號(hào)：U495；0221．7文獻(xiàn)標(biāo)識(shí)碼：B隨著經(jīng)濟(jì)全球化步伐的加快和通信信息技術(shù)間，不考慮車輛每次最大行駛里程，不考慮運(yùn)輸時(shí)的發(fā)展，物流這個(gè)服務(wù)行業(yè)已經(jīng)成為了一個(gè)跨地的規(guī)章制度等。此外，補(bǔ)充的約束條件是：車輛完域，跨行業(yè)，跨國(guó)界的復(fù)合型產(chǎn)業(yè)。成任務(wù)之后要回到原點(diǎn)，也就是配送中心，運(yùn)輸兩在物流諸多環(huán)節(jié)中，配送占有重要的地位。配節(jié)點(diǎn)間為對(duì)稱路徑，即A點(diǎn)到B點(diǎn)與B點(diǎn)到A點(diǎn)送質(zhì)量的好壞，直接影響到企業(yè)的利潤(rùn)、形象，以及所付出代價(jià)是相等的，并且節(jié)點(diǎn)間是任意可達(dá)的。客戶的滿意度等。物流配送路線的優(yōu)化問(wèn)題，是評(píng)2蟻群算法定配送質(zhì)量好

3、壞的重要標(biāo)準(zhǔn)。因此，本文以目前研蟻群算法最早是由意大利學(xué)者M(jìn)．Dofigo提出究較多的蟻群算法為核心，來(lái)探索車輛優(yōu)化組合問(wèn)的，它來(lái)自于對(duì)蟻群的行為研究，通過(guò)研究螞蟻集題，使運(yùn)輸路線最優(yōu)，從而減少成本，提高效益。體尋徑時(shí)，利用稱為“外激素”的生物信息激素選1問(wèn)題描述擇后繼行為的智能過(guò)程形成。蟻群優(yōu)化算法就是物流配送方案目標(biāo)是要達(dá)到配送效益最高或?qū)ψ匀唤缰形浵伒膶な尺^(guò)程進(jìn)行模擬而得出的一配送成本最低，配送里程最短，配送服務(wù)水準(zhǔn)最優(yōu)種模擬進(jìn)化算法。它具有較好的并行性、協(xié)作性和以及配送勞動(dòng)的消耗最小。而常見的配送路線約魯棒性，尋優(yōu)特性好等特點(diǎn)。蟻群算法已用于解束條件則有以下幾個(gè)：決

4、多種組合優(yōu)化問(wèn)題，例如最短路徑尋優(yōu)問(wèn)題、收貨人對(duì)貨物品種、規(guī)格和數(shù)量的要求TSP問(wèn)題、二次分配問(wèn)題、運(yùn)輸調(diào)度問(wèn)題等。收貨人對(duì)貨物送達(dá)時(shí)間或時(shí)間范圍的要求2．1算法基本描述道路運(yùn)行條件的制約給定n個(gè)城市的TSP問(wèn)題，人工螞蟻數(shù)量為車輛最大裝載能力的限制m，這些螞蟻具有記憶功能，并具有以下特征：車輛最大行駛里程數(shù)的限制以及司機(jī)的最長(zhǎng)(1)根據(jù)信息素濃度和啟發(fā)式信息，用相應(yīng)的工作時(shí)間的限制轉(zhuǎn)移概率選擇下一個(gè)城市。在建立系統(tǒng)模型時(shí)，前面提到了有許多因素需(2)將已經(jīng)走過(guò)的城市放人記憶表中，記憶表要考慮，但為了簡(jiǎn)化問(wèn)題，提出以下假設(shè)：里的城市將不再被選擇為下一個(gè)城市。(1)第一個(gè)假設(shè)

5、：一個(gè)配送中心(2)第二個(gè)假設(shè)：多輛汽車的配送路線優(yōu)化(3)完成一次循環(huán)后，根據(jù)整個(gè)路徑的長(zhǎng)度來(lái)(3)第三個(gè)假設(shè)：考慮車輛載重量釋放相應(yīng)的信息素，并更新走過(guò)的路徑上的信息其他假設(shè)：假設(shè)貨物在運(yùn)輸途中是不會(huì)變質(zhì)損素。壞的，不考慮貨物回收需求，不考慮司機(jī)的工作時(shí)螞蟻選擇下一個(gè)城市的轉(zhuǎn)移概率為：收稿日期：2009—12一O8作者簡(jiǎn)介：宋鴿(1985一)，女，河南駐馬店人，碩士研究生，研究方向：智能信息處理，Email：hilary403@163．tom．+通訊作者：王子牛，Email：znwang@gzu．edu．cn．貴州大學(xué)學(xué)報(bào)(自然科學(xué)版)第27卷信息啟發(fā)式因子：反映了螞蟻

6、在運(yùn)動(dòng)過(guò)程中P：=J{∑：(￡)叼(￡)allowedk(1)所累積的信息量在指導(dǎo)螞蟻群搜索中的相對(duì)重要【ootherwise程度。期望啟發(fā)式因子：反映了期望啟發(fā)式信息在其中，r代表路徑之間的信息索，代表路徑ij指導(dǎo)蟻群在搜索過(guò)程中的相對(duì)重要程度。之間的啟發(fā)信息，在TSP問(wèn)題中，通?！?=1／d，在蟻群算法模型中用參數(shù)P：表示信息素?fù)]發(fā)即路徑的長(zhǎng)度。allowed表示螞蟻k還沒有訪問(wèn)因子，則1一P就是信息素殘留因子。的節(jié)點(diǎn)的集合，每次循環(huán)將已經(jīng)訪問(wèn)的節(jié)點(diǎn)從列表信息素強(qiáng)度Q：為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)中剔除。參數(shù)，為問(wèn)題所考慮的權(quán)重。路徑上的信息素總量。信息素的更新：3實(shí)例仿

7、真(￡+)=P·To-(￡)+(1一p)·∑AT；3．1功能設(shè)計(jì)(2)建立的模型從功能上來(lái)說(shuō)，主要包括以下幾隨著時(shí)間的推移，經(jīng)過(guò)個(gè)時(shí)刻，螞蟻完成一點(diǎn)：①地圖上節(jié)點(diǎn)、路徑的顯示功能，②可以隨意添次循環(huán)，以前留下的信息素將逐漸消逝，用參數(shù)1一加或刪除節(jié)點(diǎn)，③選定的節(jié)點(diǎn)可以設(shè)置需求量約P表示信息消逝程度，P是一個(gè)取值范圍在0到1的束，④可以手工調(diào)整相關(guān)參數(shù)，⑤能夠演示路徑變常數(shù)，△丁表示第k只螞蟻本次循環(huán)中留在路徑化將計(jì)算結(jié)果清晰表示出來(lái)。上的信息量。3．2模型實(shí)現(xiàn)M．Dorigo曾提出三種信息素增量的算法：模型需要為企