模糊需求下時間依賴型車輛路徑優(yōu)化

范厚明,李 蕩,孔 靚,任曉雪

(大連海事大學交通運輸工程學院,遼寧大連 116026)

1 引言

車輛路徑問題(vehicle routing problem,VRP)由Dantzig[1]于1959年提出,屬于經(jīng)典的NP–hard問題,自提出以來,成為運籌學和組合優(yōu)化領域的前沿研究熱點問題.隨著現(xiàn)代物流的發(fā)展,城市交通負載日益繁重,傳統(tǒng)的VRP模型難以滿足快捷、高效的配送要求.為此一些學者基于現(xiàn)實中出現(xiàn)的不同情況對VRP問題進行了拓展研究,使其不斷貼近實際,如有顧客訪問時間窗限制的帶時間窗的車輛路徑問題(vehicle routing problem with time windows,VRPTW)、考慮了客戶需求不確定的模糊需求車輛路徑問題(vehicle routing problem with fuzzy demand,VRPFD)、車輛行駛速度變化的時間依賴型車輛路徑問題(time dependent vehicle routing problem,TDVRP)等.本文研究的客戶需求模糊且有時間窗約束的時間依賴型車輛路徑問題(time dependent vehicle routing problem with fuzzy demand and time windows,TDVRPFDTW)是VRPTW,TDVRP,VRPFD3者的集成,更符合現(xiàn)實路網(wǎng)環(huán)境及配送要求,針對該問題的研究具有重要的理論與實際意義.

VRPTW出現(xiàn)較早,已有較多、較成熟的研究.而有關(guān)VRPFD問題,現(xiàn)有文獻多應用模糊集可能性、可信性等理論界定模糊需求變量和相關(guān)約束.Goncalves等[2]基于可信性理論,通過建立模糊機會補償模型,用模糊模擬和智能算法來求解帶時間窗的VRPFD;曹二保等[3]針對VRPFD問題,建立基于模糊可信性理論的模糊機會約束規(guī)劃模型,并提出求解該問題的一種基于隨機模擬的混合差分進化算法;Cao等[4]構(gòu)建模糊機會約束規(guī)劃模型對開放式的多中心VRPFD進行了研究,利用隨機模擬和改進的差分進化算法求解;Kuo等[5]以垃圾收集系統(tǒng)為研究對象,運用基于遺傳算法的混合粒子群算法求解VRPFD;王君等[6]針對具有模糊顧客需求的帶時間窗車輛路徑問題,提出了管理車輛服務模糊需求的動態(tài)優(yōu)化策略,設計了嵌入模糊模擬的改進非支配排序混合遺傳算法來求解模型;張建勇等[7]通過引入決策者主觀偏好值的概念,建立了模糊機會規(guī)劃模型,提出了一種基于模糊模擬的混合遺傳算法;Shi等[8]考慮了具有模糊需求的家庭醫(yī)療藥物的調(diào)度問題,構(gòu)建模糊機會約束模型,提出了一種混合遺傳算法與隨機模擬方法相結(jié)合的求解方法;Chang-Shi等[9]設計混合蟻群算法求解VRPFD,并提出一種雙車對環(huán)協(xié)調(diào)策略以減少額外成本.張曉楠等[10]設計混合分散搜索和變鄰域搜索的變鄰域分散搜索算法求解VRPFD,并提出一種新的失敗點返回策略.李陽等[11]基于先預優(yōu)化后重調(diào)度的思想,提出一種兩階段變鄰域禁忌搜索算法對其求解,并在重調(diào)度階段提出一種新的點重調(diào)度策略對預優(yōu)化方案進行調(diào)整.

