Research On Online Carpooling Matching Problem Considering Carpool Sites

With the rapid development of the economy and the number of private cars,China’s urban road resources have fallen into a situation of “the demand outnumbers the supply”.As an effective way to solve urban congestion,carpooling can not only optimize and compensate for the existing public transport modes and capacity,but also meet the quality needs of residents in daily travel.However,the existing online carpooling as a more public-friendly and green travel method,there are still many shortcomings in operation and service,such as the excessive detour distance,low matching rate,and long flexibility time required by users,which greatly reduce user satisfaction and business operation quality.Based on this,this article proposes to study the matching problem of online carpooling considering carpool sites,in order to design a carpooling service that attracts more users,and promote the development of online carpooling.Firstly,after clarifying the concept and characteristics of online carpooling and summarizing the types of matching,the research object of this paper is showed which is a static online carpooling matching problem with hard time window.Subsequently,the detailed constitution and matching process of site-carpooling system are described.Secondly,the k-d tree data structure is used to design an efficient method for determining feasible pick-up and drop-off sites for passengers,and construct feasible matching recognition conditions for all passengers.Then,a multi-objective integer programming model with the goal of the largest number of matching users and the largest driving distance savings is established to optimize the matching results by using graph theory knowledge.Thirdly,the design of the solution method of feasible matching and optimal matching is discussed.Based on the analysis of the problem structure,an improved enumeration method is designed by mining the relationship between different types of matches and the relationship between the matching and carpooling sites to obtain all feasible matches.Then the hierarchical sequence method combined with the CPLEX solver is used to solve the optimal matching result.Finally,the site-carpooling matching model and algorithm are validated with small-scale and large-scale examples,and the sensitivity analysis of the matching results is performed.The results show that higher matching rate and driving distance savings can be obtained by using site-carpooling.The ratio of driver to rider and the length of time flexibility have different effects on the matching results.