，

(1.遼寧石油化工大學(xué) a.信息與控制工程學(xué)院 b.石油化工過程控制國家級(jí)實(shí)驗(yàn)教學(xué)示范中心，遼寧 撫順 113001；3.東北大學(xué)信息科學(xué)與工程學(xué)院流程工業(yè)綜合自動(dòng)化國家重點(diǎn)實(shí)驗(yàn)室,沈陽 110819)

0 引言

第四方物流(The Fourth Party Logistics，4PL)供應(yīng)商是一個(gè)供應(yīng)鏈的集成商，它對(duì)公司內(nèi)部和具有互補(bǔ)性的服務(wù)供應(yīng)商所擁有的不同資源、能力和技術(shù)進(jìn)行整合和管理，以提供一整套供應(yīng)鏈解決方案。4PL的發(fā)展一方面給物流企業(yè)發(fā)展帶來了機(jī)遇，另一方面，也給理論界帶來許多具有挑戰(zhàn)性的研究問題，如4PL的運(yùn)行優(yōu)化[1-2]、利潤(rùn)分配[3]、網(wǎng)絡(luò)設(shè)計(jì)[4-5]、路徑優(yōu)化[6]等等。

4PL路徑優(yōu)化問題(4PL Routing Optimization Problem,4PLROP)是在復(fù)雜物流配送網(wǎng)絡(luò)中尋求供應(yīng)城市到需求城市的一個(gè)配送路徑，4PL供應(yīng)商在選擇路徑的同時(shí)還要對(duì)提供配送服務(wù)的第三方物流(The Third Party Logistics,3PL)供應(yīng)商做出選擇。因此，增加了問題的求解難度。但它是4PL運(yùn)作優(yōu)化的關(guān)鍵問題之一，已經(jīng)成為國內(nèi)外理論界和企業(yè)界特別關(guān)注的焦點(diǎn)。目前，已有許多研究學(xué)者對(duì)4PLROP展開研究，并取得一些成果，為4PLROP問題的研究奠定了基礎(chǔ)。Chen等[7]從4PL運(yùn)作的關(guān)鍵問題出發(fā)，基于圖論知識(shí)建立了4PLROP的多維權(quán)有向圖模型，采用遺傳算法求解了10節(jié)點(diǎn)的4PLROP問題?？紤]到Chen給出的是4PLROP的概念模型，Huang等[8]基于配送網(wǎng)絡(luò)的多重圖，給出了4PLROP的具體的數(shù)學(xué)模型，并設(shè)計(jì)嵌入Dijkstra算法的免疫算法對(duì)該模型進(jìn)行了求解。繼而，基于免疫規(guī)劃對(duì)免疫算法進(jìn)行了改進(jìn)，對(duì)該問題進(jìn)行了進(jìn)一步的求解，并與傳統(tǒng)的免疫算法進(jìn)行了對(duì)比分析[9]?？紤]到客戶對(duì)交貨期的需求可能具有時(shí)間窗特征，Bo等[10]建立了帶時(shí)間窗的4PLROP數(shù)學(xué)模型，并利用和聲搜索算法對(duì)該問題進(jìn)行了求解。在此基礎(chǔ)上，作者進(jìn)一步對(duì)時(shí)間窗的硬約束進(jìn)行釋放，即考慮了帶軟時(shí)間窗的4PLROP，對(duì)不滿足時(shí)間窗要求的路徑進(jìn)行相應(yīng)懲罰，并加到目標(biāo)函數(shù)中[11]。考慮到多任務(wù)的情況，黃[12]等建立了帶有費(fèi)用折扣的4PLROP模型，并采用蟻群算法對(duì)問題進(jìn)行求解。Tao[6]等采用列生成算法對(duì)所建立的模型進(jìn)行了求解。在物流配送過程中，配送時(shí)間往往受天氣、路況等其他因素的干擾，導(dǎo)致不能按期完成配送任務(wù)，從而帶來不確定性。為了提高服務(wù)水平，需要對(duì)配送時(shí)間的不確定性進(jìn)行有效的刻畫。Huang等將這種不確定性看成是模糊的，建立了相應(yīng)的模糊規(guī)劃數(shù)學(xué)模型，并分別用遺傳算法[13]、兩階段遺傳算法對(duì)相應(yīng)的數(shù)學(xué)模型進(jìn)行了求解[14]。Huang等[15]將配送時(shí)間看成是不確定的，采用不確定性理論建立了不確定性模型，并將其轉(zhuǎn)化成確定性模型，采用改進(jìn)的不同的遺傳算法對(duì)問題求解。Huang等在文[16]中又將不確定模型與隨機(jī)規(guī)劃模型進(jìn)行了對(duì)比分析，論證了不確定性模型的有效性。