有關(guān)TDVRP的研究,Hu等[12]針對客戶時間窗和車輛旅行時間不確定的車輛路徑問題,提出了一種魯棒優(yōu)化模型,并設計了一種基于改進的自適應變鄰域搜索啟發(fā)式的兩階段算法求解;Balseiro等[13]提出一種混合的插入啟發(fā)式蟻群算法來求解帶時間窗的TDVRP;Deng等[14]對帶時間窗的TDVRP,提出了一種混合蟻群算法和最大最小蟻群算法的多螞蟻系統(tǒng)算法求解;段征宇等[15]使用“最大–最小螞蟻系統(tǒng)”改進蟻群系統(tǒng)求解TDVRP;Kuo等[16]提出關(guān)于TDVRP的一種總油耗計算模型,并設計了串行模擬退火算法,尋找碳排放量最少的路徑;吳瑤等[17]考慮路網(wǎng)的時變特性,研究易腐食品的生產(chǎn)–配送問題,建立了以系統(tǒng)總成本為目標的優(yōu)化模型,并設計混合遺傳算法求解;穆東等[18]提出一種并行的模擬退火算法求解TDVRP,提高了傳統(tǒng)串行模擬退火算法求解TDVRP的效率;Figliozzi[19]改進了Solomon測試數(shù)據(jù)庫,設計了Figliozzi測試數(shù)據(jù)庫,用于對求解TDVRP的不同算法進行對比.

通過梳理已有文獻可見,現(xiàn)有研究還存在以下不足:1)現(xiàn)有針對VRPFD文獻多為求解算法的創(chuàng)新以及服務失敗后返回策略的研究,雖然有文獻[2,7]綜合考慮了客戶模糊需求和時間窗的約束,但也都只考慮了車輛行駛速度不變的情況,忽視了天氣變化、高峰時段、突發(fā)事件等因素對交通狀況的影響,從而導致基于速度恒定的VRPFD模型不能準確的反應和解決實際問題;2)現(xiàn)有針對TDVRP的研究,雖然大多考慮了客戶時間窗的約束,且分別提出不同的求解算法,但目前的研究基本都視客戶的需求是已知的、確定的,沒有考慮現(xiàn)實生活中客戶的需求的模糊性和不確定性.針對以上不足,本文以TDVRPFD為研究對象,并考慮客戶時間窗的約束,首先基于模糊可信性理論構(gòu)建模糊機會約束規(guī)劃模型,并設計自適應大規(guī)模鄰域搜索算法對其求解,然后針對預優(yōu)化路徑的失敗點及其后續(xù)點進行重調(diào)度,有效降低由于客戶需求模糊影響導致的配送路徑額外成本,為合理的選擇配送方案提供理論依據(jù).

2 問題描述及模型建立

2.1 問題描述

本文所研究的TDVRPFDTW可描述為在一個完備的有向圖G=(V,E)中,V={0}∪V0,V0={1,2,…,n}為客戶點的集合;0表示配送中心,配送中心能夠滿足所有客戶需求.E={(i,j)|i,j∈V}表示邊的集合,其中(i,j)表示客戶i和客戶j之間的邊,其路徑成本為cij.配送中心配有m臺車型相同的車輛,車輛的最大載重重量為Q,用K={1,2,…,m}表示車輛集合.每個客戶的需求量在配送前是不確定的,用三角模糊數(shù)來表示.T0jk表示車k從配送中心的出發(fā)時刻,為車輛k到達客戶i的時刻,表示車輛k在客戶i的開始服務時刻,tsi表示配送車輛在客戶i的服務時間,表示車輛k離開客戶i的時刻,tijk表示車輛k從客戶i到j的行駛時間.客戶i(i∈V0)的需求必須在時間窗[ETi,LTi]內(nèi)滿足,ETi為客戶i的最早可接受服務時刻,LTi為客戶i的最遲可接受服務時刻.如果早于ETi,則車輛k在客戶i處等待,等待時間否則,

決策變量xijk表示車輛k是否從i行駛到j,若是,則xijk=1,否則為0;yjk表示客戶j是否由車輛k服務,若是,則yjk=1,否則為0.

2.2 速度時間依賴函數(shù)表示

本文采用Ichoua[20]速度時間依賴函數(shù)表示動態(tài)路網(wǎng),Ichoua的時間依賴行駛函數(shù)如下圖1所示,把路段的旅行速度表示為分段函數(shù)形式,如圖1(a),由此得到連續(xù)的路段行程時間函數(shù),如圖1(b),使得路網(wǎng)滿足先入先出(first in first out,FIFO)準則.

