基于蒙特卡罗树搜索的出租车路径推荐方法  

TAXI PATH RECOMMENDATION METHOD BASED ON MONTE CARLO TREE SEARCH

作　　者：韩东轩 路丹丹 郑斯杰 吴亚东[1,3] Han Dongxuan;Lu Dandan;Zheng Sijie;Wu Yadong(College of Computer Science and Technology,Southwest University of Science and Technology,Mianyang 621000,Sichuan,China;Engineering Technology Center,Southwest University of Science and Technology,Mianyang 621000,Sichuan,China;College of Computer,Sichuan University of Science&Engineering,Zigong 643000,Sichuan,China)

机构地区：[1]西南科技大学计算机科学与技术学院,四川绵阳621000 [2]西南科技大学工程技术中心,四川绵阳621000 [3]四川轻化工大学计算机学院,四川自贡643000

出　　处：《计算机应用与软件》2023年第2期265-273,共9页Computer Applications and Software

基　　金：国家自然科学基金项目(61802320,61872304);国家重点研究计划项目(2016QY04W0801);国防基础科研计划项目(JCKY2017404C004);四川省科技创新苗子工程项目(2019118);2020四川省大学生创新创业训练计划项目(S202010619003S)。

摘　　要：针对出租车路径推荐的问题,研究空闲出租车与潜在乘车请求之间接载最短路径推荐的方法。通过蒙特卡罗树搜索算法计算潜在乘车请求的权重,利用多臂老虎机算法获得出租车最大载客概率,使得出租车能够快速到达潜在乘车权重较大的街道,减少车辆空载行驶的情况。与现有技术相比,该方法中用于预测潜在乘车请求的模型可以进行动态概率获取,对纽约真实出租车数据的应用案例表明,该方法的推荐质量明显高于现有方法。此外,利用三维粒子隐喻车辆刻画推荐结果以简化路径推荐模型的实现方式,可视化道路潜在乘客以及出租车运行状态以帮助城市管理者和用户进行理解。Aiming at the taxi path recommendation problem, this paper studies the method of the shortest path recommendation between idle taxis and potential ride requests. The method calculated the weight of potential passengers on the street through the Monte Carlo tree search, and used the multi-arm slot machine to obtain the maximum probability of carrying passengers. It allowed taxis to quickly reach the streets with greater potential passenger weight, and reduced the number of taxis without load. Compared with the existing method, the model that was used to predict the potential ride request in this method can obtain the dynamic probability. The application case on real taxi data in New York city shows that the recommended quality of this method is significantly higher than that of the existing methods. This paper uses three-dimensional particle metaphors to describe the recommendation results of taxi, so as to simplify the implementation of the route recommendation model, and visualize the potential passengers on the road and the operating status of taxis to help city managers and users understand.

关 键 词：路径推荐 道路权重 蒙特卡罗树搜索 多臂老虎机 路线规划 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]