Geohash编码在出租车巡游路线推荐中的应用*

栾方军 张鹏旭 曹科研

（沈阳建筑大学信息与控制工程学院 沈阳 110168）

1 引言

城市道路拥堵目前已经成为城市道路交通问题中最突出的问题。交通拥堵一方面影响着人民群众的身心健康，另一方面造成了更大的城市交通压力。如何提高传统交通工具的运行效率成为了新的研究内容。由于出租车在城市居民的日常生活中发挥着重要作用，与其他公共交通工具如公交车或地铁相比，出租车的运行路线具有随机性和不确定性，通常不会遵循固定的路线寻找乘客。多数出租车司机在街道上漫无目的地寻找乘客，这种无目的寻找不仅浪费了出租车司机的油耗和时间，而且增加了城市出租车的空载率，降低了公共交通运行效率的同时，进一步加剧了城市交通压力。为了加快智慧城市的发展，对空闲出租车司机推荐一个巡游路线显得尤为重要。

基于这一研究思路，本文设计了一种新颖的出租车巡游路线推荐模型。图1概述了本文推荐模型的整体流程：利用8位Geohash编码覆盖所在城市的路网，并将其写入Neo4J图数据库中，GRU神经网络根据出租车历史数据预测出每个8位Geohash网格内每小时的乘客数量，并把该数据更新到Neo4j中对应的路段中。当该路段所有Geohash区域更新完后，得到的累加数量即是该路段预测后的总乘客数量。结合出租车当前所处的时间段及其GPS信息，每当出租车行驶到一个路段的终点之前，经过推荐系统计算出以该路段终点为起点的单位距离乘客数量更多的路段推荐给出租车司机，直至出租车接到乘客，结束推荐。

图1 推荐模型的整体流程

2 相关工作

2.1 出租车寻客推荐

现今技术主要采用热区域推荐和热路线推荐，来实现出租车巡游接客效率的提高。

热区域推荐［1～5］是指推荐一个包含很多乘客的区域，基于乘客需求量并结合司机当前位置构建，对其进行推荐可以一定程度上提高搭载成功率。存在的问题是只有目的地具有较高的接客概率，但出租车司机到达该目的地的路线是随机的，并没有对司机到达热区域范围的路线进行进一步优化，在行驶在该路线过程中很可能错失路边订单。

热路线推荐［6～10］：相对于热区域推荐，热路线推荐更加完整。如Lai［6］提出了城市交通库仑定律的概念，对城市出租车和乘客之间的关系进行建模，并提出了一种路线推荐方案。出租车和乘客被视为正电荷和负电荷。Meng［7］设计了一个净利润目标函数，以评估行驶路线的潜在利润，为出租车司机开发了具有成本效益的推荐系统。本文属于热路线推荐的范畴。

2.2 神经网络

长短期记忆（LSTM）网络［11］是RNN的变体，是为了解决梯度消失和梯度爆炸而产生的。LSTM和普通RNN相比多出了三个控制器（输入控制，输出控制，忘记控制）。GRU是Cho［12］等于2014年提出的一种优化了LSTM结构的变体。GRU神经网络不引入额外的记忆单元，将LSTM的输入控制和忘记控制合并为了一个更新门，具有更加精简的特性。综上所述本文使用GRU神经网络进行预测。

2.3 Geohash编码

Geohash是Gustavo Niemeyer和GM Morton于2008年发明的公共领域地理编码系统。Geohash将地理位置编码转换为由字母和数字组成的短字符串。Geohash基本原理是分别将经纬度进行二等分编码，按照其所属区域进行连续编码，再将两组编码混合进行Base32编码，最后生成需要的Geohash编码。其具有分层的空间数据结构，可将空间利用Z曲线填充细分为任意精度属性的网格状［13］。Geohash编码在地理位置方面还有更丰富的应用，Jin用Geohash以字符串形式对商店的位置进行编码，将其视为POI嵌入模型的上下文［18］。Wang利用Geohash编码提出了一种数据结构的并行网格合并和过滤算法可以提取海道边界信息［19］。Liu采用Geohash方法为分布式存储器建立分布式空间索引［20］。但目前还没有相关文献把Geohash编码应用在出租车巡游路线推荐中。

