基于网格化的出租车空载寻客路径推荐

高 瞻 余 辰 向郑涛 陈宇峰*

1(湖北汽车工业学院电气与信息工程学院 湖北 十堰 442002)2(华中科技大学计算机科学与技术学院 湖北 武汉 430074)

0 引 言

现代化城市建设日新月异，人们交通出行方式更加多样化，为方便人们随时快速地到达任意目的地，打车服务显得尤为重要，出租车作为出现较早且保存至今的交通出行工具，在城市交通中扮演着十分重要的角色。目前的出租车由于区域供需比不平衡、调度不合理、载客路径规划不智能也造成了较多的社会问题，如：市民打车难、空载出租车司机寻客难等，这些问题直接导致了大量乘客的打车需求得不到满足，出租车司机载客效率低挣不到钱，以及由于出租车空载巡游造成的资源浪费和环境污染等。

针对这些问题，学者们已经做了大量的研究，如袁晶等[1-2]通过北京出租车GPS轨迹数据分析学习乘客的移动模式和出租车司机搭客卸客的行为，以利益最大化、路线最快、最高概率载客、最短等待队列多种路径推荐方式，设计出租车推荐系统，推荐最佳等待地点搭载乘客；以最大可能发现空闲车辆和最小平均等待时间两种top-k的策略，设计乘客推荐系统，为乘客推荐步行距离区域最近的停车点。唐炉亮等[3]提出了出租车上下客时空分布的线密度探测模型，获取城市出租车上下客的时空分布规律，理解和认知了城市空间的动态性。文献[4]从大量复杂的出租车GPS轨迹数据中，搜素和挖掘有效信息，设计打车推荐系统(Taxi-RS)，通过该系统可以提供给乘客一个特定的搭乘地点以及搭乘的概率和等待时间。文献[5]引入出租车驾驶经验作为关键因素分析，设计位置到位置图模型(OFF-ON Model)分析乘客下车位置与下一个乘客上车位置之间的关系，为出租车推荐更有利的巡航位置。文献[6]针对出租车拼车服务，采用区域划分，将区域作为旅程的标识，找出可能去往乘客目的地的出租车，将具有最小绕远时间比例的车辆推荐给用户，减少了行驶里程和时间花费。

出租车推荐系统相关的文献中，以相似的目标主要考虑的因素包含：当前位置与推荐位置之间的距离、等待下一位乘客的时间、乘客上下车位置关系、预期的行程费用等。本文在前人相关研究的基础上，综合考虑了城市地理特点、打车订单分布等因素计算载客核心点，基于空载出租车在驶向载客核心点途中载客概率最大化问题，研究空载出租车寻客路径推荐，使出租车在较短的寻客距离内最大概率地搭载到乘客。首先，对相关研究进行分析，提出本文需要解决的问题。然后，针对问题进行建模，根据网约车的订单数据分布特点提出了基于环形切割的聚类算法，以及基于网格化的出租车曼哈顿路径模型。最后，通过实验对本文提出的方法进行验证与分析。

1 问题分析

目前我国许多城市因为地理特点、环城公路、工业生产、人口分布等因素以“环”进行区域划分，例如目前北京被划分为六个环，成都被划分为五个环。容易发现，位于同一环形区域内，不同方位的人口密度、交通状况等特征具有较大的相似性，而不同环之间则存在明显的差异，即呈现出环内相似、环间不同的特点。这直接影响了城市居民的分布情况，进而使打车需求量也呈现相似特点。同时，随着现代化城市建设的发展，城市交通道路变得交错纵横，呈现出“网”状结构，车辆去往同一目的地的路径出现了更多的选择，这使得通过网格化来研究出租车路径具有了现实意义。

本文数据集来源于滴滴出行“盖亚”数据开放计划[7]，数据集包含成都市2016年11月的滴滴网约车订单数据约620万条、轨迹数据约10亿条。本文主要对其中的OD(Origin-Destination)数据进行研究，数据信息如表1所示。

表1 网约车订单信息表

基于网约车、出租车轨迹数据或OD数据相关的研究已经较为丰富了，部分学者致力于轨迹数据或OD数据聚类算法或路径规划算法的优化[8-12]，也有许多学者着重于出租车调度与资源利用最大化问题[13-14]。学者们通过不同的角度来考虑出租车路径的推荐，其中最简单、常见的方法是基于最短距离或最节省时间的路径规划方法。载客核心点的计算和推荐方面，大多数的研究没有考虑载客核心点与区域面积、乘客订单数量的关系；载客路径推荐方面，更多地考虑了不同策略的路径规划算法，针对空载出租车驶向载客核心点的过程中实现载客概率最大化问题研究的相对较少。本文将从上述2个方面展开研究，综合考虑相关因素对空载出租车载客路径推荐方法进行改进。

