張鵬，石莎莎，寧濤

(1.大連交通大學(xué) 創(chuàng)新創(chuàng)業(yè)教育學(xué)院， 遼寧 大連 116028；2.大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116054;3.大連民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，遼寧 大連 116600) *

隨著中國電子商務(wù)的普及,物流公司的分銷需求逐年增加.然而,物流公司也面對許多干擾問題的發(fā)生,如配送車輛發(fā)生故障導(dǎo)致客戶的送貨時間延遲,客戶的取消送貨,以及客戶的送貨時間改變等因素.如何運(yùn)籌好一個合理的物流配送方案, 保證客戶的貨物準(zhǔn)時到達(dá)而不影響客戶的滿意度是物流公司需要解決的問題.

近年來,許多學(xué)者在車輛調(diào)度的干擾問題上取得了很大進(jìn)展. Francesco Ferrucci[1]針對動態(tài)車輛問題,提出了一種新的主動實時控制方法,利用隨機(jī)理論引導(dǎo)車輛進(jìn)入未來可能的需求區(qū)域,來最大限度地減少客戶的不便. Mu Q[2]針對車輛運(yùn)輸途中發(fā)生的故障,提出兩種禁忌搜索算法,能快速生成新的方案,通過實驗驗證了算法的有效性.趙亮等[3],楊文超等[4]運(yùn)用干擾管理思想,建立了干擾管理方案, 調(diào)整車輛的配送使干擾最小化.曹慶奎等[5]構(gòu)建了客戶價值的干擾管理模型,從整體上降低了客戶的不滿意度.符俊波等[6]將干擾管理思想應(yīng)用在生活垃圾收運(yùn)的車輛調(diào)度上,對收集點(diǎn)垃圾量的變化提出擾動恢復(fù)策略,有效地減少了車輛的成本.

前景理論和累積前景理論是由Kahneman和Tversky[7]提出,是決策者在面臨風(fēng)險條件時對結(jié)果的選擇進(jìn)行分析的理論.車輛的干擾問題也會面臨著決策的風(fēng)險,對此,學(xué)者們運(yùn)用前景理論進(jìn)行了研究.YANG L[8]提出了累積前景理論方法來解決應(yīng)急響應(yīng)中的風(fēng)險決策問題.任斌等[9]對災(zāi)后應(yīng)急救援物資的動態(tài)變化,建立了價值函數(shù)和概率權(quán)值, 通過求得前景值最小得到救援方案,提高了救援的效率.通過前景理論,寧濤等[10]從用戶對貨物期待送達(dá)時間角度,建立了用戶心理期望感知函數(shù)模型.Diana L[11]研究了時間壓力對決策行為的影響,并建立了相應(yīng)的風(fēng)險承擔(dān)模型,實驗驗證了時間壓力下增加了風(fēng)險尋求收益.黃婷婷等[12]對不同年齡段的乘客出行的路徑選擇進(jìn)行了研究,通過前景理論描述了乘客對路徑選擇上的決策行為.

基于干擾管理思想,本文提出一種干擾策略,并建立了擾動恢復(fù)模型.同時,考慮干擾后對客戶滿意度的影響,將累積前景理論與干擾策略相結(jié)合.改進(jìn)的蟻群算法旨在解決這個問題,最后通過數(shù)據(jù)的測試驗證了算法和干擾策略的有效性.

1 基于累積前景理論

1.1 累積前景理論描述

對于物流商而言,客戶的滿意度直接影響到物流商的信譽(yù)度.物流商希望最大可能的在客戶規(guī)定的時間窗[ETi，LTi]內(nèi)送到貨物,同時也希望能增加客戶i的滿意度.根據(jù)前景理論,由于配送貨物到達(dá)時間是不確定的,客戶i會通過某種渠道獲取配送到達(dá)時間T0,i(即在不發(fā)生干擾情況下,初始調(diào)度送達(dá)時間)作為心理預(yù)期的參考點(diǎn),如果實際配送到達(dá)時間Th,i在[ETi，LTi]內(nèi),并且到達(dá)時間Th,i

1.2 價值函數(shù)的確定

