基于粒子群算法的易逝品供應(yīng)物流網(wǎng)絡(luò)優(yōu)化

梁瑞偉

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

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

韓世蓮等定義了客戶等待時(shí)間的含義及目標(biāo)規(guī)劃的原理，對(duì)帶時(shí)間窗的多目標(biāo)物流配送線路優(yōu)化問題建立了一個(gè)線性規(guī)劃模型。在模型建立時(shí)考慮了運(yùn)輸費(fèi)用最小、運(yùn)輸時(shí)間最短和所有客戶的等待時(shí)間最短三個(gè)相互沖突的目標(biāo)。

王海麗等以帶時(shí)間窗的車輛配送規(guī)劃模型為基礎(chǔ)，以制冷成本、車輛固定成本和運(yùn)輸成本之和的總成本為目標(biāo)函數(shù)，建立了一個(gè)關(guān)于易腐食物品的冷藏配送模型。在求解的算法設(shè)計(jì)上，構(gòu)造了一個(gè)基于鄰域搜索的節(jié)約算法。

陳軍等研究了由于采購聯(lián)盟間成員信息的不完全與不對(duì)稱。各成員均將對(duì)方的期望需求作為對(duì)方的實(shí)際需求進(jìn)行估計(jì)。針對(duì)易逝品采購與運(yùn)輸?shù)奶攸c(diǎn)，提出了關(guān)于調(diào)劑價(jià)格的特殊約束條件并建立了一個(gè)聯(lián)盟期望利潤(rùn)模型，最后用數(shù)值進(jìn)行了仿真。

王海軍等根據(jù)應(yīng)急物流的特點(diǎn)，將模擬退火算法用于應(yīng)急物流的車輛調(diào)度研究之中并通過實(shí)例將模擬退火算法和免疫算法進(jìn)行了比較，證明了用模擬退火算法來優(yōu)化車輛行駛路徑的可行性和全局最優(yōu)性。

問題提出

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

數(shù)學(xué)建模

在建立該問題的數(shù)學(xué)模型之前?；诹Ｗ尤核惴ǖ奶卣?，為方便建模與優(yōu)化運(yùn)算，設(shè)定參數(shù)和決策變量如下：

CO_ij-企業(yè)從供應(yīng)商i處采購的j種物料的單價(jià)；

Q_j-企業(yè)需要采購的第j種物料的數(shù)量；

Cl_ijk-從供應(yīng)商i處采購的j種物料運(yùn)送至中轉(zhuǎn)站k處的運(yùn)費(fèi)單價(jià)；

C2_jk-從中轉(zhuǎn)k站處將第j種物料運(yùn)送至企業(yè)的運(yùn)費(fèi)單價(jià)；

T_ik-表示從企業(yè)i到中轉(zhuǎn)站j的運(yùn)輸時(shí)間，各物料所需時(shí)間相同；

T_j-表示將第種物料運(yùn)送至選定的中轉(zhuǎn)所需的時(shí)間；

T_k-物料從中轉(zhuǎn)站k運(yùn)送至企業(yè)所需的時(shí)間；

a_j-單位時(shí)間內(nèi)物料價(jià)值損失占物料總價(jià)值的百分比；

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

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

其中下標(biāo)含義為：i為供應(yīng)商索引號(hào)（u=1，2，…，I），j為企業(yè)所需原材料索引號(hào)（j=1，2，…，J），k為中轉(zhuǎn)站索引號(hào)（k=1，2，…，K）。

在定義了上述參數(shù)符號(hào)之后，可建立該供應(yīng)物流網(wǎng)絡(luò)模型的總成本目標(biāo)函數(shù)。該總成本函數(shù)由四部分構(gòu)成：購成本，第一次運(yùn)輸成本，第二次運(yùn)輸成本，運(yùn)輸時(shí)間損耗成本。（忽略中轉(zhuǎn)費(fèi)用和中轉(zhuǎn)時(shí)間）：

約束條件為：

算法設(shè)計(jì)

在本模型中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個(gè)0，1決策變量，且這些決策變量需要滿足，這兩個(gè)約束條件。也就是說這i*j+k個(gè)0，1決策變量中可行解必然是含有J+1個(gè)1，而其它決策變量均為O。其中前面J個(gè)1分別確定每種原材料的供應(yīng)商，最后一個(gè)1確定所選擇的中轉(zhuǎn)站。

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

該方法主要是在計(jì)算粒子最優(yōu)值時(shí)做了一些特殊的處理以使每個(gè)粒子均滿足約束成為可行解。

實(shí)例仿真

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

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

從表5-5中可知，三種粒子群算法均能穩(wěn)定的收斂到全局最優(yōu)解，而在30次實(shí)驗(yàn)中，兩種改進(jìn)的粒子群算法收斂到最優(yōu)解的平均迭代次數(shù)均比標(biāo)準(zhǔn)粒子群算法所需要的平均迭代次數(shù)少，說明改進(jìn)的粒子群算法在求解該實(shí)例中的收斂速度要比標(biāo)準(zhǔn)粒子群算法快。

即A物料選擇在供應(yīng)商三處采購；B物料選擇在供應(yīng)商一處采購；c物料在供應(yīng)商三處采購，選擇中轉(zhuǎn)站二為物料中轉(zhuǎn)集中運(yùn)輸中轉(zhuǎn)站。

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

運(yùn)輸成本為：56，25（萬元）

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

總成本為：747.6375（萬元）

用窮舉例法本實(shí)例有81種方案，該結(jié)果與窮舉法獲得的最優(yōu)方案相同。

本文首先提出了易逝品的供應(yīng)物流網(wǎng)絡(luò)優(yōu)化問題，其后基于粒子群算法對(duì)該問題建立了各數(shù)學(xué)模型，最后用粒子群算法來求解了該模型，比較了三種粒子群算法在該實(shí)例的收斂速度，并將粒子群算法獲得的方案與用窮舉法算出的結(jié)果進(jìn)行比較，說明了用粒子群算法對(duì)該問題的整套解決方案是有效的。