[發(fā)明專利]一種基于車輛路徑規(guī)劃的改進(jìn)人工魚群優(yōu)化方法

無效

• 申請?zhí)枺?/td>: 201010204047.1
• 申請日: 2010-06-18
• 公開（公告）號: CN101866384A
• 公開（公告）日: 2010-10-20
• 發(fā)明（設(shè)計）人: 柳毅;王曉耘;魏潔
• 申請（專利權(quán)）人: 杭州電子科技大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/00
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 杜軍

技術(shù)領(lǐng)域

本發(fā)明屬于工程技術(shù)領(lǐng)域，涉及一種基于車輛路徑規(guī)劃的改進(jìn)人工魚群優(yōu)化方法。

背景技術(shù)

近年來，我國大力倡導(dǎo)“堅持開發(fā)節(jié)約并重、節(jié)約優(yōu)先，按照減量化、再利用資源化的原則”的循環(huán)經(jīng)濟(jì)，大部制造企業(yè)實現(xiàn)了生產(chǎn)者責(zé)任延伸制，對廢舊產(chǎn)品召回進(jìn)行再制造。典型的例子就是聯(lián)想集團(tuán)備件物流處采取的“客戶自行更換備件單元”，其過程就是企業(yè)把新的計算機(jī)配件送達(dá)終端客戶手中并進(jìn)行上門服務(wù)，同時取回已損壞的計算機(jī)配件。這種雙向運輸方式就是典型的帶回程取貨車輛路徑問題(Vehicle?Routing?Problem?with?Backhaul，VRPB)，而如何在逆向物流中經(jīng)濟(jì)合適地安排車輛的配送路徑，對物流產(chǎn)業(yè)的發(fā)展有著重要的影響。

人工魚群算法(Artificial?Fish?Swarm?Algorithm，簡稱AFSA)是由國內(nèi)學(xué)者李曉磊，邵之江，錢積新提出的一種基于動物行為的群體智能優(yōu)化算法。該算法簡單易實現(xiàn)，具有取得全局極值、避免陷入局部極值的良好能力，對搜索空間也有一定的自適應(yīng)能力，而且算法對初值與參數(shù)選擇不敏感，具有較強(qiáng)的魯棒性和較好的收斂性能。目前人工魚群算法已應(yīng)用于多個工程領(lǐng)域，并取得了較好的效果，具體包括：計算機(jī)網(wǎng)絡(luò)的路由選擇、通風(fēng)巷道漏風(fēng)點辨識、配電網(wǎng)絡(luò)重構(gòu)和灌區(qū)優(yōu)化配水等。但算法在保持探索與開發(fā)平衡的能力較差、算法運行后期搜索的盲目性較大、尋優(yōu)結(jié)果精度低和運算速度慢等。

發(fā)明內(nèi)容

本發(fā)明提出一種改進(jìn)的人工魚群優(yōu)化方法，安排可回程取貨車輛配送路徑，提高車輛服務(wù)路徑上取貨、送貨節(jié)點的效率。

本發(fā)明采用如下技術(shù)解決方案：將人工魚群算法仿生學(xué)原理和決策者主觀偏好進(jìn)行有效結(jié)合，重構(gòu)了人工魚群算法的尋優(yōu)公式；引入魚群感知范圍的概念，通過判斷車輛路徑上節(jié)點的需求量和當(dāng)前車輛剩余運輸能力，以及決策者主觀偏好對人工魚的移動步長、視野范圍和鄰域搜索進(jìn)行動態(tài)調(diào)整；改進(jìn)人工魚群算法的全局搜索能力提高，可以優(yōu)化調(diào)度可回程取貨車輛的取、送貨行為。

本發(fā)明方法的具體步驟是：

步驟1.考慮到VRPB問題的特點，隨機(jī)生成初始規(guī)模的人工魚群。將t時期車輛的狀態(tài)用人工魚個體的狀態(tài)向量X＝(X_i(t)，i＝1，2，…，F(xiàn)_number)表示，其中，i為車輛將要服務(wù)的節(jié)點，X_i(t)為當(dāng)前車輛可載貨容量；目標(biāo)函數(shù)Y_i＝F(X_i(t))決定人工魚當(dāng)前所在位置的食物濃度；人工魚個體之間的距離表示為d_i，i+1＝‖X_i-X_i+1‖；對于VRPB問題，需要將人工魚的初始位置放在起點和終點上，因為車輛只有從起點出發(fā)到達(dá)終點，或者從終點出發(fā)回到起點才是一個有效解。

步驟2.自適應(yīng)的設(shè)定鄰域搜索范圍。t時期人工魚個體X_k的鄰域定義為：N_k＝{X_k|d_k，k+1＜Visual}，其中Visual表示人工魚的感知范圍。其中鄰域半徑R_n的確定非常關(guān)鍵，如果太大不足以發(fā)現(xiàn)一些重要個體，如果太小會形成局部極值點，降低算法搜索速度。引入魚群感知范圍一排斥區(qū)、中性區(qū)和吸引區(qū)的概念。假設(shè)人工魚的鄰域距離為R₁，在這個距離之內(nèi)的其他魚對此魚有排斥作用；鄰域距離在R₁和R₂之間為中性區(qū)域，在這個范圍內(nèi)的其他魚對此魚的作用可能為排斥，也可能為吸引；鄰域距離R₂和R₃之間的區(qū)域為吸引區(qū)，在此區(qū)域的其他魚對此魚有吸引作用；距離R₃之外不屬于魚的感知范圍，其中R₁＜R₂＜R₃。

步驟3.自適應(yīng)的覓食行為。在基本人工魚群算法中，人工魚不能改變運動方向。設(shè)定α，β分別為速度向量與兩個坐標(biāo)軸的方向角，根據(jù)式(1)分別確定參數(shù)α_k(t)，β_k(t)的值決定人工魚群下一步的移動方向。引入交換序操作符“⊕”重構(gòu)人工魚群算法的覓食公式(2)，這樣就擴(kuò)大了人工魚群算法的搜索范圍，能夠有效地避免傳統(tǒng)人工魚群算法“早熟收斂”的缺點。