多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)模型與算法

李 銳，孫福明

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001

1 引言

物流業(yè)務(wù)外包已經(jīng)成為許多企業(yè)提高自身的核心競(jìng)爭(zhēng)力的有效途徑。隨著經(jīng)濟(jì)全球化的發(fā)展，往往需要多個(gè)物流公司合作才能完成一項(xiàng)物流任務(wù)。由于能夠整合不同的第三方物流（3PL）資源，依靠其信息方面的優(yōu)勢(shì)，解決單獨(dú)靠一家3PL不能完成的任務(wù)，第四方物流[1]（4PL）開(kāi)始得到關(guān)注。在運(yùn)作過(guò)程中，4PL需要根據(jù)需求設(shè)計(jì)合理的物流網(wǎng)絡(luò)來(lái)提供有效的物流服務(wù)?，F(xiàn)實(shí)中，很多情況需要承擔(dān)多個(gè)確定的供需點(diǎn)對(duì)之間的配送任務(wù)，即多到多的配送任務(wù)。目前，4PL網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題已經(jīng)得到一定的研究[2-4]。然而，這些研究都是考慮4PL承擔(dān)某種產(chǎn)品的配送或回收任務(wù)。

此外，3PL運(yùn)輸供應(yīng)商可能提供多種運(yùn)輸方式供選擇，所以在4PL網(wǎng)絡(luò)設(shè)計(jì)過(guò)程中需要同時(shí)考慮選擇3PL運(yùn)輸商及運(yùn)輸方式。可見(jiàn)，研究多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題具有現(xiàn)實(shí)意義。目前，國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)考慮多種運(yùn)輸方式的物流及運(yùn)輸相關(guān)問(wèn)題進(jìn)行了研究。Ghorbani[5]研究配送網(wǎng)絡(luò)的選址庫(kù)存問(wèn)題，并考慮多種運(yùn)輸方式和3PL運(yùn)輸供應(yīng)商。Haddad-Sisakht等[6]研究不確定下考慮多種運(yùn)輸方式的閉環(huán)供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。Masoud等[7]研究多種運(yùn)輸方式對(duì)汽車供應(yīng)鏈可持續(xù)性的影響。郭等[8]對(duì)多種運(yùn)輸模式下的生產(chǎn)運(yùn)輸問(wèn)題進(jìn)行了研究。然而，考慮多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題則還沒(méi)有得到關(guān)注。

本文研究考慮多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。與現(xiàn)有4PL網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題不同，文中在4PL承擔(dān)多供需點(diǎn)對(duì)物流配送任務(wù)情況下同時(shí)考慮3PL具有多種運(yùn)輸方式，建立問(wèn)題的數(shù)學(xué)優(yōu)化模型，并設(shè)計(jì)混合蛙跳算法求解。最后，通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證模型的合理性及算法的有效性。

2 問(wèn)題描述及模型

考慮4PL負(fù)責(zé)多個(gè)供需點(diǎn)對(duì)之間產(chǎn)品的物流配送任務(wù)，并通過(guò)3PL服務(wù)節(jié)點(diǎn)和3PL運(yùn)輸供應(yīng)商來(lái)完成，其中每個(gè)3PL運(yùn)輸供應(yīng)商提供多種運(yùn)輸方式。多到多配送下的4PL網(wǎng)絡(luò)可表示為無(wú)向多重圖，如圖1所示。網(wǎng)絡(luò)的節(jié)點(diǎn)包括供應(yīng)點(diǎn)、需求點(diǎn)和3PL服務(wù)節(jié)點(diǎn)（配送中心、倉(cāng)庫(kù)等），網(wǎng)絡(luò)的邊表示3PL運(yùn)輸供應(yīng)商。多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題是通過(guò)選擇3PL服務(wù)節(jié)點(diǎn)、3PL運(yùn)輸供應(yīng)商及運(yùn)輸方式來(lái)確定網(wǎng)絡(luò)結(jié)構(gòu)，在各個(gè)供需點(diǎn)對(duì)的配送時(shí)間滿足要求的條件下，最小化網(wǎng)絡(luò)總成本。

圖1 多到多配送下的4PL網(wǎng)絡(luò)

2.1 符號(hào)說(shuō)明

