The Research On Pick-up Tree Based Route Recommendation

With the rapid development of world urbanization, the city is facing problems such as population expansion, environmental pollution and traffic congestion. If not resolved, the development of the city will be constrained by the aforementioned prob-lems. Modern data acquisition techniques such as global positioning system (GPS), radio-frequency identification (RFID), mobile phone positioning, and wireless sensor network have resulted in the collection of huge data in the form of trajectories dur-ing the past years. Moreover, information techniques such as ubiquitous computing, big data, cloud computing and the internet of things, bring us a series of solutions for the problems. The focus of this article is taxi driving problem. A pick-up tree based route recommender system is proposed in this paper which aims to recommend suit-able routes for taxi drivers, therefore it raises the income of taxi drivers and reduces the gasoline consumption.In this paper, the main work is as follows:1. A route model of the set of taxis is given in this paper, and the run-time com-plexity of this model is also analyzed.2. We analyze the problems in the existing theories, and propose a structure named pick-up tree based on skyline computation. Therefore taxi's current position and pick-up positions are organized by pick-up tree.3. We present a probability model to estimate gasoline consumption of every route. By bringing in fairness and adopting the estimated gasoline consumption as the weight of every route, two recommendation methods for the set of taxis are pro-posed. The weighted Round-Robin recommendation method thinks over the weights of every route. Furthermore, the max-min weighted Round-Robin recommendation method takes the fairness of the set of taxis into consideration. Meanwhile, some key techniques of existing taxi recommender systems are improved, such as data cleaning, calculation of pick-up possibility, space-time clustering.4. Our experimental results on real-world taxi trajectories data sets have shown that the proposed recommendation methods effectively reduce the driving distance be-fore carrying passengers, especially when the number of cabs becomes large. Mean-while, the run-time cost of our method is also lower than the existing methods.