作者：白程宇、姜东晓
运筹规划模型不光能解决如选址这样传统的全局优化问题，也可以与其他学科交叉，完成很多有趣有用的决策过程。
本期介绍一种海量快递员GPS轨迹数据的路网匹配模型，通过交通工程 + 运筹规划的方式，实时展现城市中所有快递员派送路径的流式结构及热力分布，帮助决策者清晰、完整地掌握全局路径概况。基于这种可视化，可以挖掘快递员GPS数据中隐含的空间集聚和流动的动态规律，有助于柜机网络布局问题的发现与解决，从而促进柜机网络规划与决策的精确化、科学化，具有宝贵的价值。
一、业务描述
1.1 轨迹数据挖掘的重要性
随着信息通讯技术(Information and communication technologies，ICT)的高速发展和位置感知(Location Awareness)设备如智能手机、车载GPS等的普及应用，海量的交通连续型时空轨迹数据集成为令交通工程领域兴奋的新数据源。此类移动定位数据获取成本低，覆盖范围广，且拥有时态特性，既可以进行微观个体活动模式的研究，也可以进行宏观活动系统的研究。比如动态感知城市道路的路网交通状态、拥堵状况、十字路口等重要交通节点的车流量状况，分析车辆轨迹的时空规律等。
我们App以2分钟为采集精度，收集着所有快递员的GPS散点轨迹信息，每日数据量以数十亿计量。那么如何可视化这些散点数据，从全局视角实时地、清晰地、完整地掌握路径热力分布概况呢？
1.2 处理上的难点
快递员上传的GPS数据本身对信息传达的失真：轨迹点投影到路网上的需求是交通工程上很多可视化研究的第一步。我们希望轨迹可以反映真实路网的布局，但2分钟甚至10分钟采集一次的GPS数据因为离散，造成数据点间连线与路网产生较大偏差。
海量数据高效处理：路网数据在百万级别，快递员GPS点在数十亿级别，二者建立匹配关系相当耗时，用传统方法即使只是一个行政区（如深圳市南山区）的范围也需要69个小时的计算。亟需一种高速求解算法来提高大规模问题的处理能力。
二、技术实现
2.1 建立路网信息空间索引
我们从由地图制作爱好者维护的开源网站OpenStreetMap下载了全国路网信息的结构化数据，再由产品组同事解析后转化为空间索引（路线ID，路径坐标点）的数据结构给到我们。如下图是北京市路网展示效果图。全国路网数据总量在500万级别。
但是其中数据过于细节，很多数据对于流量分析是无用的，比如：操场、公园等。我们需要分析的是快递员行驶的路径及其路径上的流量变化。所以对全国路网数据根据数据标识进行筛选，留下主干道和街道等与快递员有关的路网数据，如下图所示：
2.2 KDtree模型实现高效轨迹投影
轨迹点投影到路网上的需求，传统做法可用ARCGIS将点位与路段进行空间邻近连接，但处理速度与效率面对大规模问题时不佳。
KDTree是一个非常高效的最邻近搜索算法，通过建立索引树来提高检索速度。在python中使用K-D也非常简单，直接调用scipy.spatial即可。但KDTree包的问题在于，其本身是不支持以经纬度球面距为metric来进行搜索的。而如果我们不进行经纬度转化，直接调用KDTree的话，会由于计算出的距离误差而导致我们的搜索出现偏差。
直接掉包用的是欧氏距离而非我们想要的球面距，因此，我们的思路是先将经纬度进行转化，然后再调用KDTree去检索，最后将计算出的距离再转化为球面距。
通过算法将快递员GPS数据与路网数据进行一一匹配，实验数据结果表明一个行政区40,000个路网坐标点 × 720,000个上报GPS点，解空间为2.88E10（28亿）时，并行的KDTree模型可以在10s内完成全部计算，比传统做法提速25,000倍。
且匹配效果的精度也较高，整体效果来看如下概念图，将蓝色快递员GPS点整体向路网点纠偏。
概念图来源：https://zhuanlan.zhihu.com/p/50776628
2.3 流量统计和前端渲染
完成全部投影后，按路径ID统计流量热力。某条路上途径的快递员越多，被投影点也越多，流量热力值越高，线条也越粗。效果图如下，可以看到一些干道流量明显要粗，支路则普遍很细，与实际情况相符合。
概念图来源：https://zhuanlan.zhihu.com/p/50776628
最终产品组前端同事使用echarts和Amap技术选然后，展示了可根据快递员GPS投影结果(快递员在该道路上出现的频次)进行层次化细分的可视化效果。道路颜色随着流量增加而渐变，流量较少的路网的用绿色进行标识，流量较大的路网用红色进行标识，中间过渡色为黄色。所以深圳市哪些道路是快递员出现频率最高的，哪些是最低的，就一目了然了。
三、从可视化到决策
基于该可视化结果，我们还可以继续分析更细节的信息。下图是深圳市全部快递员某天内在路网上的出现频次分布图，横轴以快递员投影点为单位由低（左）到高（右）顺序排列，纵轴是同类路线统计个数，可以看出：
（1）整体分布呈左侧集中右侧长尾。
（2）频次最高的5%的路径中快递员的出现频次超过26次，位于75%~95%之间的出现频次为9-26次，小于9次的占比最大有75%。
分析的意义在于：
首先流式结构反映出的流动规律与实际正好吻合，具备良好的解释性。大部分快递员只在自己区域内活动，涉及到的路线不多（左侧75%的路径人数都较少），但位于长尾处的几条路线是需要重点关注的快递员主干线。
其次，热力最高的5%的路线（长尾部分）的交通顺畅度，会影响到整体快递员的派送能效，我们在做路径规划、或者路况越策等决策时，更需要重点关注这些道路，提升它们所带来的效果要远大于其他路线。
最后，我们可以在2.5小时内对全国所有地区生成一张这样的属于它自己的热力画像图，使得每个地区精准快速决策成为可能。
四、总结
通过交通工程 + 运筹规划模型的交叉方式，我们实现了海量数据下的流式结构路网匹配，实时展现了城市中所有快递员派送路径的流式结构及其热力分布，帮助决策者清晰、完整地掌握全局路径概况。基于这种概况，可以延伸出轨迹预测、柜机网再规划等一系列决策，拓展了企业在理性决策上的多样性和深度。
五、后记
到这里，我们就完成了【优化算法为理性决策赋能系列】的介绍，相信大家对运筹模型在企业理性决策中的作用也有了更深刻的了解。我们的工作内容，理性但不冰冷，前沿但仍接地气。拥抱现代科技是企业发展的趋势，我们愿意用所学为业界贡献一份力量。