問(wèn)題模型的相關(guān)集合、參數(shù)及決策變量分別如表1和表2所示。

2.2 優(yōu)化模型

基于以上符號(hào)說(shuō)明和變量定義，建立多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化模型如下：

（1）目標(biāo)函數(shù)

表1 集合及參數(shù)

目標(biāo)函數(shù)式（1）最小化總的物流成本，包括3PL服務(wù)節(jié)點(diǎn)、3PL運(yùn)輸供應(yīng)商某種運(yùn)輸方式的開(kāi)設(shè)成本，所有供需對(duì)點(diǎn)之間產(chǎn)品的運(yùn)輸和處理成本。

（2）配送時(shí)間約束

式（2）要求所有供需點(diǎn)對(duì)的配送時(shí)間不大于β，其中包括處理時(shí)間和運(yùn)輸時(shí)間。

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

表2 決策變量

約束式（3）和式（4）表示如果3PL服務(wù)節(jié)點(diǎn)被選擇服務(wù)于供需點(diǎn)對(duì)p，則必須有與其連接的3PL運(yùn)輸供應(yīng)商的一種運(yùn)輸方式被選擇來(lái)運(yùn)出和運(yùn)入產(chǎn)品；否則，沒(méi)有3PL運(yùn)輸供應(yīng)商或運(yùn)輸方式被選擇；約束式（5）、（6）分別要求供需點(diǎn)對(duì)p的供應(yīng)點(diǎn)和需求點(diǎn)必須通過(guò)3PL運(yùn)輸供應(yīng)的某種運(yùn)輸方式來(lái)運(yùn)出和運(yùn)入產(chǎn)品。

（4）能力約束

式（7）和（8）分別為3PL服務(wù)節(jié)點(diǎn)和3PL運(yùn)輸供應(yīng)商某種運(yùn)輸方式的能力約束，并要求被選擇服務(wù)于供需點(diǎn)對(duì)之間配送路徑的3PL服務(wù)節(jié)點(diǎn)和3PL運(yùn)輸供應(yīng)商的某種運(yùn)輸方式必須是已開(kāi)設(shè)的。

（5）決策變量約束

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

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

考慮多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題是傳統(tǒng)設(shè)施選址問(wèn)題的擴(kuò)展，因此也是NP-hard問(wèn)題。在問(wèn)題規(guī)模較大的情況下，求解很困難，所以智能優(yōu)化算法更適合對(duì)該問(wèn)題進(jìn)行求解。本文設(shè)計(jì)混合蛙跳算法對(duì)問(wèn)題進(jìn)行求解。

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

本文根據(jù)問(wèn)題的特點(diǎn)設(shè)計(jì)SFLA進(jìn)行求解，通過(guò)向量對(duì)青蛙個(gè)體進(jìn)行編碼。同時(shí)，為了滿足配送路徑的連通性約束，分別設(shè)計(jì)初始種群生成方法和青蛙的跳躍操作。

3.1 混合蛙跳算法步驟

混合蛙跳算法步驟如下：

步驟1生成含有F個(gè)青蛙的初始群體Pop0={X1,X2,…,XF}（詳見(jiàn)3.3節(jié)），并按3.5節(jié)方法計(jì)算青蛙（解）Xi的評(píng)價(jià)函數(shù)值 f( )Xi。

步驟2將群體劃分為M個(gè)族群，Pop={P1,P2,…,PM}。將青蛙按照評(píng)價(jià)函數(shù)值從小到大排序，并依次逐一循環(huán)分配給M個(gè)族群，每個(gè)族群Pk由N個(gè)青蛙組成，即

步驟3對(duì)每個(gè)族群執(zhí)行深度局部搜索，具體過(guò)程如下：

重復(fù)上述過(guò)程，直到達(dá)到設(shè)定的更新迭代次數(shù)。

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

步驟5輸出最好解。

3.2 個(gè)體的編碼與解碼

