基于人工魚群算法的模糊運輸路徑問題研究

徐博文，程 然

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

1 引言

運輸路徑問題作為庫存路徑問題（IRP）下的子問題，是研究如何降低物流總成本要攻克的主要問題之一。由于該問題是典型的NP-HARD問題，使用傳統優化方法很難得到問題最優解或滿意解。Montoya-Torres J R[1]回顧了1988—2014年以來運輸路徑問題的主要論文，并提出構造啟發式算法是該問題的主要研究方向；Amr Farahat[2]等針對IRP問題中庫存和運輸兩方面開發了兩種不同處理方法，其中產品運輸問題被分解為一組獨立的報童問題。并通過計算實驗，發現分類優化性能優于整體優化；Lalla-Ruiz E[3]在庫存分配完畢基礎上提出了一種多車庫開放路徑模型(MDOVRP)，車輛將貨物交付給他們路線上的顧客后，不需要返回倉庫可以繼續工作；李昌兵[5]等建立了選址—路徑—庫存問題一體優化的混合整數規劃模型，并分別設計了庫存和路徑的兩階段啟發式算法，并通過算例仿真證明了該策略的合理有效性。張麗萍[6]等采用一種改進的遺傳算法對其路徑模型進行優化，通過數值分析表明，其改進的方法具有更優性。本文在已知IRP問題的相應庫存分布方案的基礎上，從運輸路徑角度出發，建立了相應模型，然后嘗試使用啟發式算法-人工魚群算法解決該問題，得到相應的庫存分布方案。

2 模型建立

IRP問題的模型是多階段模型，優化目標是確定每個銷售渠道所占的比例，并制定相應的運輸計劃，以最大限度地降低總預期成本。由于本文是在已知IRP問題的相應庫存分布方案的基礎上，制定相應開放路徑運輸方案以優化運輸成本，故作一些粗糙模型假設[4]如下：

（1）需求分配：各個零售商的需求已對應分配給各配送點。

（2）無限供應：無論時間或規模如何，貨物都可立即運輸。

（3）貨物兼容：不同零售商的貨物可混在同一輛車中運輸。

（4）延期交貨：不考慮庫存階段延誤成本。

部分指數如下：

車輛：k=1,2,…,M；配送點：i=1,2,…,Nk；零售商：j=1,2,…,L。

部分參數如下：

W：總成本；

γ：影響因子；

nk：車輛承載零售商的數量；

bk：車輛載重；

：車輛從零售商j1到零售商j2產生的物料成本；

ej：每個零售商所占的份額；

μ(nk-1)：任何時期零售商期望總量；

rkj：運送路徑；

Vislk：車輛視野。

相應成本函數[6]如下：

式（1）表示運輸距離成本部分，式（2）表示時間成本部分。

2.1 精確模型建立

式（3）是數學模型的目標函數,目的是最小化總成本；式（4）保證每條路徑上的各商店的總需求量不超過此條路徑配送車容量；式（5）表示每條路徑服務的商店數不超過總商店數；式（6）要求每個商店都得到車輛的配送服務；式（7）表示每條路徑的商店個數；式（8）表示每個商店有唯一的車輛為之服務；式（9）表示檢測車輛是否需要進行二次運輸。

2.2 模糊模型建立

由于供應鏈網絡的復雜性和現實運輸市場的不確定性，整個分配網絡中的很多參數很有可能是隨著時間、空間等因素在不斷變化的，各層級的能力也都是模糊變量，且上述模型的約束多為非線性或非凸形，求解最優解比較困難，因此，我們基于供應鏈網絡模型，利用模糊數學[10]和不確定規劃[11]的知識，將精確模型轉化為模糊期望值模型（EVM）來降低求解難度，并在此基礎上進行分析。

步驟1：令E=0;

步驟2：在ξij的ε-水平集隨機產生，k=1,2,…,m。記uk為組成的向量，i=1,2,…,N，其中ε為一個充分小的數;

步驟3：

令a=f(x,u1)∧f(x,u2)...∧f(x,um),b=f(x,u1)∨f(x,u2)∨...∨f(x,um)

步驟4：在區間[a,b]隨機產生r;

步驟5：如果r≥0，則E←E+Cr{f(x,ξ)≥r};

步驟6：如果r＜0，則E←E-Cr{f(x,ξ)≤r};

步驟7：重復第4步到第6步N次;

步驟8：U(x)=E[f(x,ξ)]=a∨0+b∧0+E(b-a)/N。

EVM模型如下：

式（11）是數學模型的目標函數,目的是使期望值總和最小；式（12）保證每條路徑上的各商店的總期望不超過此條路徑配送車容量；式（13）表示每條路徑服務的商店期望不超過總商店數；式（14）要求每個商店都得到車輛的配送服務；式（15）表示每條路徑的商店個數；式（16）表示每個商店有唯一的車輛為之服務；式（17）表示檢測車輛是否需要進行二次運輸。

3 人工魚群算法（AFSA）

由于該分配網絡問題的NP-HARD特性，本文探討啟發式算法作為求解方法，選擇了一種適應該分配網絡的人工魚群算法[7]并進行相應改進來求解上述模型。

人工魚群算法是2002年李曉磊等觀察魚類流動特點后提出的一種與動物本能活動反應相似的尋優模式，其相關概念簡介如下：

3.1 AFSA幾種典型行為

（1）隨機行為。魚在水中漫無目的進行本能移動，它是覓食行為的一個缺省行為。

（2）覓食行為。在發現食物時，魚類會迅速的朝著有食物的方位游去，是魚類所具有的最基本的行為。

（3）聚群行為。魚類會通過聚群在一起的方式來提高其本身的生存率。該行為具有跳出局部約束去尋找其他局部最優的能力。

（4）追尾行為。在魚群游動過程中，當其中一條或幾條魚感覺到食物并逐漸向它轉移時，相鄰的魚在發掘其行動后有跟隨動作。該行為可以在某個局域內明確目標快速做出選擇與行動，進而快速尋優，并防止AF在局部范圍內滯留過久。

3.2 AFSA中一些特殊的用法

（1）擁擠度[8]。魚群算法中引入擁擠度δ(0＜δ＜1)限制人工魚群的大小。此方法可以避免在較優的領域內聚集過多的魚而增加競爭、增大成本，在次優或其他領域聚集魚類較少或沒有魚而產生資源浪費現象。

（2）公告板。算法中設置公告板來記錄當前人工魚狀態，每一條魚在行動之后就與公告板上所記錄的狀態相比較，如若狀態更加優秀，就取而代之。這樣，公告板就記錄了整個尋優過程中的大部分數據。通過使用人工魚群算法不斷改變各點自身狀態，并將相應數據與公告欄比較，在經過一系列反復搜索尋優后，所得最優結果最終被留在公告板上。

3.3 魚群算法中的主要函數

魚群算法主要函數見表1。

4 運輸路徑問題人工魚群算法（AFSA）

人工魚群算法解決運輸路徑問題的基本過程如下：

步驟1:初始化解空間；

步驟2:零售商通過覓食行為、聚群行為、追尾行為選擇分銷中心；

步驟3:更新公告欄數據；

步驟4:檢查終止條件；

步驟5:優化數據，循環步驟2-步驟4；

步驟6:輸出結果。

4.1 算法設計

算法中用一個二維數組來表示車輛的配送路徑，一個二維數組作為公告板記錄當前零售商與運載車輛的狀態。Xj為當前零售商狀態，Step為移動步長，di，dj分別表示運載車輛、零售商的位置。選擇一個零售商，嘗試各種行為并依次判斷當前狀態是否能夠執行聚群行為、追尾行為。

4.1.1 覓食行為。在當前車輛視野Visual內隨機移動到新的位置作為下一步移動的方向公告欄更新數據并進行下一個零售商的行為選擇。

4.1.2 聚群行為。移動至當前視野Visual內交接能力最強的分銷中心所處的位置判斷是否滿足聚群行為的條件，如果滿足，則得到下一步移動的方向公告欄更新數據并進行下一個零售商的行為選擇；不滿足條件則繼續進行覓食行為，如重復Tru_number次，仍找不到更合適的位置，則執行隨機行為。

4.1.3 追尾行為。搜索至當前步長Step 內最大零售商所選擇分銷中心位置以計算運輸成本；判斷是否滿足追尾行為的條件，如果滿足，則得到下一步移動的方向公告欄更新數據并進行下一個零售商的行為選擇；不滿足條件則繼續進行追尾行為，如重復Tru_number次，仍找不到更合適的位置，則執行隨機行為。

4.2 改進及優化

可以發現，人工魚群算法在運算初期具有很強的收斂性；隨著算法的運算過程，收斂速度有所下降，此時可以采用改進視野、分段優化、混合優化等方法提升其后期收斂性。

4.2.1 視野的改進及優化。在魚群模式所討論的視野概念中，視野的選擇、移動的步長都是隨機的，而視野對算法中各種行為和收斂性能有較大影響。若視野范圍較大，則人工魚的全局搜索能力強，但精度低，運算量大；若視野范圍較小，則人工魚的局部搜索能力強，精度高。所以我們在算法運行前期，采用了較大的視野，意在增強全局搜索能力和收斂速度，并隨著算法的進行，視野和步長逐漸縮小，提高其局部搜索能力和結果精度。視野和步長的調整公式如下:

其中，Visualz為供貨商的視野；Visualt，Stept為當前視野，步長，初始值為Visualz/4 、Stepz/4 ；Visualm，Stepm為最小可移動視野，步長。 s ∈[0,1]用來控制α的變化速率，這里分別取S=1,S=3/4,S=2/3,S=1/2，所得的α值及視野Visual變化如圖1、圖2所示。

圖1 函數α 變化圖

圖2 視野變化圖

4.2.2 覓食行為的優化。覓食行為執行的是一種隨機試探行為,其目的是尋找較優的解,該行為受視野、步長等條件約束。在試探Try_number次的過程中,如果不滿足前進條件,但有合適的矢量方向，則記錄下這個矢量步長，這樣可以化簡運算量,加快向全局最優解轉化。

5 算例分析

本文以五個配送點（97，120；-100，40；-133，-104；-10，-79；137，-30）和十五個零售商（251，200；-156，-91；-93，79；-210，282；126，143；-18，-157；-238，-239；78，-92；246，-217；-201，-224；-80，-127；-169，-138；262，-64；40，262；204，-72）組成的配送系統進行研究，各零售商的期望分別為（327.5；236.5；207.5；329；439.5；492；315.5；148；516；557；417；328.5；218.5；111.5；356），相應的庫存分布方案見表2。

表2 庫存分布方案

仿真1 給出了改進AFSA 算法求解與遺傳算法（GA）求解結果分析，算法進化代數為30 次，成本比γ=1/3；車輛載重bk=1 000 ；Visualz=500 ，Visualm=0.001，Step=Visual/3，選取s=3/4、s=1 進行迭代，其中，GA 的交叉率為0.6，變異概率為0.1。最終的最優路徑數據見表3。

表3 最優路徑數據對比

通過實驗結果可知，AFSA不僅所需確定的參數少，加入S值優化后其收斂速度和精確度間的調整更加簡單、直觀。在迭代次數相同的情況下，改進視野及步長后取S=3/4 的人工魚群算法取得了比遺傳算法更好的優化結果。

6 結語

本文通過對IRP問題下的子問題-運輸路徑問題的相關分析及建立相應模型并實踐計算，得到了如下結論：

（1）庫存分布問題和運輸路徑問題，既可以分開考慮，也可以一并研究。

（2）對相應的運輸路徑問題模型進行模糊處理既可以降低模型的難度，也可以使模型更加直觀明了。

（3）對以人工魚群算法為基礎的啟發式算法進行相應的改進和優化，使之應用于運輸路徑問題，是可行有效的。

（4）改進優化視野和步長可以提高人工魚群算法局部搜索能力及運算結果的精度。

本文通過模糊模擬簡化了相應的庫存路徑模型，實際問題中的一些不穩定因素的影響，還需進一步的研究以改進和完善。