周 曉

福建江夏學院工商管理學院，福州，350108

1 相關研究與問題提出

物流網絡是由若干物流節(jié)點以及連接這些節(jié)點的運輸線路構成的。一旦建設成形，網絡基礎設施和設備在較長的一段時期內不會發(fā)生改變，各線路和節(jié)點的最大物流處理能力會對所流經物流量的大小產生約束，進而影響到整個物流網絡流量的分布。隨著多品種、小批量的物流需求特性日益突出，如何有效降低物流成本成為社會和企業(yè)要解決的關鍵問題。在已有物流網絡資源條件下，對于具有較大物流處理能力的跨區(qū)域網絡，可以通過規(guī)模經濟效應有效提高網絡資源利用率，從而達到降低成本的目的。此時，物流總成本是物流量的凹函數(shù)，但是，對于區(qū)域內部的物流網絡，與跨區(qū)域網絡相比，由于網絡能力約束比較苛刻，物流量分布比較分散，規(guī)模經濟效應難以實現(xiàn)，單位物流成本往往隨著物流量的增加而增加，物流總成本往往表現(xiàn)為物流量的凸函數(shù)形式。物流成本是影響物流網絡流量分配的決定因素，因此，綜合考慮物流網絡的混合凹凸成本屬性和網絡能力約束，對物流網絡流量進行分配優(yōu)化研究，具有現(xiàn)實意義。

在現(xiàn)有的相關研究中，物流網絡的流量分配問題往往是綜合在物流設施選址問題中進行研究的，針對該問題已出現(xiàn)了大量的研究成果[1-7]。多數(shù)學者是從算法優(yōu)化的角度尋求設施選址問題的最佳求解方法，比如，以無容量約束的設施選址問題為研究對象，Watanabe采用人工蜂群算法[1]，akir提出了模糊c-均值(FCM)算法[2]，Heidari提出了改進的粒子群優(yōu)化算法[3]分別對該問題進行求解。Armas考慮了客戶需求和服務成本的不確定性，提出了一種啟發(fā)式算法對隨機無容量約束的設施選址問題進行研究[4]。針對無容量限制和有容量限制的二級設施選址問題，Litvinchev和Fernandes分別提出了拉格朗日啟發(fā)式算法[5]和遺傳算法[6]的求解方法。Qin結合庫存決策問題來分析多商品物流網絡設計問題，重點分析了物流節(jié)點的庫存費用，并給出了節(jié)點的容量約束[7]，但是沒有考慮線路的容量約束。這些研究多以成本最小化作為問題的優(yōu)化目標，但是往往忽略了物流的規(guī)模效應以及容量約束對成本的影響。

本文根據(jù)不同的物流成本特性將物流網絡分成兩級，在考慮線路和節(jié)點容量限制的基礎上，對整體物流網絡的流量分配優(yōu)化問題進行建模，并給出一種雙層遺傳算法進行模型求解。最后，通過算例驗證該算法的有效性。

2 問題描述與數(shù)學模型

將物流網絡簡化為簡單二級網絡結構，第一級網絡實現(xiàn)供應節(jié)點至中間節(jié)點的區(qū)域之間的貨物流動?？紤]規(guī)模經濟效應，第一級網絡物流成本是物流流量的凹函數(shù)。第二級網絡實現(xiàn)貨物由中間節(jié)點至各需求節(jié)點的區(qū)域內的分配。第二級網絡由于規(guī)模操作性較前級網絡大大降低，加上該級網絡資源的能力約束，物流成本表現(xiàn)為物流流量的凸函數(shù)。針對上述二級物流網絡結構，進行物流流量的分配優(yōu)化研究，確定通過各中間節(jié)點的物流流量，供應節(jié)點至中間節(jié)點，中間節(jié)點至需求節(jié)點之間各路徑的物流流量，目標是實現(xiàn)整體網絡物流成本的最小化。

問題的假設條件設定如下：

(1)由于不平衡供需問題可以通過增加虛擬供應/需求節(jié)點將問題轉化為平衡問題，因此，為簡化問題，假設供應總量與需求總量相等；

(2)不考慮中間節(jié)點發(fā)生的物流成本；

(3)網絡中所有貨物都必須經過中間節(jié)點，無法直接由供應節(jié)點至需求節(jié)點；

(4)中間節(jié)點之間無物流流量分配；

(6)物流節(jié)點滿足流量守恒條件。

問題的數(shù)學模型構建如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中，式(1)表示將第一級網絡和第二級網絡的物流成本綜合考慮，以整體網絡的物流總成本作為問題的目標函數(shù)，實現(xiàn)其最小化。式(2)和式(3)分別是供應和需求約束。式(4)和式(5)是中間節(jié)點的物流處理能力約束。式(6)是流量守恒約束。式(7)是路徑容量約束。式(8)是網絡物流流量的非負整數(shù)約束。

3 模型求解

具有凹費用特性和容量約束的物流網絡流量分配優(yōu)化問題是最小凹費用問題，屬于NP-難問題[9]。以此問題為子問題的具有非線性凹凸費用的二級物流網絡流量分配優(yōu)化問題也屬于NP-難問題，常規(guī)方法求解困難。問題的關鍵在于如何確定中間節(jié)點的物流流量分配，在此基礎上便可以確定各級網絡的物流流量分配。結合問題特性，設計出雙層遺傳算法對模型進行求解。內層優(yōu)化算法應用于第一級和第二級網絡的物流流量獨立分配優(yōu)化；外層優(yōu)化算法通過確定中間節(jié)點流量分配，結合內層優(yōu)化算法，實現(xiàn)整體物流網絡的流量分配優(yōu)化。

3.1 外層優(yōu)化算法

3.1.1 染色體編碼

