任 亮，黃 敏，王洪峰，王興偉

(1.東北大學(xué)信息科學(xué)與工程學(xué)院流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室,沈陽(yáng) 110819;2.武漢科技大學(xué)恒大管理學(xué)院,武漢 430081)

0 引言

隨著電子商務(wù)的發(fā)展以及市場(chǎng)競(jìng)爭(zhēng)的加劇，人們對(duì)物流服務(wù)的要求不斷提高[1-2]。而傳統(tǒng)的第三方物流(Third Party Logistics, 3PL)由于協(xié)作、整合能力不足等問(wèn)題，很難滿足當(dāng)前激烈競(jìng)爭(zhēng)的市場(chǎng)需求[3]。因此，以整合復(fù)雜供應(yīng)鏈資源為主要目的的第四方物流(Fourth Party Logistics, 4PL)吸引了國(guó)內(nèi)外的廣泛關(guān)注[4-5]。

4PL是一個(gè)供應(yīng)鏈的集成商，它對(duì)其內(nèi)部和具有互補(bǔ)性服務(wù)供應(yīng)商所擁有的不同資源、能力和技術(shù)進(jìn)行整合和管理，以提供一整套供應(yīng)鏈解決方案[6]。

路徑問(wèn)題是4PL優(yōu)化中的關(guān)鍵問(wèn)題[7]。4PL路徑問(wèn)題作用于4PL服務(wù)中的配送過(guò)程，直接影響客戶的滿意度和企業(yè)收益，許多學(xué)者對(duì)其進(jìn)行了研究[8-9]。研究中多借鑒網(wǎng)絡(luò)中基于圖的研究方法[10]，主要有兩種思路。第一種思路是在4PL網(wǎng)絡(luò)上先依據(jù)一定規(guī)則選取路徑，而后考慮在指定路徑上的優(yōu)化問(wèn)題，即在指定路徑上選擇合作的3PL供應(yīng)商[11]。Li等[12]將4PL優(yōu)化分解為路線優(yōu)化和供應(yīng)商選擇兩個(gè)子問(wèn)題，在最優(yōu)路線計(jì)算完成后，用資源分配模型進(jìn)行供應(yīng)商選擇。第二種思路是同時(shí)選擇路徑和供應(yīng)商。Zhang等[13]將一個(gè)多重有向圖中的每條邊描述為一個(gè)3PL供應(yīng)商，同時(shí)考慮路徑和3PL供應(yīng)商信息，清晰的描述了該問(wèn)題，并以物流費(fèi)用最小作為目標(biāo)，基于Dijkstra方法快速求解了小規(guī)模的4PL路徑問(wèn)題。李銳等[14]用無(wú)向多重圖描述4PL網(wǎng)絡(luò)，同樣將圖中的每條邊描述為一個(gè)3PL供應(yīng)商，以最小化網(wǎng)絡(luò)總成本為目標(biāo)，研究了較為復(fù)雜的4PL網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。由于第二種思路從全局角度優(yōu)化供應(yīng)鏈，同時(shí)考慮了路徑選擇和供應(yīng)商選擇，可以獲得較好的優(yōu)化效果。

上述研究大多是針對(duì)單一目標(biāo)問(wèn)題，考慮物流費(fèi)用最小或物流時(shí)間最短。但在實(shí)際物流運(yùn)行中，往往需要權(quán)衡費(fèi)用和時(shí)間因素。Liu等[15]從調(diào)度排序角度，以最小化總運(yùn)輸費(fèi)用、運(yùn)輸時(shí)間以及拖期時(shí)間為目標(biāo)，研究了多目標(biāo)4PL優(yōu)化問(wèn)題。該文將物流任務(wù)分解成多階段活動(dòng)，研究了如何為物流活動(dòng)選擇合適的3PL供應(yīng)商，但沒(méi)有考慮運(yùn)輸過(guò)程中的路徑選擇問(wèn)題。因此，本文從多目標(biāo)的角度研究4PL路徑問(wèn)題，在集成考慮供應(yīng)商選擇優(yōu)化和路徑選擇優(yōu)化兩方面的基礎(chǔ)上，基于多重圖，以物流費(fèi)用最小和時(shí)間最短為目標(biāo)，建立相應(yīng)的優(yōu)化模型。由于該問(wèn)題屬NP難問(wèn)題，采用智能優(yōu)化算法進(jìn)行求解，數(shù)值實(shí)例表明了算法的有效性。

1 問(wèn)題描述

本文要解決的問(wèn)題是，在多條路徑以及多個(gè)3PL供應(yīng)商可供選擇的情形下，為客戶提供一套將運(yùn)輸任務(wù)從初始節(jié)點(diǎn)配送到目的節(jié)點(diǎn)的運(yùn)輸方案。方案要求滿足一定的承載能力以及信譽(yù)約束，并最小化總運(yùn)輸費(fèi)用以及總運(yùn)輸時(shí)間。

作為供應(yīng)鏈的整合者，4PL集成供應(yīng)鏈網(wǎng)絡(luò)信息以及所有備選3PL供應(yīng)商信息，為客戶設(shè)計(jì)路徑方案的同時(shí)需要選擇3PL供應(yīng)商。對(duì)于同樣一段運(yùn)輸任務(wù)，基于不同的運(yùn)輸方式、不同的服務(wù)質(zhì)量、需要時(shí)間的不同等特點(diǎn)，可能會(huì)有多個(gè)3PL供應(yīng)商可供選擇。綜合到一張多重圖上，可用具有多屬性的邊來(lái)描述，每條邊表示在該段路徑上提供服務(wù)的某個(gè)3PL供應(yīng)商。4PL選擇最優(yōu)3PL供應(yīng)商的組合，即多重圖中選擇最優(yōu)路徑，既考慮了路徑優(yōu)化，又考慮了3PL供應(yīng)商的選擇問(wèn)題。

圖1 4PL路徑問(wèn)題多重圖Fig.1 Multi-graph of 4PL routing problem

數(shù)學(xué)模型建立如下：

(1)

(2)

s.t.

Pijk≥Pxijk(R)

(3)

Dijk≥Dxijk(R)

(4)

(5)

(6)

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

(7)

式(1)和式(2)為目標(biāo)函數(shù)，表示最小化該運(yùn)輸任務(wù)的總運(yùn)輸費(fèi)用和時(shí)間；式(3)表示被選3PL供應(yīng)商的承載能力應(yīng)滿足客戶需求；式(4)表示被選3PL供應(yīng)商的信譽(yù)滿足客戶需求；式(5)和式(6)中xijk(R)和yi(R)為決策變量，分別表示邊和節(jié)點(diǎn)是否被R選中；式(7)表示R為一條從vs出發(fā)并結(jié)束于ve的通路。

上述模型是一個(gè)多目標(biāo)決策問(wèn)題，且目標(biāo)之間相互制約。眾多可能解中，一般不存在一個(gè)優(yōu)于其他所有解的方案，即并不存在絕對(duì)最優(yōu)解?？紤]到本問(wèn)題是一個(gè)多重圖上的NP難問(wèn)題，選擇智能算法與線性加權(quán)的選好函數(shù)法相結(jié)合的方法進(jìn)行求解。在算法迭代過(guò)程中，每一代種群先進(jìn)行支配關(guān)系比較，獲得當(dāng)前非支配集，而后再通過(guò)加權(quán)更新種群信息。并將選好權(quán)值設(shè)定為參數(shù)，針對(duì)決策者不同的目標(biāo)權(quán)衡求解基于多重圖的多目標(biāo)路徑優(yōu)化問(wèn)題。分別給種群非支配個(gè)體的兩個(gè)目標(biāo)加上權(quán)重系數(shù)α1和α2，目標(biāo)函數(shù)可表示為：

min{α1C+α2T}

(8)

其中

α1+α2=1

(9)

(10)

(11)

由于通過(guò)權(quán)重系數(shù)α1和α2對(duì)費(fèi)用和時(shí)間進(jìn)行權(quán)衡，決策者可以根據(jù)側(cè)重點(diǎn)的不同，對(duì)系數(shù)進(jìn)行不同的權(quán)重分配，使之符合當(dāng)前物流的實(shí)際運(yùn)作。

上述模型是一個(gè)基于離散點(diǎn)、多屬性的約束NP難問(wèn)題，因此，采用對(duì)離散問(wèn)題具有很好契合性的蟻群算法進(jìn)行求解。

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

