薄桂華 黃敏 柳欣

0 引言

不確定環(huán)境下的路徑規(guī)劃問題,在計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)中已被廣泛地研究,尤其是在不同領(lǐng)域如通信路由和交通工程的應(yīng)用[1-2]．由于交通網(wǎng)絡(luò)擁擠、硬件故障、交通擁堵或事故、臨時(shí)建筑項(xiàng)目和天氣條件等因素,使得不確定性無處不在．在配送過程中,因?yàn)槿狈皶r(shí)更新的在線信息(道路狀況等),客戶將考慮在可能的費(fèi)用范圍內(nèi),做出較好的路徑選擇以規(guī)避風(fēng)險(xiǎn),即在路徑選擇決策時(shí)往往涉及到配送費(fèi)用和承擔(dān)風(fēng)險(xiǎn)之間的權(quán)衡．

實(shí)際配送過程中,客戶更希望在某個(gè)時(shí)間段內(nèi)接受配送服務(wù),而不是具體時(shí)間點(diǎn)．即客戶有時(shí)間窗口限制,這里的時(shí)間窗口限定了配送服務(wù)必須在該時(shí)間段內(nèi)完成．如果配送任務(wù)提前完成,將可能帶來庫存成本等費(fèi)用,增加了配送成本就等于增加了損失而減少了收益,從而帶來提前風(fēng)險(xiǎn),該風(fēng)險(xiǎn)是不容忽視的一個(gè)現(xiàn)實(shí)情況．如果配送任務(wù)延后完成,將降低第四方物流(Forth-Party Logistics,4PL)企業(yè)的信譽(yù)度,從而帶來收益的損失,即帶來拖期風(fēng)險(xiǎn)．

陳建清等[3]指出4PL路徑優(yōu)化問題(4PL Routing Optimization Problem,4PLROP)是4PL研究的關(guān)鍵問題之一．4PL供應(yīng)商不僅要對(duì)配送路徑進(jìn)行優(yōu)化選擇,還要對(duì)第三方物流(Third-Party Logistics,3PL)供應(yīng)商進(jìn)行選擇,這樣使問題更為復(fù)雜,增加了問題求解難度．李秀等[4]把問題分解為路線優(yōu)化和供應(yīng)商選擇兩個(gè)子問題,在最短路線計(jì)算完成后,再進(jìn)行供應(yīng)商選擇,這樣會(huì)帶來最優(yōu)性的損失．此外,該方法在計(jì)算配送路線時(shí)沒有選擇供應(yīng)商,因而在第二階段很可能受已固定的路線限制,選擇到不同的供應(yīng)商而產(chǎn)生額外的轉(zhuǎn)運(yùn)費(fèi)用．Chen等[5]設(shè)計(jì)了Dijkstra算法和遺傳算法求解4PLROP,為4PLROP的研究奠定了基礎(chǔ)．Huang等[6-7]給出了4PLROP具體的數(shù)學(xué)模型,提出了免疫算法和混合免疫算法來求解4PLROP,并驗(yàn)證了算法的有效性．任亮等[8]針對(duì)環(huán)境的不確定性建立了帶有時(shí)間窗和隨機(jī)運(yùn)輸時(shí)間4PLROP的機(jī)會(huì)模型,并采用蟻群算法對(duì)模型進(jìn)行求解,驗(yàn)證了算法的有效性．Tao等[9]從費(fèi)用折扣角度對(duì)4PLROP建立了混合整數(shù)規(guī)劃模型．文獻(xiàn)[10-12]分別考慮了帶有硬時(shí)間窗和軟時(shí)間窗約束的4PLROP問題,并采用和聲搜索對(duì)問題進(jìn)行求解．黃敏等[13]建立考慮單一運(yùn)輸方式的4PL路徑優(yōu)化模型,并根據(jù)問題特點(diǎn)設(shè)計(jì)混合算法對(duì)模型進(jìn)行求解．盧福強(qiáng)等[14]針對(duì)物流運(yùn)輸過程中3PL供應(yīng)商

