Understanding taxi drivers’ routing choices from spatial and social traces

Abstract

Most of our learning comes from other people or from our own experience. For instance, when a taxi driver is seeking passengers on an unknown road in a large city, what should the driver do? Alternatives include cruising around the road or waiting for a time period at the roadside in the hopes of finding a passenger or just leaving for another road enroute to a destination he knows (e.g., hotel taxi rank)? This is an interesting problem that arises everyday in cities all over the world. There could be different answers to the question poised above, but one fundamental problem is how the driver learns about the likelihood of finding passengers on a road that is new to him (as he has not picked up or dropped off passengers there before). Our observation from large scale taxi driver trace data is that a driver not only learns from his own experience but through interactions with other drivers. In this paper, we first formally define this problem as socialized information learning (SIL), second we propose a framework including a series of models to study how a taxi driver gathers and learns information in an uncertain environment through the use of his social network. Finally, the large scale real life data and empirical experiments confirm that our models are much more effective, efficient and scalable that prior work on this problem.

Keywords

routing choices / socialized information learning / social network

References

[1] Heylighen F. Collective intelligence and its implementation on the web: algorithms to develop a collective mental map. Computational & <?Pub Caret?>Mathematical Organization Theory, 1999, 5(3): 253-280

[2] Nickel M, Tresp V, Kriegel H P. A three-way model for collective learning on multi-relational data. In: Procedings of the 28th International Conference on Machine Learning. 2011, 809-816

[3] Szuba T, Polanski P, Schab P, Wielicki P. Transactions on Computational Collective Intelligence. Springer, 2011, 50-73

[4] Zhu X, Gibson B, Rogers T. Co-training as a human collaboration policy. In: Proceedings of the 25th American Association for Artificial Intelligence Conference on Artificial Intelligence. 2011, 852-857

[5] Ng A Y, Russell S. Algorithms for inverse reinforcement learning. In: Proceedings of International Conference on Machine Learning. 2000, 663-670

[6] Ronald N, Dignum V, Jonker C, Arentze T, Timmermans H. On the engineering of agent-based simulations of social activities with social networks. Inform Software Technology, 2012, 54(6): 625-638

[7] Velagapudi P, Varakantham P, Sycara K, Scerri P. Distributed model shaping for scaling to decentralized pomdps with hundreds of agents. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent systems. 2011, 955-962

[8] Cao B, Pan J, Zhang Y, Yeung D, Yang Q. Adaptive transfer learning. In: Proceedings of the 24th American Association for Artificial Intelligence Conference on Artificial Intelligence. 2010, 407-412

[9] Wang H, Yang Q. Transfer learning by structural analogy. In: Proceedings of the 25th American Association for Artificial Intelligence Conference on Artificial Intelligence. 2011, 513-518

[10] Bhatt G. Information dynamics, learning and knowledge creation in organizations. The Learning Organization, 2000, 7(2): 89-99

[11] Varakantham P, Kwak J, Taylor M, Marecki J, Scerri P, Tambe M. Exploiting coordination locales in distributed pomdps via social model shaping. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2009, 313-320

[12] Liu S, Liu Y, Ni L M, Fan J, Li M. Towards mobility-based clustering. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010, 919-928

[13] Zhu H, Zhu Y, Li M, Ni L. SEER: metropolitan-scale traffic perception based on lossy sensory data. In: Proceedings of IEEE International Conference on Computer Communications. 2009, 217-225

[14] Ma S, Zheng Y, Wolfson O. T-share: a large-scale dynamic taxi ridesharing service. In: Proceedings of 29th IEEE International Conference on Data Engineering. 2013, 410-421

[15] Yuan J, Zheng Y, Xie X, Sun G. T-drive: enhancing driving directions with taxi drivers’ intelligence. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 220-232

[16] Seuken S, Zilberstein S. Memory-bounded dynamic programming for dec-pomdps. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence. 2007, 2009-2015

[17] Alpern S, Reyniers D. Spatial dispersion as a dynamic coordination problem. Theory and decision, 2002, 53(1), 29-59

[18] Yuan J, Zheng Y, Zhang L, Xie X, Sun G. Where to find my next passenger. In: Proceedings of the 13th International Conference on Ubiquitous Computing. 2011, 109-118

[19] Yuan N J, Zheng Y, Zhang L, Xie X. T-finder: a recommender system for finding passengers and vacant taxis. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10): 2390-2403

[20] Powell J W, Huang Y, Bastani F, Ji M. Towards reducing taxicab cruising time using spatio-temporal profitability maps. In: Proceedings of the 12th International Symposium on Advances in Spatial and Temporal Databases. 2011, 242-260

[21] Zheng X, Liang X, Xu K. Where to wait for a taxi? In: Proceedings of the 14th International Conference on Ubiquitous Computing. 2012, 149-156

[22] Lee D H, Wang H, Cheu R L, Teo S H. A taxi dispatch system based on current demands and real-time traffic conditions. Transportation Research Record, 2004, 1882: 193-200

[23] Seow K T, Dang N H, Lee D H. Towards an automated multiagent taxi-dispatch system. In: Proceedings of IEEE International Conference on Automation Science and Engineering. 2007, 1045-1050

[24] Seow K T, Dang N H, Lee D H. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation Science and Engineering, 2010, 7(3): 607-616

[25] Argote L, Miron-Spektor E. Organizational learning: from experience to knowledge. Organization Science, 2011, 22(5): 1123-1137

[26] Dubra J, Maccheroni F, Ok E A. Expected utility theory without the completeness axiom. Journal of Economic Theory, 2004, 115(1): 118-133

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg