邵良杉，聞爽爽＊

1.遼寧工程技術大學，管理科學與工程研究院，遼寧 葫蘆島 125105

2.遼寧工程技術大學，工商管理學院，遼寧 葫蘆島 125105

引 言

2006年3 月通過的《國民經濟和社會發(fā)展第十一個五年規(guī)劃綱要》中，將“大力發(fā)展現代物流業(yè)”作為單獨小節(jié)列出，至此物流逐漸成為經濟研究中的熱議話題。作為物流的核心過程，運輸掌握著整個物流系統(tǒng)的“命脈”，運輸成本的高低關系著整個物流系統(tǒng)運營的優(yōu)劣。運輸活動不能創(chuàng)造實物產品，只會提供運輸勞動，使待運輸物資發(fā)生位移。身處快速發(fā)展的社會中，隨著制造業(yè)、服務業(yè)的不斷發(fā)展和人們逐步提升的生活水平，出現了一種區(qū)位關系——即資源、產地和市場，由此造成運輸成本在經濟發(fā)展中的作用日漸明朗。因此，降低運輸成本、優(yōu)化產銷配置、合理規(guī)劃路線，將對整個物流系統(tǒng)產生巨大的影響。

目前運輸問題的發(fā)展趨勢主要分為：傳統(tǒng)運輸問題、B 運輸問題、D 運輸問題以及JIT 運輸問題。傳統(tǒng)運輸問題包括兩類，即企業(yè)產銷平衡問題和企業(yè)產銷不平衡問題。在產銷平衡問題的運價表中一般將不可能的運輸方案設為任意大的正數，而對于產銷不平衡問題通常采取虛擬假設產地或銷地的辦法將其轉化為產銷平衡問題。本研究主要討論傳統(tǒng)運輸問題中的企業(yè)產銷平衡問題。

運輸問題的幾大特點主要為：（1）多產地與多銷地；（2）產銷兩地的產額不同——每個產地的產量不同，每個銷地的銷量也不同；（3）每種產銷組合之間的運價都不同；（4）在滿足供需的條件下如何組織調運，選出最佳調運方案使總運費最小。

針對運輸問題的特點，以往解決運輸問題的方法通常包括：線性規(guī)劃法、表上作業(yè)法、圖上作業(yè)法、網絡解法。傳統(tǒng)算法的時間復雜度和空間復雜度會隨著數據維度的不斷增加而升高，使問題求解變得不易，耗時費力，故針對大型復雜運輸問題，目前主要采用如機器學習、神經網絡優(yōu)化算法、人工群峰算法、遺傳算法、鄰域搜索算法、混沌優(yōu)化算法等一系列智能優(yōu)化算法來求解[1-5]。Sharma 等通過啟發(fā)式算法成功求解了經典運輸問題并得到一個良好的初始化解[6]； Adlakha 等提出了一種簡單的啟發(fā)式算法來解決成本固定的運輸問題，但其求解時間更久[7]；Lotfi 等[8]通過優(yōu)先級編碼的遺傳算法解決運輸問題，在與結合最小生成樹的遺傳算法求解質量對比后，證明了其效率；Molla-Alizadeh-Zavardehi等對比了三種優(yōu)化算法求解可變參數的運輸問題[9]；Kenan 等在2019年建立了Karagul-Sahin 近似方法，使運輸問題的求解時間相較于之前算法下降[10]。早期研究除了會帶來人工運籌學計算的誤差、經驗判斷等缺陷外，還包括神經網絡的大量數據需求、遺傳算法的交叉變異過程、易陷入局部最優(yōu)等計算機算法的工作問題。

海鷗優(yōu)化算法（Seagull Optimization Algorithm，SOA）是Dhiman 等[11]于2019年最新提出的新型元啟發(fā)式優(yōu)化算法，該算法的原理是模擬海鷗在遷徙過程中通過自身位置的不斷變化，朝著最佳位置的方向前進所表現出的較強全局搜索能力，以及海鷗在攻擊獵物過程中通過不斷改變角度和速度產生螺旋運動形狀所具有的較強局部搜索能力優(yōu)化目標函數，該算法的發(fā)明初衷即解決大規(guī)模工程約束問題。故針對運輸問題的特點以及早期研究的缺陷，本研究基于海鷗優(yōu)化算法來解決企業(yè)平衡運輸成本最小化問題，同時為煤礦行業(yè)運輸調度系統(tǒng)管理提供智能解算工具，后續(xù)可推廣至各個行業(yè)的運輸問題求解中。

1 問題模型

1.1 問題描述

