多種運輸方式的4PL多到多網絡設計模型與算法

李 銳，孫福明

遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001

1 引言

物流業務外包已經成為許多企業提高自身的核心競爭力的有效途徑。隨著經濟全球化的發展，往往需要多個物流公司合作才能完成一項物流任務。由于能夠整合不同的第三方物流（3PL）資源，依靠其信息方面的優勢，解決單獨靠一家3PL不能完成的任務，第四方物流[1]（4PL）開始得到關注。在運作過程中，4PL需要根據需求設計合理的物流網絡來提供有效的物流服務。現實中，很多情況需要承擔多個確定的供需點對之間的配送任務，即多到多的配送任務。目前，4PL網絡設計問題已經得到一定的研究[2-4]。然而，這些研究都是考慮4PL承擔某種產品的配送或回收任務。

此外，3PL運輸供應商可能提供多種運輸方式供選擇，所以在4PL網絡設計過程中需要同時考慮選擇3PL運輸商及運輸方式。可見，研究多種運輸方式的4PL多到多網絡設計問題具有現實意義。目前，國內外學者已經對考慮多種運輸方式的物流及運輸相關問題進行了研究。Ghorbani[5]研究配送網絡的選址庫存問題，并考慮多種運輸方式和3PL運輸供應商。Haddad-Sisakht等[6]研究不確定下考慮多種運輸方式的閉環供應鏈網絡設計問題。Masoud等[7]研究多種運輸方式對汽車供應鏈可持續性的影響。郭等[8]對多種運輸模式下的生產運輸問題進行了研究。然而，考慮多種運輸方式的4PL多到多網絡設計問題則還沒有得到關注。

本文研究考慮多種運輸方式的4PL多到多網絡設計問題。與現有4PL網絡設計問題不同，文中在4PL承擔多供需點對物流配送任務情況下同時考慮3PL具有多種運輸方式，建立問題的數學優化模型，并設計混合蛙跳算法求解。最后，通過仿真實驗來驗證模型的合理性及算法的有效性。

2 問題描述及模型

考慮4PL負責多個供需點對之間產品的物流配送任務，并通過3PL服務節點和3PL運輸供應商來完成，其中每個3PL運輸供應商提供多種運輸方式。多到多配送下的4PL網絡可表示為無向多重圖，如圖1所示。網絡的節點包括供應點、需求點和3PL服務節點（配送中心、倉庫等），網絡的邊表示3PL運輸供應商。多種運輸方式的4PL多到多網絡設計問題是通過選擇3PL服務節點、3PL運輸供應商及運輸方式來確定網絡結構，在各個供需點對的配送時間滿足要求的條件下，最小化網絡總成本。

圖1 多到多配送下的4PL網絡

2.1 符號說明

問題模型的相關集合、參數及決策變量分別如表1和表2所示。

2.2 優化模型

基于以上符號說明和變量定義，建立多種運輸方式的4PL多到多網絡設計優化模型如下：

（1）目標函數

表1 集合及參數

目標函數式（1）最小化總的物流成本，包括3PL服務節點、3PL運輸供應商某種運輸方式的開設成本，所有供需對點之間產品的運輸和處理成本。

（2）配送時間約束

式（2）要求所有供需點對的配送時間不大于β，其中包括處理時間和運輸時間。

（3）配送路徑的連通性約束

表2 決策變量

約束式（3）和式（4）表示如果3PL服務節點被選擇服務于供需點對p，則必須有與其連接的3PL運輸供應商的一種運輸方式被選擇來運出和運入產品；否則，沒有3PL運輸供應商或運輸方式被選擇；約束式（5）、（6）分別要求供需點對p的供應點和需求點必須通過3PL運輸供應的某種運輸方式來運出和運入產品。

（4）能力約束

式（7）和（8）分別為3PL服務節點和3PL運輸供應商某種運輸方式的能力約束，并要求被選擇服務于供需點對之間配送路徑的3PL服務節點和3PL運輸供應商的某種運輸方式必須是已開設的。

（5）決策變量約束

式（9）～（12）表示二值的0-1決策變量。

3 算法設計

考慮多種運輸方式的4PL多到多網絡設計問題是傳統設施選址問題的擴展，因此也是NP-hard問題。在問題規模較大的情況下，求解很困難，所以智能優化算法更適合對該問題進行求解。本文設計混合蛙跳算法對問題進行求解。

