如何用数据实现运钞车线路的智能规划
验“金”室
随着智能变革的到来，企业智能化逐步深入。人工智能技术的应用不仅在企业运营、管理以及决策流程上减少了人工干涉，还使得企业大数据决策更加精准、快速。目前，银行业已上线多种场景智能辅助决策模型，甚至在某些场景已逐步替代人工处理，实现了流程上的自动化、智能化。本文对如何利用数据规划运钞车的工作线路，实现运钞车线路的智能规划进行探讨。
一、哪些业务需要使用运钞车
在日常银行的业务场景中，现金配送作为银行现金运营管理的重要工作，涉及日常银行网点款箱配送与回收、银行上门服务、ATM设备加钞等业务服务场景。
1
银行网点的款箱配送与回收
由于现金管理相关要求，现金及重要凭证是不允许留在银行网点过夜的。银行网点的款箱必须在网点营业前完成分散派送、在网点营业结束后进行回收。其中，分散派送需要运钞车从银行金库提取款箱配送到各个网点，而回收需要运钞车从各个网点将款箱配送至银行金库集中存放。
2
银行上门到点服务
银行会与某些客户签订上门服务协议。在协议约定时间，银行会为单位客户提供指派专人到客户指定场所办理现金收付、送取单据等特定服务。运钞车将随同专人为客户提供上门服务。
3
银行ATM加钞服务
银行负责所在城市ATM的运营管理工作。每日银行将根据ATM钞箱内的现金使用情况与预期的ATM吞吐金额，制定ATM加钞计划。当有ATM需要加钞时，银行将安排运钞车配送新的钞箱替换ATM中旧的钞箱。
二、运钞车线路规划的难点
由于银行网点数量和ATM设备等数量众多、地理位置分布广泛，受交通状况以及服务时间等条件制约，以传统方式依赖人工经验对运钞车线路进行规划具有极高的复杂度，需要综合考虑以下情况，往往难以在短时间内做出最优的线路规划。
1
服务站点类型多
服务站点包括银行网点、银行上门服务点和银行ATM。不同类型的服务站点有不同的服务需求。
2
服务站点数量多
服务站点数量往往不少于100个。
3
服务站点分布范围广
不仅城市市区有服务站点，郊区及偏远地区也有不少服务站点。
4
服务站点服务时间不一
不同服务站点有不同的服务时间要求，如不同的银行网点有不同的营业时间。
5
服务具有优先级关系
为了保障银行网点的正常运营，运钞车线路的规划需优先确保银行网点款箱配送任务在各网点开门前完成。
6
服务具有前后依赖关系
以银行ATM加钞服务为例，银行网点内的ATM加钞通常采用网点自行加钞的方式。为了减少等待时间，运钞车将配送网点款箱与ATM钞箱配到网点后立刻到下一个银行网点进行配送。ATM加钞替换下来的钞箱将在后续的线路规划中重新收集。
三、问题解决思路
既然人工规划运钞车线路难点那么多、设计那么复杂，那我们不如抛弃人工设计的想法，以构建数学模型为思路。其实，上文提到的3个场景可以简单地抽象为一类问题。
有一定数量的服务站点，各自有不同的服务时间需求，由一个中心向客户提供物品，一个车队负责配送物品。如何规划车队的行驶线路既能确保服务站点的需求得到满足，又能使用最少的车辆、节省配送车队的行车成本？这正是带时间窗车辆路径问题（VRPTW）。
VRPTW问题的求解思路类似于遍历搜索，常用求解方法分为两类：
1
精确求解方法
具体有分支界限法、分支切割法、集合涵盖法等。但由于求解空间十分庞大，这些精确解法往往很难取得较好的结果。
2
启发式求解方法
具体有节省法、模拟退火、禁忌搜寻、遗传算法、蚁群算法等。这些基于人工智能的启发式算法在解决组合优化问题上显示出了强大性能，目前主流的解决方案都属于该类别。
四、求解实例
主流的解决方案均采用启发式算法求解，其主要算法运用的就是大名鼎鼎的遗传算法。
1
基于遗传算法的求解实例
遗传算法借鉴了达尔文进化论中自然选择和自然进化的原理，模拟生物在自然界中的进化过程所形成的一种优化求解方法。采用遗传算法解决VRPTW问题有三个与基础算法有所区别的要点。
（1）个体编码
个体编码的设计希望把问题的解编码到遗传算法的染色体中。该实例采用自然数编码，将0代表现金中心，1、2……n代表服务站点。举个例子，假定一个中心的车队有2辆车、服务站点有5个，那么就可能存在这么一条染色体（染色体长度=服务站点数目+线路数目+1）：
0、5、2、1、0、3、4、0
它代表着车队的行驶路线如下所示。
车辆一：0-5-2-1-0
车辆二：0-3-4-0
每条路线都被0包裹（以0开始、以0结束），也就可以简单地理解为这是一条以现金中心为起点、以现金中心为终点的线路。
（2）交叉算子
传统的交叉算子不适用于以自然数编码个体的VRPTW问题求解中。以单点交叉为例，以下的两条父染色体：
经过在单点交叉操作可能出现如下子代染色体：
子代染色体1转换回线路规划结果：
0-3-2-9-6-0
0-7-1-5-6-7-9-0
可以发现，线路数从原来的3条变成了2条、服务站点出现重复访问的情况，不是可行的规划结果。
因此，我们参考学位论文《基于电动汽车的带时间窗的路径优化问题研究》设计的交叉算子步骤（目标路线数目为N）：
①在父代染色体a中随机挑选一条线路route_select_a；
②将route_select_a未访问的服务站点按父代染色体b的访问顺序排列，并把该排列称为perm；
③将perm多次随机拆分成N-1条路线，分别计算多次拆分的适应度，保留perm的最佳拆分；
④将perm的最佳拆分与route_select拼接组合成为子代染色体A；
⑤同样地，将上述步骤的父代染色体a、b交换，合成子代染色体B。
（3）突变算子
突变算子步骤如下：
①随机选择染色体的两个服务站点进行交换，计算适应度；
②重复步骤1多次，保留最佳突变结果。
针对VRPTW问题，将遗传算法进行适配，能够解决VRPTW问题的求解。但遗传算法的适配上无论是个体编码、交叉算子、突变算子都有着极多的选择，如何选择最优的组合，挑选出合适的适配方式将是一个极为耗时的工作。因此，在调教遗传算法的同时，可以考虑利用开源求解方法为遗传算法提供一个良好的种群初始化，以提高遗传算法的规划结果。
2
基于ortools的求解实例
ortools是google开源的运筹优化套件，用于解决车辆路径、流程、整数和线性规划以及约束编程等棘手的统筹优化问题。Ortools将规划算法进行了高层级的封装，仅需提供线路规划的基础数据与约束条件就能自动规划出线路结果。以官方demo为例，提供以下数据便可使用默认参数求解VRPTW问题。
其中，time_matrix是时间矩阵，time_matrix[i][j]代表了i站点到j站点的耗时；而time_windows是各站点服务时间窗的设置，第二行的(7, 12)代表第二个站点必须在[7,12]这个时间窗内访问；num_vehicles代表规划的目标线路数；depot代表中心的标号。
以下是demo输出的结果，可以看出，这是四条线路的规划结果，每个服务站点的最早访问时间与最晚访问时间都能输出在结果当中。
五、方案关键点
在现实世界中，估计服务站点间的行驶距离是成功解决运钞车线路问题的关键点，如何才能获取最为精确的行驶距离是一个值得研究的课题。以下是笔者考虑到的行驶距离估计及修正方法。
1
基于实时地图数据支持的
运钞车行驶时间估计
互联网上有实时地图路径规划的服务API，在数据获取阶段，可以利用各类地图服务的资源，给行驶时间提供一个较为准确的基于地图数据的初始估计值。
2
基于大数据统计的
运钞车行驶时间修正
银行可获取运钞车的历史行驶路径及相关行驶记录，通过分析可获得大量的服务站点间行驶时间。再结合日历信息，运钞车行驶时间可通过统计当日历史同期的行驶时间平均值进行估计。其中，历史同期可能是周同期，如当天是周一则以历史上的周一平均数据值估计；可能是月同期，如当天是2日以历史上2日的平均数据值估计；也可能是节假日同期，如当日是节假日后第一天则以历史上节假日后第一天的平均数据值估计。分析运钞车行驶历史数据可获得部分服务站点间更为精确的行驶时间，进而对基于地图数据的初始估计值做出一轮修正。
3
基于业务规则引擎的
运钞车行驶时间修正
业务专家对钞车行驶路线有深刻的认识，能为行驶时间数据提供一系列的修正规则。通过整合业务专家提供的修正规则、编写修正规则引擎，能将业务专家的深刻认识应用于基于地图数据的初始估计值的进一步修正。
（1）线路数自动设置
在VRPTW求解算法中大都需要预设规划线路数，而实际上我们往往无法得知现实问题的目标规划线路数。由于运钞车线路规划希望尽量降低车辆的需求量，即减少规划线路书，我们可以先预设一个较大的规划线路数以确保能在该条件下问题有可行解，再逐步减少规划线路数直至规划无法获得可行解，这时能获取可行解的最小规划线路数即为我们的目标规划线路数。其中，为了避免算法的多次规划造成时间上的极大浪费，在检索最小规划线路数时可以采取二分的方法。通过二分的机制，可将时间上的消耗控制在一个可接受的范围内。
（2）多算法规划结果整合
常用的VRPTW求解算法都是启发式算法，而启发式算法有其不确定性。不仅算法多次规划可获得不同结果，在不同数据集的输入下不同启发式算法的性能表现也不尽相同。可以发现，扩展求解算法的种类与规划次数也能大幅影响最终的规划效果。因此，实际规划中并行调用各类算法并最终根据预设评价指标挑选整合规划结果十分必要。
基于线路规划算法自动规划银行运钞车辆的最优行驶路线，可实现站点的智能排线，使银行能够在满足站点服务需求的条件下减少运钞车行车成本，推动服务智能化。
更多精彩内容
FCC30+
长按左边二维码
关注我们不迷路