3 构建路网与神经网络预测

3.1 图数据库构建路网

图数据库起源于欧拉理论和图理论，也可称为基于图的数据库，是NoSQL按照数据模型分类的一种。Baas［15］已经在图数据库和关系数据库中使用相同的OSM数据创建了一个测试环境，证明了在最短路径分析或连接性查询中基于图的数据库是最有益的。由于城市路网的数据规模非常庞大并且多为半结构化数据，故本文将路网建模为图2。在本文中使用的Neo4J 4.0是一种开源性的图数据库管理系统。其不仅支持完整的ACID规则可以清晰地表示半结构化数据，而且提供了REST API方便程序语言访问。Neo4J的特性符合城市路网建模的要求。

在路网地图中路线Route是一连续的路段集合，Route={s1，s2，s3···s k}在每个路线Route中路段si-1.end=si.start，每个路段si都有自己的开始路口Intersection_Begin和结束路口Intersection_End。每个路口是由经纬度和唯一的Intersection_ID所确定的，其中每个交叉路口是两条以上路线的交点。

图2 海口市部分路网地图

本文使用的地图数据来自于开放街道地图OpenStreetMap［16］，其地形数据被存储在后缀为OSM格式的文件中。OSM的原始数据由node，relation和key-value pairs组成。如海口市秀英区的OSM文件部分内容如下：

其中215566172是Route牡丹路的编号，由4个编号分别为2250274197，2249907634，2250360142，2250304358的路口节点组成。其中Intersectio_ID为2250274197的路口经纬度是110.2958684，20.0302589。OSM数据使用Python语言的py2neo和xml库解析后写入到Neo4J图数据库中。

当需要使用Neo4J时，使用一种叫做CQL的声明性模式匹配语言作为查询工具。如MATCH p=（）-［r：R_140582515］->（）RETURN p UNION ALL MATCH p=（）-［r：R_215560399］->（）RETURN p，即可查询出编号为215560399的世贸北路和编号为140582515茉莉路的路线，路段和路口等信息。同理根据图2的海口市部分路网地图可以查询出对应的Neo4J数据路网，如图3所示。

图3 使用Neo4j构建后的路网

3.2 Geohash网格与路网结合

为了能够准确预测需求，将城市划分为合适大小的区域是实现准确预测的前提。表1为不同Geohash编码长度对经纬度误差的影响。把Geohash的经纬度误差映射到地图上就是各种不同大小的网格。本文使用8位长度的Geohash编码，其映射到地图上面积相当于是一个361m2的网格。当出租车司机发起查询时，根据出租车的经纬度匹配到其对应的Geohash编码网格内。把历史数据的每个时间步长中各个网格内的出租车载客订单数和相关信息送入GRU神经网络中学习。

表1 Geohash编码长度对经纬度误差的影响

3.3 GRU神经网络预测

本文使用的历史数据为滴滴向学界开放的海口市出租车订单数据［17］，订单数据包括订单起止点坐标等信息。

数据范围：［19.536300，110.130600］，［20.128100，110.130600］，［19.536300，110.694100］，［20.128100，110.694100］

日期范围：

2017年5月1日至2017年10月31日

数据预处理：

1）清洗掉订单时间在日期范围外的，经纬度不在海口市的和乱码的数据。

2）对历史数据中出租车司机接客成功的位置其所在经纬度进行Geohash编码。

验证历史数据的充分性：

本文利用信息论中的互信息概念，互信息是变量间相互依赖性的量度，两个离散随机变量D和Z的互信息可以定义为I(D;Z)。

其中H(D)，H(Z)是边缘熵，H(D，Z)是D和Z的联合熵。

