資源描述:
《同時取送貨車輛路徑問題的改進(jìn)人工魚群算法.pdf》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、第34卷第3期杭州電子科技大學(xué)學(xué)報V01.34.No.32014年5月JournalofHangzhouDianziUniversityMav.2014doi:10.3969/j.issn.1001—9146.2014.03—008同時取送貨車輛路徑問題的改進(jìn)人工魚群算法柳毅,余福茂,俞武揚(杭州電子科技大學(xué)管理科學(xué)與信息工程研究所,浙江杭州310018)摘要:該文在建立同時送取貨車輛路徑問題數(shù)學(xué)模型基礎(chǔ)上,針對車輛負(fù)載波動性的特點,構(gòu)造相應(yīng)的人工魚群算法的四元個體模型;利用動態(tài)設(shè)置視野范圍、鄰域搜索方法改進(jìn)人工魚群算法的覓食和追尾操作行為,仿真算例證明改進(jìn)人工魚群算法能
2、快速收斂得到較優(yōu)解,具有較強工程應(yīng)用價值。關(guān)鍵詞:可同時取送貨車輛路徑問題;人工魚群算法;鄰域搜索中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:A文章編號:1001—9146(2014)03—0034—040引言同時取送貨車輛路徑問題(VehicleRoutingProblemwithSimultaneousDeliveryandPickup,VRPSDP)是逆向物流管理領(lǐng)域里重要的優(yōu)化問題。文獻(xiàn)[1]從逆向物流的角度分析建立VRPSDP問題的數(shù)學(xué)模型,并提出4種不同標(biāo)準(zhǔn)的插入式啟發(fā)算法;文獻(xiàn)[2]在建立VRPSDP問題數(shù)學(xué)模型的基礎(chǔ)上,提出兩種局域搜索啟發(fā)式算法求解具有車輛行程
3、約束的VRPSDP問題;文獻(xiàn)[3]提出一種自適應(yīng)混合遺傳算法求解以集成方式處理取貨和送貨操作的可同時取送貨車輛路徑問題。啟發(fā)式算法一般能夠在較短的時間內(nèi)求出VRPSDP問題的近似解,但隨著問題規(guī)模增大,其解空間的搜索能力有限。文獻(xiàn)[4]提出一種通過模擬魚類覓食、聚集和追尾行為獲得全局最優(yōu)值的人工魚群優(yōu)化算法(ArtificialFishSwarmAlgorithm,AFSA)。為此,本文根據(jù)物流配送車輛實際情況,以總行駛距離最短為優(yōu)化目標(biāo)建立該問題的整數(shù)規(guī)劃模型,結(jié)合人工魚的動態(tài)搜索和尋食策略,提出一種求解VRPSDP問題的改進(jìn)人工魚群算法。1VRPSDP問題的建模描述V
4、RPSDP問題可描述為:有n個客戶節(jié)點(1,2,?,n),第i個客戶節(jié)點的取貨需求量為Pi,送貨需求量為qi。配送中心安排載重量為Q的k輛車為客戶送貨并收集客戶物品,每個客戶位置及取送貨需求量已知,且客戶只接受一次服務(wù),在車輛安排滿足客戶需求前提下,求車輛總行程長度最短。MinZ=∑Jy∑diJ‘J—(1)i=0J=0k:1nitls.t∑∑Xijk=11≤j≤n(2)1=Uk=lYijk≤xijkQk0≤i≤n,1≤j≤n+1,1≤k≤m(3)∑ydijxIjk≤Lk:1,2,?,m(4)收稿Et期:2013—06—26基金項目:教育部人文社會科學(xué)青年基金資助項目(12
5、YJC630130),浙江省自然科學(xué)基金資助項目(LY12G01003)作者簡介:柳毅(1978一),男,遼寧沈陽人,副教授,物流系統(tǒng)優(yōu)化.第3期柳毅等:同時取送貨車輛路徑問題的改進(jìn)人工魚群算法35∑Y。ik=∑qj∑x.jk1≤k≤m(5)∑yjk=∑Yijk+(pi—qj)∑xk1≤j≤n+1,1≤k≤m(6)xiIjjk:I10其翌它k從i訪問j0u≤i≤n,1≤j≤n+1,1≤k≤m(7),y.ik/>00≤i≤n,1≤j≤n+1,1≤k≤in(8)式(1)表示車輛總運行距離最短,式(2)表示每個客戶節(jié)點都要被訪問且僅服務(wù)一次;式(3)表明當(dāng)車輛k經(jīng)過弧(i,j)
6、的載重量Yijk不能超過車輛容量Q,如果車輛k不經(jīng)過弧(i,j)則其載重y=0;式(4)表示最大行駛距離約束;式(5)表示車輛完成各顧客節(jié)點服務(wù)任務(wù)后回到配送中心時其載貨量為本次配送路線中各客戶取貨需求量之和;式(6)表示車輛在任意點的載貨量滿足在該點取貨需求量與送貨需求量代數(shù)求和的恒等關(guān)系;式(7)表示決策變量的性質(zhì);式(8)表示車輛k行駛在弧(i,j)上的載重量。2改進(jìn)人工魚群算法設(shè)計2.1構(gòu)造人工魚個體模型人工魚個體模型為一個四元組Xi=,其中參數(shù)G為物流配送中需要服務(wù)的客戶節(jié)點組成的二維坐標(biāo)點集合,目標(biāo)函數(shù)值Y=
7、f(X;)表示人工魚當(dāng)前食物濃度值,由送貨需i求量qi、取貨需求量P配與車輛剩余空間(Q—P一∑q)構(gòu)成;VisualScope表示人工魚的感知范圍,s=1Direct表示人工魚群運動方向,受此刻車輛可載貨物容量支配。2.2動態(tài)設(shè)置人工魚群搜索視野改進(jìn)人工魚群算法搜索視野r的值非常重要,r值設(shè)置過大不易獲得人工魚群中的最優(yōu)個體,太小算法容易早熟一獲得局部極值點。為此,根據(jù)文獻(xiàn)[5]增加人工魚感知范圍動態(tài)設(shè)置魚群搜索視野,dij=distance(Xi,Xj)表示人工魚x和xi之間的距離,人工魚xi的搜索視野為VisualSco