A Cost-Effective Sequential Route Recommender System for Taxi Drivers
- 1 September 2023
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 35 (5) , 1098-1119
Abstract
This paper develops a cost-effective sequential route recommender system to provide real-time routing recommendations for vacant taxis searching for the next passenger. We propose a prediction-and-optimization framework to recommend the searching route that maximizes the expected profit of the next successful passenger pickup based on the dynamic taxi demand-supply distribution. Specifically, this system features a deep learning-based predictor that dynamically predicts the passenger pickup probability on a road segment and a recursive searching algorithm that recommends the optimal searching route. The predictor integrates a graph convolution network (GCN) to capture the spatial distribution and a long short-term memory (LSTM) to capture the temporal dynamics of taxi demand and supply. The GCN-LSTM model can accurately predict the pickup probability on a road segment with the consideration of potential taxi oversupply. Then, the dynamic distribution of pickup probability is fed into the route optimization algorithm to recommend the optimal searching routes sequentially as route inquiries emerge in the system. The recursion tree-based route optimization algorithm can significantly reduce the computational time and provide the optimal routes within seconds for real-time implementation. Finally, extensive experiments using Beijing Taxi GPS data demonstrate the effectiveness and efficiency of the proposed recommender system. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: This work was partially supported by the Hong Kong Research Grants Council [Grants CityU 21500220, CityU 11504322] and the National Natural Science Foundation of China [Grant 72201222]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0112 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0112 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .Keywords
This publication has 28 references indexed in Scilit:
- Time-Location-Relationship Combined Service Recommendation Based on Taxi Trajectory DataIEEE Transactions on Industrial Informatics, 2017
- On-demand high-capacity ride-sharing via dynamic trip-vehicle assignmentProceedings of the National Academy of Sciences, 2017
- Spatiotemporal Pattern Analysis of Taxi Trips in New York CityTransportation Research Record: Journal of the Transportation Research Board, 2016
- Cost-Aware Collaborative Filtering for Travel Tour RecommendationsACM Transactions on Information Systems, 2014
- Predicting Taxi–Passenger Demand Using Streaming DataIEEE Transactions on Intelligent Transportation Systems, 2013
- T-Finder: A Recommender System for Finding Passengers and Vacant TaxisIEEE Transactions on Knowledge and Data Engineering, 2012
- Context-aware taxi demand hotspots predictionInternational Journal of Business Intelligence and Data Mining, 2010
- Stochastic gradient boostingComputational Statistics & Data Analysis, 2002
- Random ForestsMachine Learning, 2001
- Long Short-Term MemoryNeural Computation, 1997