本文以小时为时间粒度研究出租车订单数据的分布和迁移。选取任意1小时的OD数据，利用百度Echarts组件提供的heatmap类型的数据可视化接口，读取数据起点经纬度(on_lon、on_lat)绘制热力图，如图1所示。从图中发现越靠近城市内环区域的网约车订单越密集，外环则反之，打车需求量与地理分布有密切联系。针对城市道路“环”形区域划分、“网”状道路特点，本文将对OD数据进行环形切分，充分考虑每个环形区域订单数量和区域面积因素合理计算每个区域载客核心点的数量，使聚类结果更为合理、分布更加均匀，以保证出租车从任意位置驶向最近的载客核心点的平均空载行驶距离较短。对OD数据进行网格化处理，将具有较短路径且拥有最大乘客数量的一条路径推荐给出租车司机，实现出租车空载驶向载客核心点的途中载客概率最大化，避免行驶途中经过的小区域乘客被忽视。

图1 成都市OD数据热力图

为实现上述目标，下面两个问题将在后面着重探讨：

• 对于环形切分后的区域，如何合理地建立区域面积、区域订单数量与载客核心点数量关系，计算每个区域的聚类数量。

• 如何进行网格化并找到空载行驶途中载客概率最大的路径。

2 系统建模

2.1 基于环形切分的聚类方法

载客核心点是乘客数量比较密集的区域中心点，一般位于火车站、汽车站、大型商场、公司、学校、娱乐场所等附近，出租车司机比较容易载到乘客或在非打车高峰时段停车等候乘客。因此，在做出租车空载路径推荐之前，需要先利用聚类算法找到载客核心点作为出租车空载寻客的目标点。

通过分析成都市出租车订单分布情况可以发现以下特征：环中心区域属于市中心地段，是人们活动的核心区域，打车需求非常大，但随着环半径的增加订单数量呈现递减趋势；相同环内，不同区域的订单数量分布比较相似；随着环半径的增加，环内区域面积不断扩大，交通状况会更加通畅，使出租车相比于市中心的拥堵地段相同时间内行车距离更大、油耗更少，允许出租车有更长的空载寻客里程。基于此，笔者提出环形切分的聚类方法计算载客核心点。

根据成都市环状地理特点，环形切分如图2所示。对于每个环状区域，利用历史订单数据选择合适的聚类算法找出载客核心点。轨迹数据挖掘的聚类方法包含：划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法等。聚类算法的选择不是本文研究的重点，为了高效地处理大量的历史订单数据，同时将区域面积和打车需求量与聚类数量建立联系，本文选用较为高效且可以灵活设置聚类数量的经典划分聚类算法K-means。

图2 环形切分示意图

订单数据的数量和分布直接影响载客核心点的数量和分布情况，因此，笔者首先假设相邻两个环形区域之间载客核心点的数量与其对应区域内的订单数量成正比，即：订单数量越大的环形区域内的载客核心点数量越多。通常，市区中心区域订单数量十分密集而边缘区域的订单数据相对较少，为了避免城市中心区域核心点数量过多，而外环区域的载客核心点数量过于稀少，笔者引入区域面积作为影响载客核心点数量的另一个关键因素，并认为相邻两个环形区域之间载客核心点的数量与其对应区域面积也成正比关系。根据上述观点，为了简化模型和计算，本文将聚类数量、订单数据、区域面积3者之间的关系模型设计如下(参数说明见表2)：

(1)

为避免较大的资源消耗，城市区域出租车平均空载寻客距离通常应该在3公里以内，市中心地段由于打车需求量比较大，平均空载寻客距离应小于1公里。为了计算出每个环形区域的聚类数量，首先需要计算整个区域总的载客核心点数量以及第一个环形区域的载客核心点数量C1。因此，文中分为2种情况计算，当单独考虑市中心区域，即最内环时，出租车平均寻客半径为1 km，那么在半径为1 km的圆域内至少存在一个载客核心点，则可由式(2)计算出C1(计算结果向下取整)；当考虑整个城市区域时，空载出租车的平均寻客半径不超过3 km，那么在半径为3 km的圆域内至少存在一个载客核心点，则可由式(3)得到市区总的载客核心点数量。

(2)

(3)

2.2 出租车空载寻客曼哈顿路径模型

文献[15]为研究路由算法给出了曼哈顿路径的定义，本文类似地给出出租车空载寻客曼哈顿路径的定义如下：

定义1如果两个经纬度位置点之间的一条路径，它从起点到终点仅仅使用两个方向并且这两个方向为非相反方向，那么这条路径就被称作出租车空载寻客曼哈顿路径，文中简称曼哈顿路径。