本文選擇初始調(diào)度方案客戶i預(yù)期到達(dá)時間T0,i作為參考點(diǎn),與干擾發(fā)生后實際配送時間Th,i作比較,xi=T0,i-Th,i表示客戶預(yù)期到達(dá)時間與實際到達(dá)時間的差值,xi≥ 0, 表現(xiàn)為收益;xi<0, 表現(xiàn)為損失.對于干擾的客戶,干擾發(fā)生后,客戶i的心里預(yù)期的參考點(diǎn)也會隨之改變,參考點(diǎn)變成調(diào)整方案后獲取新的配送到達(dá)時間;對于無法配送而取消的客戶i實際配送時間變成0,即Th,i=0, 心里預(yù)期的參考點(diǎn)變成客戶i的服務(wù)時間窗下限LTi, 這樣增加損失程度,加大取消客戶的懲罰;對于新增車輛上客戶的價值函數(shù)v(xi)=0. 價值函數(shù)公式(1)如下:

(1)

α和β表示風(fēng)險偏好系數(shù),分別表示在收益與損失價值函數(shù)的凹凸程度,λ表示損失規(guī)避系數(shù),λ越大,代表客戶的不滿意度增加;反之,減少.本文參照研究數(shù)據(jù),a=b=0.88,λ=2.55.

1.3 決策權(quán)重的確定

在干擾發(fā)生后,每個客戶對貨物配送是否提前或者晚到的心理預(yù)期存在一定的概率p,對于取消的客戶心里預(yù)期概率p=1,pi公式如下:

(2)

(3)

(4)

式中,[ETi,LTi]代表客戶的時間窗,xi≥0,表示“收益”,收益權(quán)重為ω+(p)如式(3),xi<0，表示“損失”,收益權(quán)重為ω-(p),如式(4).本文參d照研究數(shù)據(jù),З=0.61，δ=0.69.

1.4 累積前景值模型

累積前景理論模型是將單個的概率事件整合在一起，從全局的角度進(jìn)行前景理論分析，因此本文建立了相關(guān)的模型.

單個客戶的前景值U(xi),其中，v(xi)+表示“收益”,v(xi)-表示“損失”.公式為:

U(xi)=v(xi)-ω-(p)+v(xi)+ω+(p)

(5)

累積前景值f1,公式為：

(6)

單個客戶前景值是每個客戶收益值值與損失值之和,累積前景值f1是所有用戶前景值之和.在干擾發(fā)生后,物流商調(diào)整方案,通過計算累積前景值f1,來判斷是否對客戶滿意度干擾較大.當(dāng)f1≥0,說明干擾后的方案增加了客戶的滿意度,f1越大,客戶滿意度越高;當(dāng)f1<0,說明干擾后的方案降低了客戶的滿意度,f1越小,客戶滿意度越低.

其中,V′為干擾發(fā)生時未完成的客戶集合；P為初始方案的路徑集合，P′為新方案的路徑集合；