但當(dāng)前研究沒有對(duì)由于時(shí)間的不確定性而引起的風(fēng)險(xiǎn)進(jìn)行刻畫、度量與控制。在實(shí)際的配送過程中，正是由于在4PL運(yùn)作中3PL供應(yīng)商的運(yùn)輸時(shí)間和中轉(zhuǎn)時(shí)間存在著不確定性，導(dǎo)致配送任務(wù)不能按期完工，從而帶來拖期風(fēng)險(xiǎn)。使得4PL供應(yīng)商不能為客戶提供及時(shí)優(yōu)秀的配送方案，而導(dǎo)致配送成本的增加及自身信譽(yù)和客戶滿意度的下降。因此，研究考慮拖期風(fēng)險(xiǎn)的4PLROP問題具有理論和實(shí)際意義。

本文在充分考慮上述實(shí)際情況下，引入了在險(xiǎn)值(Value-at-Risk,VaR)來刻畫及度量拖期風(fēng)險(xiǎn)的大小，即拖期量小于某個(gè)值的概率要大于給定的置信水平。建立了以最小化拖期風(fēng)險(xiǎn)為目標(biāo)，配送費(fèi)用為約束的數(shù)學(xué)模型，并設(shè)計(jì)具有復(fù)雜網(wǎng)絡(luò)搜索能力的嵌入刪除算法的和聲搜索算法(Deletion Algorithm Embedded Harmony Search,DA-HS)對(duì)問題進(jìn)行求解，測(cè)試了不同規(guī)模的實(shí)例，并將求解結(jié)果與嵌入刪除算法的遺傳算法(Deletion Algorithm Embedded Genetic Algorithm,DA-GA)、基本的聲搜索算法(Harmony Search,HS)和枚舉算法(Enumeration Algorithm,EA)進(jìn)行了對(duì)比分析，測(cè)試結(jié)果表明所提模型和算法是有效的。

1 數(shù)學(xué)模型

1.1 問題描述及變量定義

圖1 7節(jié)點(diǎn)問題的多重圖Fig.1 Multi-graph of seven nodes problem

如圖1所示，4PLROP可以用多重圖G(V,E)進(jìn)行表示，其中V(V=n)表示節(jié)點(diǎn)的集合，E表示邊的集合。s是供應(yīng)城市，t是需求城市，其他中間點(diǎn)是中轉(zhuǎn)城市，它們具有費(fèi)用和時(shí)間屬性。假設(shè)每段運(yùn)輸任務(wù)只能由一個(gè)3PL供應(yīng)商負(fù)責(zé)，由于任意兩個(gè)城市之間可能存在多個(gè)3PL提供配送服務(wù)，故圖中任意兩點(diǎn)間可能有多條邊(每條邊代表一個(gè)3PL，邊上的數(shù)字是3PL的編號(hào))，每條邊都具有費(fèi)用和時(shí)間屬性。

供應(yīng)商為客戶提供配送方案時(shí)，要考慮到時(shí)間的不確定性而導(dǎo)致的拖期風(fēng)險(xiǎn)，對(duì)風(fēng)險(xiǎn)進(jìn)行度量及監(jiān)控，以滿足客戶對(duì)配送時(shí)間的需求，提高客戶的滿意度。對(duì)客戶來說，只要費(fèi)用在其預(yù)算之內(nèi)，按時(shí)完工的概率越大越好；一旦拖期的話，拖期量越小越好，即最大程度地保證按時(shí)完成配送任務(wù)，一旦拖期，拖期風(fēng)險(xiǎn)越小越好。因此，基于以上考慮，在用VaR來度量拖期風(fēng)險(xiǎn)的基礎(chǔ)上，建立以最小化拖期風(fēng)險(xiǎn)為目標(biāo)，配送費(fèi)用為約束的數(shù)學(xué)模型。目標(biāo)是求得滿足費(fèi)用約束的拖期風(fēng)險(xiǎn)最小的配送的方案。

(1)

(2)

1.2 VaR的定義

VaR的比較規(guī)范的定義是，在正常的市場(chǎng)條件和給定的置信水平上，在給定的持有期間內(nèi)，某一投資組合預(yù)期可能發(fā)生的最大的損失?；蛘哒f，在正常的市場(chǎng)條件和給定的時(shí)間段內(nèi)，該投資組合發(fā)生大于VaR值損失的概率僅為給定的概率水平，可以表示為

Pr{ΔP>VaR}=1-β

(3)

其中，ΔP為證券組合在持有期內(nèi)的損失，β為置信水平，VaR為置信水平β下處于風(fēng)險(xiǎn)中的價(jià)值。置信水平的選取反映了投資主體對(duì)風(fēng)險(xiǎn)的厭惡程度，置信水平越高，厭惡風(fēng)險(xiǎn)的程度越大。由VaR的定義可知，置信水平越高，資產(chǎn)組合的損失小于其VaR值的概率越大，也就是說，VaR模型對(duì)于極端事件的發(fā)生進(jìn)行預(yù)測(cè)時(shí)失敗的可能性越小。

圖2 VaR的定義Fig.2 Definition of VaR

如果Z是隨機(jī)變量，則VaR的數(shù)學(xué)定義如式(4)[17]，其中，β是置信水平。圖2給出了VaR定義的圖示。例如，某公司1994年年報(bào)披露，1994年該公司一天的95%VaR值為100萬美元。其含義是指，該公司可以以95%的可能性保證，1994年每一特定時(shí)點(diǎn)上的證券組合在未來24小時(shí)之內(nèi)，由于市場(chǎng)價(jià)格變動(dòng)而帶來的損失不會(huì)超過100萬美元，即損失超過100萬美元的概率不會(huì)超過5%。

VaR(Z)=inf{t:p(z≤t)≥β}

(4)

本文中采用VaR來度量拖期風(fēng)險(xiǎn)的大小，即拖期量小于某個(gè)值的概率要大于等于客戶給定的置信水平。

1.3 VaR準(zhǔn)則下的數(shù)學(xué)模型

基于以上變量定義，建立如下數(shù)學(xué)模型：

minVaRβ(ΔT)

(5)

(6)

(7)

R={vs,…,vi,k,vj,…,vk}∈G

(8)

xijk(R),yj(R)∈{0,1}

(9)

式(5)是目標(biāo)函數(shù)，最小化拖期風(fēng)險(xiǎn)，即VaR值，β為置信水平，即客戶的風(fēng)險(xiǎn)偏好；式(6)是配送費(fèi)用約束，其中C0是客戶給定的可提供的最大的費(fèi)用；式(7)是隨機(jī)變量，即拖期量ΔT的表達(dá)式；式(8)是路徑約束，即保證所選路徑是從初始點(diǎn)到目的點(diǎn)的合法的連通路徑；式(9)是決策變量約束。

1.4 VaR的轉(zhuǎn)化

(10)

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

文獻(xiàn)[10]設(shè)計(jì)了HS算法來求解4PL路徑優(yōu)化問題，但是該算法不能保證所產(chǎn)生的初始解和新解是合法解(合法的路徑)，因此需要對(duì)非法解進(jìn)行修復(fù)。修復(fù)過程會(huì)丟失當(dāng)前解的優(yōu)良信息，且當(dāng)問題規(guī)模比較大的時(shí)候，此修復(fù)過程非常耗時(shí)。從而導(dǎo)致該算法在求解大規(guī)模問題時(shí)，不能在合理的時(shí)間內(nèi)找到最優(yōu)解或滿意解。

