Research On Long-term Carpooling Problem Based On Distributed Variable Neighborhood Search

With the rapid growth of China's economy,private cars have become a common travel tool,but the traffic pressure and environmental pollution caused by it have become increasingly evident.carpooling can effectively alleviate the above problems,so Carpooling Problem(CPP)has gradually become a hot field of research.Long-Term Carpooling Problem(LTCPP)is a sub problem of carpooling problem.It is a special carpooling problem with similar user destination and fixed relationship between users.In this paper,Variable Neighborhood Search Algorithm(VNSA)is used to study the problem of long-term carpooling problem.The algorithm can solve the long-term carpooling problem in a short time by local search with different neighborhood structures.Firstly,the long-term carpooling problem was analyzed,and a mathematical model with travel cost as the objective function and time window constraint and vehicle capacity constraint is constructed.Then,according to the distribution of the user's geographic location,the users were divided into the carpooling groups by using the hybrid distance priority algorithm,and the high quality initial solution was obtained by the constraint verification of the carpooling groups.In order to avoid the local optimal,this paper optimized the initial solution by constructing the different neighborhood search structures.The optimal solution to meet the constraints of time window and vehicle capacity was obtained after the neighborhood search iterative optimization,.Finally,the variable neighborhood search mechanism based on distributed computing was constructed to improve the reliability and accuracy of the algorithm and save the cost of travel.The experimental results show that the algorithm can obtain the high quality solution for large scale examples,at the same time,the algorithm has a high advantage in the convergence speed and the time of solving the problem.