Research On Carpooling Algorithm Based On Completely Subgraphs And Route Similarity

At present,large cities are facing increasingly severe traffic congestion and environmental pollution problems.Carpooling becomes an integral part of existing transportation systems,because it can increase the occupancy rate of existing vehicles.In this paper,the main contents include the long-term commuting carpooling and real-time carpooling.In view of the difficulty of solving the traditional carpooling algorithm and the problem of poor real-time performance,a commuting carpooling algorithm based on complete subgraphs and a real-time carpooling algorithm based on route similarity are proposed.We further validate the carpooling algorithms effectiveness,using the urban road data,the subway card data and the taxi GPS data.The main contents include:1.In order to solve the problem of traditional commuting carpooling problem,a carpooling algorithm based on complete subgraph is proposed.According to the time,space,reputation and other factors,the satisfaction degree is calculated among the users.Further a commuter carpooling demand network is built,taking the commutation demand as the node,the carpooling as the edge and the carpooling satisfaction degree as the weight.On the basis of the carpooling demand network,the carpooling group is represented by the complete subgraphs,and the whole carpooling scheme is a segmentation of the complete subgraphs.The original carpooling linear programming problem becomes a maximum weight matching problem in the graph theory.Although the maximum weight matching problem is NP-hard,it is possible to find the carpooling scheme quickly and efficiently by two approximate algorithms,GSA and TSA.In the experiment,a simulation is verified with Shanghai Metro card data which represents the commuting demand of the Shanghai residents.The results show that in the small driver coverage or in the small success rate of negotiations,carpooling can still have a good performance.2.Aiming at the problem of route planning in carpooling algorithm,a route planning algorithm based on OpenStreetMap,an open source map data,is proposed.The OpenStreetMap data is used to extract the urban road network backbone of Shanghai.Then,the road network is set up based on the intersection point and the connecting road between the intersections,and the geographic distance between the intersections.Based on the intersection road network,the shortest path is calculated.Combined with Shanghai Qiangsheng Taxis data to further estimate the average driving speed and duration of each road section,the time road network with weight of road section duration is obtained.The optimal time road network is obtained by iteratively optimizing the speed and duration of each road section using the difference between the estimated time and the actual driving time.Finally,the sum of the estimated time of all the routes in the training set is minimized,and the optimal route between different intersections are obtained by this network.The experimental results show that the difference between the sum of estimated travel time and actual travel time is small and the route planning is fast and accurate.3.Aiming at the difference of demand between commuters and real-time users,a real-time carpooling algorithm based on similarity of routes is proposed.First,the difference of restriction between real-time carpooling and commuting carpooling is defined.Then,two-person real-time carpooling is taken as an example.Carpooling mode,route time constraint and route similarity are introduced.A simple sorting algorithm can verify the effectiveness of the 2-person carpooling algorithm based on route similarity.Afterwards,the problem is extended to the k-person carpooling,and the carpool problem and constraint are redefined,and the k-person carpooling problem is modeled based on the complete subgraph model.According to the k-person route similarity demand network,we use the GPS data set of Qiangsheng Taxis and the approximation algorithm GSA to validate the results.The results show that the real-time carpooling algorithm based on the similarity of route is good and the vast majority of carpool recommendations are get within a short waiting time.