蟻群算法是20世紀(jì)90年代發(fā)展起來(lái)的一種模仿螞蟻群體行為的智能化算法。該算法引入正反饋并行機(jī)制，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法結(jié)合等優(yōu)點(diǎn)[16]。尤其針對(duì)離散路徑優(yōu)化類(lèi)問(wèn)題，用螞蟻覓食來(lái)模擬整個(gè)路徑的尋優(yōu)過(guò)程，具有很好的契合性。任務(wù)的起點(diǎn)為螞蟻的出發(fā)點(diǎn)，任務(wù)的終點(diǎn)為螞蟻食物所在位置，可行路為螞蟻覓食可能行走的路徑。因此，蟻群算法可以很好的模擬本問(wèn)題的求解過(guò)程。

停滯現(xiàn)象是造成蟻群算法容易陷入局部最優(yōu)的根本原因。針對(duì)此問(wèn)題，本文采用動(dòng)態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法[17]，引入動(dòng)態(tài)調(diào)整的選擇策略，以提高蟻群算法的全局搜索能力和搜索速度。改進(jìn)轉(zhuǎn)移策略描述如下：

(12)

(13)

其中，NP為種群規(guī)模，NG為最大迭代次數(shù)，ng為當(dāng)前迭代次數(shù)。i為當(dāng)前節(jié)點(diǎn)標(biāo)號(hào)，z為當(dāng)前可供選擇的第z條邊。piz(ng)為第ng代時(shí)當(dāng)前邊(i,z)的選擇概率。allowedi為節(jié)點(diǎn)i當(dāng)前可供選擇的邊的集合。τiz(ng)為第ng代時(shí)當(dāng)前邊的信息素啟發(fā)信息，ηiz為當(dāng)前邊的路徑啟發(fā)信息。ηiz=1/Ciz，其中Ciz為當(dāng)前邊(i,z)的費(fèi)用，max{ηiz}表示啟發(fā)信息ηiz的最大值。α和β分別為信息素和路徑信息的相對(duì)重要程度。δ是選擇策略調(diào)節(jié)系數(shù)，當(dāng)δ為0時(shí)，χiz(ng)取值為1，此時(shí)該改進(jìn)算法即退化為基本蟻群算法。qiz是從第一次迭代開(kāi)始，經(jīng)過(guò)邊(i,z)的螞蟻總個(gè)數(shù)?？梢钥闯觯?dāng)?shù)^(guò)程趨于次優(yōu)解時(shí)，雖然次優(yōu)解上的信息素不斷增強(qiáng)，但同時(shí)qiz也在不斷增大，χiz(ng)值不斷減小，其選擇概率也不斷減小，從而抑制因次優(yōu)解上信息素過(guò)度劇增而導(dǎo)致的過(guò)早收斂，有利于算法的全局搜索。

圖2 改進(jìn)蟻群算法流程圖Fig.2 Flowchart of the improved ant colony algorithm

信息素更新規(guī)則如式(14)和(15)所示：

τiz(ng+1)=ρτiz(ng)+Δτiz(ng)

(14)

(15)

算法流程圖如圖2所示。

3 實(shí)例分析

假設(shè)某4PL公司承接了某一地區(qū)的供應(yīng)鏈物流業(yè)務(wù)，需要執(zhí)行從供應(yīng)鏈起始節(jié)點(diǎn)到目的節(jié)點(diǎn)的運(yùn)輸任務(wù)。任務(wù)要求滿足一定的承載能力以及信譽(yù)約束，并最小化總運(yùn)輸費(fèi)用以及總運(yùn)輸時(shí)間。

3.1 參數(shù)分析

為測(cè)試算法性能，首先定義相關(guān)參數(shù)。算法運(yùn)行100次，Best表示100次中的最好值，Bad表示最差值，Mean表示平均值，Time表示算法運(yùn)行一次所需要的時(shí)間，S表示標(biāo)準(zhǔn)偏差，如式(16)所示。

(16)