因此，針對(duì)上述問題及4PL路徑優(yōu)化問題的特點(diǎn)，設(shè)計(jì)了DA-HS算法。主要設(shè)計(jì)思想是：先在多重圖上用HS算法的優(yōu)化機(jī)制產(chǎn)生一個(gè)簡(jiǎn)單圖；然后用DA算法在此簡(jiǎn)單圖上求出前K條拖期風(fēng)險(xiǎn)最小的路徑。由于最優(yōu)解不一定是某個(gè)圖上的最短路徑，也有可能是次最短路徑，因此該算法求前K條最短路徑而不是最短路徑。該算法每次迭代能產(chǎn)生多個(gè)解，而傳統(tǒng)的HS算法僅產(chǎn)生一個(gè)解，提高了算法的收斂速度。

本節(jié)先簡(jiǎn)單介紹HS和DA算法，然后介紹本文提出的DA-HS算法以及DA-GA算法。

2.1 和聲搜索算法

HS算法是2001年韓國學(xué)者Geem等人通過類比音樂和最優(yōu)化問題的相似性而提出的一種新的智能優(yōu)化算法[19]。類似于遺傳算法對(duì)生物進(jìn)化的模仿、模擬退火算法對(duì)物理退火機(jī)制的模仿以及粒子群優(yōu)化算法對(duì)鳥群魚群的模仿等，HS模擬了音樂演奏的原理。音樂演奏中，樂師們憑借自己的記憶，通過反復(fù)調(diào)整樂隊(duì)中各樂器的音調(diào)，最終達(dá)到一個(gè)美妙的和聲。算法首先產(chǎn)生HMS(Harmony Memory Size,和聲記憶庫的大小)個(gè)初始解(和聲)存入和聲記憶庫(Harmony Memory, HM)中；每個(gè)設(shè)計(jì)變量以概率HMCR(Harmony Memory Considering Rate,HMCR)在HM內(nèi)搜索新值，以概率1-HMCR在變量可能值域中搜索新值；對(duì)于在HM中產(chǎn)生新值的設(shè)計(jì)變量，以概率PAR(pitch adjusting rate,PAR)產(chǎn)生局部擾動(dòng)；判斷新解目標(biāo)函數(shù)值是否優(yōu)于HM內(nèi)的最差解，若是，則替換之；然后不斷迭代至收斂。

2.2 刪除算法

刪除算法(Deletion Algorithm,DA)[20]的核心思想：通過在有向圖中已有的最短路徑上刪除某條弧，并尋找替換的弧來尋找下一條可選的最短路徑。DA算法實(shí)際上是通過在有向圖中增加附加節(jié)點(diǎn)和相應(yīng)的弧來實(shí)現(xiàn)的。算法的詳細(xì)步驟可參考文獻(xiàn)[16]。

2.3 嵌入刪除算法的和聲搜索算法

該算法主要包括編碼設(shè)計(jì)、初始化問題和算法參數(shù)、初始化HM、新解的產(chǎn)生、更新HM、終止準(zhǔn)則。

2.3.1 編碼方案

采用以邊為基礎(chǔ)的整數(shù)編碼。先將多重圖用鄰接矩陣表示，矩陣中的行和列分別代表多重圖上的節(jié)點(diǎn)，圖中有邊相連的兩節(jié)點(diǎn)對(duì)應(yīng)的矩陣元素值為兩節(jié)點(diǎn)間的邊數(shù)，即rij；沒有邊相連時(shí)對(duì)應(yīng)的矩陣元素值為0。然后將矩陣中的上三角非零元素逐行從左到右編碼得到一個(gè)向量n=(n1n2…ni…nN)，其中ni為第i個(gè)解分量hi的最大取值，N為該問題的編碼長(zhǎng)度，即解分量的個(gè)數(shù)。當(dāng)表示簡(jiǎn)單圖的時(shí)候，每個(gè)解分量取值為1≤hi≤ni，當(dāng)表示路徑的時(shí)候，每個(gè)解分量hi可以取零值。

