基于K近邻查询的出租车供应量评估方法

覃文杰

摘 要：随着滴滴、Uber等打车软件的兴起，对于出租车供应量的评估需求也越来越大。出租车的供应量评估综合是考虑不同地区的可用出租车数量和出租车需求，得到整体出租车供应量的分布作为车辆调度的依据，达到提高服务质量的目的。本文定义了出租车/乘客密度的计算公式以及供应量的计算公式，并将它们应用在上海市的路网数据和真实出租车轨迹数据集上，分别求得各个区域可用出租车的密度和乘客的密度，然后得出上海市整体的出租车供应量情况。实验证明了该方法的有效性。

关键词： 路网； 出租车； K近邻查询； 评估方法； 大数据

中图分类号：TP931 文献标识码：A 文章编号：1009-3044（2018）07-0231-03

Abstract： The demand of taxi supply evaluation increases with the rapid development of location based services like Uber. For the purpose of increasing service quality， taxi supply evaluation should take the amount of taxi available and the needs of the passengers both into account， and calculate the distribution of taxi supply as the basis of vehicle scheduling. In this paper， the density formula of taxis/passengers and supply evaluation formula are proposed. We apply these formulas to the road networks of Shanghai and the real track of taxi datasets， and prove the effectiveness of our method by experiment.

Key words： road networks； taxi； k nearest neighbor query； evaluation； big data

1 引言

近年来滴滴、Uber等新兴交通方式发展迅猛，在人们的日常生活中扮演着越来越重要的角色，如何调度路网上大量出租车则成为了影响整体服务质量的一个关键点。要评估一个区域出租车的供应量首先要考虑该区域内空闲出租车的数量以及潜在乘客的数量，可用的方法包括基于欧式距离的K近邻查询或者基于路网距离的K近邻查询等，接着以此计算出出租车和乘客的密度，最终计算出出租车供应量的区域分布。后文提供了使用K近邻查询结果计算出租车或乘客密度的公式，以及使用两个密度计算出租车供应量的公式，并通过实验验证了评估的效果。

2 供应量评估方法

2.1 密度计算公式

密度反映的是移动目标在查询点周边的分布情况，假设查询点X在某一时刻kNN的查询结果为[cj1，cj2，…，cjk]， 每一个查询结果对应路网距离的列表为[disj1，disj2，…，disjk]，那么定义查询点在当前时刻的密度为DK=k = k / 。

2.2 供应量计算公式

假设查询点X在当前时刻周围空闲出租车的密度为Dcar， 潜在乘客的密度为Dpassenger，那么定义查询点X当前时刻的出租车供应量为F（k）=Dcar - Dpassenger = k×（ 1 / - 1 /）。其中disjk为第k辆可用出租车的距离，disik为第k个潜在乘客的距离。

2.3 实验

对于每一个不同的K值，我们都可以计算出一个不一样的供应量分布。我们可以根据实际的调度需求来调整K值的选择，如选择供应量方差最大的K值以使得整体供应量的差异最大。后文实验选择K为275得到以下结果。

2.3.1 出租车密度

上图为上海市晚高峰时段出租车的密度分布，可以看出上海市中心沿黄浦江区域的可用出租车分布较为密集，而其余区域可用出租车分布较少。

2.3.2 乘客密度

以乘客的需求为负值，计算得上海市晚高峰乘客密度分布如图2。由图可知，晚高峰时段上海市乘客需求最大的区域仍以市中心为主，但深颜色区域较之图1要更大，因此乘客的区域分布更广。

2.3.3 供应量分布

根据我们2.2节的公式可以计算得出上海市晚高峰时段出租车的供应量分布如图3.可以明显看出上海市中心区域颜色整体偏蓝，属于供不应求区域，而外围颜色鲜亮，属于供过于求区域。此时可以考虑将周边区域的出租车调往市中心区域以缓解整体的乘车压力。

3 结论与展望

本文用K近邻查询结果定义了出租车和乘客的密度计算公式，以及出租车供应量计算公式。并通过实验验证了该评估公式在上海市路网和出租车轨迹数据集上可以直观地看出出租车供应量的分布情况，从而为系统管理员调度出租车辆提供依据。待完善之处包括：1） 评估的效果根据检查点在地图上分布的疏密差别很大，如果检查点数量较少，那么只能得到较为初略的评估结果，如果查询点数量较大，则会带来较大计算量，因此在查询算法上可以据此做出相应优化以适应大量查询点同时查询；2）依据不同的K值可以得到不同的评估结果，因此选择一个合适的K值非常重要，后续可以根据不同的评估需求，比较不同K值得评估结果，以此选择一个最优的K值。

參考文献：

[1] Papadias D， Zhang J， Mamoulis N， et al. Query processing in spatial network databases[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment， 2003： 802-813.

[2] Samet H， Sankaranarayanan J， Alborzi H. Scalable network distance browsing in spatial databases[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM， 2008： 43-54.

[3] Lee K C K， Lee W C， Zheng B. Fast object search on road networks[C]//Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology. ACM， 2009： 1018-1029.

[4] Huang W， Li G， Tan K L， et al. Efficient safe-region construction for moving top-k spatial keyword queries[C]//Proceedings of the 21st ACM international conference on Information and knowledge management. ACM， 2012： 932-941.

[5] Zhong R， Li G， Tan K L， et al. G-tree： An efficient index for knn search on road networks[C]//Proceedings of the 22nd ACM international conference on Information & Knowledge Management. ACM， 2013： 39-48.

[6] Zhong R， Li G， Tan K L， et al. G-tree： An efficient and scalable index for spatial search on road networks[J]. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（8）： 2175-2189.

[7] Pfoser D， Jensen C S， Theodoridis Y. Novel approaches to the indexing of moving object trajectories[C]//VLDB. 2000： 395-406.

[8] ?altenis S， Jensen C S， Leutenegger S T， et al. Indexing the positions of continuously moving objects[M]. ACM， 2000.

[9] Jensen C S， Lin D， Ooi B C. Query and update efficient B+-tree based indexing of moving objects[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment， 2004： 768-779.

[10] Hu H， Xu J， Lee D L. A generic framework for monitoring continuous spatial queries over moving objects[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM， 2005： 479-490.