基于作業負荷均衡的金融押運車輛調度問題

李明琨,柏高帥,蔣欣穎

(上海大學管理學院,上海200444)

近年來,隨著中國經濟的迅速增長,金融服務業得到了空前發展.國有銀行、城市銀行乃至私有銀行在全國各大城市增設了大量銀行網點,銀行的現金流也呈指數增長的趨勢,專業的金融保安押運服務應運而生,為銀行網點、超市、醫院等場所提供現金押運服務.對于保安押運公司來說,如何實現科學的現金押運線路規劃是一個重要的議題,對提高押運過程的安全性、降低押運成本和提高工作效率起著關鍵的作用.該問題為車輛路徑規劃問題[1-2]的一種,車輛路徑規劃問題涉及眾多學科并已有廣闊的應用前景,如報紙投遞問題[3]、校車調度問題[4]、垃圾回收問題[5]、應急物流[6]等.

然而,銀行現金押運問題具有一定的特殊性.由于銀行網點在選址時要考慮人口分布、交通條件、商業集聚效應等多方面因素,導致網點布局從現金押運的角度看較為混亂.例如,有的地方較為集中,而有的地方則十分分散,容易導致各押運線路的工作負荷不均衡,這不僅會影響員工的服務效率和工作態度,還會增加企業的管理難度,如控制安全風險.押運線路間工作負荷的不均衡,易導致單一車輛的在途時間延長.而已有研究表明[7-8],現金押運風險與押運車攜帶的現金總量、在途時間或行駛距離等呈正相關.同時,押運公司需要考慮押運車使用過多帶來的人力、物力和財力成本.如果能夠通過科學的方法對押運車的路徑進行優化,減少押運車的使用量和行駛里程,不僅可以為企業節約成本,還能提高工作效率、降低風險.

針對上述問題,本工作提出一個以押運成本最優化和押運線路工作時間均衡為目標的多目標優化模型,并采用基于Solomon插入節約算法及鄰域搜索等算法對問題進行求解和比較分析,以實現金融押運資源的合理配置.

1 銀行押運車調度問題描述及模型

早送晚接是保安押運公司最主要的業務.早送,即在銀行早上營業前,押運車從金庫把款箱運送到各銀行網點；晚接,即在下午銀行網點業務清算完成后,押運車在規定時間內把款箱從網點運回金庫.

1.1 問題描述

早送晚接業務主要有以下幾個特點.

(1)押運車要在規定時間內到達銀行網點.為了保證銀行的正常營業,服務開始時間要嚴格落在銀行規定的時間窗內,這是銀行最基本的要求,所以時間特性是該業務中非常重要的因素.

(2)在早送晚接服務過程中,押運車大部分的工作時間是行駛在城市路網的高峰期,行駛速度容易受到影響.所以,押運車在網點間的行駛時間受行駛速度的影響較大.

(3)容量約束在早送晚接業務中起的作用較小,押運車很少出現滿載行駛的情況.

(4)不同押運線路之間存在工作負荷不均衡的情況.因為銀行網點的分布較為散亂,有的配送點比較集中,很快就能完成配送任務,而有的配送點比較偏遠且分散,導致配送任務繁重,而且存在安全隱患和影響服務質量等問題.

通過上述分析,可以把銀行押運車調度問題轉化為帶時間窗的車輛路徑問題,押運公司需要在押運過程中解決以下幾方面的問題：①降低押運成本；②保證押運過程中銀行網點的服務質量；③不同押運線路之間的工作量均衡.

由此可以看出,押運過程的運營成本低、服務及時、各線路工作量均衡是押運車路徑問題的主要解決目標.因此,有別于過往現金押運研究[2,7-8],雖會考慮搶劫風險、時間因素等,但仍以最小化車輛使用、最短化路徑等為目標,需要建立考慮押運工作量均衡的銀行押運車調度問題模型.所以,確定工作量的衡量標準成為本工作的首要任務.

1.2 工作負荷均衡的衡量