運(yùn)輸時(shí)間和運(yùn)輸成本不確定的問題,基于比例效用理論,建立了考慮客戶同時(shí)厭惡拖期和超支的4PLROP模型．但是目前大多文獻(xiàn)都沒有考慮配送時(shí)間和轉(zhuǎn)運(yùn)時(shí)間的隨機(jī)性以及由此帶來的不能按期完成配送任務(wù)的風(fēng)險(xiǎn)．文獻(xiàn)[15]建立了考慮完工風(fēng)險(xiǎn)的4PLROP的相關(guān)機(jī)會(huì)規(guī)劃模型和相關(guān)機(jī)會(huì)規(guī)劃等價(jià)確定性模型,并設(shè)計(jì)了遺傳算法對(duì)問題進(jìn)行求解．文獻(xiàn)[16]引入在險(xiǎn)值來刻畫及度量拖期風(fēng)險(xiǎn)的大小,建立以最小化拖期風(fēng)險(xiǎn)為目標(biāo)、配送費(fèi)用為約束的數(shù)學(xué)模型，并對(duì)問題進(jìn)行了求解,但是并未考慮提前風(fēng)險(xiǎn)．

本文不僅考慮拖期風(fēng)險(xiǎn),還考慮提前風(fēng)險(xiǎn)．研究的目的在于如何合理地選擇合適的配送方案,使提前和拖期風(fēng)險(xiǎn)在客戶可接受范圍內(nèi)的情況下配送費(fèi)用最?。纱?引入完工概率這一概念,通過令完工時(shí)間在時(shí)間窗口內(nèi)實(shí)現(xiàn)的概率大于某個(gè)置信水平從而給出最優(yōu)的配送方案．對(duì)于風(fēng)險(xiǎn)規(guī)避者來說,當(dāng)然是提前和拖期風(fēng)險(xiǎn)越小越好,等價(jià)于完工時(shí)間在時(shí)間窗口內(nèi)實(shí)現(xiàn)的概率越大越好,即完工概率越大越好．因此,將提前和拖期風(fēng)險(xiǎn)小于某個(gè)值的問題轉(zhuǎn)化成完工概率大于某個(gè)值的問題．

本文針對(duì)帶有提前和拖期風(fēng)險(xiǎn)的4PL路徑優(yōu)化問題,建立以最小化配送費(fèi)用為目標(biāo)、提前和拖期風(fēng)險(xiǎn)為約束的數(shù)學(xué)模型,并采用嵌入刪除算法的和聲搜索算法(Deletion Algorithm Embedded Harmony Search,DA-HS)對(duì)問題進(jìn)行求解,測(cè)試不同規(guī)模的實(shí)例,測(cè)試結(jié)果表明所提模型和算法是有效的．

1 問題描述

在求解4PL路徑優(yōu)化問題時(shí),4PL供應(yīng)商不僅要對(duì)配送路徑進(jìn)行優(yōu)化選擇,還要對(duì)提供配送任務(wù)的3PL供應(yīng)商進(jìn)行選擇．而4PL供應(yīng)商為客戶提供配送方案時(shí),要考慮到配送時(shí)間和中轉(zhuǎn)時(shí)間的不確定性而導(dǎo)致的提前和拖期風(fēng)險(xiǎn),對(duì)風(fēng)險(xiǎn)進(jìn)行量化及監(jiān)控,目標(biāo)是求得滿足提前和拖期風(fēng)險(xiǎn)約束的運(yùn)輸費(fèi)用最小的配送方案．

將問題用一個(gè)多重圖G(V,E)描述,其中|V|=n是節(jié)點(diǎn)的集合,E是邊的集合．如圖1所示,圖中的s是供應(yīng)城市,t是需求城市,其他節(jié)點(diǎn)是轉(zhuǎn)運(yùn)城市,它們具有費(fèi)用、時(shí)間屬性．由于任意兩個(gè)城市之間均可能存在多個(gè)3PL供應(yīng)商提供配送服務(wù),故圖中任意兩點(diǎn)間可能有多條邊(每條邊代表一個(gè)3PL,邊上的數(shù)字是3PL的編號(hào)),每條邊都具有費(fèi)用和時(shí)間屬性．目標(biāo)是求得從供應(yīng)城市到需求城市滿足提前和拖期風(fēng)險(xiǎn)約束的費(fèi)用最小的配送方案．

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

