一种基于Geohash方法和地图路线规划的行程匹配算法

钟克华，游东宝，苏炳辉

（广州汽车集团股份有限公司汽车工程研究院，广东 广州 511434)

1 前言

合乘的行程匹配问题是合乘路径选择的基础，在合乘双方出发地和目的地明确的情况下，通过枚举可行的出行规划路线，计算并找出这些可行的规划路线一定范围内（如路线周围2 km）的可能行程。如何提高行程匹配效率，是行程匹配研究的难点之一。目前国内外对合乘的研究在合乘基本理论，如合乘的发展状况和趋势、组织模式等方面比较成熟，在出租客车方面有应用方案应用于车辆调度。李新胜［1］提出了一种基于网络地图API的拼车系统路线发布及匹配算法。康帆［2］提出了一种利用出发时间和欧氏PickUp距离进行匹配的方法及系统，可以实现时间满足要求，并选择短距离的路线。李春风［3］先规划车主行车路线，然后采用Geohash的方式，获得该行车路线经过的网格的标识，再将乘客的起始点的网格标识与之进行匹配。该方法可以查找匹配行程，但是其对行程方向的判断效果不佳。以上几种方法以能够进行路线匹配或者以找出最优路线为目标进行设计，是在行程所涉及的地域面上查找可能同行的行程路线，存在因需要搜索的面太宽导致效率低下的问题。

为提高行程匹配效率，本文提出了一种行程匹配算法。本算法采用Geohash方法，将二维经纬度数据表示的地图点（latitude，longitude）线性化，转换成一维的字符串数据，用于查找和搜索。字符串越长，表示的范围越精确；字符串相似的表示距离相近。利用字符串的前缀匹配来查询附近点对应的信息，把二维查找转换为一维查找降低了匹配计算的复杂度。本算法通过采用行程线路匹配带的方式，缩小查找范围，进而提高查找速度和匹配效率。在考虑时间、空间、人数、交通规定等多因素后，在给定行程路线规划的基础上查找出与该路线匹配的行程，呈现给合乘双方供其选择。

2 行程匹配算法

1）输入 依据给出的出发地、目的地用导航的路径规划功能获取从出发地到达目的地可行的路线，作为算法输入。如图1所示待匹配行程起点、终点，可行规划路线和可能的匹配行程起点、终点的关系。

2）区域划分 选取1）中的一条规划路线，用Geohash方法采用编码长度为5精度为2.4 km把线路所经过的区域划分为线路顺路带并进行编码，对顺路带区域划分方格并做出有序标记，区域划分如图2所示。

3）匹配行程点查找 搜索可能匹配行程的出发地和目的地Geohash字符串，如匹配行程的出发地与目的地均落在2）中所计算出的顺路带范围内，则行程匹配；反之，行程不匹配。如图3所示，图中以C、D、E、F为出发地和目的地的行程是可匹配的，而以A、B为出发地或目的地的行程是不匹配的。

4）匹配行程方向筛选 在3）选取的可能匹配行程中，筛选出行程方向与原有行程方向一致的匹配行程。

图1 可能的匹配行程规划路线示意图

图2 行程顺路带划分示意图

图3 行程匹配关系示意图

行程方向是否一致的判定方法是：按序扫描2）中做过有序标记的顺路带区域，如果行程起点、终点出现的顺序与原有行程起点终点出现顺序一致，则认为匹配行程的方向一致；反之，则认为匹配行程方向与原有行程方向相反。

5）匹配度计算 对4）中的匹配行程，按其与原有行程出发点距离、目的地距离和出发时间相近程度计算匹配度，并进行排序。

3 算法使用方法

3.1 步骤

1）接收外部输入的行程参数，含出发地、目的地、出发时间、需要座位数 （乘客行程）、提供座位数 （车主行程）。

2）用导航的路径规划功能获取从出发地到达目的地可行的路线。

3）对第2步所获得的可能路径，选取一个路线执行第4步开始的行程匹配计算；如计算完毕，转第13步。

4）用Geohash算法计算第3步选取的行程路线的顺路带，划分方格并做标记。

5）判断行程是车主行程还是乘客行程；如是车主行程，转向第6步，如是乘客行程，转向第9步。

6）根据经纬度查找出发地与目的地均在车主行程路线顺路带范围内乘客行程。

7）判断第6步找到的乘客行程方向，选出与车主行程方向一致的乘客行程。

8）选出出发时间、座位数满足需求的乘客行程；转向第12步。

9）根据经纬度查找出发地与目的地均在乘客行程顺路带范围内车主行程。

10）判断第9步找到的车主行程方向，选出与乘客行程方向一致的车主行程。

11）选出出发时间、座位数满足需求的车主行程。

12）根据出发地距离、目的地距离、出发时间相近程度计算匹配度，依据匹配度对满足条件的行程进行排序；转向第3步进入下一个迭代循环。

13）返回排好序的匹配行程列表给使用者。

3.2 流程图

算法应用流程图见图4。

4 应用

算法应用时，需要处理以下几个问题。

1）路线规划时需要选取：高速优先、不走高速、路程最短、时间最少、费用最省等各种模式，以提供各模式下的行程线路。然后，对这些模式下的规划路线，作为匹配算法的输入，迭代计算路线顺路带，查找其匹配行程。

2）Geohash编码长度：当长度为6精度为610 m，当长度为7时，精度在76 m。实际使用时编码长度需要根据数据情况进行选择，在城市城区选取编码长度6，在郊区可以选取5。

3）在目标点选取计算过程中，因Geohash算法的区域划分和填充曲线，会产生边界问题和突变问题。

边界问题的解决办法：在查询时，除了使用定位点的Geohash编码进行匹配外，还使用周围8个区域的Geohash编码。

突变问题的解决办法：在查询附近点的时候，首先筛选Geohash编码相似的点，然后进行实际距离计算以确定点的选取。

5 总结

1）建立了利用字符串匹配来查找匹配行程的机制，采用Geohash方法将二维的经纬度转换成字符，利用字符串匹配来查找匹配行程。将二维地图点的匹配问题简化成一维字符串匹配问题，降低了计算复杂度。

2）设计了行程路线顺路匹配带，利用Geohash方法在行程路线一定范围内设计行程路线顺路匹配带。

3）提出了行程匹配度，用于标识行程的匹配程度。匹配度计算综合考虑了出行时间、出发地点距离、目标地点距离等多种因素。