Research On Solving Carpooling Problem Based On Random Forest And Variable Neighborhood Descent

With the rapid development of China’s economy,the number of private cars is increasing day by day.The increase of the number of vehicles makes traffic pressure and environmental pollution more and more serious.The above-mentioned problems can be effectively alleviated by using carpooling mode,but most of the current car-sharing modes are temporary matching,and the matching factors only consider the distance between users.The resulting car-sharing scheme ignores the user’s requirements for additional driving time and the members of the passenger team,and lacks feasibility in practical application.In addition,the solving algorithm for this problem has the problems of long solving time and poor solving quality in solving large-scale example problems.In this paper,a mathematical model based on LTCPP(Long-Term Carpooling Problem)considering matching feasibility is established,and a heuristic algorithm based on random forest and variable neighborhood descent is proposed.Based on historical carpooling data and user satisfaction information,the algorithm uses random forest algorithm to calculate the importance of each index on user satisfaction,and as the weight of the corresponding optimization objective,uses weights to represent the final objective function model,so as to avoid the subjective impact of artificial weight factors on the optimization results.On this basis,a variable neighborhood descent algorithm is designed to optimize the objective function.The algorithm can get the optimum or near optimum in short time,and has the characteristics of high efficiency and fast.The solution obtained by using VND algorithm can reduce the daily private car travel by 72%,the total mileage per day by 67%,and the satisfaction of the members of the carpool group is significantly improved.The experimental results show that the combination of random forest algorithm and VND algorithm can effectively provide high-quality solutions for long-term carpooling problems.This paper has 15 figures,10 tables and 50 references.