针对出租车路径推荐的建模方式很多，如：基于最短距离的模型[16]、基于节省成本的模型[17]、基于出租车经验的模型[18]等。相比这些模型，本文提出的曼哈顿路径模型侧重于出租车空载行驶路径上的载客概率问题，通过曼哈顿路径算法让出租车在相对较短的空载寻客里程前提下，驶向载客核心点的途中拥有最大的概率搭载到乘客。

城市交通道路错综复杂，呈现出如图3所示的网状结构，使得我们可以在实际道路中找到许多与曼哈顿路径匹配或相似的路径。因此，在解决空载出租车路径推荐时，通过网格化方法研究出租车空载巡游曼哈顿路径有了现实意义，尤其是利用网约车收集的数据做路径推荐时，由于大部分实际打车订单数据的起点位置是在马路边上，故依据订单起止点数据推荐出的曼哈顿路径与实际道路有较高的匹配度。

图3 成都市城市道路图

首先，通过2.1节所述算法计算出载客核心点作为空载出租车行驶的目标点。然后，利用通过高斯投影算法[16]将经纬度转化为平面直角坐标系，并以长度100 m进行网格化处理，根据对应的历史数据计算网格内的订单数量作为当前时刻该区域打车需求的预测值。最后，将各网格中心点作为行驶路线的中间节点，在所有曼哈顿路径中检索出拥有最大载客概率的行驶路线作为最终的推荐路径。

(a) 曼哈顿路径(b) B绕A坐标旋转到B*图4 曼哈顿路径图

3 推荐系统实现

OD数据具有较强的时空属性，因此在进行路径推荐之前，需要对时间和空间两个属性进行相关预处理工作。针对空间属性，主要的预处理工作是对环形划分半径Ri进行初始化，Ri是环形模型的重要参数，在系统建模时根据城市地理的环形半径进行设定，系统运行后将保持不变。针对时间属性，系统选取的时间粒度为1小时，即通过历史数据中相同时段的数据作为当前时段的订单需求量进行计算。首先，根据该时刻对应的订单数据进行一次环形聚类，并存储计算出的载客核心点数量及位置分布；其次，对地图进行网格化处理工作，统计并存储该时刻每个网格中的订单数量。

以上预处理工作完成以后，当出租车用户实时请求路径推荐时，获取出租车当前位置的经纬度输入系统，利用如图5所示路径推荐算法进行计算。根据车辆经纬度，首先计算出具有最短距离的载客核心点作为出租车空载行驶目标点；然后计算车辆所在的网格中心点与目标点所在网格中心点形成的直线与坐标轴的夹角，如果不是45°，则以车辆所在的网格为中心进行旋转；最后，通过递归算法遍历出租车与目标点之间小区域内的所有的曼哈顿路径，找到订单数据量最大的路径推荐给出租车司机，以实现空载出租车最大概率的载到乘客。

图5 路径推荐算法流程图

如图6所示，在下午3点半左右的时候，随机选取一个经纬度点模拟出租车当前位置坐标，系统自动选取历史数据中下午3点到4点之间的订单数据作为当前该区域的打车需求量进行计算，匹配出距离最近的载客核心点作为该出租车空载行驶的终点。经过网格化处理后，系统自动生成如式(4)所示的矩阵A，i和j表示网格坐标，a[i][j]表示网格中订单的数量，其中车辆位置为a[0][0]，核心点位置为a[n-1][n-1]，起点与终点之间的曼哈顿路径所经过的网格数为2n-1，本实例中n=12，由于网格边长设置为100 m，那么起点与终点相距2.3 km左右，通过组合数计算知道，该网格中总共存在705 432条曼哈顿路径。

图6 用户路径推荐结果

(4)

通过递归算法计算所有曼哈顿路径及路径上的订单总数量，输出订单数量最多的路径，可以得到如下3条等价的最优路径：

O→a1,0→a2,0→a3,0→a4,0→a4,1→a5,1→a5,2→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

O→a1,0→a2,0→a3,0→a4,0→a4,1→a5,1→a6,1→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

O→a1,0→a2,0→a3,0→a4,0→a4,1→a4,2→a5,2→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

系统随机选取其中一条作为最终的推荐路径，通过APICloud设计手机端系统，Android手机运行后的显示效果如图6所示。从图中可以发现，由于网格化处理后产生的曼哈顿路径只有两个方向，因此推荐的路径与地图中实际道路存在偏差。实际上，通过本算法推荐给空载出租车司机的是一条具有最优载客行驶方向的路径。

4 实验及结果分析

4.1 环形区域聚类算法结果分析

