基于作業(yè)負(fù)荷均衡的金融押運(yùn)車輛調(diào)度問題

李明琨,柏高帥,蔣欣穎

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

1.2 工作負(fù)荷均衡的衡量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 問題模型

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

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

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

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

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

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

k=1,2,···,m：押運(yùn)車；

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

C2：押運(yùn)車的單位行駛成本；

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

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

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

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

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

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

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

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

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

Ttk：車輛k的總行駛時(shí)間；

Tk：車輛k的總工作時(shí)間；

U：所有線路中最長(zhǎng)的工作時(shí)間；

V：所有線路中最短的工作時(shí)間；

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

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

決策變量

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

約束條件

上述模型的含義如下.

目標(biāo)函數(shù)(1)表示最小化押運(yùn)成本.

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

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

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

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

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

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

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

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

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

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

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

約束條件(13)表示只有當(dāng)車輛k為網(wǎng)點(diǎn)i提供服務(wù)時(shí),車輛k才會(huì)到達(dá)網(wǎng)點(diǎn)i.

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

1.4 求解方法

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

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

對(duì)于多目標(biāo)問題的求解方法,歸結(jié)起來有傳統(tǒng)優(yōu)化方法和智能優(yōu)化方法兩大類.傳統(tǒng)優(yōu)化方法包括加權(quán)法、約束法和線性規(guī)劃法等,實(shí)質(zhì)上就是先將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù),再采用上述啟發(fā)式算法達(dá)到對(duì)多目標(biāo)問題求解的目的.智能優(yōu)化方法包括非支配排序遺傳算法(non-dominated sorting genetic algorithm,NSGA)[23]、Pareto存檔進(jìn)化策略(Pareto archived evolution strategy,PAES)[24]算法、強(qiáng)度Pareto進(jìn)化算法(strength Pareto evolutionary algorithm,SPEA)[25],以及帶精英保留策略的非支配排序遺傳算法(NSGA-Ⅱ)[26]等.NSGA-Ⅱ是Deb等[26]在NSGA的基礎(chǔ)上提出的,并且經(jīng)過測(cè)試證明NSGA-Ⅱ比PAES算法和SPEA的求解效果更好.

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

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

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

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

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

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

2 案例分析

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

2.1 算例的建立

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

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

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

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

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

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

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

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

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

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

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

2.2 求解結(jié)果

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

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

單位距離行駛成本為

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

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

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

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

圖2和3是最大工作時(shí)間差和押運(yùn)成本隨速度變化的比較.總體來說,NSGA-Ⅱ的求解結(jié)果要優(yōu)于LocalSolver.

圖2 最大工作時(shí)間差對(duì)比Fig.2 Comparison of maximum differences of service time

圖3 成本對(duì)比Fig.3 Comparison of costs

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

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

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

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

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

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

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

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

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

圖6改進(jìn)NSGA-Ⅱ在變速時(shí)各線路的工作時(shí)間Fig.6 Results of time on each route using NSGA-Ⅱ

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

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

圖8 改進(jìn)NSGA-Ⅱ在變速時(shí)得到的路徑圖Fig.8 Results of routes using NSGA-Ⅱ

3 結(jié)束語

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

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

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