基于候客点规划的空闲出租车路线推荐算法

doi:10.19678/j.issn.1000-3428.0060727

计算机工程 ›› 2022, Vol. 48 ›› Issue (2): 297-305. doi: 10.19678/j.issn.1000-3428.0060727

基于候客点规划的空闲出租车路线推荐算法

陈冬梅¹, 卜霄菲², 黄河¹, 杜扬¹, 高国举¹, 孙玉娥³

1. 苏州大学计算机科学与技术学院, 江苏苏州 215006;
2. 沈阳师范大学软件学院, 沈阳 110034;
3. 苏州大学轨道交通学院, 江苏苏州 215137

收稿日期:2021-01-28 修回日期:2021-02-25 发布日期:2021-02-25
作者简介:陈冬梅(1994-),女,硕士研究生,主研方向为机器学习、智能交通;卜霄菲,讲师、博士;黄河,教授、博士;杜扬,讲师、博士;高国举,副教授、博士;孙玉娥,教授、博士。
基金资助:
国家自然科学基金（U20A20182，61873177，62072322）。

Idle Taxi Route Recommendation Algorithm Based on Waiting Point Planning

CHEN Dongmei¹, BU Xiaofei², HUANG He¹, DU Yang¹, GAO Guoju¹, SUN Yu'e³

1. School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006, China;
2. Software College, Shenyang Normal University, Shenyang 110034, China;
3. School of Rail Transportation, Soochow University, Suzhou, Jiangsu 215137, China

Received:2021-01-28 Revised:2021-02-25 Published:2021-02-25

摘要/Abstract

摘要： 为空闲出租车司机推荐有效的闲逛路线在提高出租车司机工作效率、减少乘客等待时间以及缓解交通压力方面具有重要作用。现有的研究工作主要集中于为空闲司机推荐完整的驾驶路线，没有考虑到真实路网环境下某些路段的可等待因素，使得推荐的路线因载客概率较低、行驶距离较长而花费成本较高。提出一种基于候客点规划的路线推荐算法，对出租车轨迹数据进行处理，并设计路径匹配算法将每个轨迹点与真实路段一一匹配。通过统计每个路段历史接载信息，并利用一种改进的多层感知机建立可预测时序接载概率的模型，结合路段的可等待因素设计一种最小花费成本的路线推荐算法。在真实数据集上的实验结果表明，与MNP、InExperence、Random算法相比，所提算法花费成本、巡航时间以及巡航路程均明显减少。

关键词: 空闲出租车, 接载概率, 最小成本, 路线推荐, 多层感知机

Abstract: Effective cruising route recommendation for idle taxi drivers can help to improve drivers' efficiency, reduce passengers' waiting time, and alleviate traffic jam.Most existing studies focus on recommending complete driving routes for idle drivers, and ignore the waiting areas of road segments in real road networks, which causes multiple problems to recommended routes, such as reduced pick-up probability, long driving distance, and increased cost.To address this problem, we propose a route recommendation algorithm based on waiting area planning.The algorithm processes trajectory data of taxis, and employs an algorithm to map each trajectory point to a real road segment.By collecting the historical pick-up probability of each road segment, an improved multi-layer perceptron is used to establish a model for predicting the temporal sequence of pick-up probability.On this basis, we propose a cost-effective route recommendation algorithm that considers the waiting areas of road segments.The experimental results on real-world datasets show that compared with MNP, InExperence, Randombaseline and other algorithms, the proposed algorithm effectively reduces the cruising cost, cruising time, and cruising distance.

Key words: idle taxi, pick-up probability, minimal cost, route recommendation, Multi-Layer Perceptron(MLP)

中图分类号:

TP393

陈冬梅, 卜霄菲, 黄河, 杜扬, 高国举, 孙玉娥. 基于候客点规划的空闲出租车路线推荐算法[J]. 计算机工程, 2022, 48(2): 297-305.

CHEN Dongmei, BU Xiaofei, HUANG He, DU Yang, GAO Guoju, SUN Yu'e. Idle Taxi Route Recommendation Algorithm Based on Waiting Point Planning[J]. Computer Engineering, 2022, 48(2): 297-305.

http://www.ecice06.com/CN/Y2022/V48/I2/297

图/表 8

20220301182117

20220301182120

20220301182123

20220301182127

20220301182130

20220301182133

20220301182137

20220301182141

参考文献