以圖1為例，其鄰接矩陣如(11)所示，可得7節(jié)點(diǎn)問題的向量n=(3 4 2 2 2 3 4 3 2 3 2 2)。由此可知，7節(jié)點(diǎn)問題解分量為12個(gè)，每個(gè)解分量的最大取值分別為3,4,2,2,2,3,4,3,2,3,2,2。圖3給出了向量h=(3 2 3 1 1 1 2 2 2 1 2 1)所代表的簡(jiǎn)單圖，簡(jiǎn)單圖上求得的最短路徑h=(3 0 0 1 0 0 0 0 0 1 0 0)如圖3中粗線所示。

圖3 簡(jiǎn)單圖及圖上的最短路徑Fig.3 A simple graph and the shortest path in it

(11)

2.3.2 初始化問題和算法參數(shù)

初始化問題的參數(shù)：和聲記憶庫的大小HMS、和聲記憶保留概率HMCR、記憶擾動(dòng)概率PAR、最大迭代次數(shù)NG、參數(shù)K、置信水平β、客戶可提供的最大的費(fèi)用C0和客戶要求的配送時(shí)間T0。

2.3.3 初始化HM

主要思想：對(duì)每個(gè)解分量hi隨機(jī)選取1～ni之間的一個(gè)整數(shù)，即隨機(jī)產(chǎn)生一個(gè)簡(jiǎn)單圖，然后在此圖上用DA求出前K條拖期風(fēng)險(xiǎn)最小的路徑。將滿足費(fèi)用約束的解(即路徑)存入HM中，不滿足費(fèi)用約束的解放棄，直到產(chǎn)生HMS個(gè)初始解，并按目標(biāo)函數(shù)值對(duì)初始解排序。其中，HMS與K沒有倍數(shù)關(guān)系。

(12)

DA-HS算法中的HM與HS算法的記憶庫有所不同。該算法的HM如矩陣所示，HM分為3部分，第1部分存放簡(jiǎn)單圖，第2部分存放在簡(jiǎn)單圖上求得的路徑，第3部分是目標(biāo)函數(shù)，即該路徑的拖期風(fēng)險(xiǎn)的大小。

以7節(jié)點(diǎn)問題為例，假定HMS=3,K=3。先隨機(jī)產(chǎn)生一個(gè)簡(jiǎn)單圖h=(3 2 3 1 1 1 2 2 2 1 2 1)，如圖3所示；然后，用DA求出前3條最短路，并存入HM，如式所示。

2.3.4 產(chǎn)生新解

主要思想：先用HS優(yōu)化機(jī)制產(chǎn)生新的簡(jiǎn)單圖，然后調(diào)用DA求出前K條拖期風(fēng)險(xiǎn)最小的路徑。

由于HS算法的優(yōu)化機(jī)制用來產(chǎn)生新的簡(jiǎn)單圖，此時(shí)的每個(gè)解分量hi不能取零值。為了產(chǎn)生新的簡(jiǎn)單圖，現(xiàn)對(duì)每個(gè)解分量hi進(jìn)行如下操作：

1)生成隨機(jī)數(shù)r1∈(0,1)，如果r1

2)生成隨機(jī)數(shù)r2∈(0,1)，如果r2

2.3.5 更新HM

對(duì)新產(chǎn)生的K個(gè)新解依次做如下操作：

1)新解是否滿足費(fèi)用約束，若是轉(zhuǎn)下步；否則轉(zhuǎn)3)。

2)新解是否比HM中的最差解要好，若是則用新解替換最差解；否則轉(zhuǎn)下步。

3)K個(gè)新解是否都判斷完，若是則更新HM完畢并對(duì)HM中所有解排序；否則轉(zhuǎn)(1)進(jìn)行下一個(gè)新解的判斷。

4)終止準(zhǔn)則

如果迭代次數(shù)達(dá)到NG，則算法終止，輸出最好解；否則，轉(zhuǎn)4)重新產(chǎn)生新解。

2.3.6 算法步驟

步驟1：初始化算法的參數(shù)：HMS、HMCR、PAR、NG、K、置信水平β、C0和T0。

步驟2：初始化HM。對(duì)HM中所有解(HMS個(gè))按目標(biāo)函數(shù)進(jìn)行排序。

