人工魚群算法在配送路徑優化問題中的應用

邢維 裴紅梅

摘? 要：人工魚群算法是一種利用人工魚通過模仿在一片水域中魚群覓食、聚群以及追尾等行為從而來實現優化的一種算法。人工魚群算法在物流的運輸、布局、選址、配送、調度等方面有著非常廣泛的應用。首先建立一個物流配送的路徑優化模型，在該模型的基礎上構造出解決物流配送的路徑優化問題的人工魚群算法。用該算法優化物流配送的路徑，從而有效地求解出問題的最優解。

關鍵詞：人工魚群算法;路徑優化;問題;應用

中圖分類號：TP18 文獻標志碼：A 文章編號：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 問題背景

物流配送路徑優化問題有很多解決的算法，比如粒子群算法、蟻群算法、人工魚群算法等。

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

圖1 人工魚群算法視覺描述

2 問題的提出

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

3 模型假設

（1）所有配送車輛型號相同。

（2）配送時，無天氣、交通和道路狀況的影響。

（3）配送貨物時車輛勻速行駛。

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

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

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

（7）配送車輛不能超載。

（8）配送時間要滿足客戶的時間窗。

（9）配送車輛每天有總運行時間或者是總路程的要

求。

4 模型建立

目標函數：

（1）式表示每輛車所載貨運量之和要小于該車的載重量。

（2）式表示每個客戶的貨物量可以由一輛車完成。

（3）式表示每個客戶的貨物量必須由一輛車完成。

（4）式表示車輛k是否行駛到j點與j點的任務是否由k車輛完成相對應。

（5）式表示車輛k從i點是否行駛到所有點與i點的任務是否由k車輛完成相對應。

5 人工魚群算法求解模型

計算出初始人工魚群各個人工魚的狀態，計算出相對應的食物濃度L，即目標函數值，本文所求的是路程最短的路徑，所以將最優的人工魚狀態即目標函數值最小的狀態及最小函數值記錄在公告板上。

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

第二步 聚群行為：設Xi為當前人工魚的狀態，搜索視野范圍V內R人工魚的數目為ni和聚群中心魚的位置Xc，如果■<？啄，說明伙伴中心食物較多，并且不是很擁擠，如果Li>Lc，則人工魚向中心魚位置Xc前進一步，否則進行覓食行為。其表達式為：

第三步 追尾行為：設Xi為當前人工魚的狀態，搜索鄰域V內最優狀態的人工魚為Xmin，如果Li>Lmin，Xmin鄰域中的伙伴數目為nmin，且■<？啄，說明人工魚Xmin食物較多并且不是很擁擠，所以人工魚向Xmin所在的位置前進一步，否則進行覓食行為。其表達式為：

每個人工魚在尋優的過程中，每次行為后的狀態與公告板的狀態進行比較，若優于公告板上的狀態，則將公告板的狀態及函數值進行跟新。實驗進行N0次后，公告板所記錄的狀態就是最優的狀態。

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

本文利用人工魚群算法解決了配送路徑優化問題，本算法的優點是只需要比較目標函數值就可以，對目標函數所具有的性質沒有太高的要求，對參數的設定要求均不高，全局尋優能力比較強，容易從局部極值中跳出來，得到全局的極值。

參考文獻：

[1]王西鄧.人工魚群算法的改進研究[D].西安：西安建筑科技大學，2007.

[2]王培崇.人工魚群算法研究綜述[J].中國民航飛行學院學報，2013，24（4）：22-26.

[3]楊弋，顧幸生：物流配送車輛優化調度的綜述[J].東南大學學報，2003，33（增刊）：105-111.

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

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