在實際押運過程中,每條押運線路上的總行駛里程、總服務時間和服務網點數目都各不相同,導致無法簡單地對工作負荷進行對比.關于配送線路工作量的衡量方法,已有的相關研究還沒有定論,大部分學者偏好于對行駛距離、配送量、服務的客戶數目等指標賦予不同的權重來衡量各線路工作量.

陳子俠等[9]提出了“廣義工作量”的概念,綜合考慮行駛里程、送貨量、服務商家數量這3個因素,用來衡量各送貨線路的工作量大小.具體表述如下,

式中：Wi表示某線路的工作量；Ki表示行駛路徑的長度；Yi表示歷史送貨量均值；Xi表示服務的商家數量；m1,m2,m3分別為Ki,Yi,Xi的權值,且m1+m2+m3=1.

為了均衡各配送線路的工作量Wi,給定一個誤差許可范圍,即

式中,W0表示各線路工作量的預定值,ε表示許可誤差范圍.

上述方法雖然給出了具體衡量各線路工作負荷的量化公式,能夠對各線路工作量進行綜合評價,但對于指標公式中的m1,m2,m3,W0,ε都需要人為給定,也沒有給出科學有效的確定方法,這會導致評價中摻入過多人為因素,不能客觀地反映每條線路工作量的實際情況.

文獻[10]是用工作時間、行駛距離和服務網點數對線路工作量進行綜合評價,先用最近鄰算法以線路最少且每條線路工作量均衡為目標對配送區域進行劃分,再對各路徑的行駛距離和服務時間進行優化,但沒有給出具體的權值取值方式,也沒有對工作時間與行駛距離、服務網點數三者之間的關系進行說明.

文獻[11]針對一些物流企業在調度車輛時只需支付司機出車費的情況,考慮各線路不均衡的問題,引入單位運輸費用的概念,用出車費用除以送貨量與送貨里程之和來表示.以最小化各線路單位運輸費用的平方差來表示線路工作量均衡.

文獻[12]針對物流配送系統中存在車輛負載不均衡導致的物流配送質量和配送系統柔性下降這一現象,提出了考慮均衡車輛負載的多目標路徑優化模型,以配送車輛總行駛距離盡可能短和車輛之間載運量盡可能平衡為優化目標.

文獻[13]則是針對快遞人員的收入構成很大一部分取決于計件工資,派件數量差別過大會直接導致明顯的收入差異,提出用服務客戶的總需求量表示工作量,以均方差的形式刻畫工作量不均衡.

由以上分析可以看出,針對不同業務情況可以選擇使用不同的衡量指標來對工作量進行刻畫,既可以綜合考慮多種因素,也可以只考慮某個單一因素.上述研究都是基于基本的車輛路徑問題(vehicle routing problem,VRP)來考慮,并沒有考慮服務客戶的時間窗問題,而銀行押運對時間要求十分嚴格,且押運車的大部分工作時間行駛在路網高峰期,受交通擁堵的影響比較明顯.如果簡單以行駛里程或送貨量來衡量工作量,可能會導致有些線路無法在規定時間內完成配送任務,而且銀行押運并不像普通的物流或快遞行業那樣以車輛行駛路程或送貨量的多少作為衡量業績的標準.

通過觀察可以發現,押運工作可以分為兩部分,一是行駛工作,二是服務工作.行駛距離遠,服務網點少,在途時間就多,而行駛距離近,服務網點多,服務時間就長,所以可以用工作時間來描述這兩部分的工作量,這樣既不需要人為確定權值,又考慮了押運車的行駛速度,比較符合銀行押運的特點,并且可以客觀真實地反映各線路的工作量.因此,定義某條線路的總工作時間為

式中,Tt表示某條線路押運過程中的總行駛時間,Tf表示某條線路押運過程中的總服務時間.為了使各線路的工作時間T基本相同,用最小化最大與最小工作時間的差值表示,即min(Tmax-Tmin),其中Tmax表示線路中最長的工作時間,Tmin表示線路中最短的工作時間.