圖1 Ichoua時間依賴行駛函數(shù)Fig.1 Time dependent driving function of Ichoua

首先將配送中心每天的工作時間分為P個時間段,假設配送車輛從i的出發(fā)時刻在第p(p∈[1,P])個時段內(nèi),第p個時間段的開始和結(jié)束時刻分別為[Tp,Tp+1],該時段的行駛速度為vp,客戶i到客戶j的距離為dij.配送車輛從i行駛到j,存在跨時段和不跨時段兩種可能性,若此時配送車輛在出發(fā)的第一個時間段內(nèi)就從客戶i到達客戶j,車輛無需跨時段行駛;否則配送車輛需跨時段行駛,假設車輛從i到j需跨C(C

2.3 模糊需求度量

預優(yōu)化階段,假設車輛k按客戶序列{a,b,c,e}服務,車輛從配送中心滿載出發(fā),滿載裝貨量為Q,每個客戶的需求均由三角模糊數(shù)表征.車輛服務完客戶a,b,c后的實際剩余裝載量為

由于客戶a,b,c的需求量為三角模糊數(shù),可知服務完c后的剩余車載量也為三角模糊數(shù),

基于可信性理論,當車輛k繼續(xù)對下一客戶e服務時,客戶e的需求量小于剩余車載量的可信度為

2.4 建立數(shù)學模型

在路網(wǎng)速度時變的條件下,同一配送車輛在相同的配送路線中,若不考慮客戶的時間窗約束,則配送時間隨路網(wǎng)的速度變化而變化,但有時間窗約束時,當配送車輛提前到達客戶點,也需要原地等待,這雖然縮短了車輛的行駛時間,但增加了等待時間,兩種情況下車輛離開路線中最后一個客戶點的時間相同.因此,本文以車輛行駛距離最短為目標,在預優(yōu)化階段,對于給定的決策者偏好值α,相應的預優(yōu)化模型如下:

其中:目標函數(shù)(3)為最小化路徑成本;式(4)保證每個客戶有且僅有一條車輛路徑對其服務,同時還表示車輛的進出平衡約束;式(5)表示同一客戶無路徑連通;式(6)表示每輛車僅有一條服務路徑,且從配送中心出發(fā),配送完后要返回配送中心;式(7)–(8)保證客戶點被車輛服務時一定有路徑與其連接;式(9)為支路消除約束,S為車輛k的服務路線客戶集合;式(10)–(11)表示車輛出發(fā)或返回配送中心要滿足配送中心的時間窗要求,式中ET0,LT0分別為配送中心的最早開始服務時間和最晚結(jié)束服務時間.式(12)保證了客戶的開始服務時刻必須滿足客戶間的行駛時間;式(13)為模糊容量機會約束,保證車輛在選擇點進行服務的時候,其需求量不大于Q的可信度高于預先設定的置信水平;式(14)–(15)保證車輛的開始服務時刻必須滿足顧客的時間窗約束;式(16)–(17)為決策變量屬性.

步驟2根據(jù)式(1)分別求得從當前節(jié)點出發(fā)到所有未訪問節(jié)點的到達時間,從到達時間滿足時間窗要求的未訪問客戶集中選擇開始時間最小的一個節(jié)點插入到當前路徑中.若所有未插入客戶的到達時間都不在時間窗內(nèi),則選擇到達時間距最早開始時間最近的一個節(jié)點插入到當前路徑中.

步驟3重復步驟2,若已達到當前車輛的容量約束,則重新派一輛車,若所有的節(jié)點都已訪問,則結(jié)束計算.

3 求解TDVRPFDTW的ALNS算法

VRP問題屬于經(jīng)典的NP–hard問題,本文研究的TDVRPFDTW問題考慮了時間窗,客戶需求不確定及旅行速度變化等因素的影響,求解更為復雜.自適應的大規(guī)模鄰域搜索算法(adaptive large neighborhood search algorithm,ALNS)在求解VRP問題時既能保持大規(guī)模鄰域搜索的尋優(yōu)能力,又能克服低效耗時的弱點,可在有限的時間范圍內(nèi)最大程度的遍歷客戶.故本文設計了ALNS算法對TDVRPFDTW問題進行預優(yōu)化和重調(diào)度兩階段求解,在求解的預優(yōu)化方案中,由于客戶點需求是模糊的,重調(diào)度階段先采用隨機模擬算法(stochastic simulation algorithm,SSA)對模糊需求進行確定模擬,然后對預優(yōu)化方案的服務失敗點進行重調(diào)度求解,得到最終方案.

3.1 ALNS算法框架

ALNS算法依據(jù)毀壞重建的原則,通過在每個迭代過程中摧毀和重建部分方案來逐步得到更好的方案.在這個不斷擴展解決方案鄰域的過程中,每個摧毀和重建因子會成對出現(xiàn),且都被賦予一定的權(quán)重,其被選擇的概率與其權(quán)重息息相關(guān).本文設計的ALNS算法流程如圖2所示.

3.2 ALNS算法設計

1)生成初始解.