1.1 變量定義

(1)

(2)

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

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

(3)

(4)

(5)

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

(6)

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

(7)

1.3 模型的轉(zhuǎn)化

引理1[17]有限個(gè)相互獨(dú)立的正態(tài)分布隨機(jī)變量的線性組合仍然服從正態(tài)分布．

(8)

其中,

(9)

(10)

因此,約束(4)和(5)可以轉(zhuǎn)化成

(11)

(12)

因此,數(shù)學(xué)模型包括目標(biāo)函數(shù)(3)和約束(12)、(9)、(10)、(6)和(7)．

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

本文針對(duì)模型的非線性特點(diǎn)和4PLROP問題所特有的特點(diǎn)設(shè)計(jì)了嵌入刪除算法的和聲搜索算法(DA-HS)．該算法主要包括編碼設(shè)計(jì)、初始化問題和算法參數(shù)、初始化HM、新解的產(chǎn)生、更新HM、終止準(zhǔn)則．

主要設(shè)計(jì)思想[16]是:先在多重圖上用HS算法的優(yōu)化機(jī)制產(chǎn)生一個(gè)簡(jiǎn)單圖;然后用DA算法在此簡(jiǎn)單圖上求出前K條費(fèi)用最短路徑,DA算法的詳細(xì)步驟可參考文獻(xiàn)[18-19]．由于最優(yōu)解不一定是某個(gè)圖上的最短路徑,也有可能是次最短路徑,因此該算法求前K條最短路徑而不是最短路徑．

2.1 編碼方案

采用以邊為基礎(chǔ)的整數(shù)編碼[16]．先將多重圖(圖1)用鄰接矩陣表示,矩陣中的行和列分別代表多重圖中的節(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為解向量h的第i個(gè)解分量hi的最大取值,N為該問題的編碼長(zhǎng)度,即解分量的個(gè)數(shù)．當(dāng)用解向量h表示簡(jiǎn)單圖時(shí),每個(gè)解分量取值為1≤hi≤ni,當(dāng)用解向量h表示路徑時(shí),每個(gè)解分量hi可以取零值0≤hi≤ni．

以圖1為例,其鄰接矩陣如式(13)所示,將矩陣中的上三角非零元素逐行從左到右編碼可得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．

圖2給出了解向量h=[3 2 1 1 2 3 2 2 2 1 3 1]所代表的簡(jiǎn)單圖,調(diào)用DA算法求得的圖 2上的最短路徑,即h=[0 2 0 0 0 0 2 0 2 1 0 0]如圖2中虛線所示．

0123456 [rij]7×7=01234560340000002220002030400230323020300200420020000000.(13)

圖2 簡(jiǎn)單圖及簡(jiǎn)單圖上的路徑Fig.2 Simple graph and the route in the simple graph

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

初始化問題的參數(shù):可允許配送服務(wù)完成的最早時(shí)間a和最晚時(shí)間l、和聲記憶庫的大小HMS、參數(shù)K、和聲記憶保留概率HMCR、記憶擾動(dòng)概率PAR、最大迭代次數(shù)NG、置信水平β．

2.3 初始化HM

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

2.4 產(chǎn)生新解

主要思想:先用HS算法的優(yōu)化機(jī)制產(chǎn)生新的簡(jiǎn)單圖,然后調(diào)用DA求出前K條費(fèi)用最短路徑．該算法在每次迭代過程中都產(chǎn)生K個(gè)新解,能夠在一定程度上加快算法的收斂速度．

由于采用HS來產(chǎn)生新的簡(jiǎn)單圖,因此每個(gè)解分量hi只能在0和ni之間取值．為了產(chǎn)生新的簡(jiǎn)單圖,現(xiàn)對(duì)每個(gè)解分量hi進(jìn)行如下操作[16]:

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

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

2.5 更新HM

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

1) 計(jì)算新解目標(biāo)函數(shù)值,判斷新解是否滿足約束(12),若滿足則轉(zhuǎn)下步,否則轉(zhuǎn)3);