其中p(d i)=v i/∑i vi这里的v i是第i个Geohash网格单元中，出租车接到乘客订单的数量。

I(D;Z)描述的是随机变量D和Z之间重叠的部分，但没有描述出重叠部分占整个联合熵的比例。Studholme等［14］提出了归一化互信息NMI，将互信息放在［0，1］区间里。

本文的目标是找到可以基本完全描述D中大多数信息的数据量Z。图4为归一化互信息实验图，可以看出随着Z承载着更多的以天为单位的历史数据，归一化互信息N MI(D，Z)的值在147天后均大于0.98，说明前147天的数据足以描述98%的历史数据特征。

图4 归一化互信息实验图

本文将历史出租车数据转换为时间段是一天的数据序列，如图5显示了其中一个时间段一个路段的输入数据，该数据由两部分组成P t，i和Dt，i，其中P t，i代表t时间段内第i个路段其覆盖的Geohash网格中出租车载客次数的合集，这里(0

图5 一个时间段的输入数据序列

输出Y是预测出的该城市所有路段其覆盖的Geohash网格中待打车乘客数量的合集。

本文使用GRU神经网络预测。ht是隐藏层的输出，x t是输入，每个GRU单元通过下列式子计算得到隐藏层的输出：

其中z t是更新门，r t是重置门，͂ 是候选隐藏层，它是上一隐藏层输出结果h t-1的汇总。w是训练参数矩阵。tanh是双曲正切激活函数。σ使用Sigmoid作为激励函数能够控制重置门和更新门的取值范围。当更新门是1时，隐藏层的输出h t和历史状态等值，当更新门和重置门均是0时，隐藏层的输出仅和输入xt相关。当重置门为1时，候选隐藏层与历史状态h t-1和神经网络的输入x t有关当重置门是0时候，候选隐藏层与历史状态h t-1无关。

4 出租车巡游路线推荐

4.1 Neo4J数据库与GRU神经网络预测结合

每个路段si由n个8位Geohash网格包围着，经过GRU神经网络预测后的当前时间段该路段第j(1≤j≤n)个Geohash网格内的接单数量是geo-pi ckups j则该路段预测后的当前时间段接单总数是S i-pick u ps。

本文将GRU神经网络预测的每个Geohash网格内的乘客数量，匹配到对应的路段上计入Si-pick u ps总数更新到Neo4J中对应路段关系的pickups标签，如编号是R_2155661721的路段［Road：R_2155661721｛length：267，pickups：19｝］表示为该路段长度是267m，GRU神经网络预测的编号是R_2155661721的路段该时间段内一共有19名待打车乘客。

当每个推荐路段存在n(n≥1)辆预通过的空驶出租车时，则每个空出租车当前时间段遇到待打车乘客数量Ti-pi ckups为

算法1 出租车巡游路线推荐算法

Algorithm 1 Route Recommendations for Taxi DriversInput：Longitude and latitude of taxi

Output：Recommended Si

1：whileTaxi did not receive passengersdo

2： length=［］，pickups=［］，values=［］

3： lon，lat←Update latitude and longitude of the taxi

4： Intersection←Get the nearest intersection of taxi

5： length←Returns all length of road segments starting form this intersection

6： pickups←Returns all Ti-pickups of road segments starting from this intersection

7：fori in len（pickups）do

8： values.append（pickups［i］/length［i］

9：end for

10： return Recommended Si of the best values

11：end while

4.2 巡游路线推荐

表2是出租车巡游路线推荐算法的伪代码，当出租车司机开始使用巡游路线推荐系统时，算法会根据该出租车的GPS信息匹配到离其最近的一个路口Intersection_ID。以这个路口为起点，依次找到单位距离乘客数量最多的未行驶路段，累加推荐路段即为出租车巡游最优路线。直到出租车司机载客成功停止推荐。如图6为出租车推荐的一条巡游路线其中的两个路段，在出租车达到第一个路段的终点路口时如果还没有接到订单则继续推荐下一个路段。在推荐过程中可以实时显示空载出租车司机行驶过程中周边区域待打车乘客数量。

图6 本文方法推荐的一条巡游路线

5 实验结果分析及讨论

实验环境为操作系统WIN10专业版，Intel Core i7-8550U CPU，8GB内存，NVIDIA MX250独立显卡，480G SSD硬盘。

为了验证模型预测的准确性，本文使用均方误差（MSE）。MSE是一种常用的回归损失函数，是指参数估计值与参数真值之差平方的期望值；

从数学上来说，确定神经网络的参数是一个最优化问题。由3.3节中的互信息可知前147天的数据足以描述98%的历史数据特征，本文选择数据集中前150天的数据作为训练集，后30天的数据作为测试集。使用Keras中的序贯模型进行编程，构建两层GRU神经网络。其中，第一层GRU网络有64个神经元，第二层GRU网络有32个神经元，输出层设置为1。为了增加神经网络模型的非线性，减少梯度消失问题的同时加快训练速度，本文使用ReLU激活函数。为避免其产生过拟合的现象，将训练出来的模型Dropout数值设置为0.3。本文选用的损失函数是均方误差MSE，优化器选用adam，它可以使收敛速度更快的同时波动幅度更小。模型训练批次（batch）为64，迭代次数（epoch）为50次。如图7所示横坐标是迭代次数，纵坐标是loss，当迭代次数到50时，训练集和测试集的loss都趋于稳定。

图8是GRU神经网络预测效果图，横坐标是小时数，纵坐标是随机选取的Geohash编码为w7w3vym8的地图网格内的待打车乘客数量，其中图中虚线是真实值，实线是GRU的预测值，由于预测的后30天共720 h的数据放在图中过于紧凑，本文取了预测值和真实值的后200h生成实验图形。由式（11）得到训练集的MSE=0.027，测试集的MSE=0.032，可以看到预测结果是令人满意的。

图7 GRU神经网络的loss

图8 GRU预测效果

本文模拟实验将四个出租车于2017-6-1日上午9时以Geohash编码是w7w3vyp2的所在位置即从海口市茉莉路与滨海路的交叉口随机出发，三个出租车开始无目的巡游，分别用三条虚线表示，另外一个出租车按照本文的推荐方法巡游用实线表示。由图9可知，随着推荐巡游路线的引入，出租车遇到待打车乘客数量得到显著提升。图9中横坐标是出租车的行驶距离，单位是m，纵坐标是在此行驶过程中遇到的等待打车的乘客数量。由图可知在2km距离的巡游中，无目的巡游的出租车1在480m的地方遇到了1名乘客，出租车2共遇到了7名打车乘客，出租车3共遇到了8名乘客。使用本文方法的出租车遇到了20名乘客。由此可得使用本文的推荐巡游路线能够大幅度增加出租车遇到打车乘客次数，减少出租车空驶，进一步提高司机的利润。

图9 出租车行驶距离与遇到乘客的关系

6 结语

在城市交通系统中，出租车因其快捷方便的特性而广受乘客选择。如何向出租车司机推荐一个更优巡游路线，成为出租司机能否提高载客效率的关键环节。基于上述发现本文提出了一个直接在开源数据库系统Neo4j上使用CQL语句，实现针对大规模出租车路网与轨迹数据的高效范围查询，利用更长字符的Geohash编码具有更小误差网格的特点，实现了一种基于GeoHash编码的空闲出租车巡游路线推荐技术，并通过实验验证了该方法技术上的有效性。

在接下来的工作中，将通过两个方面着手进一步完善本文的方法：一方面获取更加充分的城市出租车数据，通过分析这些记录，来更好地感知乘客的出行影响因素。另一方面，充分考虑到城市道路的经常性修缮的问题，在当前工作的基础上引入触发器算法自动更新Neo4J上的路网属性，以便构建更具实时性，准确性的出租车路线推荐模型。