考慮提前/拖期風險的第四方物流路徑優(yōu)化問題研究

薄桂華 黃敏 柳欣

0 引言

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

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

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

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

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

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

1 問題描述

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

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

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

1.1 變量定義

(1)

(2)

1.2 數學模型

基于以上變量定義,建立如下數學模型:

(3)

(4)

(5)

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

(6)

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

(7)

1.3 模型的轉化

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

(8)

其中,

(9)

(10)

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

(11)

(12)

因此,數學模型包括目標函數(3)和約束(12)、(9)、(10)、(6)和(7)．

2 算法設計

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

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

2.1 編碼方案

采用以邊為基礎的整數編碼[16]．先將多重圖(圖1)用鄰接矩陣表示,矩陣中的行和列分別代表多重圖中的節(jié)點,圖中有邊相連的兩節(jié)點對應的鄰接矩陣元素值為兩節(jié)點間的邊數,即rij;沒有邊相連時對應的鄰接矩陣元素值為0．然后將此鄰接矩陣中的上三角非零元素逐行從左到右編碼得到一個向量n=[n1n2…ni…nN],其中ni為解向量h的第i個解分量hi的最大取值,N為該問題的編碼長度,即解分量的個數．當用解向量h表示簡單圖時,每個解分量取值為1≤hi≤ni,當用解向量h表示路徑時,每個解分量hi可以取零值0≤hi≤ni．

以圖1為例,其鄰接矩陣如式(13)所示,將矩陣中的上三角非零元素逐行從左到右編碼可得7節(jié)點問題的向量n=[3 4 2 2 2 3 4 3 2 3 2 2]．由此可知,7節(jié)點問題解分量為12個,每個解分量的最大取值分別為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]所代表的簡單圖,調用DA算法求得的圖 2上的最短路徑,即h=[0 2 0 0 0 0 2 0 2 1 0 0]如圖2中虛線所示．

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

圖2 簡單圖及簡單圖上的路徑Fig.2 Simple graph and the route in the simple graph

2.2 初始化問題和算法參數

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

2.3 初始化HM

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

2.4 產生新解

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

由于采用HS來產生新的簡單圖,因此每個解分量hi只能在0和ni之間取值．為了產生新的簡單圖,現對每個解分量hi進行如下操作[16]:

1) 生成隨機數r1∈(0,1),如果r1

2) 生成隨機數r2∈(0,1),如果r2

2.5 更新HM

對新產生的K個新解依次做如下操作:

1) 計算新解目標函數值,判斷新解是否滿足約束(12),若滿足則轉下步,否則轉3);

2) 根據目標函數值判斷新解是否比HM中的最差解要好,若好則用新解替換HM中最差解,否則轉下步;

3) 若K個新解都判斷完,則更新HM并對HM中所有解排序，否則轉1)．

2.6 算法步驟

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

Step2:初始化HM,對HM中所有解(HMS個)按目標函數進行排序．

Step3:產生新解．用HS算法的優(yōu)化機制生成新的簡單圖,然后調用DA算法求出前K條費用最短路徑．

Step4:更新HM．

Step5:如果迭代次數達到NG,則算法結束并輸出最好解，否則轉Step3．

3 實驗結果與分析

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

3.1 參數測試

算法參數的獲取是經過大量仿真實驗獲得的,即當其他參數不變時,測試某一個參數對算法最好率的影響．最好率為算法獲得最好解的次數占算法運行總次數的比率．其中,計算最好率時算法運行總次數為100．

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

圖3 參數K性能分析Fig.3 Performance of parameter K

圖4 參數HMS性能分析Fig.4 Performance of parameter HMS

圖5 參數HMCR性能分析Fig.5 Performance of parameter HMCR

圖6 參數PAR性能分析Fig.6 Performance of parameter PAR

圖7 參數NG性能分析Fig.7 Performance of parameter NG

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

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

3.2 實例分析

本節(jié)分別求解了7,15,30,50和100節(jié)點的5個不同規(guī)模的算例．其中,50和100節(jié)點問題的數據是隨機產生的,隨機產生數據方法為:將n個節(jié)點隨機地放在一個a×a的正方形區(qū)域內,點(0,0)和(a,a)分別代表初始節(jié)點和目的節(jié)點,如果兩個節(jié)點間的歐幾里得距離小于等于d,則兩節(jié)點間有邊相連[20],

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

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

表2 當β=0.8時，不同實例的求解結果Table 2 Results of different cases when β=0.8

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

表3 當β=0.9時，不同實例的求解結果Table 3 Results of different cases when β=0.9

4 結論

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