基于粒子群算法的易逝品供應物流網絡優化

梁瑞偉

在對易逝品的采購與運輸規劃的過程中，不但要考慮其采購成本，運輸成本，而且還要考慮其時間成本。在很多情況下，時間成本甚至是更具決定意義的一個因素。本文依托湖南省教育廳科技處項目（項目編號1lc0926）對一個典型的易逝品采購問題建立了基于粒子群算法的數學模型，并用標準粒子群算法和改進的粒子群算法對其進行了求解，說明了用粒子群算法對該問題的整套解決方案是有效的。

在現實生活中有些物品其價值隨著時間的流逝其價值逐漸減少。我們稱這類物品為易逝品。像時裝、電子元件等，其時效性很強，一段時間后由于新產品的出現使其價值迅速降低；蔬菜、水果、肉類等，對它們進行保鮮不易而且所需要的成本很高高，存在著時間成本。因此在對易逝品的采購與運輸規劃的過程中，不但要考慮其采購成本，運輸成本，而且還要考慮其時間成本。在很多情況下，時間成本甚至是更具決定意義的一個因素。

韓世蓮等定義了客戶等待時間的含義及目標規劃的原理，對帶時間窗的多目標物流配送線路優化問題建立了一個線性規劃模型。在模型建立時考慮了運輸費用最小、運輸時間最短和所有客戶的等待時間最短三個相互沖突的目標。

王海麗等以帶時間窗的車輛配送規劃模型為基礎，以制冷成本、車輛固定成本和運輸成本之和的總成本為目標函數，建立了一個關于易腐食物品的冷藏配送模型。在求解的算法設計上，構造了一個基于鄰域搜索的節約算法。

陳軍等研究了由于采購聯盟間成員信息的不完全與不對稱。各成員均將對方的期望需求作為對方的實際需求進行估計。針對易逝品采購與運輸的特點，提出了關于調劑價格的特殊約束條件并建立了一個聯盟期望利潤模型，最后用數值進行了仿真。

王海軍等根據應急物流的特點，將模擬退火算法用于應急物流的車輛調度研究之中并通過實例將模擬退火算法和免疫算法進行了比較，證明了用模擬退火算法來優化車輛行駛路徑的可行性和全局最優性。

問題提出

在這里考慮一家企業向I家供應商采購J種物料（這些物料為易逝品）經過K個中轉站中的某一個集中將物料運送至企業，每種物料的價值以單位時間a_j的速率遞減；公司需要確定采購每種物料的供應商以及中轉站，以使采購成本、運輸成本以及物料價值按時間的損耗成本之和最小。該問題可用窮舉法尋找最優方案，需要比較的方案為I^J*K個，其復雜程度與供應商、采購原材料種數呈指數增長，與中轉站個數呈倍數增長。

數學建模

在建立該問題的數學模型之前。基于粒子群算法的特征，為方便建模與優化運算，設定參數和決策變量如下：

CO_ij-企業從供應商i處采購的j種物料的單價；

Q_j-企業需要采購的第j種物料的數量；

Cl_ijk-從供應商i處采購的j種物料運送至中轉站k處的運費單價；

C2_jk-從中轉k站處將第j種物料運送至企業的運費單價；

T_ik-表示從企業i到中轉站j的運輸時間，各物料所需時間相同；

T_j-表示將第種物料運送至選定的中轉所需的時間；

T_k-物料從中轉站k運送至企業所需的時間；

a_j-單位時間內物料價值損失占物料總價值的百分比；

S_ij-表示中物料j是否在供應商處i采購，是則S_ij=1否則S_n=0；

D_k-中轉站k是否為本次采購方案選定的中轉站是則D_k=1否則D_k=0；

其中下標含義為：i為供應商索引號（u=1，2，…，I），j為企業所需原材料索引號（j=1，2，…，J），k為中轉站索引號（k=1，2，…，K）。

在定義了上述參數符號之后，可建立該供應物流網絡模型的總成本目標函數。該總成本函數由四部分構成：購成本，第一次運輸成本，第二次運輸成本，運輸時間損耗成本。（忽略中轉費用和中轉時間）：

約束條件為：

算法設計

在本模型中CO_ij、C1_ijk、C2_jk、T_ik、T_k、Q_j、a_j均為已知變量，T_j為中間變量，只有S_ij和D_k為決策變量，而且S_ij和D_k均為0，1變量，總共有I*J+K個0，1決策變量，且這些決策變量需要滿足，這兩個約束條件。也就是說這i*j+k個0，1決策變量中可行解必然是含有J+1個1，而其它決策變量均為O。其中前面J個1分別確定每種原材料的供應商，最后一個1確定所選擇的中轉站。

粒子群算法最初是用于求解連續性優化問題的，對這種0，1型離散性優化問題有對應的二進制粒子群算法來解決。但考慮到本模型中約束的特點，可對連續型粒子群算法稍做變換然后用來求解該問題將會十分便捷。用連續型粒子群算法來優化該問題的具體步驟可如下：初始化，每個粒子為I*J+K維，均取（0，1）之間的隨機值，并把它分成J行I列加1行K列的兩個矩陣，按此方法同樣對速度進行初始化；計算粒子的適應值。對每個粒子先將其每行最大元素置為1，其他元素值為0，讓后按照式（5.1）計算出其適應值；找出每個粒子歷史最優與群體最優粒子；更新粒子位置；更新粒子速度；按照步驟2）計算更新后粒子的適應值，更新粒子歷史最優與群體最優；判斷是否滿足終止條件，是則終止計算輸出結果，否則轉移到第四步。

該方法主要是在計算粒子最優值時做了一些特殊的處理以使每個粒子均滿足約束成為可行解。

實例仿真

考慮一家電子廠需要從三個供應商S₁、S₂、S₃中采購三種電子元件A、B、C經過三個中轉站D₁、D₂、D₃中的某個中轉站中轉然后集中將物料運送至工廠E。其中物料隨時間損耗比率為a_j=0.25%/天其它相關數據如表5-1——表5-4所示：

公司需要制定一個采購方案從這三家供應商處采購三種原材料并選擇合適的中轉站以使采購成本、運輸成本、時間損耗成本之和最小。本文將用粒子群算法計算上述模型并用matlable語言編寫程序，最終解決該問題。在該實例中每個粒子的維數為I*J+K=3*3+3=12設定種群規模為20，迭代代數為500代。用三種粒子群算法計算，通過30次實驗，獲得收斂到最優解的平均迭代次數如表5-5所示，最優方案方案如表5-6，表5-7所示。

從表5-5中可知，三種粒子群算法均能穩定的收斂到全局最優解，而在30次實驗中，兩種改進的粒子群算法收斂到最優解的平均迭代次數均比標準粒子群算法所需要的平均迭代次數少，說明改進的粒子群算法在求解該實例中的收斂速度要比標準粒子群算法快。

即A物料選擇在供應商三處采購；B物料選擇在供應商一處采購；c物料在供應商三處采購，選擇中轉站二為物料中轉集中運輸中轉站。

該方案采購成本為：652.5（萬元）

運輸成本為：56，25（萬元）

物料隨時間的損耗成本為：35.8875（萬元）

總成本為：747.6375（萬元）

用窮舉例法本實例有81種方案，該結果與窮舉法獲得的最優方案相同。

本文首先提出了易逝品的供應物流網絡優化問題，其后基于粒子群算法對該問題建立了各數學模型，最后用粒子群算法來求解了該模型，比較了三種粒子群算法在該實例的收斂速度，并將粒子群算法獲得的方案與用窮舉法算出的結果進行比較，說明了用粒子群算法對該問題的整套解決方案是有效的。