[1] LI X C, CONG G, CHENG Y.Spatial transition learning on road networks with deep probabilistic models[C]//Proceedings of the 36th International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2020:349-360.
[2] WANG S, BAO Z F, CULPEPPER J.S, et al.A survey on trajectory data management, analytics, and learning[J].ACM Computing Surveys, 2020, 1(1):1-36.
[3] 李浩, 霍雯, 裴春营, 等.融合VGG与FCN的智能出租车订单预测模型[J].计算机工程, 2020, 46(12):276-282. LI H, HUO W, PEI C Y, et al.Intelligent taxi order forecasting model fusing VGG with FCN[J].Computer Engineering, 2020, 46(12):276-282.(in Chinese)
[4] 孙冠东, 张兵, 刘禹岍, 等.基于载客数据的出租车热门区域功能发现[J].计算机工程, 2017, 43(5):16-22. SUN G D, ZHANG B, LIU Y Q, et al.Taxi hot area function discovery based on passenger data[J].Computer Engineering, 2017, 43(5):16-22.(in Chinese)
[5] QU M, ZHU H S, LIU J M, et al.A cost-effective recommender system for taxi drivers[C]//Proceedings of 2014 ACM Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2014:45-54.
[6] GARG N, RANU S.Route recommendations for idle taxi drivers:find me the shortest route to a customer![C]//Proceedings of 2018 ACM Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2018:1425-1434.
[7] QU B T, YANG W X, CUI G, et al.Profitable taxi travel route recommendation based on big taxi trajectory data[J].IEEE Transactions on Intelligent Transportation Systems, 2019, 21(2):653-668.
[8] YUAN J, ZHENG Y, XIE X, et al.T-drive:enhancing driving directions with taxi drivers' intelligence[J].IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1):220-232.
[9] WANG R, CHOW C Y, LYU Y, et al.TaxiRec:recommending road clusters to taxi drivers using ranking-based extreme learning machines[J].IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3):585-598.
[10] LIU Y C, LIU C R, LU X J, et al.Point-of-interest demand modeling with human mobility patterns[C]//Proceedings of 2017 ACM International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2017:947-955.
[11] JI S G, WANG Z Y, LI T R, et al.Spatio-temporal feature fusion for dynamic taxi route recommendation via deep reinforcement learning[J].Knowledge-Based Systems, 2020, 205:106302.
[12] QIN G Y, LI T N, YU B, et al.Mining factors affecting taxi drivers' incomes using GPS trajectories[J].Transportation Research Part C:Emerging Technologies, 2017, 79:103-118.
[13] YUAN J, ZHENG Y, ZHANG L H, et al.Where to find my next passenger[C]//Proceedings of 2011 ACM International Conference on Ubiquitous Computing.New York, USA:ACM Press, 2011:109-118.
[14] YUAN N J, ZHENG Y, ZHANG L H, et al.T-Finder:a recommender system for finding passengers and vacant taxis[J].IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10):2390-2403.
[15] VERMA T, VARAKANTHAM P, KRAUS S, et al.Augmenting decisions of taxi drivers through reinforcement[C]//Proceedings of 2017 International Conference on Automated Planning and Scheduling.Palo Alto, USA:AAAI Press, 2017:409-417.
[16] CHEN Y P, FU Q W, ZHU J H, et al.Finding next high-quality passenger based on spatio-temporal big data[C]//Proceedings of 2020 IEEE International Conference on Cloud Computing and Big Data Analytics.Washington D.C., USA:IEEE Press, 2020:447-452.
[17] LI X J, SUN Y E, LIU Q, et al.Promise:a taxi recommender system based on inter-regional passenger mobility[C]//Proceedings of 2019 International Joint Conference on Neural Networks.Washington D.C., USA:IEEE Press, 2019:1-8.
[18] LI X L, PAN G, WU Z H, et al.Prediction of urban human mobility using large-scale taxi traces and its applications[J].Frontiers of Computer Science, 2012, 6(1):111-121.
[19] HWANG R H, HSUEH Y L, CHEN Y T, et al.An effective taxi recommender system based on a spatio-temporal factor analysis model[J].Information Sciences, 2015, 314(12):28-40.
[20] LUO Z W, LV H M, FANG F, et al.Dynamic taxi service planning by minimizing cruising distance without passengers[J].IEEE Access, 2018, 6:70005-70016.
[21] LÜ H M, FANG F, ZHAO Y S, et al.A performance evaluation model for taxi cruising path recommendation system[C]//Proceedings of 2017 Pacific-Asia Conference on Knowledge Discovery and Data Mining.Berlin, Germany:Springer, 2017:156-167.
[22] YU X L, GAO S, HU X B, et al.A Markov decision process approach to vacant taxi routing with e-hailing[J].Transportation Research Part B:Methodological, 2019, 121(6):114-134.
[23] RONG H G, ZHOU X, YANG C, et al.The rich and the poor:a Markov decision process approach to optimizing taxi driver revenue efficiency[C]//Proceedings of 2016 ACM International on Conference on Information and Knowledge Management.New York, USA:ACM Press, 2016:2329-2334.

选择文件类型/文献管理软件名称

选择包含的内容

基于候客点规划的空闲出租车路线推荐算法

Idle Taxi Route Recommendation Algorithm Based on Waiting Point Planning

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	丁庆丰, 李晋国. 一种物联网环境下的分布式异常流量检测方案[J]. 计算机工程, 2022, 48(8): 152-159.
[2]	李昆仑, 于志波, 翟利娜, 赵佳耀. 基于注意力机制与改进TF-IDF的推荐算法[J]. 计算机工程, 2021, 47(8): 69-77.
[3]	陈曦, 朱小栋, 高广阔, 肖芳雄. 基于混合向量模型的中文评论情感分析[J]. 计算机工程, 2020, 46(1): 309-314.
[4]	王攀,陈雪娇. 基于堆栈式自动编码器的加密流量识别方法[J]. 计算机工程, 2018, 44(11): 140-147,153.
[5]	杨静,徐彦,姜赢. 多层感知机权值扰动敏感性计算算法研究[J]. 计算机工程, 2015, 41(9): 225-232.
[6]	张伟;刘峰. 价格着色Petri网的最小成本可达问题[J]. 计算机工程, 2009, 35(1): 79-81.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于候客点规划的空闲出租车路线推荐算法

Idle Taxi Route Recommendation Algorithm Based on Waiting Point Planning

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 6

编辑推荐

Metrics

本文评价