行駛時間主要受路程和行駛速度的影響,考慮安全性等問題,押運車一般行駛在城市的主要干路上,各網點間的行駛線路都較為固定.而押運車的行駛速度則受高峰期的影響較為明顯.服務時間是指押運車到達銀行網點到離開該網點的時間,押運員在這段時間內將款箱交接給銀行的工作人員.而銀行的現金需求量較為穩定,即使需求增多,對服務時間的影響也較小.

1.3 問題模型

用圖G=(V,E)表示配送網絡,其中V={0,1,···,n,n+1}和E={(i,j)|i,j∈V,i/=j}分別是頂點和邊的集合.頂點0和n+1表示業務金庫(這里把業務金庫分成兩個點,0表示車輛的出發點,n+1表示完成任務后的返回點),金庫里停放著m輛完全相同的車.每個網點i都有一個允許服務的時間窗[ei,li].對稱的距離矩陣(dij)定義在邊集E上,dij=dji對于任意i,j都成立.

需要解決的問題是動用多少輛車,以及如何規劃車輛的行駛線路才能使得成本最少且工作量均衡,并滿足以下條件：①所有押運車均從金庫出發并且最后回到金庫；②每個網點有且僅

有一輛車到達和服務一次；③押運車必須在每個網點的時間窗內開始服務.

參數符號說明如下.

i,j=0或n+1：銀行業務金庫；

i,j=1,2,···,n：銀行網點；

k=1,2,···,m：押運車；

C1：押運車的調用成本；

C2：押運車的單位行駛成本；

dij：網點 i到網點 j 的距離,i,j=0,1,···,n,n+1；

fi：押運車在網點 i的服務時間,i=1,2,···,n；

tij：押運車從網點i到網點j的行駛時間,i,j=0,1,···,n,n+1；

Q：車輛k的最大裝載量,k=1,2,···,m；

qi：網點 i的需求量,i=1,2,···,n；

ei：網點i的時間窗上限,即允許最早開始服務時間；

li：網點i的時間窗下限,即允許最遲開始服務時間；

M ：罰因子,一個無窮大的數；

Tfk：車輛k的總服務時間；

Ttk：車輛k的總行駛時間；

Tk：車輛k的總工作時間；

U：所有線路中最長的工作時間；

V：所有線路中最短的工作時間；

wik：車輛k在網點i的等待時間；

Sik：車輛 k 到達網點 i的時間,i=0,1,···,n,n+1,k=1,2,···,m,如果車輛 k 沒有到達網點i,則Sik=0,其中S0k表示車輛k從金庫出發的時間,S(n+1)k表示車輛k完成任務返回金庫的時間.

決策變量

根據以上符號定義,建立模型如下：

約束條件

上述模型的含義如下.

目標函數(1)表示最小化押運成本.

目標函數(2)表示最小化線路中最大與最小工作時間的差值.

約束條件(3)表示每一輛押運車都必須從銀行的業務金庫出發.

約束條件(4)表示每一輛押運車完成任務后都必須返回銀行業務金庫.

約束條件(5)表示點0是押運車的出發點,而不是返回點.

約束條件(6)表示點n+1是押運車的最終返回點,而不是出發點.

約束條件(7)表示每個網點都能得到服務,且僅被服務一次.

約束條件(8)表示如果車輛k到達了網點j,則必須為網點j提供服務.

約束條件(9)表示車輛k為網點i提供服務后必須從網點i離開.

約束條件(10)表示任何一輛押運車服務的所有網點的總需求量不會超過其最大裝載量.

約束條件(11)表示押運車的時間窗約束,1～n為銀行網點時間窗約束,n+1為業務金庫的時間窗約束.

約束條件(12)表示押運車在配送路徑上相繼到達的兩個網點間的時間關系.

約束條件(13)表示只有當車輛k為網點i提供服務時,車輛k才會到達網點i.

約束條件(14)～(20)表示參數的取值.

1.4 求解方法