本文依據(jù)最近鄰算法的思想生成初始解,具體步驟如下:

步驟1于給定的出發(fā)時間,在可用車輛中選配一輛車,從配送中心出發(fā);

圖2 ALNS流程圖Fig.2 The basic flow of ALNS

2)啟發(fā)式算子.

在每次迭代中,當前解中的μ個客戶通過移除啟發(fā)式算子刪除,然后又通過插入啟發(fā)式算子構(gòu)造新的解.μ為控制鄰域大小的參數(shù),隨著μ的增大,搜索鄰域也會變得更大,也就意味著找到最優(yōu)解的可能性就越大.本文采用3種移除啟發(fā)式算子和兩種插入啟發(fā)式算子.

a)移除啟發(fā)式算子.

①隨機移除啟發(fā)式算子.

隨機移除啟發(fā)式算子是指在每次迭代中,隨機選取當前解中的μ個客戶進行刪除.

②最遠距離移除啟發(fā)式算子.

最遠距離移除啟發(fā)式算子是選擇距離成本最高的客戶刪除.在每次迭代中,計算所有路徑中所有客戶的距離成本,選取距離成本最大的μ個客戶刪除.客戶j的距離成本為D(j)=|dij+djk|,dij為j與其緊前節(jié)點i的距離,djk為j與其緊后節(jié)點k的距離.具體操作如圖3(a)所示,圖中數(shù)值為客戶之間的距離.

③最差時間移除啟發(fā)式算子.

最差時間移除啟發(fā)式算子是選取時間偏差最大的客戶從當前路徑中刪除,客戶j的時間偏差WT(j)=|yj ?aj|,式中yj為配送車輛到達客戶j的時間,aj為客戶j的最早可接受服務時間.具體操作如圖3(b)所示,圖中括號內(nèi)的數(shù)據(jù)為配送車輛到達客戶的時間和客戶的最早接受服務時間.

圖3 移除操作示意圖Fig.3 Examples of removal operation

b)插入啟發(fā)式算子.

①貪婪插入啟發(fā)式算子.

貪婪插入啟發(fā)式算子是將移除列表中的每一個客戶i以最小的插入成本插入到路徑中,在時間窗的約束下,計算其所有可行插入位置的插入成本,客戶i的插入成本C(i)=dji+dik ?djk,式中j為插入位置的前序點客戶,k為插入位置的后續(xù)點客戶,這也就是相當于以最小插入成本插入客戶.具體操作如圖4(a)所示,客戶之間的數(shù)值為被插入客戶在各位置的插入成本C.

②最好時間插入啟發(fā)式算子.

對于待重建解中的每一條子路徑,在時間窗的約束條件下,首先找出客戶j的所有可行插入位置并計算插入后的時間偏差量,客戶j的時間偏差量BT(j)=|yj ?aj|,式中:yj為配送車輛到達客戶j的時間,aj為客戶j的最早可接受服務時間,然后將客戶j插入在時間偏差量最小的位置.具體操作如圖4(b)所示,客戶之間的數(shù)值為被插入客戶在插入各位置后的時間偏差量BT.

