徐博文，程 然

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070）

1 引言

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

2 模型建立

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

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

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

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

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

部分指數(shù)如下：

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

部分參數(shù)如下：

W：總成本；

γ：影響因子；

nk：車輛承載零售商的數(shù)量；

bk：車輛載重；

：車輛從零售商j1到零售商j2產(chǎn)生的物料成本；

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

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

rkj：運送路徑；

Vislk：車輛視野。

相應(yīng)成本函數(shù)[6]如下：

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

2.1 精確模型建立

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

2.2 模糊模型建立

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

步驟1：令E=0;

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

步驟3：

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

步驟4：在區(qū)間[a,b]隨機(jī)產(chǎn)生r;

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

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

步驟7：重復(fù)第4步到第6步N次;

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

EVM模型如下：

式（11）是數(shù)學(xué)模型的目標(biāo)函數(shù),目的是使期望值總和最?。皇剑?2）保證每條路徑上的各商店的總期望不超過此條路徑配送車容量；式（13）表示每條路徑服務(wù)的商店期望不超過總商店數(shù)；式（14）要求每個商店都得到車輛的配送服務(wù)；式（15）表示每條路徑的商店個數(shù)；式（16）表示每個商店有唯一的車輛為之服務(wù)；式（17）表示檢測車輛是否需要進(jìn)行二次運輸。

3 人工魚群算法（AFSA）

由于該分配網(wǎng)絡(luò)問題的NP-HARD特性，本文探討啟發(fā)式算法作為求解方法，選擇了一種適應(yīng)該分配網(wǎng)絡(luò)的人工魚群算法[7]并進(jìn)行相應(yīng)改進(jìn)來求解上述模型。

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

3.1 AFSA幾種典型行為

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

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

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

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

3.2 AFSA中一些特殊的用法

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

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

3.3 魚群算法中的主要函數(shù)

魚群算法主要函數(shù)見表1。

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

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

步驟1:初始化解空間；

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

步驟3:更新公告欄數(shù)據(jù)；

步驟4:檢查終止條件；

步驟5:優(yōu)化數(shù)據(jù)，循環(huán)步驟2-步驟4；

步驟6:輸出結(jié)果。

4.1 算法設(shè)計

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

4.1.1 覓食行為。在當(dāng)前車輛視野Visual內(nèi)隨機(jī)移動到新的位置作為下一步移動的方向公告欄更新數(shù)據(jù)并進(jìn)行下一個零售商的行為選擇。

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

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

4.2 改進(jìn)及優(yōu)化

可以發(fā)現(xiàn)，人工魚群算法在運算初期具有很強(qiáng)的收斂性；隨著算法的運算過程，收斂速度有所下降，此時可以采用改進(jìn)視野、分段優(yōu)化、混合優(yōu)化等方法提升其后期收斂性。

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

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

圖1 函數(shù)α 變化圖

圖2 視野變化圖

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

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）組成的配送系統(tǒng)進(jìn)行研究，各零售商的期望分別為（327.5；236.5；207.5；329；439.5；492；315.5；148；516；557；417；328.5；218.5；111.5；356），相應(yīng)的庫存分布方案見表2。

表2 庫存分布方案

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

表3 最優(yōu)路徑數(shù)據(jù)對比

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

6 結(jié)語

本文通過對IRP問題下的子問題-運輸路徑問題的相關(guān)分析及建立相應(yīng)模型并實踐計算，得到了如下結(jié)論：

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

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

（3）對以人工魚群算法為基礎(chǔ)的啟發(fā)式算法進(jìn)行相應(yīng)的改進(jìn)和優(yōu)化，使之應(yīng)用于運輸路徑問題，是可行有效的。

（4）改進(jìn)優(yōu)化視野和步長可以提高人工魚群算法局部搜索能力及運算結(jié)果的精度。

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