3.1.2 群體初始化

用內層優(yōu)化算法分別對兩級網絡的物流流量分配問題進行求解。其中，初始中間節(jié)點流量M′=M。進而分別得到各級網絡的最優(yōu)解X1和X2以及相應的M′(X1),M′(X2)。

初始群體生成方法如下：

Step1:M′←θ1M′(X1)+θ2M′(X2)。θ1,θ2是隨機數(shù)，滿足θ1+θ2=1;

Step2:用內層優(yōu)化算法分別對兩級網絡的進行求解；

Step3:循環(huán)以上兩步驟，直至個體數(shù)量滿足要求為止。

3.1.3 選擇機制和適應函數(shù)

由于(μ+λ)選擇策略在搜索過程中不僅能夠保留最佳個體，而且能夠加速算法收斂[10]，所以采用該策略作為群體中個體之間的競爭機制，即在μ個父代個體以及由這μ個父代個體交叉產生的λ個子代個體中選擇μ個適應性最佳個體。算法以目標函數(shù)值，即整體網絡的物流總成本作為個體的適應函數(shù)。

3.1.4 交叉操作

λ1←(f11+f21)/(F1+F2)

λ2←(f12+f22)/(F1+F2)

3.1.5 變異操作

3.2 內層優(yōu)化算法

3.2.1 染色體編碼

由于問題的可行解表示滿足各項約束條件的物流網絡流量分布方式，所以用X={xijk|?i,?j,?k}代表染色體，xijk代表染色體基因，表示節(jié)點i至節(jié)點j的第k條路徑上的物流流量。對于第一級網絡，i,j,k分別代表r,w,p；對于第二級網絡i,j,k分別代表r,w,q。

3.2.2 群體初始化

為了加快算法的收斂速度，在包括最優(yōu)解的可行域內選擇初始群體。通過對文獻[11]中介紹的啟發(fā)式方法增加路徑約束，得到如下初始可行個體的求解方法：

step1:xijk,yijk←0；

step2:yijk←min(Ui,Vj,Cijk)+yijk；

step3:Pijk←argmin{f(yijk,Lijk)/yijk|yijk≠0}；

step4:xijk←yijk；

step5:Ui←Ui-yijk,Vj←Vj-yijk,Cijk←Cijk-yijk；

step6:循環(huán)step2-step5，直至所有物流量分配完畢。

為了實現(xiàn)群體的多樣性，群體中大多數(shù)的個體通過對初始個體進行變換得到，其他少數(shù)剩余個體通過隨機選擇路徑進行流量分配得到。變換操作的具體思路是任意選擇若干條流量為0的路徑，根據(jù)閉回路法找到包含每條路徑的回路或者與其平行的路徑，繼而可以由回路中各路徑流量或者平行路徑流量以及各路徑的容量限制確定所選擇路徑的流量大小，回路中其他路徑或者平行路徑的流量相應進行增減。顯然，所得初始群體均為問題的可行解。

3.2.3 選擇機制和適應函數(shù)

選擇機制與外層優(yōu)化算法相同，適應函數(shù)取子網絡的物流成本函數(shù)。

3.2.4 交叉操作

依據(jù)參考文獻[12]提出的交叉方法，內層優(yōu)化算法的交叉方法設計如下：對于個體X1和X2，取X2中流量不為0，且X1中流量為0的所有路徑的一半作為X1的變換路徑，對其執(zhí)行前面介紹的變換操作。變換路徑的選擇是根據(jù)下式進行的：

(9)

即，取αijk值小的路徑優(yōu)先進行變換。

3.2.5 變異操作

變異操作在一定變異概率下通過隨機選擇子代個體中流量為0的路徑進行變換操作來實現(xiàn)。當變異的個體為子種群中的最佳個體時，同樣采用(1+1)選擇策略。

4 算例驗證

表1 第一級物流網絡的路徑容量和長度

表2 第二級物流網絡的路徑容量和長度

通過一系列的測試確定算法參數(shù)取值如下：交叉概率為0.9，變異概率為0.1；內層優(yōu)化算法μ=100，λ=200，迭代次數(shù)500；外層優(yōu)化算法μ=50，λ=100，迭代次數(shù)100。對算法進行多次運行后得到的部分計算結果如表3所示。由表3可知，該算例的最優(yōu)目標值為51 605單位費用，相應的物流網絡流量最優(yōu)分配方案如表4所示。

表3 部分計算結果

表4 物流網絡流量的最優(yōu)分配方案

5 結 論

規(guī)模經濟效應是影響多品種、小批量需求特性下物流網絡流量分配方式的重要因素。規(guī)模經濟效應表現(xiàn)為單位物流成本隨著物流量的增加而減少，物流總成本是物流量的凹函數(shù)。物流線路和節(jié)點的能力約束是影響物流網絡流量分配的另一個重要因素。當網絡能力約束比較苛刻，并且物流量分布比較分散時，規(guī)模經濟效應難以實現(xiàn)，單位物流成本往往隨著物流量的增加而增加，物流總成本是物流量的凸函數(shù)。本文以二級物流網絡為研究對象，在詳細分析各級物流子網絡特征的基礎上，建立了物流網絡流量分配優(yōu)化模型，該模型考慮了物流網絡節(jié)點和線路的容量約束與運輸?shù)囊?guī)模經濟效應對成本的影響，將物流總成本定義為流量的混合非線性函數(shù)，并給出了一種雙層遺傳算法對模型進行求解。該算法由求解各級物流子網絡的流量分配方案的內層算法和求解連結兩級子網絡的中間節(jié)點的流量分配方案的外層算法所構成，通過兩層算法的不斷迭代運行，最終得到優(yōu)化結果。最后，用算例驗證了模型和算法的有效性。