韩东轩 路丹丹 郑斯杰 吴亚东,3
1(西南科技大学计算机科学与技术学院 四川 绵阳 621000) 2(西南科技大学工程技术中心 四川 绵阳 621000) 3(四川轻化工大学计算机学院 四川 自贡 643000)
近年来，城市交通路网完善，同时由于滴滴等打车平台的兴起，打车出行成为乘客的首选。但是城市的交通呈现明显的潮汐状态，由于城市道路高峰期的拥堵情况，出租车无法以最快速度到达潜在客户所在位置；
同样，由于平峰期出租车空载时间较长，存在潜在客户与出租车之间距离较远的问题。以上两种情况均会造成接客频率下降、运力浪费、环境污染、城市交通资源利用不高的情况。而现阶段的研究普遍为出租车与乘客之间的路径优化问题，并未涉及面向出租车进行路径推荐使得出租车能够在下一条通过的路径中有最大概率接载潜在乘客。上限置信区间算法(The Upper Confidence Bound Algorithm，UCB)在蒙特卡罗树搜索(Monte Carlo Tree Search，MCTS)的选择步骤中，用来评估值最大的子节点，这个值被命名为UCB值。树图置信算法(Upper Confidence Bound Apply to Tree，UCT)把MCTS与UCB算法联系在一起，使得道路交通的路径推荐结果，在时间和空间搜索速度和效率方面具有传统搜索算法无可比拟的优势。针对上述问题，本文研究和实现一种基于MCTS的出租车路径推荐方法，解决出租车与潜在乘客之间最短路径路线推荐问题，提出一种路径推荐模型。与Garg等[1]的论文相比，本文方法使用Python NetworkX简化了路网实现方法，并利用三维粒子隐喻车辆刻画推荐结果以简化路径推荐模型的实现方式，可视化道路潜在乘客以及出租车运行状态以帮助城市管理者和用户进行理解。对纽约真实出租车数据的应用案例研究表明，本文方法的推荐质量明显高于现有方法。
1.1 出租车路径推荐
租车路径推荐一直以来都是网约车平台管理者和城市交通管理者关注的问题。孔蕙心[2]设计了一种基于实时客流分布的路线推荐算法，采用K-means聚类算法对载客推荐点进行划分，计算出载客概率，为出租车司机推荐接客点。刘相言等[3]设计一种出租车综合推荐系统，为出租车在空载和载客状态下推荐成本最低行驶路线，同时设计了拼车决策，降低了出租车成本。戚欣等[4]使用一种改进的A*算法实现路径规划，对轨迹进行聚类分析，在路网的基础上构建k个路段的热点路段图，为出租车司机提供最优的路径规划方法，缩短空驶时间。Garg等[1]采用蒙特卡罗树搜索算法(MCTS)搜索司机与乘客之间的最短距离，使用上限置信区间算法计算道路的权重，将道路重要性较高的结果推荐给空闲的出租车司机，减少空闲出租车司机的行驶时间，并且该系统在异常情况(体育赛事、演唱会等)具有良好的鲁棒性。Wang等[5]设计了TaxiRec框架来评估和发现潜在乘客的道路集群，该框架提出了极端学习机模型评估每个道路集群的潜在乘客找寻潜力，并为道路提供聚类建议。Hwang等[6]提出出租车巡航位置推荐系统，考虑了出租车当前位置与推荐位置之间的距离，下一名乘客的等待时间以及预期的乘车费用，采用位置对位置的图模型获取乘客下车位置与下一个乘客上车位置之间的关系，采用开关模型估计行程票价，并开发基于该推荐系统的虚拟出租车巡航系统，表明在出租车巡航位置推荐上该系统的有效性。
1.2 蒙特卡罗树搜索应用
MCTS算法于2006年Alpha Go应用中被世人熟知。近年来由于通用计算的发展，MCTS算法目前在游戏对弈、路径规划等方面有着很好的前景。在Lenz等[7]提出一种应用于自动驾驶车辆的MCTS协同组合运动规划算法，在此基础上提出并行决策、智能驾驶模型的微观交通仿真和协同成本函数，展示了在车辆无须相互通信的情况下的自动驾驶结果。Sabar等[8]提出一种基于MCTS超启发式框架，将低层次启发式的搜索空间建模为一个决策树，并使用MCTS遍历该树，以确定应用于当前状态的低层次启发式的最佳序列。该框架可以运用于带时间窗的车辆路径规划问题等领域，证明了框架的通用性。Powley等[9]设计一种模拟连续实时域的路径规划和转向的控制器，使用MCTS方法来规划和引导细粒度路径，该方法可以应用于运动规划和控制领域，并与人类对手相抗衡。Haeri等[10]提出两种VNE算法：MaVEn-M算法使用多商品流算法，MaVEn-S使用最短路径算法进行虚拟链路映射，并使用MCTS为马尔可夫决策过程框架形式化虚拟节点设计节点映射的动态策略，设计盈利能力作为目标函数，得出该算法可以使基础设施的提供商利润最大化。
路径推荐模型目的是向出租车推荐潜在乘客所在街道的位置，解决出租车与潜在乘客之间最短路径路线推荐问题。城市中乘客的乘车需求看似随机分布，实际上潜在乘客产生的概率却具有一定规律，路径推荐模型需要表达乘客概率分布的问题；
当出租车周边具有多个潜在乘客时，需要根据潜在乘客产生的概率，向出租车推荐最优路径，使得出租车通过推荐的道路时能够有较大概率接到乘客；
潜在乘客的产生是动态变化的，需要考虑出租车到潜在乘客之间的最短路径问题，确保出租车能够在潜在乘客动态变化过程中接到乘客。
2.1 乘客概率分布
潜在乘客的乘车需求在城市中宏观下看似随机分布，但是乘客产生的概率却伴随时间和地区的特征而具有一定规律。一天当中，城市的中心例如商业区、商务区(CBD)等可能具有持续较大乘客产出概率，而这些潜在乘车需求所处道路或者与该道路相连接的道路必然会被推荐给出租车；
在上下班高峰期，城市区域与区域之间，例如住宅区与商业区之间，住宅区与CBD之间的通行需求较高，出租车载客呈现区域对区域特征，而处于住宅区的上车需求必然会被推荐给出租车，出租车将会呈现向距离最近的住宅区涌动的趋势，当出租车下客后，会在商业区或者CBD出现较多的空载出租车，而这时，周边非热门区域的潜在乘车需求可能无法被满足；
在半夜或平峰期的城市周边，除了酒吧街、小吃街等通宵营业的区域具有较大乘客产出概率，乘客呈现随机趋势分布在城市的各个地方，此时需要向出租车推荐距离最近的乘客和最短接乘路线，避免出租车较长时间空载。为了解决以上问题，本文模型根据纽约出租车载客情况历史数据进行训练，在道路路网上投放乘客坐标，并使用可视化技术将乘客概率分布展现在对应的地图上，便于城市管理者和用户更好地掌握一天中城市内乘客产出概率分布情况。
2.2 出租车接客最短路径
当出租车接受推荐模型的结果时，我们需要规划一条从出租车出发到达乘客所在道路的路径，即出租车接客最短路径。该路径的产生需要模型在真实的路段网络中进行搜寻，所以本文模型在构建路段网络时，将道路用边表示，道路与道路之间的连接用节点表示。网络中每一个节点是一个状态，最短路径搜索的方法是从一个节点移动到另一个节点。搜索开始时，路径推荐模型选择最优结果作为出租车的出发路段，如果被选择的边没有找到乘客，那么从当前位置重新选择一条边，这个过程持续到乘客被找到。直观地来说，由于乘客产出概率是动态变化的，所以不能简单地从历史数据中获取静态的乘客产出位置来计算出租车接客的最短路径。为了解决这个问题，本文模型在获取两个节点间最短路径长度时，采用了迪杰斯特拉算法获取从当前位置到周边各道路的最短路径。
2.3 出租车竞争
对出租车进行路径推荐时不光要考虑当前最大乘客概率，还要考虑出租车之间的竞争关系，因为同一个乘客只能乘坐一辆出租车，因此，当确定乘客产出概率的分布后，采用蒙特卡罗树搜索(MCTS)路径推荐模型必须知道当前出租车周边路线中的客户数量，以确保多辆出租车不会被分配同一个客户。推荐模型向当前出租车推荐计算输出的乘客出现权重值最高的道路。而在计算权重值时，如何平衡出租车的竞争关系，是一个待解决的问题。为了解决这一问题，本文设置了一个基于MCTS的离线学习模型，使用该离线模型学习位于道路附近的历史乘客请求并获得UCB值。将该离线学习模型训练后，便可应用于出租车动态路径推荐的过程中。
2.4 在线推荐
推荐模型分为两个阶段：离线学习模型与在线推荐阶段。在出租车动态巡游的过程中，使用在线推荐模型对出租车进行路径推荐。在该阶段，出租车作为查询节点，推荐模型向该节点推荐最大UCB值，出租车按照推荐结果巡游整条道路并到达推荐道路的另一端，这时候在线推荐模型将验证车辆是否接到乘客。如果出租车没有接到乘客，那么推荐结果将形成负反馈输入到推荐模型中，推荐模型将会减少该条道路的推荐概率。此时推荐模型会基于当前出租车查询节点位置生成一个新的推荐结果用于下一次出租车巡游。如果出租车接到乘客，会给该部分带来正反馈。即使处于在线状态下，推荐结果也会反馈到离线和在线两个模型中，权重值将会动态更新，该模型具有较强实时性。
总的来说，本文的主要贡献如下：(1) 本文提出一种基于MCTS的路径推荐方法，该方将树搜索思想应用于城市路网中，通过这种方法，出租车可以获得在线路径推荐。(2) 本文为空闲出租车司机制定路线，使得车辆到达潜在乘客需求的距离最小化。(3) 本文对纽约的真实出租车数据进行了测试，例如在交通变化或者异常情况下的适应，发现该方法的推荐质量明显高于现有方法。
3.1 推荐模型流程
本文提出的路径推荐模型流程如图1所示。
图1 路径推荐模型流程
本文所使用的路径推荐模型分为2部分，第1部分使用Python NetworkX[11]构建地图中道路和道路之间的关系，即道路路网，而道路路网与出租车载客历史数据作为训练样本训练。第2部分是将乘客需求和出租车当前位置输入至已经训练后的蒙特卡罗树搜索(MCTS)路径推荐模型中，路径推荐模型通过计算给出推荐路径结果，出租车按照推荐结果行驶后具有最大的接到乘客的概率。
3.2 路网构建
为了解决地图上的路径搜寻问题，本系统采用复杂网络分析库Python NetworkX[11]基于OSM地图进行道路网络构建，将道路用边表示，道路与道路之间的连接用节点表示，构建结果是可视化在OSM地图上的道路线条，该过程是在可视化系统中建立基本的道路信息和道路关系信息，便于树搜索算法进行路径推荐。路网构建输入为路网信息字典，输出为网络G′，构建的步骤如下：
Step1构建路网信息字典NodesInfoDict，初始化网络G。
Step2读取道路信息数据Nodes.csv，解析道路开始与结束的GPS坐标值。
Step3将道路ID作为关键字Key、道路信息(道路长度L、所在区域R、区域类型T等)作为输入值value，存入NodesInfoDict。
Step4读取道路关系数据Links.csv，获取道路之间的连接，源路段S，目标路段T。
Step5当Sin NodesInfoDict或T in NodesInfoDict，执行下一步，否则执行Step 4。
Step6在网络中增加一个边G.addEdge(S,T,weight=NodeInfoDict[S].L)。
Step7在网络中增加一个边G.addEdge(T,S,weight=NodeInfoDict[T].L)。
Step8返回网络G′。
3.3 乘客最大概率算法
在本文中，采用多臂老虎机算法是为了使得在最少的路途花费时间中得到最大的载客概率，即获得最优的道路UCB值。在蒙特卡罗树搜索算法的选择过程中，将子节点看作老虎机进行随机选择，就像解决多臂老虎机问题一样选择下一个节点i。而算法执行时并不知道哪个子节点i的收益高，而是付出一定的代价来发现哪个节点的收益高。
定义1多臂老虎机的手臂即为本文蒙特卡罗树搜索选择步骤中子节点i，即下一个被选中的路径。
定义2多臂老虎机的选择收益值Qr(a)即为本文蒙特卡罗树搜索选择步骤中的下一个被选中的路径的潜在乘客存在的概率。
定义3在一个多臂老虎机问题中，当m条手臂中的每一条手臂被选择时都有一个期望的收益值。
在第r轮被挑选的路径表示为Ar,对应的收益值记为Wr,将一条任意的路径p的期望收益值表示为Qr(a)。
Qr(a)=E[wr|Ar=p]
(1)
(2)
使用该算法获得的路径最大概率和通过选择最佳的路径所获得的那些概率的差距，被称作累计遗憾值，并且使用该算法的目标是最小化它的累计遗憾值。
定义4累计遗憾值是由于没有选择实际最佳路径的损失。r轮的累计遗憾值被表示为：
(3)
式中：C(p)是手臂p在r轮被选择的次数。
3.4 UCT算法
树图置信算法(Upper Confidence Bound Apply to Tree,UCT)把蒙特卡罗树搜索算法(MCTS)与UCB算法联系在一起，在本系统中，对于计算道路交通的路径推荐结果，在时间和空间搜索速度和效率方面具有传统搜索算法无可比拟的优势。上限置信区间算法(The Upper Confidence Bound Algorithm，UCB)在蒙特卡罗树搜索的选择步骤中用来评估值最大的子节点，这个值被命名为UCB值。MCTS是通过多次模拟得到大部分节点的UCB值，并在下一次模拟中根据前序步骤中最大的UCB值来选择有价值的节点继续模拟，最终将这些UCB值反向传播后输出，作为路径推荐的评估依据。UCB算法的计算公式如下：
(4)
在UCT算法运行过程中，系统输入出租车初始位置、乘客乘车需求坐标，通过路径推荐模型的运算后，输出道路的UCB值。UCB值表示道路的权重，即定义一条路径p，其UCB值较高时，出租车经过这条路径p，可以更容易接到乘客。也可以将UCB值理解为道路的乘客产出速率，道路UCB值越高的地方，司机越容易选择该条道路。
在本文方法中，UCT算法的流程为：
步骤1选择。选择过程是根据当前获得所有的子节点的统计结果，选择最优的子节点。系统输入出租车初始位置，即当前路网方向允许的第一个路口，称为根节点R，输出当前UCB值最大的子节点imax。在此步骤中，系统采用多臂老虎机算法随机选择根节点R的下一个路网节点(子节点i)。
算法使用UCB公式作为搜索树选择遍历的评估函数，来估计UCB值最高的最优节点，在搜索树选择遍历期间，采用式(5)进行选择。
(5)
式中：Si表示节点i的值(初始节点为R)；
xi表示节点i的经验平均值；
C表示常数；
t表示模拟的总数，模拟过程见Step 3。搜索树选择遍历时，由式(5)返回的当前具有最大UCB值的节点作为被选中的子节点imax，同时在遍历期间，一旦找到更大UCB值节点i，就更新子节点imax。
步骤2扩展。扩展是在当前的统计结果不足以计算出下一个步骤时，随机选择一个子步骤。系统输入上一步的根节点R，输出根节点R的完全遍历标记。扩展过程实际是把根节点R的所有子节点i全部访问一次。对每一个子节点i的访问均会执行算法的Step 1-Step 4。例如，在算法的第一次搜索中，算法最终处于树的某一子节点imax根部，可以认为算法未访问其他子节点i，所以在访问一个子节点后，算法会执行Step 3。若该被访问的节点已经执行过Step 3，那么算法将会将该节点作为初始节点。如果一个根节点R的所有子节点都被访问，那么认为Step 2结束。
步骤3模拟。模拟过程是模拟游戏博弈树的过程。系统输入某一子节点imax，执行Step 1，输出下一步应该到达的路网节点。Step 3可以反复执行多次。模拟过程运用单次博弈策略，也就是说从当前状态(某一个随机计算的初始节点)开始评估近似的树节点，最终在终端节点结束。模拟过程中，算法采用Rollout策略进行移动，Rollout见式(6)。
RolloutPolicy:Si→ai
(6)
式中：Si表示节点i的值；
该函数输入当前的搜索状态，输出下一次移动的选择结果。在MCTS的模拟中，Rollout函数可以多次运行，本系统设计了迪杰斯特拉算法获取最短路径来运行Rollout，迪杰斯特拉算法从根节点R开始向外扩展，在路网中寻找R到子节点i的最短路径。
步骤4反向传播。反向传播是根据模拟的结果，计算对应路径上统计记录的值。算法在完成模拟步骤后，将UCB值最高的结果传给出租车的初始位置R，并将该子节点i标记为已访问状态。出租车即可以按照该结果行驶。该步骤输入结果为子节点imax的值Si，输出结果为新节点inext。
3.5 最短路径求解
本模型在构建路段网络时，将道路用边表示，道路与道路之间的连接用节点表示。蒙特卡罗树搜索是在当前状态空间内给定随机样本去寻找最佳行为的一种方法，在MCTS的搜索过程中，搜索空间以树的形态存在，如果搜索过程从父节点到子节点，那么两个节点就被连接[1]，所以每个节点都是一种状态。而路段网络中每一个节点都是一个状态，并且搜索行为是通过边从一个节点移动到另一个节点。在线推荐过程中，通过初始化出租车当前位置作为查询节点，利用MCTS的搜索结果选择最高UCB值作为出租车的出发路段(边)，出租车对该路段进行巡游，如果该边没有找到乘客，那么模型就会继续通过MCTS进行搜索并对出租车做下一次推荐，直到乘客被找到。然而乘客需求是动态变化的，所以最高的UCB值也不能是静态的。为了满足这种动态的搜索过程，本模型在搜索两个节点之间的路径长度时，采用了迪杰斯特拉算法来获取乘客的上下车点。迪杰斯特拉算法是从一个节点到其他节点的最短路径算法，以搜索树的父节点为起始点，向外扩展，直到找到乘客需求即扩散到终点为止。
3.6 在线推荐阶段
在在线推荐阶段，推荐系统不仅向出租车推荐路线，同时还对于出租车是否接到乘客的结果来更新模型。该阶段与离线学习的区别是：
(1) 查询节点：真实的出租车作为查询节点来进行，而不是历史数据中的节点。
(2) 潜在乘客需求不再是历史数据获得。路径推荐的成功是由实时的道路数据决定的，出租车接受推荐建议后若没有接到乘客，那么会进行下一次推荐。最终出租车接到乘客后，相应的权重值将会反馈到出租车经过的所有路段。
在线推荐阶段的流程如下：
步骤1设定某一真实出租车为查询节点。
步骤2获取离线学习阶段中该节点附近的UCB值。
步骤3出租车驶向UCB值最高的道路。
步骤4若出租车未接到乘客，那么执行步骤1，同时进行负反馈，使用MCTS更新出租车经过道路的所有UCB值至离线学习系统。
步骤5若出租车接到乘客，完成查询。
以上步骤通过算法伪代码表示如下：
输入：路径p的初始节点R。
输出：路径p的子节点imaxUCB值ρUCBp。
1.设定路网所有道路UCB值ρUCBp=0
2.设定第r轮初始值r=0
3.循环：对于每个路径p，则设置Si=0
4.限定搜索总数t在设定范围[tmin,tmax]中
5.基于UCB算法与式(3)：
7.更新遍历的所有道路上的ρUCBp
8.否则，直接更新
3.7 路径推荐模型特性
路径推荐模型分为两个阶段：离线学习阶段和在线推荐阶段。模型特性如下：
(1) 动态性：传统的出租车路线预测技术是从历史数据中建立一次推荐模型[12-13],和传统技术不同的是，本文提出的是动态性推荐模型，基于在线推荐阶段出租车的成果或失败的反馈来更新过去的推荐结果。
(2) 多样性：MCTS能够利用不断地反馈建议来做到推荐模型的多样性。如果区域的上下班高峰期等开始形成，那么出租车经过区域形成正反馈，这一过程导致该区域增加更多的出租车。另一方面，如果区域的热力信息降低，负反馈将被反馈到模型中。
(3) 多辆出租车竞争平衡：通过动态性推荐模型的使用，MCTS算法可以适应多个出租车之前的竞争。在传统技术[13]上，静态模型的结果使用殆尽后模型会推荐相同的线路给出租车司机；
推荐过程不能推荐两条目的地相同的路线给同一出租车司机[12]，若存在上下班高峰期或机场火车站到站后，这些区域内没有足够的出租车。
(4) 时间片(time-slot)独立：乘客乘车需求是随着时间变化的，传统的推荐模型将历史数据划分成独立的时间片，以便于推荐模型可以按照独立的时间建立[13]，但在实际道路中，这种方法[13]存在不成立的情况。本文MCTS不需要将数据分割成时间片，从而形成更加实用的推荐平台。
本文设计两个实验来对路径推荐方法进行说明。
实验1，离线学习阶段实验，模型对历史数据进行学习获得道路的UCB权重值。
实验2，UCB可视化实验，本方法采用D3.js库进行前端可视化展现，目的是直观地呈现UCB推荐路径的结果，进一步验证和解释路径推荐方法。
4.1 实验数据介绍
出租车历史乘车数据集由Brian等[14]的开源纽约市出租车运行数据集提供，该数据集记录了2010年至2013年的纽约市的约7亿条出租车乘车记录。本文从中选取了2011年约1.7亿的历史数据集作为训练样本；
该路网关系数据集反映了纽约市约26万条路网关系。纽约市处于平原地带，所以路网呈现井字型分布，道路标志完善，在使用NetworkX建立路网时，可以使用边之间的关系进行抽象建立，便于研究。
4.2 实验环境介绍
本实验在PC环境下完成，实验环境为：
CPU：E3- 1231 V3；
内存：16 GB；
显卡：NVIDIA GTX960；
系统版本：Windows 10。
4.3 离线学习阶段实验
本实验使用纽约市出租车运行的历史数据集，由推荐系统对该数据集进行离线学习获得道路的UCB值，并证明UCB值与被推荐路径的关系。同时，本例作为路径推荐模型的离线学习结果部分，通过样本集进行随机搜索获得纽约市曼哈顿地区的道路UCB值，这些遍布所有道路的UCB值是作为出租车巡游过程中在线推荐的基准，为真实的出租车路径推荐提供基础推荐值。
本例从历史数据中随机筛选出1 000辆出租车以及1 000个乘客需求。选定纽约曼哈顿地图作为研究载体，曼哈顿地区道路数据集中有12 000条边。定义1辆出租车作为查询节点采用MCTS计算1次而获得UCB值，从而得到下一条道路的推荐为1个round。当每1辆出租车平均搜索1个round时，出租车仅仅搜索了以自己为根节点的周边子节点，并未遍历整个曼哈顿地区，所以本例反复运行了3 000个round。每一次(3 000 round)运行时间为16分钟左右。
该次计算实验结果为26 600个UCB值。本例随机抽取计算结果，数据样例见表1。
表1 UCB值结果样例
表1中，ID维度表示道路的ID编号，Production Rate表示乘客产出概率，UCB维度表示UCB的计算结果。
由表1可以看出，计算后的UCB值无上限，但是在可视化结果中，本系统将其正则化为0～1的分布，再映射在色度条中，通过色度来区分UCB值的高低。本例计算的结果存在乘客产出速率(Production Rate)高，但是UCB值低，或者乘客产出速率低，但是UCB值高的情况。该情况分析见表2。
表2 乘客产出与UCB值的关系
乘客产出速率与UCB值的高低无正相关关系，所以不分析乘客产出速率高、UCB值高或者乘客产出速率低、UCB值低的情况。
4.4 可视化设计实验
针对出租车，本文使用三维粒子隐喻车辆，接着采用粒子的运动效果描述出租车的运动情况，从而获知车辆在行驶过程的道路选择情况，此外，用户能够同时观察城市里所有车辆的实时运行情况。针对道路选择情况，这里使用色度刻画道路的UCB大小，如图2所示，色度深的地方，表明该路段为UCB值高的路段。一方面能够帮助我们调整模型的参数快速对模型进行优化，另一方面能够帮助城市管理者实时地对城市道路的运行情况进行监控。
图2 路径推荐结果可视化
假设道路p1至pn的UCB值较高，即该段道路色度较深，那么用户可以通过可视化设计获得以下信息：
(1) 道路p1乘客乘车请求较多或持续具有乘客请求。
(2) 与道路p1相连接的道路p2的乘客请求较多，出租车接客必会经过道路p1。
(3) 道路p1的乘客请求较多，p1周边相连接的道路p2,3,…,n均可通向p1，道路p2,3,…,n具有高UCB值。
另一方面，本系统对于UCB进行蓝色编码，让UCB值可视化作为路网绘制的载体，在地图上进行路网的展现。用户在使用该系统时，将真实的道路信息和UCB值进行对应，可以直观高效地识别出乘客需求较高的道路。
本案例使用由Brian等[14]的开源纽约市出租车运行数据集，将4.3节中纽约市曼哈顿区域出租车历史数据作为训练集，并与Qu等[12]和Verma等[13]的方法进行对比。
Qu等[12]提出的模型是空闲出租车路径预测技术，本文以该技术为基础。
Verma等[13]将城市分为几个区域，并设定区域的道路为推荐路径。与Qu等[12]和本文推荐方法不同的是，Verma等[13]需要获得出租车载客和下客的位置，以及出租车在空闲时段的轨迹。由于Verma等[13]并未使用纽约出租车运行数据集，所以本文建立基于纽约出租车运行数据集的Verma等[13]方法模型以便进行比较。
5.1 评估框架
为了评估系统性能，本文将数据集分为两部分：训练集和测试集。学习过程将在训练集中完成，而后在测试集上进行验证。为了进行验证，本文规定了查询时间范围[t,t+r]，如果在[t,t+r]的R中接载乘客，则推荐路径p成功。当最终找到乘客时，该乘客请求将会从测试集中移除，以保证不会分配相同的需求。
本案例使用随机选择方法构造随机训练集，选择曼哈顿地区的出租车司机中的X%作为训练集，X是随机训练集的大小。
5.2 评价指标
本文使用改进比例(%)来评价MCTS与Qu等[12]和Verma等[13]的性能差异。通常来说，改进比例(%)能够更好地反映本模型带来的性能差异。在数学上，改进比例(%)定义如下：
(7)
式中：dB为Qu等[12]或Verma等[13]方法的结果；
dMCTS为使用本文推荐模型的结果。-1表明Qu等[12]或Verma等[13]方法推荐的路径长度较短。
5.3 推荐质量
出租车每时每刻不断请求路径推荐，随着推荐查询越来越多，由于测试集中的乘客乘车请求是有限的，系统的推荐结果会变得很困难。特别指出，查询数量指的是出租车进行搜索的次数。
通过图3和图4可以得到，MCTS推荐的性能更好。但正如图4所示，Qu等[12]的改进比例高达60%，而Verma等[13]的改进比例高达160%。MCTS能够采用动态推荐模型来实现推荐质量改进，随着出租车请求增加，节点查询概率改变，因此基于静态模型的预测受到影响。
图3 MCTS推荐性能与查询数量的关系
图4 Verma等[13]和Qu等[12]推荐性能与查询数量的关系
其次，图3和图4中，MCTS与另外两种的性能差距最初增加，然后饱和并且下降。这种现象是因为最初乘客密度高，所以推荐系统更容易找到乘客。然而，随着未乘车的乘客数量减少，推荐任务变得更加困难，Verma等[13]和Qu等[12]的推荐质量下降，但MCTS保持较高推荐性能。此外，当几乎所有乘客都被分配时，所有推荐技术都变得十分困难，推荐质量的差距减小。
接下来本文研究推荐质量与训练集大小的关系。特别指出，训练集大小指训练集占整个数据集的比例。图5和图6的结果表示，训练集很小时，改进比例更高。随着训练集的增加，MCTS的改进比例减少。需要注意的是，这个结果并不代表MCTS随着训练集大小的增加而变差，它只是显示了MCTS与Verma等[13]和Qu等[12]的性能差距。在MCTS推荐模型中，离线阶段获得的推荐结果用于在线学习阶段，因此，训练数据较少时不会对在线学习造成影响。但Verma等[13]和Qu等[12]却需要大量的训练数据来学习推荐策略以获得与MCTS相同的推荐质量。
图5 MCTS推荐质量与训练集大小的关系
图6 Verma等[13]和Qu等[12]推荐质量与训练集大小的关系
本文提出一种最短路径搜索和推荐的方法，该方法使用蒙特卡罗树搜索(MCTS)来找寻出租车与潜在乘客需求之间的最短路径，使得预测潜在客户成为可能。该方法以搜索树的形式抽象出租车路网空间，并可以不断训练路网的动态特性，例如非周期性或特殊的乘客需求，使得出租车路径推荐的效率更高，使出租车走向无人驾驶成为可能。本文主要研究乘客和出租车之间的交互关系，而未进行交通异常现象和道路通量的考虑，下一步可以从时间维度以及道路通量入手，采用有限元方法对道路数据进行分解，以获得更加精准的结果。
猜你喜欢路网出租车乘客嫦娥五号带回的“乘客”中学生数理化·八年级物理人教版(2022年3期)2022-03-16乘坐出租车数学小灵通·3-4年级(2020年10期)2020-11-10最牛乘客今日农业(2019年16期)2019-01-03打着“飞的”去上班 城市空中交通路网还有多远环球飞行(2018年7期)2018-06-27凭什么今古传奇·故事版(2017年24期)2018-02-07省际路网联动机制的锦囊妙计中国公路(2017年11期)2017-07-31首都路网 不堪其重——2016年重大节假日高速公路免通期的北京路网运行状况中国公路(2017年7期)2017-07-24路网标志该如何指路?中国公路(2017年10期)2017-07-21车上的乘客数学小灵通(1-2年级)(2016年3期)2016-11-15高铁丢票乘客索退款被驳回公民与法治(2016年2期)2016-05-17