物資的運輸調度問題一直是運輸問題研究的重點，其具體文字表述如下：某種物料有多個生產地點和銷售地點，根據每個銷售地點的需求和生產地點的產量，該種物料需要運送到相應的銷售地點，且為了不浪費資源，總產量必須等于總銷量，在了解各生產廠家的產量和各銷售廠家的銷售量以及各生產區(qū)到各銷售區(qū)的單位運輸價格（或運距）后，問如何分配貨物的運輸量和運輸路線，使總運輸成本（或總運輸量）最小，效益最大化[12-14]？

1.2 運輸問題數學模型

1.2.1 傳統(tǒng)運輸問題模型

典型的運輸問題數學模型：設某種產品有m個產地Ai（i=1,2,…,m），有n 個銷地Bj（j=1,2,…,n），將X 設為從產地Ai運往銷地Bj的物資量，從Ai運出的總運量應等于Ai的產量ai，銷地Bj的銷量等于bj，Cij是對應產地與銷地之間的費用，因此Xij應滿足：

所以，總費用為：

運費問題的數學模型如下：

其中，約束條件為：

通常情況下，對于實際問題，不會始終滿足產銷平衡條件，所以常用以下2種方法將不滿足產銷平衡條件的運輸問題轉化為符合產銷平衡條件的產銷平衡運輸問題，其數學模型如下：

1.2.2 B 運輸問題數學模型

B 運輸問題是基于傳統(tǒng)運輸問題在考慮節(jié)約資源、緊急情況約束條件下的特殊運輸問題，在傳統(tǒng)運輸問題上引入了時間，B 運輸問題的數學模型：

1.2.3 D 運輸問題數學模型

隨著社會的進步，網絡的發(fā)展，一些及時供應商品如保鮮產品、節(jié)日物資等要在給定時間之前送達，故D 運輸問題應運而生，在B 運輸問題基礎上，給定一個預警時間t0，D 運輸問題數學模型[15]：

則滿足t0的數學模型為：

1.2.4 JIT 運輸問題數學模型

隨著豐田生產方式的發(fā)展，一種零庫存的JIT（Just In Time）運輸問題被廣泛用于多產地、多物資、多銷地的運輸問題中，在此種模式下，引入了更多的約束條件，包括m個產地不止生產一種物資，而是可以生產ω1，ω2，…，ωk等k種物資，物資ω1從Ai運到Bj所需時間為tijl，運價為Cijl，Xijl表示運量，JIT 運輸問題模型：

綜上所述，運輸問題經歷了由傳統(tǒng)運輸問題——B 運輸問題——D 運輸問題——JIT 運輸問題，其中D 運輸問題是特殊的JIT 運輸問題，即當時，也就是只有一種物資的JIT 問題；而B 運輸問題就是將預警時間設為0 的D 運輸問題的特殊情況；傳統(tǒng)運輸問題同理是時的特殊B 運輸問題。

故本文通過研究傳統(tǒng)運輸問題，便能推導出B運輸問題——D 運輸問題——JIT 運輸問題等后續(xù)延伸出的運輸問題的求解過程。

2 SOA 算法介紹

2.1 SOA 生物學范式

海鷗，學名為落葉松科（拉丁學名：Larus canus），是一種海鳥，一般情況下，喜群居生活。海鷗是非常聰明的鳥，他們可以通過團隊協作順利找到并攻擊獵物。遷移和攻擊行為是海鷗最顯著的特性，其中遷移被定義為為了生存，海鷗從一個地方到另一個地方的季節(jié)性移動，在遷移的同時，它們通過攻擊海上的候鳥，從而達到捕食的目的。在攻擊行為中，海鷗表現的最明顯特征就是做出自然的螺旋形運動，概念模型如圖1所示，使其與目標函數相關聯，便可以完成一系列優(yōu)化過程[16]。后續(xù)內容主要通過研究海鷗的遷移和攻擊兩種自然行為過程，使其與約束條件及目標函數相關聯，進而求解企業(yè)平衡運輸問題[17-22]。

圖1 海鷗的遷徙和攻擊行為示意圖Fig.1 Schematic diagram of seagull migration and attack behavior

2.2 SOA 數學模型

2.2.1 遷移（全局搜索）

海鷗優(yōu)化算法的遷移過程就是該算法的全局搜索過程，主要通過模擬海鷗遷移過程中海鷗群的位置移動。在全局搜索階段，每只海鷗個體必須符合以下三個條件：

（1）避免相互接觸

為了避免與其他海鷗之間相互接觸，通過引入變量A來計算海鷗的新位置（圖2(a)）。