步驟3：產(chǎn)生新解。用HS算法的優(yōu)化機(jī)制生成新的簡(jiǎn)單圖，然后調(diào)用DA算法求出前K條目標(biāo)函數(shù)值最小的路徑。

步驟4：更新HM。

步驟5：如果迭代次數(shù)達(dá)到NG，則算法結(jié)束并輸出最好解；否則轉(zhuǎn)步驟 3。

2.4 嵌入刪除算法的遺傳算法(DA-GA)

編碼方案和初始種群的產(chǎn)生方法同DA-HS算法。目標(biāo)函數(shù)作為適值函數(shù)，即最小化拖期風(fēng)險(xiǎn)。選擇策略采用截?cái)噙x擇方法，選擇最好的前T個(gè)個(gè)體，讓每一個(gè)個(gè)體有1/T的選擇概率，即平均每個(gè)得到NP/T個(gè)繁殖機(jī)會(huì)[21]。交叉方式為單點(diǎn)交叉。最大迭代次數(shù)作為停止準(zhǔn)則。

產(chǎn)生新一代種群的主要思想：先用GA優(yōu)化機(jī)制產(chǎn)生新的簡(jiǎn)單圖，然后調(diào)用DA求出前K條拖期風(fēng)險(xiǎn)最小的路徑。

3 實(shí)例分析

為了驗(yàn)證上述問題的數(shù)學(xué)模型和算法的有效性，本節(jié)測(cè)試了5個(gè)不同規(guī)模的算例，并將測(cè)試結(jié)果與DA-GA、HS[11]和EA進(jìn)行了對(duì)比。算法采用VC++語言實(shí)現(xiàn)，運(yùn)行環(huán)境為Intel(R)Core(TM)i7-2600CPU 3.40GHz PC臺(tái)式機(jī)。

3.1 數(shù)據(jù)的產(chǎn)生

本節(jié)分別求解了7，15，30，50和100節(jié)點(diǎn)的5個(gè)不同規(guī)模的算例。其中，其中7，15和30節(jié)點(diǎn)的數(shù)據(jù)來自文獻(xiàn)[10]；50和100節(jié)點(diǎn)問題的數(shù)據(jù)是隨機(jī)產(chǎn)生的，隨機(jī)產(chǎn)生數(shù)據(jù)方法為：將n個(gè)節(jié)點(diǎn)隨機(jī)地放在一個(gè)a*a的正方形區(qū)域內(nèi)，點(diǎn)(0,0)和(a,a)分別代表初始節(jié)點(diǎn)和目的節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)間的歐幾里得距離小于等于d，則兩節(jié)點(diǎn)間有邊相連[22]，有邊相連的節(jié)點(diǎn)間邊的個(gè)數(shù)在閉區(qū)間[2,4]中隨機(jī)生成，邊的費(fèi)用和時(shí)間、節(jié)點(diǎn)的費(fèi)用和時(shí)間都是隨機(jī)生成的。50節(jié)點(diǎn)算例的網(wǎng)絡(luò)節(jié)點(diǎn)分布圖，其中a=3，d=0.75；100節(jié)點(diǎn)算例的網(wǎng)絡(luò)節(jié)點(diǎn)分布圖，其中a=4，d=0.7。

圖4 參數(shù)NG性能分析Fig.4 w. r. t. NG performance analysis

3.2 參數(shù)測(cè)試

以7節(jié)點(diǎn)問題為例，詳細(xì)測(cè)試了算法參數(shù)對(duì)算法性能的影響并獲得一組最佳參數(shù)組合。算法參數(shù)的獲取是經(jīng)過大量仿真實(shí)驗(yàn)獲得的，即當(dāng)其他參數(shù)不變時(shí)，測(cè)試某一個(gè)參數(shù)對(duì)算法最好率的影響。圖4給出了NG對(duì)算法性能的影響，由圖可知，當(dāng)NG達(dá)到70以后，算法趨于穩(wěn)定。其中，最好率為算法獲得最好解的次數(shù)占算法運(yùn)行總次數(shù)的比率，計(jì)算最好率時(shí)算法運(yùn)行總次數(shù)為100。仿真實(shí)驗(yàn)表明，DA-HS算法最好的參數(shù)分別為K=2，HMS=5，HMCR=0.75，PAR=0.05，NG=70。

