帶回程取貨車輛路徑問題的人工魚群算法研究

柳 毅

(杭州電子科技大學管理科學與信息工程研究所,浙江杭州310018)

0 引 言

帶回程取貨車輛路徑問題(Vehicle Routing Problem with Backhaul,VRPB)是VRP問題的衍生,能夠將送貨取貨過程結合起來,實現(xiàn)在送貨的同時取貨[1]。文獻2,3分別應用遺傳算法和啟發(fā)式算法解決這類問題,但遺傳算法的計算量大、收斂速度較慢;啟發(fā)式算法缺乏魯棒性。人工魚群算法是模擬魚群的覓食、聚群和追尾行為的優(yōu)化算法,從構造單條魚的底層行為做起,通過魚群各個體的局部尋優(yōu),達到全局最優(yōu)值在群體中突現(xiàn)的目的,具有克服局部極值的能力[4]。因此,本文提出用人工魚算法來求解帶回程取貨車輛路徑問題。

1 帶回程取貨車輛路徑問題的數(shù)學模型

式1是求運輸成本最小的目標函數(shù);式2表明保證每個節(jié)點只被一輛車服務一次;式3表明客戶節(jié)點只可以被一輛車訪問,而初始節(jié)點被所有車輛訪問;式4-7表明車輛任何時間所載貨物不能超過其最大能力;式8為各個決策變量取值約束。V={i}為所有客戶節(jié)點i的需求集合;M={k}為所有車輛的集合;Qk是車輛k的能力;C={Cij}是各節(jié)點間的距離矩陣;Pi是客戶i的取貨需求量;di是客戶i的送貨需求量;Xijk決定車輛從節(jié)點i到達節(jié)點j后,是否由車輛k服務;Yijk是從節(jié)點i到達節(jié)點j時車輛k上的送貨輛;Zijk表示從節(jié)點i到達節(jié)點j時車輛k上的取貨輛;Uik表示節(jié)點i是否由車輛k服務。

2 求解VRPB問題的人工魚群算法

對于VRPB問題需要將人工魚的初始位置放在起點和終點節(jié)點上,因為車輛只有從起點出發(fā)到達終點,或者從終點出發(fā)到達起點才是一個有效解。

(2)覓食行為。人工魚當前狀態(tài)為Xi,人工魚下一步狀態(tài)向量Xinext,Random()表示[0,Step]間的隨機數(shù),當Xj食物濃度(FCj)大于Xi食物濃度(FCi)時,則向該方向前進一步;否則重新隨機選擇狀態(tài)Xj進行判斷。

(3)人工魚個體在t時期能量函數(shù)Vs(t)：

式中,Vs(t)為時期t人工魚個體Xs(t)的能量,λ為大于0的常數(shù)。初始時Vs(0)=λ Ys(Xs(0)),人工魚個體Xs(t)從低濃度食物區(qū)游到高濃度食物區(qū)進食,即Ys(Xs(t+1))>Ys(Xs(t)),則該人工魚能量增加;人工魚個體Xs(t)從高濃度食物區(qū)游到低濃度食物區(qū),即Ys(Xs(t+1))≤Ys(Xs(t)),則該人工魚消耗能量。

(4)聚群行為。人工魚當前狀態(tài)為Xi,搜索當前鄰域內的伙伴數(shù)目nf及計算中心位置Xck：

式中,Xck表示中心位置狀態(tài)向量Xc的第k個元素;Xjk表示伙伴Xj的第k個元素。計算該中心位置的食物濃度值FCc：

式12表明伙伴中心位置有較多的食物并且不太擁擠,朝伙伴的中心位置方向前進一步;否則人工魚執(zhí)行覓食行為。

(5)追尾行為。設人工魚當前狀態(tài)為Xi,探索當前鄰域內(即(di,j≤Visual)的伙伴中Y為最大的伙伴Xmax,如果FCmax>FCi,表明伙伴Xmax具有較高的食物濃度并且不太擁擠,則朝伙伴Xmax的方向前進;否則執(zhí)行覓食行為。

式中,Xmaxk表示狀態(tài)向量Xmax的第k個元素。若人工魚當前可見域內沒有其它伙伴,也執(zhí)行覓食行為。

(6)行為評價。根據(jù)所要解決問題的性質,對人工魚當前所處的環(huán)境進行評價,設立公告板記錄最優(yōu)個體狀態(tài)及該個體位置的食物濃度值,每條人工魚行動一次后就將自身當前狀態(tài)與公告板進行比較,如果優(yōu)于公告板則用自身狀態(tài)取代公告板狀態(tài),從而選擇一種合適的行為。

(7)新增服務的鄰域搜索。當動態(tài)產生新的客戶需要服務時,采用基于距離原則的鄰域搜索策略。以當前新的客戶點(xadd,yadd)為圓心,其到車場的距離為半徑的圓形范圍內尋找在途車輛,即滿足：

式中,(yk,yk)為干擾發(fā)生時刻車輛k所在位置,(x0,y0)為車場的位置,從而得到能服務新客戶點的在途車輛集合。當所有在途車輛均無法為新客戶點服務時,則需從車場增派車輛為其服務。

(8)判斷中止條件。判斷是否達到最大迭代次數(shù)MAXG,若是則輸出公告板的計算結果;否則,G=G+1轉步驟4繼續(xù)進行覓食行為。

3 仿真算例分析

為驗證人工魚群算法求解VRPB問題的有效性,采用文獻5中的實驗數(shù)據(jù),將Solomon精確車輛路徑問題的實例R101、R102改造成為25、50個節(jié)點VRPB問題(將3的倍數(shù)節(jié)點改造為取貨需求節(jié)點,取貨量為原送貨量),計算時人工魚的個數(shù)為50,移動步長為10,視野范圍為50,啟發(fā)式算法和人工魚群算法的仿真優(yōu)化結果如表1所示。

表1 啟發(fā)式算法與人工魚群算法仿真結果比較

實驗結果表明在車輛使用數(shù)基本相同的前提下,人工魚群算法所得車輛行駛距離明顯小于啟發(fā)式算法所得行駛距離。在最小化車輛使用數(shù)與車輛行駛距離的目標函數(shù)情況下,人工魚群算法的收斂情況明顯優(yōu)于啟發(fā)式算法。

4 結束語

人工魚群算法具有簡單易實現(xiàn),對初值與參數(shù)選擇不敏感等優(yōu)點,本文采用人工魚群算法求解帶回程取貨車輛路徑問題,仿真結果表明該算法具有較好的全局優(yōu)化能力,可以取得令人較為滿意的效果。

[1] Guo F,Long Y.Genetic algorithms for improved vehicle routing problems with backhauls[C].Beijing：Proceedings of the 12th International Conference on Industrial Engineering and Engineering Management,2006：606-610.

[2] Baker BM,Ayechew M A.A genetic algorithm for the vehicle routing problem[J].Computers&Operations Research,2003,30(5)：787-801.

[3] Fisher M L.Optimal solutionof vehicle routing problems using minimum K-trees[J].Operations Research,1994,42(4)：626-643.

[4] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐,2002,22(11)：32-38.

[5] Toth P,Vigo D.A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls[J].European Journal of Operational Research,1999,11(3)：528-544.