人工魚(yú)群算法在配送路徑優(yōu)化問(wèn)題中的應(yīng)用

邢維 裴紅梅

摘? 要：人工魚(yú)群算法是一種利用人工魚(yú)通過(guò)模仿在一片水域中魚(yú)群覓食、聚群以及追尾等行為從而來(lái)實(shí)現(xiàn)優(yōu)化的一種算法。人工魚(yú)群算法在物流的運(yùn)輸、布局、選址、配送、調(diào)度等方面有著非常廣泛的應(yīng)用。首先建立一個(gè)物流配送的路徑優(yōu)化模型，在該模型的基礎(chǔ)上構(gòu)造出解決物流配送的路徑優(yōu)化問(wèn)題的人工魚(yú)群算法。用該算法優(yōu)化物流配送的路徑，從而有效地求解出問(wèn)題的最優(yōu)解。

關(guān)鍵詞：人工魚(yú)群算法;路徑優(yōu)化;問(wèn)題;應(yīng)用

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2020）27-0136-02

Abstract： Artificial fish swarm algorithm is a kind of algorithm that uses artificial fish to achieve optimization by imitating the behavior of fish swarm in a water area， such as foraging， clustering and tail chasing. Artificial fish swarm algorithm is widely used in transportation， layout， location， distribution and scheduling of logistics. First of all， a path optimization model of logistics distribution is established. Based on the model， an artificial fish swarm algorithm is constructed to solve the path optimization problem of logistics distribution. The algorithm is intended to realize the path optimization for logistic distribution， so as to effectively obtain the optimal solution to the problem.

Keywords： artificial fish swarm algorithm; path optimization; problem; application

1 問(wèn)題背景

物流配送路徑優(yōu)化問(wèn)題有很多解決的算法，比如粒子群算法、蟻群算法、人工魚(yú)群算法等。

人工魚(yú)群算法是2002年李曉磊等人提出的。在一片水域中，存在的魚(yú)的數(shù)量最多的地方就是該水域中營(yíng)養(yǎng)物質(zhì)含量最高的地方，利用該特點(diǎn)來(lái)模仿魚(yú)群在水中覓食、聚群以及追尾等行為來(lái)得到全局最優(yōu)解，這就是人工魚(yú)群算法的思想。人工魚(yú)群算法具有并行處理和全局尋優(yōu)的特點(diǎn)，即其收斂速度較快，能夠克服局部極值從而取得全局極值，是一個(gè)經(jīng)常被用新型的高效的尋優(yōu)方法（見(jiàn)圖1）。

圖1 人工魚(yú)群算法視覺(jué)描述

2 問(wèn)題的提出

在一個(gè)城市里，有一配送中心，有m輛車(chē)，需要向n個(gè)客戶(hù)配送貨物，每一個(gè)客戶(hù)對(duì)貨物都有相應(yīng)的需求量，車(chē)輛在配送中心將貨物裝好車(chē)后需要將貨物送到顧客所在的位置，如何選擇配送路線才能使配送成本最低？問(wèn)題最關(guān)鍵的地方在于怎樣安排配送車(chē)輛數(shù)目及車(chē)輛行駛路線，從而使得配送路程最短。

3 模型假設(shè)

（1）所有配送車(chē)輛型號(hào)相同。

（2）配送時(shí)，無(wú)天氣、交通和道路狀況的影響。

（3）配送貨物時(shí)車(chē)輛勻速行駛。

（4）配送的貨物是同一種。

（5）客戶(hù)的位置以及需求量已知。

（6）配送中心到客戶(hù)之間的距離已知，以及各客戶(hù)之間的距離已知。

（7）配送車(chē)輛不能超載。

（8）配送時(shí)間要滿足客戶(hù)的時(shí)間窗。

（9）配送車(chē)輛每天有總運(yùn)行時(shí)間或者是總路程的要

求。

4 模型建立

目標(biāo)函數(shù)：

（1）式表示每輛車(chē)所載貨運(yùn)量之和要小于該車(chē)的載重量。

（2）式表示每個(gè)客戶(hù)的貨物量可以由一輛車(chē)完成。

（3）式表示每個(gè)客戶(hù)的貨物量必須由一輛車(chē)完成。