3.3 算例分析

本節(jié)首先以7節(jié)點(diǎn)問題為例，詳細(xì)分析了算法的求解結(jié)果。其次，為了驗(yàn)證算法的有效性，分別求解了7，15，30，50和100節(jié)點(diǎn)的5個(gè)不同規(guī)模的算例，將3種算法的求解結(jié)果進(jìn)行了對(duì)比分析。

表1給出了當(dāng)時(shí)間約束T0=80和費(fèi)用約束C0=73時(shí)，7節(jié)點(diǎn)問題的求解結(jié)果。

表1 T0=80,C0=73時(shí)7節(jié)點(diǎn)問題算法的求解結(jié)果Tab.1 Results of algorithm for solving 7 nodes problem with T0=80, C0=73

由表中數(shù)據(jù)可知，當(dāng)置信水平β=0.9時(shí)，求得的最好解(VaR值)為10.983 5，即物流供應(yīng)商以90%的概率能夠保證配送時(shí)間的拖期量小于等于10.983 5，對(duì)應(yīng)的配送費(fèi)用為73，對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v3,1,vt}，即在供應(yīng)城市s和需求城市t間選擇編號(hào)為2和3的城市作為中轉(zhuǎn)城市，兩兩城市間提供配送服務(wù)的3PL編號(hào)分別為2，2，1；當(dāng)置信水平增加到β=0.95時(shí)求得的最好解(VaR值)為19.473 3，即以95%的概率能夠保證配送時(shí)間的拖期量小于等于19.473 3，對(duì)應(yīng)的配送費(fèi)用為73，對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v3,1,vt}，即在供應(yīng)城市s和需求城市t間選擇編號(hào)為2和3的城市作為中轉(zhuǎn)城市，兩兩城市間提供配送服務(wù)的3PL編號(hào)分別為2，2，1；當(dāng)置信水平增加到β=0.99時(shí)，求得的最好解(VaR值)為35.400 6，即拖期量超過35.400 6的概率小于1%，對(duì)應(yīng)的配送費(fèi)用為73，對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v3,1,vt}，即在供應(yīng)城市s和需求城市t間選擇編號(hào)為2和3的城市作為中轉(zhuǎn)城市，兩兩城市間提供配送服務(wù)的3PL編號(hào)分別為2，2，1。上述結(jié)果表明，當(dāng)時(shí)間約束和費(fèi)用約束不變時(shí)，隨著置信水平的增加(風(fēng)險(xiǎn)厭惡)，配送路徑不變，但是拖期量增大。因此，4PL可以根據(jù)客戶的風(fēng)險(xiǎn)偏好，控制拖期量的大小，在風(fēng)險(xiǎn)和拖期量之間做個(gè)權(quán)衡。

表2給出了置信水平、配送時(shí)間和費(fèi)用約束的不同組合下，7節(jié)點(diǎn)問題的求解結(jié)果。其中，“β”為置信水平；“T0”為客戶要求的最晚的配送時(shí)間；“C0”為客戶給定的可承擔(dān)的最大費(fèi)用值；“NG”是算法的迭代次數(shù)；“最好解”是算法能夠求得的最好的解(評(píng)價(jià)標(biāo)準(zhǔn)是目標(biāo)函數(shù))；“最好率”為算法運(yùn)行100次中找到的最好解的個(gè)數(shù)與100的比率；“最好路徑”是最好解對(duì)應(yīng)的配送路徑；“時(shí)間”是算法運(yùn)行一次的運(yùn)行時(shí)間，單位秒。

表2 不同β、T0和C0下7節(jié)點(diǎn)問題的求解結(jié)果Tab.2 Results of 7 node case with different value ofβ, T0and C0

