ABSTRACT
We study the problem of route recommendation to idle taxi drivers such that the distance between the taxi and an anticipated customer request is minimized. Minimizing the distance to the next anticipated customer leads to more productivity for the taxi driver and less waiting time for the customer. To anticipate when and where future customer requests are likely to come from and accordingly recom- mend routes, we develop a route recommendation engine called MDM: Minimizing Distance through Monte Carlo Tree Search. In contrast to existing techniques, MDM employs a continuous learning platform where the underlying model to predict future customer requests is dynamically updated. Extensive experiments on real taxi data from New York and San Francisco reveal that MDM is up to 70% better than the state of the art and robust to anomalous events such as concerts, sporting events, etc.
- Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer . 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning Vol. 47, 2--3 (2002), 235--256. Google ScholarDigital Library
- Prithu Banerjee, Sayan Ranu, and Sriram Raghavan . 2014. Inferring uncertain trajectories from partial observations ICDM. 30--39. Google ScholarDigital Library
- Prithu Banerjee, Pranali Yawalkar, and Sayan Ranu . 2016. Mantra: a scalable approach to mining temporally anomalous sub-trajectories SIGKDD. 1415--1424. Google ScholarDigital Library
- Dan Donovan, Brian; Work . 2016. New York City Taxi Trip Data (2010--2013). (2016).Google Scholar
- Yong Ge, Hui Xiong, Alexander Tuzhilin, Keli Xiao, Marco Gruteser, and Michael Pazzani . 2010. An energy-efficient mobile recommender system. In SIGKDD. 899--908. Google ScholarDigital Library
- Levente Kocsis and Csaba Szepesvári . 2006. Bandit based monte-carlo planning. In European conference on machine learning. Springer, 282--293. Google ScholarDigital Library
- Vinay Kolar, Sayan Ranu, Anand Prabhu Subramainan, Yedendra Shrinivasan, Aditya Telang, Ravi Kokku, and Sriram Raghavan . 2014. People In Motion: Spatio-temporal Analytics on Call Detail Records COMSNETS. 1--4.Google Scholar
- Shubhadip Mitra, Sayan Ranu, Vinay Kolar, Aditya Telang, Arnab Bhattacharya, Ravi Kokku, and Sriram Raghavan . 2015. Trajectory aware macro-cell planning for mobile users INFOCOM. 792--800.Google Scholar
- Gabor Nagy and Saıd Salhi . 2005. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research Vol. 162, 1 (2005), 126--141.Google Scholar
- OpenStreetMap contributors . 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org . (2017).Google Scholar
- Michal Piorkowski, Natasa Sarafijanovoc-Djukic, and Matthias Grossglauser . 2009. A Parsimonious Model of Mobile Partitioned Networks with Clustering COMSNETS. Google ScholarDigital Library
- Jason W Powell, Yan Huang, Favyen Bastani, and Minhe Ji . 2011. Towards reducing taxicab cruising time using spatio-temporal profitability maps. In International Symposium on Spatial and Temporal Databases. Springer, 242--260. Google ScholarDigital Library
- Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong . 2014. A cost-effective recommender system for taxi drivers SIGKDD. 45--54. Google ScholarDigital Library
- Sayan Ranu, P Deepak, Aditya D Telang, Prasad Deshpande, and Sriram Raghavan . 2015. Indexing and matching trajectories under inconsistent sampling rates ICDE. 999--1010.Google Scholar
- Reuters . 2016. Uber debuts self-driving vehicles in landmark Pittsburgh trial. https://www.reuters.com/article/us-uber-autonomous/uber-debuts-self-driving-vehicles-in-landmark-pittsburgh -trial-idUSKCN11K12Y. (2016).Google Scholar
- Richard S Sutton and Andrew G Barto . 1998. Reinforcement learning: An introduction. Vol. Vol. 1. MIT press Cambridge. Google ScholarDigital Library
- The-Straits-Times . 2016. World's first driverless taxi trial kicks off in Singapore. http://www.straitstimes.com/singapore/transport/worlds-first-driverless-taxi-trial-kicks-off-in-singapore. (2016).Google Scholar
- Tanvi Verma, Pradeep Varakantham, Sarit Kraus, and Hoong Chuin Lau . 2017. Augmenting Decisions of Taxi Drivers through Reinforcement Learning for Improving Revenues. In ICAPS, Vol. Vol. 27. 409--417.Google Scholar
- Huimin Wen, Jianping Sun, and Xi Zhang . 2014. Study on Traffic Congestion Patterns of Large City in China Taking Beijing as an Example. Procedia - Social and Behavioral Sciences Vol. 138 (2014), 482--491.Google ScholarCross Ref
- Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang . 2010. T-drive: driving directions based on taxi trajectories SIGSPATIAL. 99--108. Google ScholarDigital Library
- Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie, and Guangzhong Sun . 2011. Where to find my next passenger. In 13th international conference on Ubiquitous computing. 109--118. Google ScholarDigital Library
- Yu Zheng, Yanchi Liu, Jing Yuan, and Xing Xie . 2011. Urban computing with taxicabs. In 13th international conference on Ubiquitous computing. 89--98. Google ScholarDigital Library
- Yu Zheng, Jing Yuan, Wenlei Xie, Xing Xie, and Guangzhong Sun . 2010. Drive smartly as a taxi driver. In 7th international conference on autonomic & trusted computing. 484--486. Google ScholarDigital Library
Index Terms
- Route Recommendations for Idle Taxi Drivers: Find Me the Shortest Route to a Customer!
Recommendations
A cost-effective recommender system for taxi drivers
KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data miningThe GPS technology and new forms of urban geography have changed the paradigm for mobile services. As such, the abundant availability of GPS traces has enabled new ways of doing taxi business. Indeed, recent efforts have been made on developing mobile ...
The Automation of the Taxi Industry – Taxi Drivers’ Expectations and Attitudes Towards the Future of their Work
AbstractAdvoc ates of autonomous driving predict that the occupation of taxi driver could be made obsolete by shared autonomous vehicles (SAV) in the long term. Conducting interviews with German taxi drivers, we investigate how they perceive the changes ...
Taxi Route Recommendation Based on Urban Traffic Coulomb’s Law
Web Information Systems Engineering – WISE 2017AbstractWith the advances and availability of networking and data processing technologies, the number of researches supporting taxi as a mean of transportation and further optimization of their route selection is increasing and broadly discussed. For the ...
Comments