算法參數(shù)取值均為經(jīng)多次測(cè)試后，算法性能表現(xiàn)較好時(shí)的一組參數(shù)組合。測(cè)試過(guò)程如表1所示。表1為7節(jié)點(diǎn)實(shí)例中，當(dāng)α1和α2分別取0.6和0.4時(shí)，測(cè)試改進(jìn)算法中迭代次數(shù)對(duì)結(jié)果的影響。并且，從表1可以看出，針對(duì)小規(guī)模問(wèn)題，算法能夠很快求得所提出問(wèn)題的最優(yōu)解(此時(shí)問(wèn)題規(guī)模較小，實(shí)驗(yàn)中通過(guò)枚舉算法驗(yàn)證其為最優(yōu)解)。

表1 迭代次數(shù)NG對(duì)結(jié)果的影響Tab.1 The effect of NG on the results

3.2 算法對(duì)比分析

如前文所述，改進(jìn)算法在δ為0時(shí)，即轉(zhuǎn)化為基本蟻群算法。因此，綜合三個(gè)實(shí)例，在測(cè)得的較好參數(shù)組合情況下，δ分別取為0和測(cè)得值，即可對(duì)ACA和IACA進(jìn)行對(duì)比，對(duì)比結(jié)果如表2所示。可以看出，對(duì)于小規(guī)模以及中等規(guī)模問(wèn)題，兩種算法均可以快速有效的求得較好解。對(duì)于較大規(guī)模問(wèn)題，基于動(dòng)態(tài)調(diào)整選擇策略的IACA比ACA具有較明顯的優(yōu)越性。無(wú)論最差解、最好解，還是平均值，IACA均優(yōu)于ACA。隨著問(wèn)題規(guī)模的增大，算法搜索需要的時(shí)間增長(zhǎng)，標(biāo)準(zhǔn)偏差變大。針對(duì)較大規(guī)模問(wèn)題，改進(jìn)算法依舊能夠有效的獲得較好解。

表2 ACA與IACA結(jié)果對(duì)比Tab.2 Comparison of ACA and IACA

3.3 多目標(biāo)分析

本文考慮的是雙目標(biāo)優(yōu)化問(wèn)題，通過(guò)對(duì)權(quán)重系數(shù)α1和α2的調(diào)整，可對(duì)費(fèi)用和時(shí)間進(jìn)行權(quán)衡。根據(jù)決策者側(cè)重點(diǎn)的不同，可以對(duì)該系數(shù)進(jìn)行不同的權(quán)重分配。表3為15節(jié)點(diǎn)實(shí)例在不同α1和α2時(shí)的結(jié)果對(duì)比?？梢钥闯觯?dāng)費(fèi)用和時(shí)間權(quán)重系數(shù)中有一個(gè)為0時(shí)，該問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。隨著費(fèi)用權(quán)重系數(shù)不斷變大，決策者對(duì)費(fèi)用的重要性感知不斷增強(qiáng)，解的目標(biāo)值逐漸增加。在不同權(quán)值分配下，改進(jìn)算法均能快速、有效獲得問(wèn)題的較好解。

表3 加權(quán)系數(shù)對(duì)結(jié)果的影響Tab.3 The effect of weighting coefficient on the results

4 結(jié)語(yǔ)

本文針對(duì)4PL路徑問(wèn)題，集成考慮了路徑選擇優(yōu)化和供應(yīng)商選擇優(yōu)化兩方面的問(wèn)題。建立了以物流費(fèi)用最少和運(yùn)輸時(shí)間最短為目標(biāo)的數(shù)學(xué)模型，為第四方物流路徑優(yōu)化提供了建模工具。進(jìn)而，采用改進(jìn)蟻群算法對(duì)模型進(jìn)行求解，并通過(guò)實(shí)例與基本蟻群算法進(jìn)行對(duì)比。對(duì)比結(jié)果表明，當(dāng)問(wèn)題規(guī)模較小時(shí)，兩種算法對(duì)該類(lèi)問(wèn)題都具有較好的效果。隨著問(wèn)題規(guī)模的增大，改進(jìn)算法體現(xiàn)出其優(yōu)越性。針對(duì)決策者不同的決策偏好，算法都可以快速有效的幫助決策者做出最終決策，并協(xié)助決策者設(shè)計(jì)分析偏好，從而為上述問(wèn)題提供了有效的求解工具。