混合蛙跳算法將種群個體視為青蛙，整個種群由多個子群構成。子群中個體進化是通過青蛙的三次跳躍操作更新實現的。目前，SFLA已經得到一定的研究[9]，并在圖像分割[10]、作業車間調度[11-12]、車輛路徑[13]、光伏模型識別[14]、電源規劃[15]、云資源配置和工作流調度[16]、無線傳感器網絡節點三維定位[17]等問題中得到應用。

本文根據問題的特點設計SFLA進行求解，通過向量對青蛙個體進行編碼。同時，為了滿足配送路徑的連通性約束，分別設計初始種群生成方法和青蛙的跳躍操作。

3.1 混合蛙跳算法步驟

混合蛙跳算法步驟如下：

步驟1生成含有F個青蛙的初始群體Pop0={X1,X2,…,XF}（詳見3.3節），并按3.5節方法計算青蛙（解）Xi的評價函數值 f( )Xi。

步驟2將群體劃分為M個族群，Pop={P1,P2,…,PM}。將青蛙按照評價函數值從小到大排序，并依次逐一循環分配給M個族群，每個族群Pk由N個青蛙組成，即

步驟3對每個族群執行深度局部搜索，具體過程如下：

重復上述過程，直到達到設定的更新迭代次數。

步驟4將所有族群的個體混合，確定全局最好個體；如果滿足終止條件，則執行步驟5，否則，轉到步驟2。

步驟5輸出最好解。

3.2 個體的編碼與解碼

青蛙個體可由一組向量來表示。向量的數量為供需點對的數量。每個向量表示供需點對之間的一條路徑。如圖2所示，每個向量由三部分組成，其中第一部分表示節點的選擇情況，每一位表示路徑可能經過的節點（需求點除外），取值為“0”表示該節點沒有在路徑上，取“非0”值表示該節點在路徑上，并且下一個節點為其值對應的節點；第二部分表示路徑可能經過的節點之間3PL運輸供應商的選擇情況，“0”表示沒有供應商被選擇，“非0”表示其值對應的供應商被選擇；第三部分表示運輸方式的選擇情況，每一位表示某兩個節點之間3PL供應商的運輸方式的選擇情況，“0”表示沒有運輸方式被選擇，“非0”表示其值對應的運輸方式被選擇。值得注意的是，因為不同的供應點或需求點與3PL服務節點之間的連接情況不同，所以不同路徑所對應的向量維數可能不同。

圖2 個體向量的表示

根據上述編碼規則，給定向量的取值可以唯一確定對應的路徑，進而可以確定變量和的值，再由約束式（7）和式（8）即可確定解 xijkm和 yi。

3.3 初始種群的生成

按照3.2節中青蛙個體的編碼方式，隨機生成初始種群。為了滿足路徑的連通性約束式（3）～（6），按照下列步驟產生個體的向量：

步驟1生成向量的節點部分。從供應點vs對應位開始，依次隨機確定路徑經過的節點及節點對應位的數值。如果某節點的下一個節點都已經是路徑上的節點，則返回到供應點，并重新確定節點部分，直到到達需求點vl。如果某節點的下一個節點包含需求點，則其對應位的取值為需求點。

步驟2根據路徑經過的節點順序，依次隨機選擇3PL運輸供應商，確定對應位的值。

步驟3根據3PL供應商的選擇情況，依次找到被選擇3PL供應商的對應位，并隨機選擇運輸方式，確定對應位的值。

3.4 跳躍操作

青蛙在1次和2次跳躍過程中，根據族群Pk最差個體與族群最好個體（或全局最好個體）來產生新個體。在產生新個體的過程中，為了滿足路徑的連通性約束式（3）～（6），新個體的第 p 個向量由個體與或的對應向量與（或按照如下步驟生成：

步驟1對于向量的節點部分執行交叉操作：從供應點vs對應位開始，根據路徑經過的節點按式（13）依次執行節點對應位 j的交叉操作。在交叉過程中，如果與（或）中對應位的值為需求點，則取值為需求點；如果對應位的值分別為“0”和“非0”，則取“非0”值。如果中對應位的值為需求點，則停止交叉過程。

式中rand表示[ ]0,1之間隨機數。

步驟2根據路徑經過的節點次序，按照式（14）確定3PL運輸供應商部分對應位 j的值。設路徑經過的某兩個節點之間有ξj個3PL運輸供應商，那么對應位的取值范圍為 1,2,…,ξj。如果中對應位的值小于1，則取1；如果對應位的值大于ξj，則取ξj。式中，round表示四舍五入取整。

步驟3根據路徑經過的節點次序和被選擇的3PL運輸供應商，再按照式（14）確定運輸方式部分對應位的值。設路徑選擇的某個3PL運輸供應商提供的運輸方式數量為τ，那么對應位的取值范圍為1,2,…,τ。如果中對應位的值小于1，則取1；如果對應位的值大于τ，則取τ。