對VRP求解方法的研究一直都是重點和難點.1972年,Karp[14]證明了VRP是非確定性多項式(non-deterministic polynomial,NP)問題.隨后,Savelsbergh[15]和Solomon[16]指出帶時間窗的VRP比普通的VRP更復雜,有些問題甚至很難找到可行解.

VRP的主要求解算法有3類：精確算法、經典啟發式算法和現代啟發式算法.由于精確算法不適合求解大規模問題,所以實用價值不大.經典啟發式算法主要包括節約算法、最近鄰域算法、掃描算法和Solomon插入節約算法[17]等,而且大量的數據仿真證明Solomon插入節約算法的求解效果要優于節約算法、最近鄰域算法和掃描算法.由于經典啟發式算法使用局部尋優的搜索方法,結構簡單且速度快,但是往往只能得到較優的可行解,所以一般被用來構造初始可行解.現代啟發式算法主要有模擬退火算法[18]、遺傳算法[19]、禁忌搜索算法[20]、粒子群算法[21]、蟻群算法[22]等,有較強的全局搜索能力,能夠跳出局部最優解,但是結構比較復雜,求解時間較長.所以,目前的研究重點還是現代啟發式算法.

對于多目標問題的求解方法,歸結起來有傳統優化方法和智能優化方法兩大類.傳統優化方法包括加權法、約束法和線性規劃法等,實質上就是先將多目標函數轉化為單目標函數,再采用上述啟發式算法達到對多目標問題求解的目的.智能優化方法包括非支配排序遺傳算法(non-dominated sorting genetic algorithm,NSGA)[23]、Pareto存檔進化策略(Pareto archived evolution strategy,PAES)[24]算法、強度Pareto進化算法(strength Pareto evolutionary algorithm,SPEA)[25],以及帶精英保留策略的非支配排序遺傳算法(NSGA-Ⅱ)[26]等.NSGA-Ⅱ是Deb等[26]在NSGA的基礎上提出的,并且經過測試證明NSGA-Ⅱ比PAES算法和SPEA的求解效果更好.

NSGA-Ⅱ求得的Pareto最優解分布均勻,收斂性和魯棒性較好.但是,NSGA-Ⅱ具有一般遺傳算法收斂速度慢、早熟等缺陷,所以本工作對NSGA-Ⅱ進行了部分改進,具體算法如下.

(1)采用Solomon插入節約算法[17]求解問題模型獲得初始解,從而構造一個較好的可行個體.

(2)在此個體的鄰域內生成部分個體,這些個體的數目占初始種群規模的10%,其他個體隨機產生,共同構成初始種群.

(3)選用2-interchange局域搜索法,并應用全局最優(global-best,GB)策略[27]搜索所有鄰域解.λ-interchange局部搜索法于1993年由Osman[28]提出,是一種高效的鄰域搜索算法.

改進后的NSGA-Ⅱ采用自然數編碼方式,由Solomon插入節約算法產生初始解,選擇算子使用二進制錦標賽選擇法,雜交算子使用路徑雜交法,變異算子使用逆轉變異法.然后,對雜交和變異后產生的個體按概率1%進行局部搜索,直到找到比原個體更優的個體以替代原個體.

為了與NSGA-Ⅱ得出的結果進行對比,同時采用LocalSolver對該多目標問題求解.LocalSolver是基于模擬退火算法和各種局部搜索算法的優化求解軟件,支持連續變量、0-1決策變量和整數變量,可以解決非線性、非凸和多目標優化等問題,并且適用于解決大規模組合優化和次序優化問題.LocalSolver可以在給定解的基礎上進行優化,所以在求解時也把Solomon插入節約算法產生的解作為初始解.

2 案例分析

本工作以上海保安押運有限公司在上海市青浦區中國農業銀行的業務數據為基礎建立了實際案例.

2.1 算例的建立