圖4 插入操作示意圖Fig.4 Examples of insertion operation

3)自適應調(diào)整機制.

本文采用輪盤賭來確定每一次迭代中選擇的移除或插入啟發(fā)式算子.ρi表示每次迭代中移除啟發(fā)式算子hi(或插入啟發(fā)式算子)的權(quán)重,初始值設為1,則在m個啟發(fā)式中,啟發(fā)式算子hi被選擇的概率可表示為搜索過程分為若干段完成,每一段由φ個連續(xù)的迭代過程組成,在每一段的迭代結(jié)束后,根據(jù)記錄的啟發(fā)式算子性能調(diào)整所有的權(quán)重ρi.

定義πi為啟發(fā)式算子hi在當前段所獲得的評價總分數(shù),在每段的迭代之前πi的值設置為0,啟發(fā)式算子hi的得分πi由參數(shù)σ1,σ2,σ3所決定.若迭代之后的新解為全局最優(yōu)解,則此次迭代所用到的啟發(fā)式算子得分為σ1;若新的解代表的路徑之前沒有訪問過,且這個新解比當前解優(yōu),則啟發(fā)式算子得分為σ2;若新的解代表的路徑之前沒有訪問過,且這個新解比當前解差,但此新解被接受,則啟發(fā)式算子得分為σ3.λi表示啟發(fā)式算子hi在當前段中迭代應用的次數(shù),若λi >0,則每段迭代結(jié)束后ρi更新,

η為控制參數(shù),η∈[0,1].若λi=0,則在下一段的迭代中ρi保持不變.

4)劣解接受標準和迭代終止條件.

為了避免陷入局部最優(yōu),本文依據(jù)模擬退火算法設計劣解接受標準和迭代終止準則.通過對當前解S中的客戶進行移除和插入重建的操作,產(chǎn)生新解St,如果obj(St)

溫度T從每次迭代的初始溫度Tstar開始,在每次迭代中,溫度T的冷卻速率為τ(0<τ <1),在溫度達到臨界值后停止迭代.

3.3 重調(diào)度策略

在實際操作中,即使預優(yōu)化方案中車輛裝載量滿足所有客戶點可信度檢驗,也是有可能出現(xiàn)客戶點需求量超出車輛剩余裝載量的情況,此時該客戶點為服務失敗點,該路線上失敗點及后續(xù)客戶都不能被服務,此時就要執(zhí)行點返回策略來進行路線調(diào)整,由于路徑失敗導致的相關(guān)超出預優(yōu)方案部分配送路徑所增加的費用稱為額外費用.

1)隨機模擬算法.

假定只有配送車輛到達客戶點進行服務時,客戶點的模糊需求量才得以明確,在算法中通過隨機模擬算法(SSA)模擬客戶點需求量來確定失敗點.在給定模糊需求數(shù)[d1i,d3i]中生成一個隨機數(shù)d,并計算其隸屬度μ(d),再生成一個[0,1]范圍內(nèi)的隨機數(shù)ε,比較μ(d)和ε,若εμ(d),則客戶i的實際需求量為d,否則重新生成d和ε,直至滿足εμ(d)為止.

2)重調(diào)度.

針對失敗點所導致的服務失敗問題,現(xiàn)有文獻多采用點返回策略進行處理.如圖5的簡單例子所示,圖5(a)為預優(yōu)化路徑,圖5(b)失敗點返回,圖5(c)失敗前點返回,圖5(d)失敗前序點返回3種方式,其中圖5(b)屬于失敗點返回補貨策略,圖5(c)–5(d)屬于預先補貨策略.

圖5 失敗點返回策略示意圖Fig.5 Examples of failure point return policy

由三角形三邊原理可知,預補貨策略明顯優(yōu)于失敗點返回補貨策略,但難以確定預補貨策略的最優(yōu)返回點,在后續(xù)客戶需求不明確時難免出現(xiàn)不當返回,從而增加額外成本.因此本文采用重調(diào)度策略,重調(diào)度策略在文獻[11]中的應用證明了其可獲得更好的調(diào)整方案,具體調(diào)度過程如下:

