李明琨,柏高帥,蔣欣穎

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

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

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

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

1 銀行押運車調(diào)度問題描述及模型

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

1.1 問題描述

早送晚接業(yè)務(wù)主要有以下幾個特點.

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

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

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

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

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

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

1.2 工作負荷均衡的衡量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 問題模型

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

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

有一輛車到達和服務(wù)一次；③押運車必須在每個網(wǎng)點的時間窗內(nèi)開始服務(wù).

參數(shù)符號說明如下.

i,j=0或n+1：銀行業(yè)務(wù)金庫；

i,j=1,2,···,n：銀行網(wǎng)點；

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

C1：押運車的調(diào)用成本；

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

dij：網(wǎng)點 i到網(wǎng)點 j 的距離,i,j=0,1,···,n,n+1；

fi：押運車在網(wǎng)點 i的服務(wù)時間,i=1,2,···,n；

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

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

qi：網(wǎng)點 i的需求量,i=1,2,···,n；

ei：網(wǎng)點i的時間窗上限,即允許最早開始服務(wù)時間；

li：網(wǎng)點i的時間窗下限,即允許最遲開始服務(wù)時間；

M ：罰因子,一個無窮大的數(shù)；

Tfk：車輛k的總服務(wù)時間；

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

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

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

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

wik：車輛k在網(wǎng)點i的等待時間；

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

決策變量

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

約束條件

上述模型的含義如下.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 求解方法

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

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

對于多目標問題的求解方法,歸結(jié)起來有傳統(tǒng)優(yōu)化方法和智能優(yōu)化方法兩大類.傳統(tǒng)優(yōu)化方法包括加權(quán)法、約束法和線性規(guī)劃法等,實質(zhì)上就是先將多目標函數(shù)轉(zhuǎn)化為單目標函數(shù),再采用上述啟發(fā)式算法達到對多目標問題求解的目的.智能優(yōu)化方法包括非支配排序遺傳算法(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的基礎(chǔ)上提出的,并且經(jīng)過測試證明NSGA-Ⅱ比PAES算法和SPEA的求解效果更好.

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

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

(2)在此個體的鄰域內(nèi)生成部分個體,這些個體的數(shù)目占初始種群規(guī)模的10%,其他個體隨機產(chǎn)生,共同構(gòu)成初始種群.

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

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

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

2 案例分析

本工作以上海保安押運有限公司在上海市青浦區(qū)中國農(nóng)業(yè)銀行的業(yè)務(wù)數(shù)據(jù)為基礎(chǔ)建立了實際案例.

2.1 算例的建立

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

圖1 上海市青浦區(qū)農(nóng)業(yè)銀行網(wǎng)點分布Fig.1 Branches of Agriculture Bank at Qingpu district of Shanghai

參數(shù)設(shè)定如下.

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

(2)需求量.根據(jù)調(diào)研結(jié)果,平均每輛押運車至少能滿足10個網(wǎng)點的配送需求.這里把每個網(wǎng)點的需求設(shè)為10,每輛押運車的容量上限為100.

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

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

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

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

根據(jù)上述參數(shù)設(shè)置,可以得到各網(wǎng)點的位置坐標、時間窗及服務(wù)時間如表1所示,業(yè)務(wù)金庫以點0及24表示.

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

2.2 求解結(jié)果

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

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

單位距離行駛成本為

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

2.2.1 恒速時的結(jié)果分析

假設(shè)車輛在各網(wǎng)點間的平均行駛速度都相同,改變車輛的行駛速度,得出求解結(jié)果如表2所示.

表2 恒速時的求解結(jié)果Table 2 Results with constant speed

圖2和3是最大工作時間差和押運成本隨速度變化的比較.總體來說,NSGA-Ⅱ的求解結(jié)果要優(yōu)于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的優(yōu)化結(jié)果,其他情況下NSGA-Ⅱ得出的押運成本都較低.

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

2.2.2 變速時的結(jié)果分析

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

圖4 金庫與銀行網(wǎng)點分布Fig.4 Distribution of treasury and bank branches

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

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

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

圖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-Ⅱ得到的路徑圖.可以看出,在區(qū)域1速度較慢的情況下,改進NSGA-Ⅱ選擇單獨使用1輛車在區(qū)域1內(nèi)服務(wù),說明當速度發(fā)生變化時,改進NSGA-Ⅱ也能靈活地作出調(diào)整,使各線路的工作量更加均衡.

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

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

3 結(jié)束語

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

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

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