Research On Key Technologies For Intelligent Ride Sharing Systems Based On Large-Scale Trajectory Data

Ride sharing has been widely studied in academia as a means of reducing the number of cars,congestion,and pollution by sharing empty seats.With the popularization of mobile networks and the development of GPS,Beidou,and other positioning systems,the large-scale trajectory data has brought new opportunities and challenges for ride sharing systems.This dissertation focuses on key issues such as vehicle filtering,moving pattern discovery,trips matching and planning,and ride sharing optimization in ride sharing systems based on large volume trajectories.Main contributions are summarized as follows.·To effeetively search k-nearest vehicles from massive moving vehieles on large-scale road networks,we propose a V-Tree indexing algorithm.Existing stud-ies focus on either kNN search on static objects or continuous kNN search with Euclidean-distance constraints.The former cannot support dynamic updates of moving objects while the latter cannot support road networks.To address these issues,we propose a new index named V-Tree based on a separator theorem for planar graphs.The complex of searching and updating is reduced to O(log)level.It can meet the needs of a massive moving vehicles index on large-scale road networks.·For discovering location activity pattern in ride sharing systems,a high-occupancy utility proportion mining algorithm,OCEAN,is proposed.Existing related mining techniques cannot reflect the importance of location pattern for ride sharing systems.For this reason,we propose a novel measure of patterns,utility occupancy,for ride sharing systems.The challenge of high utility occupancy item-set discovering is the lack of monotone or anti-monotone property.So we derive an upper bound for utility occupancy and design an efficient mining algorithm called OCEAN based on a fast implementation of utility list.Evaluations of real-world trajectory data and other four datasets show that OCEAN is efficient and effective in finding patterns for ride sharing systems with large utility occupancy.·For multi-trip matching and route planning in ride sharing systems,a cluster-based matching and planning algorithm Roo is proposed.The existing methods consider the multi-order matching plan as the two steps of matching the trip and planning the route,and often only consider the starting and ending positions of the trip when matching trips.To solve this problem,a road network based spatio-temporal distance metric is proposed.Based on this metric,a multi-trip matching planning algorithm that considers both trip matching and route planning is de-signed,which provides a more flexible choice of sharing,thereby reducing mileage expenses.·To analyze the urban activity for perfecting ride sharing systems,we propose an urban activity mining framework for ride sharing systems based on vehicular social networks named NBAF.Vehicle scheduling,waiting time for passengers,price strategy,and other factors all determine the experience of ride sharing systems.It is necessary to effectively discover urban activity pattern for improving ride sharing systems.To meet this requirement,we propose an urban activity mining framework based on urban activity network.This analysis framework can effectively describe the mobility patterns between regions in the city and provide support for the improvement and macro-scheduling of ride sharing systems.