（4）式表示車(chē)輛k是否行駛到j(luò)點(diǎn)與j點(diǎn)的任務(wù)是否由k車(chē)輛完成相對(duì)應(yīng)。

（5）式表示車(chē)輛k從i點(diǎn)是否行駛到所有點(diǎn)與i點(diǎn)的任務(wù)是否由k車(chē)輛完成相對(duì)應(yīng)。

5 人工魚(yú)群算法求解模型

計(jì)算出初始人工魚(yú)群各個(gè)人工魚(yú)的狀態(tài)，計(jì)算出相對(duì)應(yīng)的食物濃度L，即目標(biāo)函數(shù)值，本文所求的是路程最短的路徑，所以將最優(yōu)的人工魚(yú)狀態(tài)即目標(biāo)函數(shù)值最小的狀態(tài)及最小函數(shù)值記錄在公告板上。

第一步 覓食行為：設(shè)Xi為當(dāng)前人工魚(yú)的狀態(tài)，在感知范圍V內(nèi)任意選一個(gè)狀態(tài)Xj，其中Xj=Xi+rand（）·V如果Li>Lj，則向Xj方向前進(jìn)一步，其中rand（）是0到1之間任意數(shù);否則，再重新任意選擇一個(gè)狀態(tài)Xj，判斷是否可以前進(jìn)一步，反復(fù)N次，仍不能滿足前進(jìn)的條件，就隨機(jī)的移動(dòng)一步，其表達(dá)式為：

第二步 聚群行為：設(shè)Xi為當(dāng)前人工魚(yú)的狀態(tài)，搜索視野范圍V內(nèi)R人工魚(yú)的數(shù)目為ni和聚群中心魚(yú)的位置Xc，如果■<？啄，說(shuō)明伙伴中心食物較多，并且不是很擁擠，如果Li>Lc，則人工魚(yú)向中心魚(yú)位置Xc前進(jìn)一步，否則進(jìn)行覓食行為。其表達(dá)式為：

第三步 追尾行為：設(shè)Xi為當(dāng)前人工魚(yú)的狀態(tài)，搜索鄰域V內(nèi)最優(yōu)狀態(tài)的人工魚(yú)為Xmin，如果Li>Lmin，Xmin鄰域中的伙伴數(shù)目為nmin，且■<？啄，說(shuō)明人工魚(yú)Xmin食物較多并且不是很擁擠，所以人工魚(yú)向Xmin所在的位置前進(jìn)一步，否則進(jìn)行覓食行為。其表達(dá)式為：

每個(gè)人工魚(yú)在尋優(yōu)的過(guò)程中，每次行為后的狀態(tài)與公告板的狀態(tài)進(jìn)行比較，若優(yōu)于公告板上的狀態(tài)，則將公告板的狀態(tài)及函數(shù)值進(jìn)行跟新。實(shí)驗(yàn)進(jìn)行N0次后，公告板所記錄的狀態(tài)就是最優(yōu)的狀態(tài)。

因此得到本次配送的最優(yōu)路徑，即路程最短，成本最低的配送路徑。

本文利用人工魚(yú)群算法解決了配送路徑優(yōu)化問(wèn)題，本算法的優(yōu)點(diǎn)是只需要比較目標(biāo)函數(shù)值就可以，對(duì)目標(biāo)函數(shù)所具有的性質(zhì)沒(méi)有太高的要求，對(duì)參數(shù)的設(shè)定要求均不高，全局尋優(yōu)能力比較強(qiáng)，容易從局部極值中跳出來(lái)，得到全局的極值。

參考文獻(xiàn)：

[1]王西鄧.人工魚(yú)群算法的改進(jìn)研究[D].西安：西安建筑科技大學(xué)，2007.

[2]王培崇.人工魚(yú)群算法研究綜述[J].中國(guó)民航飛行學(xué)院學(xué)報(bào)，2013，24（4）：22-26.

[3]楊弋，顧幸生：物流配送車(chē)輛優(yōu)化調(diào)度的綜述[J].東南大學(xué)學(xué)報(bào)，2003，33（增刊）：105-111.

[4]陳光亭，裘哲勇.數(shù)學(xué)建模[M].北京：高等教育出版社，2010.

[5]楊浩.模型與算法[M].北京：北方交通大學(xué)出版社，2002.