首先進行失敗點及后續(xù)點的確認.先對預優(yōu)化方案中路線逐條進行模擬,確認失敗點及后續(xù)點,車輛在失敗位置允許進行部分服務,隨后返回配送中心,本路徑配送結(jié)束,所有的失敗點及后續(xù)點組成待重調(diào)度客戶點集合VR={1,2,…,r},VR?V0,此時VR中僅有失敗點的需求確定,后續(xù)點的需求仍為模糊.若VR為空集,則表明預優(yōu)化方案合理,路徑中客戶點模糊需求不超出配送車輛能力,無需重調(diào)度.

然后進行客戶點的重調(diào)度.第2階段重調(diào)度策略求解的同樣是TDVRPFDTW,但問題規(guī)模相對較小.在重調(diào)度階段,決策者風險偏好值β水平設置較高,一般βα,與預優(yōu)化階段相同,重調(diào)度路徑中客戶點處同樣要進行可信性檢驗,在重調(diào)度路徑中也可能會出現(xiàn)失敗點,此時算法采取失敗點返回策略,重調(diào)度路徑優(yōu)化后對其進行模擬,客戶點需求量仍通過SSA確認.重調(diào)度階段客戶規(guī)模較小,因此重調(diào)度路徑中服務失敗的概率較小.

4 算例驗證及結(jié)果分析

采用MATLAB 2016b編譯算法在PC機上運行,電腦操作系統(tǒng)為Window 7,運行內(nèi)存大小為8 GB,CPU為4核酷睿i7–7500,主頻為3.4 GHz.經(jīng)過反復地試驗,ALNS算法參數(shù)設定如下:初始溫度Tstart=100,溫度下降速率τ=0.99,鄰域規(guī)模μ=20,每一小段的迭代次數(shù)φ=50,啟發(fā)式算子評價參數(shù)σ1=100,σ2=20,σ3=10,控制參數(shù)η=0.5;本文啟發(fā)式算法迭代代數(shù)設置為1000代.

表1 Figliozzi速度時間依賴函數(shù)Table 1 Speed time dependent function of Figliozzi

本文測試算例來自于Figliozzi[19]提供的標準測試算例,Figliozzi測試數(shù)據(jù)庫是在Solomon提供的標準測試算例的基礎上增加了4組時間依賴函數(shù).Dr.Solomon 提供的測試數(shù)據(jù)庫下載:http://w.cba.neu.edu/～msolomon/problems.htm.Figliozzi將一天的工作時間均勻地分為5等份,分別為[0,0.2T),[0.2T,0.4T),[0.4T,0.6T),[0.6T,0.8T),[0.8T,T],并假設一天存在早高峰和晚高峰,因此設置4組時間依賴函數(shù)如表1所示.

4.1 需求確定型算例驗證

目前關(guān)于TDVRPFDTW沒有標準的算例,為驗證算法的性能,首先使用Figliozzi數(shù)據(jù)庫C1類算例集求解需求確定的TDVRPTW,計算結(jié)果如表2–3所示,該結(jié)果包括車輛路徑成本和路線所需車輛數(shù)兩部分,TD為路徑成本,N表示路線所需車輛數(shù),表2中Best為目前國際上公布的最優(yōu)解.

車輛速度恒定時,表2即為VRPTW求解結(jié)果,文獻[21]在求解的9個算例中,能搜索到7個算例的最優(yōu)值,算例C103和C104未能搜索到最優(yōu)值,這兩個算例的求解結(jié)果與最優(yōu)值的誤差分別為0.10%,0.51%;從9個算例的平均值來看,文獻[19]所求得的路徑成本均值為841,相較于最優(yōu)解的平局值來說,誤差到達了1.52%,文獻[21]結(jié)果的誤差相對較小,但也有0.63%,而本文的自適應大規(guī)模鄰域搜索算法能搜索到全部算例的最優(yōu)解.

表2 需求確定速度恒定條件下測試數(shù)據(jù)結(jié)果Table 2 The results of demand determine and constant speed

表3 需求確定的TDVRPTW求解結(jié)果Table 3 The results of TDVRPTW that requirement determination