青蛙個(gè)體可由一組向量來(lái)表示。向量的數(shù)量為供需點(diǎn)對(duì)的數(shù)量。每個(gè)向量表示供需點(diǎn)對(duì)之間的一條路徑。如圖2所示，每個(gè)向量由三部分組成，其中第一部分表示節(jié)點(diǎn)的選擇情況，每一位表示路徑可能經(jīng)過(guò)的節(jié)點(diǎn)（需求點(diǎn)除外），取值為“0”表示該節(jié)點(diǎn)沒(méi)有在路徑上，取“非0”值表示該節(jié)點(diǎn)在路徑上，并且下一個(gè)節(jié)點(diǎn)為其值對(duì)應(yīng)的節(jié)點(diǎn)；第二部分表示路徑可能經(jīng)過(guò)的節(jié)點(diǎn)之間3PL運(yùn)輸供應(yīng)商的選擇情況，“0”表示沒(méi)有供應(yīng)商被選擇，“非0”表示其值對(duì)應(yīng)的供應(yīng)商被選擇；第三部分表示運(yùn)輸方式的選擇情況，每一位表示某兩個(gè)節(jié)點(diǎn)之間3PL供應(yīng)商的運(yùn)輸方式的選擇情況，“0”表示沒(méi)有運(yùn)輸方式被選擇，“非0”表示其值對(duì)應(yīng)的運(yùn)輸方式被選擇。值得注意的是，因?yàn)椴煌墓?yīng)點(diǎn)或需求點(diǎn)與3PL服務(wù)節(jié)點(diǎn)之間的連接情況不同，所以不同路徑所對(duì)應(yīng)的向量維數(shù)可能不同。

圖2 個(gè)體向量的表示

根據(jù)上述編碼規(guī)則，給定向量的取值可以唯一確定對(duì)應(yīng)的路徑，進(jìn)而可以確定變量和的值，再由約束式（7）和式（8）即可確定解 xijkm和 yi。

3.3 初始種群的生成

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

步驟1生成向量的節(jié)點(diǎn)部分。從供應(yīng)點(diǎn)vs對(duì)應(yīng)位開(kāi)始，依次隨機(jī)確定路徑經(jīng)過(guò)的節(jié)點(diǎn)及節(jié)點(diǎn)對(duì)應(yīng)位的數(shù)值。如果某節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)都已經(jīng)是路徑上的節(jié)點(diǎn)，則返回到供應(yīng)點(diǎn)，并重新確定節(jié)點(diǎn)部分，直到到達(dá)需求點(diǎn)vl。如果某節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)包含需求點(diǎn)，則其對(duì)應(yīng)位的取值為需求點(diǎn)。

步驟2根據(jù)路徑經(jīng)過(guò)的節(jié)點(diǎn)順序，依次隨機(jī)選擇3PL運(yùn)輸供應(yīng)商，確定對(duì)應(yīng)位的值。

步驟3根據(jù)3PL供應(yīng)商的選擇情況，依次找到被選擇3PL供應(yīng)商的對(duì)應(yīng)位，并隨機(jī)選擇運(yùn)輸方式，確定對(duì)應(yīng)位的值。

3.4 跳躍操作

青蛙在1次和2次跳躍過(guò)程中，根據(jù)族群Pk最差個(gè)體與族群最好個(gè)體（或全局最好個(gè)體）來(lái)產(chǎn)生新個(gè)體。在產(chǎn)生新個(gè)體的過(guò)程中，為了滿足路徑的連通性約束式（3）～（6），新個(gè)體的第 p 個(gè)向量由個(gè)體與或的對(duì)應(yīng)向量與（或按照如下步驟生成：

步驟1對(duì)于向量的節(jié)點(diǎn)部分執(zhí)行交叉操作：從供應(yīng)點(diǎn)vs對(duì)應(yīng)位開(kāi)始，根據(jù)路徑經(jīng)過(guò)的節(jié)點(diǎn)按式（13）依次執(zhí)行節(jié)點(diǎn)對(duì)應(yīng)位 j的交叉操作。在交叉過(guò)程中，如果與（或）中對(duì)應(yīng)位的值為需求點(diǎn)，則取值為需求點(diǎn)；如果對(duì)應(yīng)位的值分別為“0”和“非0”，則取“非0”值。如果中對(duì)應(yīng)位的值為需求點(diǎn)，則停止交叉過(guò)程。

式中rand表示[ ]0,1之間隨機(jī)數(shù)。