其中：fc是根據題目設置的用來控制變量A的頻率的常數，變量A從fc線性減小到0。在本次運算中，fc的值被設置為2。

（2）向最適合的海鷗方向移動

在避免了海鷗之間的相互接觸后，海鷗朝著最適合的海鷗方向移動（圖2(b)）。

式中：rd∈[0,1]。

靠近最適合的海鷗位置：海鷗移動到不與其他海鷗相撞的位置后，就向著最適合的位置所在方向進行移動，最終到達新位置。

（3）保持接近最佳海鷗位置

最后，海鷗可以更新其相對于最佳海鷗的位置，如圖2(c)所示。

圖2 海鷗遷徙行為和攻擊行為示意圖Fig.2 Schematic diagram of seagull migration and attack behavior

2.2.2 攻擊（局部搜索）

海鷗優(yōu)化算法的攻擊過程就是該算法的局部搜索過程。海鷗的自重和翅膀煽動可以使其在遷移過程中維持平衡，且可以不斷改變攻擊角度和速度。在攻擊獵物時，通過變換螺旋隊形，進行捕食（見圖2（d））。此行為在x、y、z平面中的描述公式如下：

式中：r是螺旋線每一圈的半徑，k是 [0-2π]范圍內的隨機數。u和v是定義螺旋形狀的相關系數，e是自然對數的基。使用公式（18）-（22）計算海鷗的更新位置。

完整的海鷗優(yōu)化算法步驟如下：

SOA 算法從隨機生成的總體開始，在迭代過程中，搜索代理（海鷗）可以更新其相對于最佳搜索代理（最佳海鷗）的位置。變量A從fc線性減小到0，變量B負責實現遷移和攻擊之間的平穩(wěn)過渡。海鷗優(yōu)化算法具有極好的探索和開發(fā)能力，兼具全局搜索、局部搜索的先天優(yōu)勢，故SOA 被認為是一個全局優(yōu)化器。

2.3 算法測試分析及超參數確定

本研究通過10 個基準測試函數對3 個不同的群智能優(yōu)化算法進行對比分析，如表1所示。其中f1、f2、f3、f4、f5是檢驗算法全局探索能力的多峰函數；f6、f7、f8、f9、f10為評估算法尋優(yōu)精度以及收斂速度的單峰函數。

表1 本文選用的10 個測試函數Table 1 Ten test functions selected in this paper

將SOA 算法與標準PSO、GA 算法對比實驗，從而驗證SOA 算法性能。函數變量維數D=30,種群規(guī)模N=100。實驗結果統(tǒng)計30 次運行的最優(yōu)解均值（Mean）和標準差（Std.Dev），具體實驗結果見表2。

從表2可以看出，本文所采用的SOA 算法在8個測試函數上具有較明顯的優(yōu)勢，在f3上的結果雖不具明顯優(yōu)勢，其標準差略高于PSO、GA 算法，但其平均值仍優(yōu)于PSO、GA 算法，在f10上的測試效果一般?？傮w看來海鷗優(yōu)化算法相比于粒子群算法、遺傳算法更具優(yōu)勢。因此可以說明本文采用的SOA算法有較高的尋優(yōu)能力。此外，由10 個對比函數可以看出本文采用的SOA 算法比標準PSO、GA 的尋優(yōu)結果都好，尤其對于f2、f4來說，SOA 的收斂速度提高，因此，本文的SOA 算法求解問題具備更好的性能。

表2 各算法的優(yōu)化結果（D=30,N=100）Table 2 Optimization results of each algorithm (D=30,N=100)

元啟發(fā)式算法在實際應用中的超參數調整被作為主要挑戰(zhàn)，不同的超參數值可能會產生不同的結果，故SOA 算法的參數設置有必要做如下討論：正如現有文獻所闡述的SOA 超參數設置，SOA 算法包含三個超參數，即最大迭代次數、搜索代理數和參數fc，本研究根據現有文獻設置標準設置相關參數。

（1）最大迭代次數：SOA 算法在不同的迭代次數下運行。實驗中[11]使用的Maxitemeration的值為100、500、800 和1000。結果揭示了當迭代次數增加時，SOA 會收斂到最佳狀態(tài)，故本研究取1000。

（2）搜索代理數：為了研究搜索代理數對測試函數的影響，分別對50、80、100 和200 執(zhí)行SOA算法。研究發(fā)現，當搜索代理數量設置為100 時，SOA 提供了最佳的解決方案。