2) 根據(jù)目標(biāo)函數(shù)值判斷新解是否比HM中的最差解要好,若好則用新解替換HM中最差解,否則轉(zhuǎn)下步;

3) 若K個(gè)新解都判斷完,則更新HM并對(duì)HM中所有解排序，否則轉(zhuǎn)1)．

2.6 算法步驟

Step1:初始化算法的參數(shù):可允許服務(wù)完成的最早時(shí)間a和最晚時(shí)間l、HMS、K、HMCR、PAR、NG、置信水平β．

Step2:初始化HM,對(duì)HM中所有解(HMS個(gè))按目標(biāo)函數(shù)進(jìn)行排序．

Step3:產(chǎn)生新解．用HS算法的優(yōu)化機(jī)制生成新的簡(jiǎn)單圖,然后調(diào)用DA算法求出前K條費(fèi)用最短路徑．

Step4:更新HM．

Step5:如果迭代次數(shù)達(dá)到NG,則算法結(jié)束并輸出最好解，否則轉(zhuǎn)Step3．

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證上述問題的數(shù)學(xué)模型和算法的有效性,本節(jié)測(cè)試了5個(gè)不同規(guī)模的算例．首先,以7節(jié)點(diǎn)問題為例,詳細(xì)描述了算法參數(shù)對(duì)算法性能的影響并獲得一組最佳參數(shù)組合．然后,對(duì)算法求解不同規(guī)模問題的求解質(zhì)量和效率進(jìn)行了對(duì)比分析．算法采用VC++語言實(shí)現(xiàn),運(yùn)行環(huán)境為Intel(R) Core(TM)i7-2600CPU 3.40 GHz PC臺(tái)式機(jī)．

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

算法參數(shù)的獲取是經(jīng)過大量仿真實(shí)驗(yàn)獲得的,即當(dāng)其他參數(shù)不變時(shí),測(cè)試某一個(gè)參數(shù)對(duì)算法最好率的影響．最好率為算法獲得最好解的次數(shù)占算法運(yùn)行總次數(shù)的比率．其中,計(jì)算最好率時(shí)算法運(yùn)行總次數(shù)為100．

圖3—7給出了當(dāng)置信水平β=0.8、時(shí)間窗口約束[a,l]=[65,85]時(shí),DA-HS算法求解7節(jié)點(diǎn)問題的參數(shù)測(cè)試過程,其中“最好率”是算法運(yùn)行100次中求得的最好解的個(gè)數(shù)與100的比率．仿真實(shí)驗(yàn)表明,DA-HS算法最好的參數(shù)分別為K=4(圖 3),HMS=5(圖 4),HMCR=0.8(圖 5),PAR=0.25(圖6),NG=50(圖 7)．

圖3 參數(shù)K性能分析Fig.3 Performance of parameter K

圖4 參數(shù)HMS性能分析Fig.4 Performance of parameter HMS

圖5 參數(shù)HMCR性能分析Fig.5 Performance of parameter HMCR

圖6 參數(shù)PAR性能分析Fig.6 Performance of parameter PAR

圖7 參數(shù)NG性能分析Fig.7 Performance of parameter NG