步驟2根據(jù)路徑經(jīng)過(guò)的節(jié)點(diǎn)次序，按照式（14）確定3PL運(yùn)輸供應(yīng)商部分對(duì)應(yīng)位 j的值。設(shè)路徑經(jīng)過(guò)的某兩個(gè)節(jié)點(diǎn)之間有ξj個(gè)3PL運(yùn)輸供應(yīng)商，那么對(duì)應(yīng)位的取值范圍為 1,2,…,ξj。如果中對(duì)應(yīng)位的值小于1，則取1；如果對(duì)應(yīng)位的值大于ξj，則取ξj。式中，round表示四舍五入取整。

步驟3根據(jù)路徑經(jīng)過(guò)的節(jié)點(diǎn)次序和被選擇的3PL運(yùn)輸供應(yīng)商，再按照式（14）確定運(yùn)輸方式部分對(duì)應(yīng)位的值。設(shè)路徑選擇的某個(gè)3PL運(yùn)輸供應(yīng)商提供的運(yùn)輸方式數(shù)量為τ，那么對(duì)應(yīng)位的取值范圍為1,2,…,τ。如果中對(duì)應(yīng)位的值小于1，則取1；如果對(duì)應(yīng)位的值大于τ，則取τ。

3.5 個(gè)體的評(píng)價(jià)

通過(guò)對(duì)個(gè)體Xi解碼得到(X ,Y )，并按式（15）對(duì)個(gè)體進(jìn)行評(píng)價(jià)：

式中，C( )

X,Y 為目標(biāo)函數(shù)式（1）。因?yàn)橐粋€(gè)解還可能不滿足時(shí)間約束式（2）和能力約束式（7）和（8），所以將其作為懲罰項(xiàng)加入評(píng)價(jià)函數(shù)中，η1為時(shí)間約束的懲罰系數(shù)，η2和η3分別為3PL服務(wù)節(jié)點(diǎn)和3PL運(yùn)輸供應(yīng)商的能力懲罰系數(shù)。表示：如果括號(hào)內(nèi)值為正，則取該值。

4 實(shí)驗(yàn)及結(jié)果分析

為了對(duì)模型的合理性及算法的有效性進(jìn)行驗(yàn)證，對(duì)數(shù)據(jù)隨機(jī)產(chǎn)生的算例進(jìn)行測(cè)試。模型和算法均采用Matlab語(yǔ)言編碼實(shí)現(xiàn)，并在Intel Core i5 CPU 2.20 GHz，內(nèi)存4 GB的PC機(jī)上進(jìn)行實(shí)驗(yàn)。

不同算例的規(guī)模如表3所示，包括供需點(diǎn)對(duì)的數(shù)量，3PL服務(wù)節(jié)點(diǎn)的數(shù)量和3PL運(yùn)輸供應(yīng)商及運(yùn)輸方式的數(shù)量。算例的參數(shù)都按照下面均勻分布隨機(jī)產(chǎn)生：供需點(diǎn)對(duì)之間的產(chǎn)品流通量；3PL服務(wù)節(jié)點(diǎn)的處理成本、處理時(shí)間、處理能力、開(kāi)設(shè)成本。3PL運(yùn)輸供應(yīng)商的運(yùn)輸成本、運(yùn)輸時(shí)間、運(yùn)輸能力、開(kāi)設(shè)成本。其中，考慮公路、鐵路、水路和航空四種不同運(yùn)輸方式，各種運(yùn)輸方式的參數(shù)取值如表4所示。

首先，對(duì)不同規(guī)模的算例進(jìn)行求解，每個(gè)算例SFLA分別運(yùn)行20次，并與遺傳算法（GA）進(jìn)行比較。SFLA的參數(shù)設(shè)置如下：族群數(shù)M為20，族群規(guī)模N為10，族群內(nèi)局部搜索次數(shù)為10，總循環(huán)代數(shù)為100。為了公平比較，兩種算法評(píng)估相同數(shù)量的個(gè)體，采用相同的編碼方式和初始種群生產(chǎn)方法。GA算法采用基于輪盤(pán)賭的選擇策略，采用基于路徑的多點(diǎn)交叉策略，并通過(guò)隨機(jī)改變路徑的節(jié)點(diǎn)、3PL運(yùn)輸供應(yīng)商或運(yùn)輸方式來(lái)實(shí)現(xiàn)變異策略。GA的參數(shù)設(shè)置如下：種群規(guī)模為40，循環(huán)代數(shù)為500，交叉率為0.5，變異率為0.2。表5給出算法求解的最好值、最差值、平均值和平均偏差率（（平均值－最好值/最好值）×100%）。由表5可見(jiàn)，對(duì)于不同規(guī)模的算例，SFLA的性能指標(biāo)都優(yōu)于GA，并且平均偏差率在0.3%～13%之間變化。表明SFLA能夠?qū)Σ煌?guī)模的算例進(jìn)行有效求解并保持穩(wěn)定的性能。