本文以滴滴网约车订单数据为基础进行试验与分析，通过Python语言进行计算和绘图，结合百度ECharts可视化展示。初始化环形切分半径Ri，统计每个环形区域内网约车订单数量，同时计算各环形区域面积，当i=0时，R0=0，故N0、S0均为0，结合式(1)-式(3)可以得到本文中基于环形切分后每个环内的聚类数量。实验数据计算结果如表3所示。

表3 相关实验数据

在订单数据和聚类总数相同的情况下，利用本文所述算法与直接聚类算法进行比较，绘制可视化散点图如图7所示。其中，小圆点代表订单，以不同的灰度代表经过环形切分后的环形区域，黑色矩形点代表直接聚类算法计算的核心点位置，黑色三角形点代表经过环形切分的聚类核心点位置。

图7 环形切分聚类与直接聚类对比

从图中可以发现，在总的聚类数量相同的情况下，环形区域O1中矩形点数量和三角形点数量分别为11和6，而O2中对应的数量分别为21和9，表明本文提出的基于环形切分的聚类算法与不进行任何数据处理直接采用K-means聚类算法相比，有效阻止了大量载客核心点朝着订单数量比较密集的城市中心区域分布，较大程度地避免了过多的出租车向城市中心地段聚集，而城市边缘区域出租车数量严重不足的现象。同时可以看到三角形点的分布较矩形点更为均匀，这将有效避免出租车空载巡游距离过长的现象。

4.2 路径推荐算法结果分析

基于网格化的曼哈顿路径算法，核心思想是保证最短网格距离的前提下寻找一条载客概率最大的路径推荐给出租车司机。因此实验中，用载客概率作为衡量指标，将文中所述推荐算法与经典的基于最短距离的路径规划算法进行比较分析。

载客概率定义为一条路径所经过的网格内的订单数量之和与该路径起止点之间矩形区域订单总数之比作为该路径的载客概率，∑r[p][k]表示一条路径所经过的网格的订单数量，则一条路径上的载客概率P表示如下：

(5)

试验中，随机选取一点作为出租车当前位置，系统自动匹配对应的载客核心点作为出租车空载寻客的目标点。利用基于最短距离的路径规划算法和本文所述算法的路径经纬度序列经过高斯坐标变换后绘制曲线如图8所示。图8(a)中是比较特殊的情况，最短路径和推荐的曼哈顿路径的载客概率均为40.1%，两条曲线的特征匹配性很高，由于文中算法推荐的路径与实际地图存在偏差，故此时两条曲线在实际地图上为同一条路径。图8(b)中是更一般的情况，即两条路径完全不相同时，最短路径的载客概率为40.9%，推荐的曼哈顿路径的载客概率为53.0%，此时文中算法推荐的路径相比于最短距离路径载客概率提高了12.1%。

(a)

(b)图8 路径推荐结果对比

通过实验可知，在保证相同网格距离的情况下，即排除实际路径规划可能存在的绕远距离时，文中提出的算法载客概率不低于经典的基于最短距离的路径规划算法。实际上，文中提出的算法在一个网格区域内找到最大载客概率的路径推荐给出租车司机，是以牺牲一定的空间效率来达到提升空载出租车载客概率的目的，但从空载出租车用户体验和应用效果考虑是值得的。

5 结 语

根据网约车订单数据在环形城市区域中呈现出环内相似、环间不同的数据分布特点，采用环形划分，建立载客核心点数量与区域面积、订单数量的关系模型，合理计算出各个环内的聚类数量，使得载客核心点分布相对均匀，不仅保证在核心点区域有较大数量的打车人数，也有效减少了出租车到载客核心点的平均空载距离。提出了网格化的出租车空载寻客曼哈顿路径模型，通过坐标变换使出租车与载客核心点之间始终具有饱和数量的候选曼哈顿路径，基于递归遍历算法找出载客概率最大的一条曼哈顿路径推荐给空载的出租车用户。实验表明，相同条件下，通过文中提出的算法推荐的路径载客概率不低于经典的基于最短距离的路径规划算法获得的路径。本文提出的方法为出租车空载寻客路径推荐系统的研究提供了思路。

本文仍需要进一步深入研究。首先，在数据的时间属性方面，目前采用订单数据的时间粒度为1小时，需要在未来工作中进一步分析时间粒度对路径推荐效果的影响。再者，目前系统实现的是基于网格化处理后推荐的一条具有最优载客行驶方向的路径，因此推荐的结果与真实地图路径存在偏差，未来将采用相关机器学习方法将经纬度序列与实际路径进行匹配。最后，由于文中使用的数据集是成都市网约车数据，该城市网约车OD数据具有典型的环形分布特点，故文中只针对具有环形分布的情况展开研究，后期若获取到比较合适的其他省的数据，也会对非环形分布特点的城市进行建模分析。