由表3結(jié)果對比可知:不同的速度時間依賴函數(shù)下,在車輛使用數(shù)方面,本文算法求得的路徑所需車輛數(shù)都為10輛,求解結(jié)果穩(wěn)定;在路徑成本方面,本文計算結(jié)果均優(yōu)于文獻[19]的計算結(jié)果;與文獻[18]的計算相比較,本文僅在TD3a,TD3c 速度時間依賴函數(shù)下的求解結(jié)果稍差,在其它10種速度時間依賴函數(shù)下的求解結(jié)果均優(yōu)于文獻[18],ALNS較IECE、SA相比性能優(yōu)勢明顯.綜上說明本文算法性能較優(yōu),在求解客戶需求確定的TDVRPTW問題時,能求到較好的解.

4.2 TDVRPFDTW算例求解驗證

4.2.1 預優(yōu)化方案求解

為驗證ALNS算法對TDVRPFDTW依舊合理有效,選取并改進與TDVRPFDTW對應的TDVRPTW算例C101對模型及算法進行測試,時間依賴函數(shù)類型采用TD1a,在處理客戶點需求模糊時保持原有客戶點需求為d,其模糊需求為((1?γ)d,d,(1+γ)d),其中γ=0.25,偏好值α∈(0,1],求解時令α按幅度0.1遞增.不同偏好值下,路網(wǎng)中客戶需求模糊且車輛行駛速度時變的10次預優(yōu)化結(jié)果如表4所示,表中N為最優(yōu)值所需的車輛使用數(shù),%Dev為最優(yōu)值、最差值較均值的偏差.

由表4可見:最優(yōu)值和最差值相對平局值的偏差較小,說明ALNS算法在求解TDVRPFDTW問題時性能穩(wěn)定.另外,不同決策者偏好值α對預優(yōu)化結(jié)果有較明顯的影響,從表4中最優(yōu)值可以看出,隨著決策者偏好值α的增大,配送成本整體呈現(xiàn)變高的趨勢,α在0.1～0.5之間時,配送成本較低且比較穩(wěn)定,最低成本為965,當0.9α0.6時,配送成本明顯變高,α為0.9或1時,配送成本最高為1056.綜上,在帶時間窗約束且客戶需求模糊的時間依賴型車輛路徑問題中,決策者越趨向于冒險型,即對于一次性配送成功的渴望程度越高,其需付出的實際配送成本就相對越低;反之,決策者越趨向于保守型,對于一次性配送失敗的承受程度越低,其需付出的實際配送成本相對越高.

表4 需求模糊且速度時變條件下的10次預優(yōu)化結(jié)果Table 4 Results of the 10 pre-optimizations under the time-varying speed and fuzzy demand

從表4的結(jié)果可知,本文求得的最優(yōu)預優(yōu)化方案的預優(yōu)化成本為965,完成配送任務需要12輛車,相應的預優(yōu)化路徑如圖6所示.

4.2.2 重調(diào)度

由前文分析可知,在TDVRPFDTW問題中,即使通過計算對某一客戶進行配送的可信性Crα,也無法保證對其配送任務一定可以完成,由此而產(chǎn)生的額外行駛距離就是決策者在選擇偏好值的一個重要考慮因素.本文對表4所得預優(yōu)化方案繼續(xù)進行后續(xù)需求模擬求解,在預設的每個α值下最優(yōu)預優(yōu)化方案均單獨求解10次,求解結(jié)果平均值如表5所示,表中Best是每個α下最優(yōu)預優(yōu)化方案的成本,其中ce表示由于客戶點模糊需求模擬后路徑中失敗點存在所導致的額外成本,ct表示方案總成本,N表示最終方案中所需的車輛數(shù).

圖6 最優(yōu)預優(yōu)化路徑圖Fig.6 The chart of optimal pre-optimization routes

