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

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院,遼寧大連 116026)

1 引言

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

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

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

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

2 問(wèn)題描述及模型建立

2.1 問(wèn)題描述

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

決策變量xijk表示車(chē)輛k是否從i行駛到j(luò),若是,則xijk=1,否則為0;yjk表示客戶(hù)j是否由車(chē)輛k服務(wù),若是,則yjk=1,否則為0.

2.2 速度時(shí)間依賴(lài)函數(shù)表示

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

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

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

2.3 模糊需求度量

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

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

基于可信性理論,當(dāng)車(chē)輛k繼續(xù)對(duì)下一客戶(hù)e服務(wù)時(shí),客戶(hù)e的需求量小于剩余車(chē)載量的可信度為

2.4 建立數(shù)學(xué)模型

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

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

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

步驟3重復(fù)步驟2,若已達(dá)到當(dāng)前車(chē)輛的容量約束,則重新派一輛車(chē),若所有的節(jié)點(diǎn)都已訪問(wèn),則結(jié)束計(jì)算.

3 求解TDVRPFDTW的ALNS算法

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

3.1 ALNS算法框架

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

3.2 ALNS算法設(shè)計(jì)

1)生成初始解.

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

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

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

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

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

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

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

隨機(jī)移除啟發(fā)式算子是指在每次迭代中,隨機(jī)選取當(dāng)前解中的μ個(gè)客戶(hù)進(jìn)行刪除.

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

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

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

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

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

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

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

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

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

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

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

3)自適應(yīng)調(diào)整機(jī)制.

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

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

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

4)劣解接受標(biāo)準(zhǔn)和迭代終止條件.

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

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

3.3 重調(diào)度策略

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

1)隨機(jī)模擬算法.

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

2)重調(diào)度.

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

圖5 失敗點(diǎn)返回策略示意圖Fig.5 Examples of failure point return policy

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

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

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

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

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

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

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

4.1 需求確定型算例驗(yàn)證

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

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

表2 需求確定速度恒定條件下測(cè)試數(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é)果對(duì)比可知:不同的速度時(shí)間依賴(lài)函數(shù)下,在車(chē)輛使用數(shù)方面,本文算法求得的路徑所需車(chē)輛數(shù)都為10輛,求解結(jié)果穩(wěn)定;在路徑成本方面,本文計(jì)算結(jié)果均優(yōu)于文獻(xiàn)[19]的計(jì)算結(jié)果;與文獻(xiàn)[18]的計(jì)算相比較,本文僅在TD3a,TD3c 速度時(shí)間依賴(lài)函數(shù)下的求解結(jié)果稍差,在其它10種速度時(shí)間依賴(lài)函數(shù)下的求解結(jié)果均優(yōu)于文獻(xiàn)[18],ALNS較IECE、SA相比性能優(yōu)勢(shì)明顯.綜上說(shuō)明本文算法性能較優(yōu),在求解客戶(hù)需求確定的TDVRPTW問(wèn)題時(shí),能求到較好的解.

4.2 TDVRPFDTW算例求解驗(yàn)證

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

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

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

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

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

4.2.2 重調(diào)度

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

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

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

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

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

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

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

5 結(jié)論

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

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