3.5 個體的評價

通過對個體Xi解碼得到(X ,Y )，并按式（15）對個體進行評價：

式中，C( )

X,Y 為目標函數式（1）。因為一個解還可能不滿足時間約束式（2）和能力約束式（7）和（8），所以將其作為懲罰項加入評價函數中，η1為時間約束的懲罰系數，η2和η3分別為3PL服務節點和3PL運輸供應商的能力懲罰系數。表示：如果括號內值為正，則取該值。

4 實驗及結果分析

為了對模型的合理性及算法的有效性進行驗證，對數據隨機產生的算例進行測試。模型和算法均采用Matlab語言編碼實現，并在Intel Core i5 CPU 2.20 GHz，內存4 GB的PC機上進行實驗。

不同算例的規模如表3所示，包括供需點對的數量，3PL服務節點的數量和3PL運輸供應商及運輸方式的數量。算例的參數都按照下面均勻分布隨機產生：供需點對之間的產品流通量；3PL服務節點的處理成本、處理時間、處理能力、開設成本。3PL運輸供應商的運輸成本、運輸時間、運輸能力、開設成本。其中，考慮公路、鐵路、水路和航空四種不同運輸方式，各種運輸方式的參數取值如表4所示。

首先，對不同規模的算例進行求解，每個算例SFLA分別運行20次，并與遺傳算法（GA）進行比較。SFLA的參數設置如下：族群數M為20，族群規模N為10，族群內局部搜索次數為10，總循環代數為100。為了公平比較，兩種算法評估相同數量的個體，采用相同的編碼方式和初始種群生產方法。GA算法采用基于輪盤賭的選擇策略，采用基于路徑的多點交叉策略，并通過隨機改變路徑的節點、3PL運輸供應商或運輸方式來實現變異策略。GA的參數設置如下：種群規模為40，循環代數為500，交叉率為0.5，變異率為0.2。表5給出算法求解的最好值、最差值、平均值和平均偏差率（（平均值－最好值/最好值）×100%）。由表5可見，對于不同規模的算例，SFLA的性能指標都優于GA，并且平均偏差率在0.3%～13%之間變化。表明SFLA能夠對不同規模的算例進行有效求解并保持穩定的性能。

表3 算例的規模

表4 不同運輸方式的參數取值

對不同配送時間約束下的算例I8進行求解，每個時間約束SFLA和GA分別運行20次。表6給出不同時間約束下兩種算法的運行結果。由表6可見，SFLA的平均偏差率在1%～6%之間，并且各性能指標優于GA，表明SFLA在不同的配送時間約束下仍然能夠保持性能穩定。

表7給出算例I1～I3的詳細結果，包括總成本、開設成本、運輸和處理成本、供需點對之間的配送路徑和供需點對的配送時間。其中“Path1：1—（1，3）—5—（1，4）—7”表示供需點對1和7之間的路徑Path1，該路徑經過3PL服務節點5，并且選擇節點1和5之間的3PL運輸供應商1的水路方式以及節點5和7之間的3PL運輸供應商1的航空方式進行運輸。“s-d-1：16.7”表示第1個供需點對之間的配送時間為16.7（天）。

表5 SFLA和GA求解不同規模算例結果

表6 SFLA和GA求解不同時間約束下算例I8的結果

表8給出不同配送時間約束下算例I8的詳細結果。由表8可見，隨著時間約束β的增加，總成本減少，運輸和處理成本減少。因為，當配送時間約束增加，可通過開設具有較低處理成本的3PL服務節點和較低運輸成本的3PL運輸供應商及運輸方式來構建符合配送時間約束的配送線路來完成配送任務。這可能導致配送線路的運輸和處理成本降低，進而總成本減少。

表7 不同規模算例的詳細結果

表8 不同時間約束下算例I8的詳細結果

5 結束語

在考慮多供需點對之間配送和多種運輸方式的情況下，為了獲得高效運作的4PL服務網絡，研究多種運輸方式的4PL多到多網絡設計問題。建立以總成本為目標，并滿足配送時間約束的數學優化模型。針對問題模型特點，設計SFLA進行求解。最后，通過仿真算例來驗證模型的合理性及算法的有效性。實驗結果表明模型能夠對問題合理描述，并且SFLA對不同規模和不同配送時間約束下的算例都能夠有效求解并保持性能穩定。而且，隨著配送時間約束參數的增加，運輸和處理成本將減少。