基于区域划分的出租车统一推荐算法

　　摘要：针对在极端天气或交通繁忙时乘客无法快速搭乘出租车到达目的地的问题，提出一种基于区域划分的出租车统一推荐算法，不仅提供普通打车服务，同时提供拼车服务。首先，将区域作为旅程标识，在旅程匹配方面化不可能为可能；其次，在拼车服务中算法将两对路线相近的乘客进行即时匹配，帮乘客拼车共乘；最后，选取绕远时间比例最小的出租车推荐给用户。使用包含14747辆出租车的全球定位系统（GPS）数据对算法进行评估，与CallCab系统相比虽然在减少的总里程数上下降了10%左右，但每次拼车平均只需要多花费6%的时间，且降低的送达乘客总里程数同样达到30%，不仅大幅度减少汽车尾气的排放，同时在用户更加关注的时间消耗方面表现更佳。
　　关键词：拼车；区域划分；全球定位系统数据；MapReduce；里程数
　　0引言
　　在大都市的日常生活中，出租车在所有的交通工具中扮演着一个重要的角色，例如在纽约，有超过100家公司经营着1.3万台出租车以满足每天66万多次出租车搭载请求[1-2]。然而在早晚高峰时间段，大量的乘客依旧无法快速搭乘空闲出租车。在高峰时段，乘客有时需要等待30min以上才可以搭乘空出租车离开[2]。本文提出基于区域划分的出租车统一推荐算法，包括空闲出租车服务和拼车服务，其中拼车服务可以大幅度缓解以上问题，同时降低了车辆的空驶率，司机在同一时间段内可以多载一位付费乘客，多获得一笔车费；另一方面，乘客的出行费用也会相应降低。
　　虽然拼车服务具有如此多的优点，但几乎所有的出租车推荐系统均集中于空闲出租车的推荐，没有真正在拼车领域进行相关探究[3-7]，即使存在对于拼车模式的研究，也无法完全满足大量实时用户的拼车请求[8]。并且与空闲出租车服务不同，提供拼车服务的出租车无法随意地将乘客送往其所要到达的任意目的地。在拼车服务中，乘客需要找到可搭乘的出租车，可搭乘的含义即出租车中已经存在的乘客的目的地与新乘客的目的地方向相似。一个目的地方向为南方的乘客不会认为一辆准备开往北方的出租车是其所愿意搭乘的出租车，因为若乘坐此出租车则意味着要多耗费大量的时间。
　　本文算法首先将全球定位系统（Global Positioning System， GPS）经纬度点对转化为区域，并通过MapReduce计算模型[9-12]获取以区域标识的旅程信息和特定时刻特定区域的通过时间；然后，以三种不同的标准筛选出相比于其他实时出租车更有可能去往乘客目的地方向的出租车；最后，相比距离，本文算法以乘客更加关注的时间为标准，计算实时出租车的绕远时间比例并推荐绕远时间比例最小的实时出租车给乘客；本文最后对算法进行了相关评测。
　　1研究背景
　　1.1设备信息
　　出租车实时GPS跟踪器会不断地发送GPS数据给后台，每一个GPS数据都由六部分组成，分别表示：车牌号、时间、经度、纬度、状态和速度。
　　如图1所示：在L1点、L2点状态值为0表示出租车没有搭载乘客；在L3点状态值从0变为1，认为出租车完成了一次搭载乘客动作；在L4点时状态值为1而在L5点时变为0，认为出租车完成一次旅程，乘客下车，出租车继续行驶[13]。
　　通过持续跟踪一辆出租车的GPS数据，再根据状态值的改变判定旅程的开始与结束，可以获得旅程的起点、终点以及中间地点。根据这种方法，推荐算法可以通过原始GPS数据获取所有旅程信息。
　　1.2情景演示
　　对于普通搭载空出租车的服务众所周知，本文就不在此详细介绍，本文重点介绍拼车服务。
　　从图2中可知，一名乘客在S2点等待一辆出租车，其目的地是D2，此时乘客以起点S2、目的地D2作为基本信息提出搭乘请求。推荐算法基于实时GPS数据，在其周围无法找到空闲出租车，但是可以找到即将通过S2的已经存在乘客的出租车T，其起点为S1，所以出租车T可以作为潜在的可进行拼车服务的出租车。
　　乘客在S2点搭乘出租车T，基于先上先服务的原则，出租车T首先应该将已上车的乘客送达目的地D1（D1的位置并不确定，需要通过历史数据获得），之后从D1再开往D2。乘客无论选择普通搭载服务还是拼车服务，都需要等待出租车的到来，当等待时间超过本次旅程的时间，那么乘客会放弃搭车，所以算法将旅程时间作为随机等待时间的上限。
　　乘客搭载出租车T进行拼车，那么到达目的地的时间为：TD=等待时间+（S2→D1）+（D1→D2）；若进行普通搭车请求，到达目的地时间为：TP=等待时间+（S2→D2）。通过绕远时间比例=（TD-TP）/TP来区分不同实时出租车的效用。对于空闲出租车，其D1=D2绕远时间比例为0。
　　计算中需要的实时已存在乘客出租车T的起点S1和可能目的地D1都无法从现有的设备中获得。但随着GPS数据的积累，推荐算法可以从大量的出租车GPS数据中获得算法所需要的信息，具体过程接下来将进行详细介绍。
　　2算法流程
　　2.1算法概述
　　算法会根据用户特定的起始地、目的地、请求时间与历史GPS数据库信息，实时推荐某辆已有乘客出租车为用户提供“花费较短绕远时间”的拼车服务。
　　算法主要面临着两个难题：
　　1）根据现有的设备，无法直接获取已有乘客出租车的目的地，如果无法预测已有乘客出租车的目的地，那么拼车服务将无法实现。针对此问题，算法反向跟踪已有人出租车GPS数据，获取其搭载乘客起点，以用户起点作为旅程中间点匹配历史旅程信息，获取相应的可能目的地。
　　2）用户提出请求时，周围实时一般会存在多辆出租车，如何区分不同出租车的优劣，并对其优劣程度进行量化为用户推荐最优选择是又一个难题。本文算法站在用户的角度，对于时间消耗给予最大限度的关注，采用绕远时间比例对实时出租车进行对比，下文会进行详细叙述。