中國農業銀行基本上在上海各區都設有業務金庫,以滿足各個網點的現金管理需求.上海保安押運有限公司目前也主要是以區來劃分業務范圍,由各個區的押運大隊負責提供服務.中國農業銀行在上海市青浦區共有23家網點(見圖1),目前有5輛押運車負責這23家網點的早送晚接業務.

圖1 上海市青浦區農業銀行網點分布Fig.1 Branches of Agriculture Bank at Qingpu district of Shanghai

參數設定如下.

(1)網點坐標.各網點的坐標信息由中國農業銀行官網查詢得知,并根據高斯投影坐標公式把大地坐標轉化為平面直角坐標,銀行業務金庫的坐標為(20,20).

(2)需求量.根據調研結果,平均每輛押運車至少能滿足10個網點的配送需求.這里把每個網點的需求設為10,每輛押運車的容量上限為100.

(3)時間窗.將各支行網點的時間窗設為[0,120],表示押運車要在2 h內完成所有網點的配送任務.銀行業務金庫的時間窗為[0,180],表示押運車要在3 h內返回金庫.

(4)服務時間.押運員都接受過專業的培訓,對交接流程十分熟悉,因此交接時間較短且比較穩定.從停車、交接款箱到開車離開大約要5 min,本工作把交接的服務時間定為5 min,即 fi=5,i=1,2,···,23.

(5)行駛速度.參數tij,即兩點間的行駛時間,由路徑距離相較于車輛行駛速度來決定.考慮車輛行駛速度會對結果產生影響,實驗中將調整押運車在路網中的平均行駛速度并進行比較分析.

(6)路徑距離.一般在求解VRP時,都是把兩個需求點之間的直線距離設為路徑距離.但是由于路網的復雜性,這樣并不能合理表示實際的道路情況.例如,在美國曼哈頓街區,從一個十字路口行駛到另一個十字路口,走過的路徑長度并不是兩點間的直線距離,因為不可能從高樓大廈之間穿過,這個實際行駛距離被稱為“曼哈頓距離”,或者是城市街區距離.設兩點A(x1,y1),B(x2,y2),則d=|x1-x2|+|y1-y2|即為曼哈頓距離.

根據上述參數設置,可以得到各網點的位置坐標、時間窗及服務時間如表1所示,業務金庫以點0及24表示.

表1 各網點的位置坐標、需求量、時間窗和服務時間Table 1 Coordinate position,demands,time window and service time of demand nodes

2.2 求解結果

本實驗使用i5-2.5G CPU,8 GB內存的PC機,操作系統為Windows 7.LocalSolver為5.0版,模擬退火水平選擇最大,即annealing level=9.NSGA-Ⅱ的開發軟件為VC++6.0,參數設置如下：最大進化代數Maxgen設為1 000代,交叉率Pc=0.8,變異率Pm=0.1.

根據調查結果,可假設平均每輛押運車價值50萬元,折舊期為10 a,不考慮余值,每車每年的折舊費為5萬元.每車每年的行駛總里程為10萬km,柴油價格約為6元/L,100 km油耗為12 L,則燃油費為7.2萬元/a.保養修理費為1萬元/a,保險費為2萬元/a,以及4名員工總工資為24萬元/a,計算可得每輛車的調用成本為

單位距離行駛成本為

即C1=876.71,C2=3.92,將上述參數代入模型中可以直觀地對求解結果進行比較.

2.2.1 恒速時的結果分析

假設車輛在各網點間的平均行駛速度都相同,改變車輛的行駛速度,得出求解結果如表2所示.

表2 恒速時的求解結果Table 2 Results with constant speed

圖2和3是最大工作時間差和押運成本隨速度變化的比較.總體來說,NSGA-Ⅱ的求解結果要優于LocalSolver.

圖2 最大工作時間差對比Fig.2 Comparison of maximum differences of service time

圖3 成本對比Fig.3 Comparison of costs

由圖2可知,在這種情況下,隨著行駛速度的降低,兩種方法得出的工作時間差有逐漸增大的趨勢,而LocalSolver的最大工作時間差上升趨勢更明顯.而在圖3中,只有速度為30 km/h時,NSGA-Ⅱ求得的押運總成本才略高于LocalSolver的優化結果,其他情況下NSGA-Ⅱ得出的押運成本都較低.

