基于作业负荷均衡的金融押运车辆调度问题

李明琨,柏高帅,蒋欣颖

(上海大学管理学院,上海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.而且,本工作提出的解决方案能够在有效降低押运成本的同时,均衡各押运线路的工作量,实现资源的合理配置.

本工作提出了将作业均衡策略思想应用于金融押运服务中的车辆调度问题,并针对实际案例通过对比分析验证模型方法.在后续研究中可进一步探讨目标受多因素影响,如随机变速等因素影响调度方案的实现等问题.