苏州A银行运钞车路径问题的研究
内容摘要
随着城市化进程的加速,城市的规模日益变大,银行为了方便人民的存取款业务
要求,纷纷增加办理网点。然而由于金融行业的特殊性,网点一般不设置金库,现金
和票据需要每天按时有效的进行专门投送和收取。网点数量多和分散性,导致运钞车
运行路径规划难度的加大。运钞车路径优化问题是一个NP-Hard问题,遗传算法对其
近似最优解的求取有很好的效果。
关键词:运钞车,路径优化,遗传算法
作 者:夏娜
指导老师:陈铭
I
Abstract
The research of route optimization based on A bank in Suzhou
The research of route optimization based
on A bank in Suzhou
Abstract
The city size is expanded very quickly according to the urbanization. In order to
convenient to the customer, many commercial banks add more branches. Because the
finical industry is very special, the cash need to send and keep in one place which will
include armed guard every day. The branched is located in different places with in one city.
This also increased the difficulty of the route optimization. The cash truck route
optimization is a NP- Hard problem. The genetic algorithm will get a better affection about
how to solve these problem.
Key words: Cash trusck, Route optimization, Genetic algorithm
Written by XIA NA
Supervsed by CHEN MING
一、研究背景及意义
(-)国外对于运钞车路径问题的研究
目前从事运纱车路径问题的研究学者还比较少。1993年,Lambert等收取款箱
的车辆路径问题抽象为带时间窗的车辆路径问题(Vehicle Routing Problem with Time
Windows, VRPTW),并在目标函数和相应的约束条件中加入了银行背景的特殊要
求。文中涉及了确定性和随机旅行时间两种情况,并采用整数规划和启发式算法进行
了求解。最后作者根据比利时银行系统的实际数据进行模拟,取得了一定成效(2)。2004
年,Tarantilis等提出了一个决策支持系统用以帮助银行进行市内车辆路径规划。文中
不仅考虑了一般的线路约束,还特别提出了最小化路线中某点被成功抢劫的概率,并
用元启发式算法进行了求解。在应用于真实的银行运营环境时,该系统得到了良好的
妙里(3)
(二)国内对于运钞车路径问题的研究
2005年,武淑萍将提出了不带时间窗的经典车辆路径问题,并基于Matlab设计
了简单的遗传算法进行求解。但是,她考虑的约束条件过于简化,只给出了包含50
个客户点的小规模问题的优化结果,实用性较差(4)。
2009年,张宏兵提出了随机需求的车辆路径问题(Vehicle Routing Problems with
Stochastic Demand, VRPSD)。VRPSD中,各银行网点的需求不可预知,因此车辆
在按照预先设定的路径行驶时会发生车辆容量不能满足路线规划与控制路线失败补
偿费用的机会约束规划两类模型相结合,作者提出了基于估计补偿的机会约束规划模
型(Chance Constrained Programming with Estimated Recourse, CCPER),使优化的
路径结果不致出现费用低而失败率高或失败率低而费用高的情况。然后,通过引入随
机模拟建立了基于精确补偿的机会约束规划模型(Chance Constrained Programming
with Accurate Recourse, CCPAR),解决了补偿费用无法计算的问题。最后,作者用
禁忌搜索算法进行了算例的计算和分析,证明CCPER和CCPAR可以有效处理
VRPSD(5)上网点需求的情况。
==>>