Route Recommendations for Idle Taxi Drivers: Find Me the Shortest Route to a Customer!

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.

References

1. 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.
2. Prithu Banerjee, Sayan Ranu, and Sriram Raghavan . 2014. Inferring uncertain trajectories from partial observations ICDM. 30--39.
3. Prithu Banerjee, Pranali Yawalkar, and Sayan Ranu . 2016. Mantra: a scalable approach to mining temporally anomalous sub-trajectories SIGKDD. 1415--1424.
4. Dan Donovan, Brian; Work . 2016. New York City Taxi Trip Data (2010--2013). (2016).
5. Yong Ge, Hui Xiong, Alexander Tuzhilin, Keli Xiao, Marco Gruteser, and Michael Pazzani . 2010. An energy-efficient mobile recommender system. In SIGKDD. 899--908.
6. Levente Kocsis and Csaba Szepesvári . 2006. Bandit based monte-carlo planning. In European conference on machine learning. Springer, 282--293.
7. 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.
8. 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.
9. 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.
10. OpenStreetMap contributors . 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org . (2017).
11. Michal Piorkowski, Natasa Sarafijanovoc-Djukic, and Matthias Grossglauser . 2009. A Parsimonious Model of Mobile Partitioned Networks with Clustering COMSNETS.
12. 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.
13. Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong . 2014. A cost-effective recommender system for taxi drivers SIGKDD. 45--54.
14. Sayan Ranu, P Deepak, Aditya D Telang, Prasad Deshpande, and Sriram Raghavan . 2015. Indexing and matching trajectories under inconsistent sampling rates ICDE. 999--1010.
15. 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).
16. Richard S Sutton and Andrew G Barto . 1998. Reinforcement learning: An introduction. Vol. Vol. 1. MIT press Cambridge.
17. 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).
18. 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.
19. 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.
20. 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.
21. 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.
22. Yu Zheng, Yanchi Liu, Jing Yuan, and Xing Xie . 2011. Urban computing with taxicabs. In 13th international conference on Ubiquitous computing. 89--98.
23. 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.

Index Terms

• Information systems

  • Information systems applications

    • Data mining

    • Spatial-temporal systems