表1給出了DA-HS算法求解7節(jié)點(diǎn)問題的結(jié)果．由表1可知:當(dāng)β=0.8、時(shí)間窗口約束[a,l]=[65,85]時(shí),算法獲得的最好解為95,對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v5,2,v3,1,vt},對(duì)應(yīng)的置信水平為0.867 642,滿足約束;當(dāng)時(shí)間窗口約束[a,l]=[70,90]時(shí),算法獲得的最好解為93,對(duì)應(yīng)的配送路徑為R={vs,4,v2,2,v5,2,v3,1,vt},對(duì)應(yīng)的置信水平為0.814 66,滿足約束．當(dāng)β=0.9、時(shí)間窗口約束[a,l]=[65,85]時(shí),算法獲得的最好解為96,對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v5,1,v3,1,vt},對(duì)應(yīng)的置信水平為0.904 403,滿足約束;當(dāng)時(shí)間窗口約束[a,l]=[70,90]時(shí),算法獲得的最好解為96,對(duì)應(yīng)的配送路徑為R={vs,2,v2,2,v5,1,v3,1,vt},對(duì)應(yīng)的置信水平為0.927 521,滿足約束．由表1中數(shù)據(jù)還可知：算法的求解時(shí)間僅為0.1 s,說明算法的求解速度很快;算法的最好率超過90%,說明算法的穩(wěn)定性很高．

表1 7節(jié)點(diǎn)問題算法的求解結(jié)果Table 1 Results of algorithm for solving seven nodes problem

3.2 實(shí)例分析

本節(jié)分別求解了7,15,30,50和100節(jié)點(diǎn)的5個(gè)不同規(guī)模的算例．其中,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)間有邊相連[20],

有邊相連的節(jié)點(diǎn)間邊的個(gè)數(shù)在閉區(qū)間[2,4]中隨機(jī)生成,邊的費(fèi)用和時(shí)間、節(jié)點(diǎn)的費(fèi)用和時(shí)間都是隨機(jī)生成的．其中,50節(jié)點(diǎn)算例的a=3,d=0.75;100節(jié)點(diǎn)算例的a=4,d=0.7．

表2給出了當(dāng)置信水平β=0.8時(shí),7,15,30,50和100節(jié)點(diǎn)的實(shí)例的求解結(jié)果．由表2可知,本文設(shè)計(jì)的算法能夠很快地求解不同規(guī)模的實(shí)例．對(duì)于中等規(guī)模的問題,如15和30節(jié)點(diǎn)的問題,算法的求解時(shí)間不到1 s，即使對(duì)于大規(guī)模問題,如100節(jié)點(diǎn)的問題,算法的求解時(shí)間僅為1 s,充分說明了算法具有很快的求解速度．算法的最好率都很高,如15節(jié)點(diǎn)問題,NG為50時(shí),最好率高達(dá)0.98;對(duì)于大規(guī)模問題,如100節(jié)點(diǎn)問題,最好率也高達(dá)92%．

表2 當(dāng)β=0.8時(shí)，不同實(shí)例的求解結(jié)果Table 2 Results of different cases when β=0.8

表3給出了當(dāng)客戶的置信水平β=0.9時(shí),不同算例的求解結(jié)果．可以看出算法的求解速度和穩(wěn)定性都保持很高的水平．本文設(shè)計(jì)的算法為4PL供應(yīng)商提供了多種可供選擇的配送方案,4PL供應(yīng)商可以根據(jù)客戶的不同風(fēng)險(xiǎn)偏好來決策可行的配送方案．

表3 當(dāng)β=0.9時(shí)，不同實(shí)例的求解結(jié)果Table 3 Results of different cases when β=0.9

4 結(jié)論

針對(duì)現(xiàn)實(shí)配送過程中配送任務(wù)既有可能延后完成也可能提前完成,從而帶來損失的實(shí)際情況,研究了帶有提前和拖期風(fēng)險(xiǎn)的4PL路徑優(yōu)化問題．建立了以最小化物流配送費(fèi)用為優(yōu)化目標(biāo)、以提前和拖期風(fēng)險(xiǎn)為約束的數(shù)學(xué)模型,根據(jù)問題的特點(diǎn),提出了嵌入刪除算法的和聲搜索算法．通過對(duì)5個(gè)不同規(guī)模的算例的求解結(jié)果進(jìn)行比較分析,表明所提模型和算法是有效的,為帶有提前/拖期風(fēng)險(xiǎn)的4PL路徑優(yōu)化問題提供了行之有效的模型和算法．