由表2中數(shù)據(jù)可知，當(dāng)置信水平β和配送時(shí)間T0不變時(shí)，隨著費(fèi)用的增加，拖期風(fēng)險(xiǎn)逐漸減??；當(dāng)置信水平β和配送費(fèi)用C0不變時(shí)，隨著可允許的配送時(shí)間的延長(zhǎng)，拖期風(fēng)險(xiǎn)越來越?。划?dāng)配送時(shí)間T0和配送費(fèi)用C0不變時(shí)，隨著置信水平β的增加，拖期風(fēng)險(xiǎn)越來越大。4PL供應(yīng)商可以根據(jù)客戶不同的風(fēng)險(xiǎn)偏好、時(shí)間和成本需求選擇合適的配送方案以控制風(fēng)險(xiǎn)。

為了更好地測(cè)試DA-HS算法的性能，將算法求解不同實(shí)例的結(jié)果與DA-GA、HS和EA進(jìn)行了對(duì)比分析。表3給出了當(dāng)客戶的置信水平β=0.9時(shí)，相同配送時(shí)間和配送費(fèi)用約束下，4種算法求解5個(gè)實(shí)例的結(jié)果對(duì)比。“--”表示EA不能在有限時(shí)間內(nèi)得到可行解。其中，15節(jié)點(diǎn)的時(shí)間和費(fèi)用約束分別為70和115；30節(jié)點(diǎn)的時(shí)間和費(fèi)用約束分別為115和190；50節(jié)點(diǎn)的時(shí)間和費(fèi)用約束分別為150和165；100節(jié)點(diǎn)的時(shí)間和費(fèi)用約束分別為210和260。

表3 4種算法求解不同規(guī)模問題的結(jié)果對(duì)比Tab.3 Comparison of four algorithms for different size

由表3中數(shù)據(jù)可知，本文設(shè)計(jì)的算法能夠很快地求解不同規(guī)模的實(shí)例且解的質(zhì)量很好。對(duì)于7節(jié)點(diǎn)問題，DA-HS、DA-GA、和HS能快速地獲得和EA一樣的最優(yōu)解。對(duì)于中等及以上規(guī)模的問題，EA不能在有效時(shí)間內(nèi)得到最優(yōu)解，而其他3種智能計(jì)算方法均可以得到相同的最好結(jié)果。但是隨著問題規(guī)模的增大HS求解時(shí)間增加的很快，而最好率卻逐漸下降，究其原因，HS將大量的時(shí)間浪費(fèi)在不合法解的修復(fù)上；DA-HS和DA-GA、避免了解的修復(fù)環(huán)節(jié)，因此節(jié)省了大量的計(jì)算時(shí)間用來獲得更高質(zhì)量的解。對(duì)于100節(jié)點(diǎn)的問題，DA-HS仍能快速獲得最好結(jié)果，且有較高的最好率，且最好率及求解時(shí)間較DA-GA更好，充分說明了DA-HS具有較高水平的求解速度和質(zhì)量。本文設(shè)計(jì)的算法是求解帶有拖期風(fēng)險(xiǎn)的4PLROP問題行之有效的方法。

4 結(jié)論

本文充分考慮現(xiàn)實(shí)復(fù)雜物流配送過程運(yùn)輸時(shí)間和中轉(zhuǎn)時(shí)間的不確定性而導(dǎo)致配送任務(wù)不能按時(shí)完工的情況，在引入了在險(xiǎn)值(VaR)來量化拖期風(fēng)險(xiǎn)大小的基礎(chǔ)上，對(duì)4PL路徑優(yōu)化問題展開研究。建立以最小化拖期風(fēng)險(xiǎn)為目標(biāo)，費(fèi)用為約束的數(shù)學(xué)模型，并設(shè)計(jì)了DA-HS算法對(duì)問題進(jìn)行求解。通過對(duì)不同實(shí)例的求解結(jié)果進(jìn)行分析表明，該算法能夠快速地求解大規(guī)模問題，且算法具有很好的穩(wěn)定性，優(yōu)于DA-GA、HS和EA。為考慮拖期風(fēng)險(xiǎn)的4PL路徑優(yōu)化問題提供了可供參考的數(shù)學(xué)模型及有效的求解算法，4PL供應(yīng)商可以根據(jù)客戶的風(fēng)險(xiǎn)偏好和預(yù)算來決策可行的配送方案。