從表5中的結(jié)果可以看出,隨著決策者偏好值α增大,由配送失敗而產(chǎn)生的額外成本總體上呈下降趨勢,說明了當決策者越趨向于保守型,配送時出現(xiàn)服務失敗的可能性越小;當α為0.9或1時,配送的額外成本為0,即決策者保守程度極高時,不會出現(xiàn)服務失敗點,此時的方案總成本也最小,最小總成本為1056;當決策者風險偏好極高時,即偏好值α為0.1時,路線所需的車輛數(shù)最多,所需車輛數(shù)比無服務失敗點時所需的車輛數(shù)多15.38%,這說明在決策者風險偏好極高時,很容易產(chǎn)生服務失敗點,從而需要新增派車輛完成后續(xù)配送任務.

表5 α遞增下各最優(yōu)預優(yōu)化方案的調(diào)整結(jié)果Table 5 Adjustment results of each pre-optimization scheme under α increasing

為分析預優(yōu)化方案與最終配送方案實際成本的關(guān)系,分別計算本文最優(yōu)預優(yōu)化方案重調(diào)度結(jié)果與α為0.9或1時的最優(yōu)預優(yōu)化方案重調(diào)度結(jié)果,其重調(diào)度結(jié)果對比如表6所示.其中全文最優(yōu)預優(yōu)化方案(以下簡稱方案1)的預優(yōu)化成本為965,α為0.9或1時的最優(yōu)預優(yōu)化方案(以下簡稱方案2)的預優(yōu)化成本為1056.

表6 不同預優(yōu)化方案重調(diào)度結(jié)果Table 6 Results of re-dispatch on different pre-optimization schemes

從表6可知,方案1在實際配送過程中有路徑4和路徑9兩條路徑出現(xiàn)服務失敗點,即需新增兩輛車完成配送任務,完成所有配送任務實際需要14輛車配送,較預優(yōu)化方案需要的12輛車增加了16.67%,且實際總成本為1127,相較于預優(yōu)化方案的成本965增加了16.79%.方案2在實際配送過程中不會出現(xiàn)服務失敗的情況,完成配送任務需要13輛車配送,總成本為1056,相較于方案1的實際配送成本1127低5.41%.在車輛使用數(shù)方面,方案2完成配送任務所需的車輛數(shù)為13輛.這較方案1實際所需車輛數(shù)少7.14%.綜上,在本文的算例中,最優(yōu)預優(yōu)方案所需的實際成本不一定最低,其實際所需的車輛數(shù)也并非最少,當決策者偏好值α為0.9或1時,即決策者十分保守時,配送過程不會出現(xiàn)服務失敗的情況,且完成服務所需的車輛和實際總成本相對較低.

5 結(jié)論

本文在對TDVRPFDTW問題的研究中,基于模糊可信性理論對客戶點模糊需求進行處理,以Ichoua速度時間依賴函數(shù)來刻畫動態(tài)路網(wǎng),構(gòu)建旅行速度時變且有時間窗要求的模糊機會約束優(yōu)化模型;在預優(yōu)化階段,設計自適應的大規(guī)模鄰域搜索算法對模型進行求解,在得到預優(yōu)化路線后,采用隨機模擬算法模擬客戶的真實需求,對于服務失敗點及其后續(xù)點,執(zhí)行重調(diào)度策略進行調(diào)整;通過對改進的Solomon算例中C1類算例集的計算驗證本文模型及算法的有效性,可得出以下結(jié)論:1)本文所建模型能夠有效解決TDVRPFDTW問題,所設計的ALNS算法搜索性能良好、有效性高,是求解這類問題的有效方法;2)在TDVRPFDTW問題中,最優(yōu)預優(yōu)化方案所需的實際成本并不一定最低.在預優(yōu)化階段,隨著決策者偏好值的增大,即決策者越趨向于保守型,其付出的配送成本反而越高,方案所需車輛數(shù)也有所增加;在重調(diào)度階段,決策者越趨向保守,其付出的額外成本就相對越低,實際所需車輛數(shù)也相對較少.

本文的研究更符合實際配送場景,研究成果不僅進一步豐富和拓展了VRP相關(guān)理論研究,也可對物流企業(yè)配送優(yōu)化決策提供科學依據(jù).未來將在開發(fā)更加有效的求解算法及減少服務失敗后的額外成本方面進一步展開研究.