P′={(i,j,k)|?i,j∈V',k∈K}

(7)

物流商希望干擾后的總成本f3最小化.在成本上分為3種,第1種是增派車輛產(chǎn)生的成本C1;第2種是車輛的運(yùn)輸成本Cij;第3種是取消客戶產(chǎn)生的成本C2.其中,n1為增派車輛數(shù)量,n2為取消客戶數(shù)量.

(8)

2 擾動恢復(fù)模型的建立及干擾策略

2.1 擾動恢復(fù)模型的建立

干擾管理可以描述為: 配送中心得到滿意的初始調(diào)度方案后, 發(fā)生信息的干擾(客戶的增加、時間窗和貨物的變化等), 配送中心需要在滿足客戶的時間和需求下, 調(diào)整初始方案,使其變動造成的干擾最小化.

變量和符合定義如下：

V：V={v0,v1,…,vN}其中,v0為配送中心, {v1,v2,…,vN}為客戶點(diǎn)集合;V′為干擾發(fā)生時未完成的客戶集合;dij為客戶i到客戶j的距離;K：K={1,2,…,k}表示所有配送車輛集合;tij為兩點(diǎn)i和j之間的行駛時間;Si為客戶i的開始服務(wù)時間；si為客戶i的服務(wù)時間;wi為客戶i的等待時間;ETi為客戶i的時間窗下限;LTi為客戶i的時間窗上限;ETi′為客戶i的新時間窗下限;LTi′為客戶i的新時間窗上限;G為車輛的載重量;Gk為干擾發(fā)生時車輛k的載重量;gi為客戶i的需求量.

本文的目標(biāo)函數(shù)用字典排序[13]表示.目標(biāo)第一優(yōu)先級P1是對客戶服務(wù)時間的累積前景理論值偏離最小; 目標(biāo)第二優(yōu)先級P2是對車輛路徑的偏離最小; 目標(biāo)第三優(yōu)先級P3是對物流商成本的花費(fèi)最小.

目標(biāo)函數(shù)：

Min LexP1∶f1P2∶f2P3∶f3

(9)

P1?P2?P3

決策變量：

約束條件：

(10)

(11)

(12)

(13)

(14)

Si=tij+wi,?i,j∈V

(15)

Siyik≥ETi,?k∈K,?i∈V

(16)

Siyik+si≤LTi,?k∈K,?i∈V

(17)

Siyik≥ETi′,?k∈K,?i∈V

(18)

Siyik+si≤LTi′,?k∈K,?i∈V

(19)

在該數(shù)學(xué)模型中,式(10)表示配送車輛服務(wù)的客戶點(diǎn)的總體需求量不大于車輛載重限制; 式(11)表示干擾發(fā)生后配送車輛服務(wù)的剩余客戶點(diǎn)的總體需求量不大于車輛載重限制;式(12)表示干擾發(fā)生后臨近救援車輛服務(wù)的客戶點(diǎn)的總體需求量不大于車輛載重限制; 式(13)表示所有車輛從配送中心出發(fā),必須返回配送中心; 式(14)表示客戶只能被一輛車服務(wù),或者取消服務(wù); 式(15)～(19)表示時間窗約束.

2.2 干擾策略

(1)增派車輛策略

當(dāng)調(diào)整后的方案對初始方案干擾較大,或者不能按時配送,選擇增派車輛配送,但增派車輛配送會增加車輛的成本.

(2)臨近救援策略

利用現(xiàn)有的在途車輛進(jìn)行的局部調(diào)整策略, 需要考慮客戶的時間和車輛的容量要求, 是否能滿足干擾發(fā)生時的情況.

(3)取消客戶策略

不能滿足前兩個策略,或者車場沒有多余車輛進(jìn)行配送,對客戶改日配送.

3 改進(jìn)的蟻群算法的設(shè)計和步驟

3.1 改進(jìn)的蟻群算法

蟻群算法具有的較強(qiáng)的魯棒性和易于其他算法相結(jié)合等優(yōu)點(diǎn),能很好的解決調(diào)度方面的相關(guān)問題,但單獨(dú)的蟻群算法在研究復(fù)雜問題時容易陷入局部最優(yōu)、收斂速度慢以及搜索最優(yōu)路徑時間過長等缺點(diǎn)[14]. 針對該缺點(diǎn),本文提出自適應(yīng)蟻群算法,在改進(jìn)轉(zhuǎn)移概率和信息素更新方式的同時,引入模擬退火算法[15],加快了算法的收斂速度.

3.2 改進(jìn)轉(zhuǎn)移概率

(20)

其中,τij是從i到j(luò)的信息濃度,α為信息素濃度的重要因子,ηij為啟發(fā)函數(shù),ηij=1/dij,表示螞蟻從客戶點(diǎn)i到j(luò)的期望程度,β為啟發(fā)函數(shù)的重要程度因子,φij是時間啟發(fā)函數(shù),φij=(LTj-ETj)/lj，其中[ETj,LTj]為客戶j時間窗,у為客戶的時間程度因子,ωij是路徑啟發(fā)函數(shù),ωij=(di0+dj0)/dij，di0是客戶i到車場的距離,dj0是客戶j到車場的距離,θ為路徑的程度因子,allowk表示車輛在滿足條件下可訪問點(diǎn)的集合.

3.3 信息素更新策略

蟻群算法尋優(yōu)的快速性是通過正反饋的信息傳遞和積累來保證的,為了充分利用循環(huán)找到最優(yōu)解,在每次循環(huán)后,對一只螞蟻的信息素進(jìn)行更新.本文提出自適應(yīng)蟻群算法改進(jìn)更新策略,更新規(guī)則如下:

(21)

其中,φ(m)=m/c為一個與迭代次數(shù)m成正比的函數(shù)，迭代次數(shù)越大φ(m)的取值越大,c為常數(shù).在蟻群算法中,螞蟻通過轉(zhuǎn)移概率選擇下一個轉(zhuǎn)移的目標(biāo),所以參數(shù)的設(shè)置會對算法的收斂速度和求解質(zhì)量上產(chǎn)生很大的影響.因此,本文引入了模擬退火的機(jī)制,并動態(tài)的調(diào)整參數(shù),有效地幫助算法跳出局部最優(yōu)解.

步驟如下：

參數(shù)含義：Hk+1為當(dāng)前螞蟻完成循環(huán)后得到的局部最優(yōu)解,Hk為上一次循環(huán)后得到的局部最優(yōu)解,NC代表循環(huán)次數(shù),T為當(dāng)前溫度,按照模擬退火機(jī)制,每次迭代之后進(jìn)行降溫,TNC+1=TNC·r,r為降溫速率.

(1)當(dāng)循環(huán)NC> 1時，ΔH=Hk+1-Hk，如果ΔH< 0 ,則保留當(dāng)前最優(yōu)解Hk+1.證明得到的解優(yōu)于上一解,并保留當(dāng)前的參數(shù)ɑ、β、у.

(2)如果ΔH= 0;或者p=exp(-ΔH/T),如果p是(0，1)之間的隨機(jī)數(shù),則接受新的惡化解作為最優(yōu)解.此時說明算法可能陷入局部最優(yōu)解,信息素濃度過高,期望值太大,需要減小α，增大Ω， 其中,(β、у、θ)∈Ω.

(22)

(3)如果ΔH> 0，并不能接受惡化解,則最優(yōu)解為Hk.此時,反應(yīng)出信息素對螞蟻選擇路徑的影響力較小,需要增大α,減小Ω.

(23)

3.4 算法流程

步驟1：生成初始調(diào)度方案,根據(jù)改進(jìn)的蟻群算法以成本最小為目標(biāo)求解.

步驟2：當(dāng)干擾發(fā)生時刻,客戶的時間窗發(fā)生變化.首先有必要判斷變化是否會干擾初始方案.本文采用文獻(xiàn)[16]提出的方法來判別是否需要改動初始方案.客戶i的原時間窗為[ETi，LTi],對客戶i的服務(wù)時間為Si,變動后客戶i的新時間窗為[ETi′,LTi′] ,tmin={LTi-Si}表示客戶i當(dāng)前所在的車輛路徑上后續(xù)客戶j的時間窗上限與開始服務(wù)時間的最小差值.所以,滿足客戶i需要變動初始方案的條件為：LTi′tmin.若客戶i的變動未對初始方案產(chǎn)生干擾,則按原計劃繼續(xù)配送;若產(chǎn)生干擾,調(diào)整初始方案,轉(zhuǎn)步驟3.

步驟3：在發(fā)生干擾后,排除已服務(wù)的客戶,并且以當(dāng)前車輛位置為虛擬配送中心,使用步驟1對當(dāng)前車輛的剩余客戶進(jìn)行重新配送,并要求最后返回原配送中心.如果新方案無法配送或者對初始方案干擾較大,轉(zhuǎn)步驟4;

步驟4：對干擾客戶i進(jìn)行新增車輛配送,或者取消配送.

4 仿真實驗

本文選取文獻(xiàn)[16]的數(shù)據(jù)進(jìn)行測試,假設(shè)條件:一個配送中心擁有8輛汽車,每輛車載重為5噸,車速為1單位,單位運(yùn)輸成本為1,增派車輛成本為140，取消客戶的成本為240.表1包含了配送中心和客戶的信息,其中0代表配送中心,1-15代表客戶.

表1 客戶信息表

改進(jìn)的蟻群算法參數(shù)設(shè)置：螞蟻數(shù)目為30，迭代次數(shù)為NC=200，信息素總量Q=100，α=1，β=3，у=3，θ=3，ρ=0.1,T=1 000，r=0.9，c=5.

采用本文改進(jìn)的蟻群算法得到最優(yōu)的初始方案:車輛1:0-9-7-6-0;車輛2:0-10-5-13-0;車輛3:0-8-4-15-14-12-0;車輛4:0-3-11-2-1-0.得到的成本為526.30,優(yōu)于文獻(xiàn)[16]的531.41.

當(dāng)時間為32.65,客戶4、6、13、14信息發(fā)生變動,變動信息如表2.

表2 客戶時間窗變動信息

配送中心收到干擾信息,首先,查看當(dāng)前車輛所在的位置,并查看此車輛是否存在干擾客戶.若不存在,正常配送;若存在,按照本文提出的干擾策略,進(jìn)行調(diào)整.調(diào)整后的方案為:車輛1：0-9-7-6-0;車輛2：0-10-5--0,客戶點(diǎn)13,需增派車輛5進(jìn)行配送;車輛5：0-13-0;車輛3:0-4-8-15-14-12-0;車輛4：0-3-11-2-1-0.

本文針對干擾發(fā)生時刻客戶時間的改變,應(yīng)用在按原計劃調(diào)度和全局重新調(diào)度上,來驗證提出的干擾方案的效果.

按原計劃調(diào)度方案：車輛1：0-9-7-6-0;車輛2:0-10-5-0,客戶點(diǎn)13,需增派車輛5進(jìn)行配送;車輛5：0-13-0;車輛3:0-8-15-14-12-0,客戶4無法進(jìn)行配送,取消客戶4的配送;車輛4：0-3-11-2-1-0.

全局重新調(diào)度方案：車輛1：0-10-5-0;車輛2：0-6-0;車輛3：0-13-9-7-0;車輛4：0-3-11-2-1-0;車輛5：0-4-8-15-14-12-0.

三種配送方案的結(jié)果如表3所示.

表3 三種方案的結(jié)果比較

從表3可以看出,本文提出的干擾管理方案累積前景值明顯優(yōu)于原計劃配送和全局重調(diào)度方案;干擾管理方案的路徑偏離與原計劃配送方案的路徑偏離相差不大,優(yōu)于全局重調(diào)度方案的路徑偏離;干擾管理方案成本高于全局重調(diào)度方案成本,但明顯低于原計劃配送方案成本.

由此可見,本文提出的干擾管理方案相對于其他方案對于客戶的滿意度干擾較小,甚至提高了客戶滿意度,這增加了客戶對物流的信任度.雖然在成本和路徑偏離上不優(yōu)于其他方案,但相差不大.這說明本文提出的干擾管理方案的有效性.

補(bǔ)充說明,對于文獻(xiàn)[16]提出的初始調(diào)度方案,針對干擾客戶6,需要重新增派車輛進(jìn)行配送,若采用本文的初始調(diào)度方案,干擾客戶6無需增派車輛,這就大大減少了干擾,說明初始調(diào)度的好壞,對干擾管理也產(chǎn)生很大的影響.

為進(jìn)一步驗證本文提出的干擾管理方法有效性,本文采用Solomon標(biāo)準(zhǔn)測試算例[17]進(jìn)行驗證,選取C101的前50個客戶、R207、R211和RC208中數(shù)據(jù)的前25個客戶和前50個客戶.假設(shè)T=50時刻,客戶配送要求時間發(fā)生變動,變動信息如表4.

表4 各組客戶的時間變動信息

本文將選取的算例的干擾管理與全局重調(diào)度方案進(jìn)行了比較,結(jié)果如表5所示.

表5 干擾管理與全局重調(diào)度方案結(jié)果的比較

由表5可以看出,本文選取的C類C101-50和RC類RC208-50數(shù)據(jù)的干擾管理方案和全局重調(diào)度方案相同,這是由于客戶的分布是聚集的,聚成多個區(qū)域,區(qū)域之間跨度較大,車輛間無法協(xié)助.相反, R類客戶是分散的,干擾后對全局重調(diào)度影響較大.而RC208-25中由于干擾客戶對干擾方案擾動較大,采用重新安排車輛策略.

由此可見,C類和RC類客戶是集群分布,配送車輛間的協(xié)助策略無法實施,存在干擾管理方案和全局重調(diào)度相同情況,而R類問題本文干擾管理方案效果會更加明顯.在成本上,干擾管理方案的成本總體上高于全局重調(diào)度方案成本,但部分相差不大且R207-25中干擾管理方案成本低于全局重調(diào)度成本.在累積前景理論值上,干擾管理方案的累積前景值大于或者等于全局重調(diào)度的累積前景值,這證明了本文的干擾策略有效性,且部分累積前景值為正數(shù),表明干擾后的方案提高了客戶的滿意度.

同時,本文的初始調(diào)度與Solomon標(biāo)準(zhǔn)數(shù)據(jù)上的最優(yōu)解相差不大,其中在R207-25車輛數(shù)2,低于Solomon的3輛,這減少了運(yùn)輸?shù)某杀?在運(yùn)行效率上,本文算法運(yùn)行20次,在客戶數(shù)量為25的平均時間為2.55 s,運(yùn)行客戶數(shù)量為50的平均時間為7.05 s.這證明了本文的算法有效性.

5 結(jié)論

本文針對物流配送中客戶時間發(fā)生改變的情況下,從客戶滿意度的角度出發(fā),將累積前景理論運(yùn)用在干擾策略上,同時考慮成本和路徑偏離的干擾,以干擾管理最小化為目標(biāo),構(gòu)建了字典排序方法和擾動恢復(fù)模型.最后,通過Solomon算例和文獻(xiàn)的對比,驗證了本文提出的干擾策略和算法的有效性.不足之處,本文只考慮了客戶時間上的變化和單一的干擾時刻,對客戶的需求和多個干擾時刻的帶來的影響,未來需進(jìn)一步驗證.