表3 算例的規(guī)模

表4 不同運(yùn)輸方式的參數(shù)取值

對(duì)不同配送時(shí)間約束下的算例I8進(jìn)行求解，每個(gè)時(shí)間約束SFLA和GA分別運(yùn)行20次。表6給出不同時(shí)間約束下兩種算法的運(yùn)行結(jié)果。由表6可見(jiàn)，SFLA的平均偏差率在1%～6%之間，并且各性能指標(biāo)優(yōu)于GA，表明SFLA在不同的配送時(shí)間約束下仍然能夠保持性能穩(wěn)定。

表7給出算例I1～I(xiàn)3的詳細(xì)結(jié)果，包括總成本、開(kāi)設(shè)成本、運(yùn)輸和處理成本、供需點(diǎn)對(duì)之間的配送路徑和供需點(diǎn)對(duì)的配送時(shí)間。其中“Path1：1—（1，3）—5—（1，4）—7”表示供需點(diǎn)對(duì)1和7之間的路徑Path1，該路徑經(jīng)過(guò)3PL服務(wù)節(jié)點(diǎn)5，并且選擇節(jié)點(diǎn)1和5之間的3PL運(yùn)輸供應(yīng)商1的水路方式以及節(jié)點(diǎn)5和7之間的3PL運(yùn)輸供應(yīng)商1的航空方式進(jìn)行運(yùn)輸?！皊-d-1：16.7”表示第1個(gè)供需點(diǎn)對(duì)之間的配送時(shí)間為16.7（天）。

表5 SFLA和GA求解不同規(guī)模算例結(jié)果

表6 SFLA和GA求解不同時(shí)間約束下算例I8的結(jié)果

表8給出不同配送時(shí)間約束下算例I8的詳細(xì)結(jié)果。由表8可見(jiàn)，隨著時(shí)間約束β的增加，總成本減少，運(yùn)輸和處理成本減少。因?yàn)椋?dāng)配送時(shí)間約束增加，可通過(guò)開(kāi)設(shè)具有較低處理成本的3PL服務(wù)節(jié)點(diǎn)和較低運(yùn)輸成本的3PL運(yùn)輸供應(yīng)商及運(yùn)輸方式來(lái)構(gòu)建符合配送時(shí)間約束的配送線路來(lái)完成配送任務(wù)。這可能導(dǎo)致配送線路的運(yùn)輸和處理成本降低，進(jìn)而總成本減少。

表7 不同規(guī)模算例的詳細(xì)結(jié)果

表8 不同時(shí)間約束下算例I8的詳細(xì)結(jié)果

5 結(jié)束語(yǔ)

在考慮多供需點(diǎn)對(duì)之間配送和多種運(yùn)輸方式的情況下，為了獲得高效運(yùn)作的4PL服務(wù)網(wǎng)絡(luò)，研究多種運(yùn)輸方式的4PL多到多網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。建立以總成本為目標(biāo)，并滿足配送時(shí)間約束的數(shù)學(xué)優(yōu)化模型。針對(duì)問(wèn)題模型特點(diǎn)，設(shè)計(jì)SFLA進(jìn)行求解。最后，通過(guò)仿真算例來(lái)驗(yàn)證模型的合理性及算法的有效性。實(shí)驗(yàn)結(jié)果表明模型能夠?qū)?wèn)題合理描述，并且SFLA對(duì)不同規(guī)模和不同配送時(shí)間約束下的算例都能夠有效求解并保持性能穩(wěn)定。而且，隨著配送時(shí)間約束參數(shù)的增加，運(yùn)輸和處理成本將減少。