基于累積前景理論的物流配送干擾管理問題研究

張鵬，石莎莎，寧濤

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

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

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

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

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

1 基于累積前景理論

1.1 累積前景理論描述

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

1.2 價值函數的確定

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

(1)

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

1.3 決策權重的確定

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

(2)

(3)

(4)

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

1.4 累積前景值模型

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

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

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

(5)

累積前景值f1,公式為：

(6)

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

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

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

(7)

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

(8)

2 擾動恢復模型的建立及干擾策略

2.1 擾動恢復模型的建立

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

變量和符合定義如下：

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

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

目標函數：

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)

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

2.2 干擾策略

(1)增派車輛策略

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

(2)臨近救援策略

利用現有的在途車輛進行的局部調整策略, 需要考慮客戶的時間和車輛的容量要求, 是否能滿足干擾發生時的情況.

(3)取消客戶策略

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

3 改進的蟻群算法的設計和步驟

3.1 改進的蟻群算法

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

3.2 改進轉移概率

(20)

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

3.3 信息素更新策略

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

(21)

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

步驟如下：

參數含義：Hk+1為當前螞蟻完成循環后得到的局部最優解,Hk為上一次循環后得到的局部最優解,NC代表循環次數,T為當前溫度,按照模擬退火機制,每次迭代之后進行降溫,TNC+1=TNC·r,r為降溫速率.

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

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

(22)

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

(23)

3.4 算法流程

步驟1：生成初始調度方案,根據改進的蟻群算法以成本最小為目標求解.

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

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

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

4 仿真實驗

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

表1 客戶信息表

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

采用本文改進的蟻群算法得到最優的初始方案:車輛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,優于文獻[16]的531.41.

當時間為32.65,客戶4、6、13、14信息發生變動,變動信息如表2.

表2 客戶時間窗變動信息

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

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

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

全局重新調度方案：車輛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.

三種配送方案的結果如表3所示.

表3 三種方案的結果比較

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

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

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

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

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

本文將選取的算例的干擾管理與全局重調度方案進行了比較,結果如表5所示.

表5 干擾管理與全局重調度方案結果的比較

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

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

同時,本文的初始調度與Solomon標準數據上的最優解相差不大,其中在R207-25車輛數2,低于Solomon的3輛,這減少了運輸的成本.在運行效率上,本文算法運行20次,在客戶數量為25的平均時間為2.55 s,運行客戶數量為50的平均時間為7.05 s.這證明了本文的算法有效性.

5 結論

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