（3）參數fc的變化：SOA 算法是針對參數fc的不同值而運行的，保持其他參數不變，即最大迭代次數和搜索代理數。取不同的fc值，分別為為1、2、3、4 和5。結果表明，當fc的值設為2 時，目標函數獲得最優(yōu)解。

故根據原始參考文獻[11]，以及現有有關于海鷗優(yōu)化算法的文獻[23-27]對于海鷗優(yōu)化算法超參數的測試、選取，本研究在仿真時，令最大迭代次數=1000，搜索代理數=100，fc=2。

3 應用實例

3.1 數據描述

為了驗證應用的SOA 算法可以有效解決企業(yè)平衡運輸問題，通過以下實例說明。

某飲料在國內有三個生產廠家，地處城市 A1，A2，A3，其一級承銷商有四個，地處城市B1，B2，B3，B4，已知各生產廠家的產量、各承銷商的銷售量以及從產地 Ai到銷地 Bj的每噸飲料的運費Cij，為響應綠色供應鏈的要求，公司要求統(tǒng)籌產銷問題，其運價表如表3所示，求運費最小的調運方案？（為了更好地與管理運籌學方法、量子粒子群算法、遺傳算法相比較，表中數據均來自文獻[28-30]。）

表3 運價表Table 3 Tariff table

3.2 結果驗證

由于該案例不涉及時間約束、重大緊急事件等約束，便不需要額外參數，故采用傳統(tǒng)運輸問題模型。

該運輸問題的數學模型如下：

（1）決策變量

設從產地Ai到銷地Bj的運量為Xij；

（2）目標函數

運費最小的目標函數為：

（3）約束條件

即產量之和等于銷量之和，故要同時滿足供應、銷售平衡條件。

供應平衡條件：

X11+X12+X13+X14=5

X21+X22+X23+X24=2

X31+X32+X33+X34=3

銷售平衡條件：

X11+X21+X31=2

X12+X22+X32=3

X13+X23+X33=1

X14+X24+X34=4

因為運量不能為負，所以運量都要滿足以下非負性約束條件：

通過對飲料廠采用SOA 算法求解，應用Matlab對案例企業(yè)途中運輸成本最小化進行軟件求解運算后，得到的最優(yōu)解如表4所示。

表4 最優(yōu)解Table 4 Optimal solution

由表中數據可知，該運輸問題最佳調運方案的成本為34，即3×2+2×1+5×2+4×2+3×2+2×1=34。通過SOA 算法得到的最優(yōu)解與傳統(tǒng)管理運籌學方法、量子粒子群算法、遺傳算法的最優(yōu)解相吻合，都是34，確實驗證了海鷗優(yōu)化算法可以解決企業(yè)平衡運輸成本最小化問題。

SOA 算法參數設置簡單，兼具全局搜索和局部搜索能力，不需要交叉、變異等步驟，提高了智能優(yōu)化算法求解運輸問題的工作效率，與傳統(tǒng)求解成本最小化的方法相比，避免了管理運籌學求解時的人為失誤、有較強的可操作性。將該算法應用在物流運輸成本問題的成本最小化中，具有較好的適應性。

對于本研究以外涉及的B 運輸問題、D 運輸問題、JIT 運輸問題與本研究方法同理操作，只需在運算時多加入對應的約束條件即可，操作較簡單，這里不再贅述。

4 結論

（1）采用了國外最新元啟發(fā)式算法——海鷗優(yōu)化算法求解企業(yè)平衡運輸問題，為今后的企業(yè)平衡運輸問題求解提供了一種新的元啟發(fā)式智能優(yōu)化算法。

（2）海鷗優(yōu)化算法作為新興的啟發(fā)式智能優(yōu)化算法，在企業(yè)傳統(tǒng)平衡運輸問題中的成功應用，開拓了B 運輸問題、D 運輸問題、JIT 運輸問題等多約束問題的解算思路，對智能時代煤礦運輸調度系統(tǒng)管理顯得尤為重要，將為煤礦行業(yè)運輸調度提供參考方法，可持續(xù)推廣至各行業(yè)的成本問題求解中。

（3）仿真結果只是驗證了小規(guī)模的企業(yè)平衡運輸成本問題，對于大規(guī)模的實際案例還需進一步推廣研究。在未來的研究中，可以開發(fā)并行海鷗優(yōu)化算法來自動檢測可用處理器的數量并在其中分配工作負載，從而實現對可用資源的有效利用；OpenMP庫可用于提高當前海鷗優(yōu)化算法的性能和效率；還可以開發(fā)SOA 算法的二進制和多目標版本來解決大規(guī)模的實際工程問題。

利益沖突聲明

所有作者聲明不存在利益沖突關系。