Research On Bilateral Matching Model And Algorithm Based On Incomplete Preference Value

With the rise of the sharing economy in recent years,various two-sided matching problems have emerged,such as drivers and passengers matching in taxi software,homeowners and tenants matching in shared homes,the sender and the courier package matching in sharing express delivery and so on.The matching problem involves the two-sided matching subject.How to make full use of the preference information given by the matching subject to make the two-sided matching decision is a difficult problem.In addition,when the scale of the two-sided matching subject is very large,it is very wasteful to use the method of traversing the solution space to solve the model.Therefore,designing a fast algorithm to solve the model is a problem worth studying.This thesis mainly studies the matching subject without giving all the preference information,and uses the matrix decomposition technique to fill the user's missing preference values,and improves the traditional simulated annealing algorithm to solve the matching model.The following work is done specifically.First,based on matrix decomposition,a solution to the two-sided matching problem when the matching subject does not give all the preference values is proposed in this thesis.The method fully exploits the potential preference of the matching subject by using the preference values already given by the matching subject.The preference values that the matching subject does not give is predicted;besides,the method can solve the problem that the weight is difficult to determine in the multi-attribute two-sided matching problem.The preference weight of the matching subject to the attribute is implicitly included in the already given preference values,so that no artificial weighting is needed,and the influence of individual subjectivity on the matching result is avoided.Aiming at the situation that the predicted preference values exceeds the specified interval,a preference values mapping mechanism is proposed to enable the predicted preference values beyond the specified interval to be reasonably mapped into a given interval.Second,an improved simulated annealing algorithm is proposed to solve the two-sided matching model.The main improvement points are as follows: 1)Initial solution selection strategy: Randomly select multiple solutions at the beginning of the algorithm,and select the cost function to obtain the optimal solution to start the iteration,optimization algorithm Pre-search process;2)internal and external loop double threshold setting: can judge whether the current solution is stable,if the solution is repeated multiple times,the sampling is considered stable,jump out of the current loop,reduce the execution time of the loop;3)dynamic selection of the de-warming function: the current solution is better When the historical average solution is selected,the temperature retreating function with faster decolation is selected.When the current solution is inferior to the historical average solution,the decolating function with slower desuperheating is selected to accelerate the desuperheating process;4)optimal state recording: recording the optimal search history Solution,avoiding the algorithm missing the optimal solution due to probabilistic selection of the difference solution.Finally,by solving the two-sided matching example,it is verified that the improved algorithm is higher in solution quality and solution efficiency than before the improvement.