通過對比兩種方法的求解結果可以看出,NSGA-Ⅱ在求解多目標問題時能夠綜合考慮兩個目標得到較優的解,而且兩種方法得出的結果都比實際使用的車輛少.

2.2.2 變速時的結果分析

青浦區農業銀行金庫與銀行網點的分布如圖4所示,由于金庫處于青浦區中心,所以金庫附近分布的銀行網點較多,且較為集中,周邊距離金庫較遠的銀行網點則較為分散,屬于混合型分布.由于早送晚接處于早晚高峰時期,部分道路擁擠較為明顯,車輛的行駛速度會受到影響.這里大致把23個網點劃分為4個區域,假設每個區域受早晚高峰的影響不同,區域1處于中心地帶,道路擁擠程度較高,區域2,3,4距離中心地帶較遠,道路擁擠程度較低.

圖4 金庫與銀行網點分布Fig.4 Distribution of treasury and bank branches

考慮早晚高峰對車輛行駛速度的影響,并結合調查情況,給每個區域和區域間的網點之間設定不同的行駛速度.押運車在區域1內各網點間的行駛速度為20 km/h,在區域2,3,4內各網點間的行駛速度為40 km/h,區域1內的網點到區域2,3,4內網點的行駛速度為30 km/h,區域2,3,4內網點間的行駛速度為40 km/h.設vij是對稱的,由此可得每兩點間的行駛時間tij,結果如表3所示.

表3 變速時的解路徑Table 3 Results of routes with variable speed

圖5和6分別是LocalSolver和改進NSGA-Ⅱ在變速時各線路的工作時間.明顯可以看出,在行駛路程差距不大的情況下,NSGA-Ⅱ規劃的各線路工作時間更加均衡.

圖5 LocalSolver在變速時各線路的工作時間Fig.5 Results of time on each route using LocalSolver

圖6改進NSGA-Ⅱ在變速時各線路的工作時間Fig.6 Results of time on each route using NSGA-Ⅱ

圖7 和8分別是在變速時LocalSolver和改進NSGA-Ⅱ得到的路徑圖.可以看出,在區域1速度較慢的情況下,改進NSGA-Ⅱ選擇單獨使用1輛車在區域1內服務,說明當速度發生變化時,改進NSGA-Ⅱ也能靈活地作出調整,使各線路的工作量更加均衡.

圖7 LocalSolver在變速時得到的路徑圖Fig.7 Results of routes using LocalSolver

圖8 改進NSGA-Ⅱ在變速時得到的路徑圖Fig.8 Results of routes using NSGA-Ⅱ

3 結束語

銀行押運車調度問題是車輛路徑問題在金融領域的一個新的應用.本工作根據銀行押運車早送晚接的業務特點,提出了押運線路工作量的衡量方法,建立以押運成本最優化和押運線路工作量均衡為目標的多目標優化模型,并考慮了不同條件和參數設置情況對押運車輛布置和路徑選擇的影響,例如早晚高峰使得車輛行駛速度發生變化.

考慮實際路徑情況,使用曼哈頓距離即城市街區距離來表示網點間距離.在Solomon插入節約算法得出的可行解的基礎上,使用基于模擬退火算法的優化軟件LocalSolver和NSGA-Ⅱ求解該多目標問題模型.由案例仿真的結果可以看出,在不同行駛速度的情況下,改進NSGA-Ⅱ得出的工作負荷均衡性都要優于LocalSolver.而且,本工作提出的解決方案能夠在有效降低押運成本的同時,均衡各押運線路的工作量,實現資源的合理配置.

本工作提出了將作業均衡策略思想應用于金融押運服務中的車輛調度問題,并針對實際案例通過對比分析驗證模型方法.在后續研究中可進一步探討目標受多因素影響,如隨機變速等因素影響調度方案的實現等問題.