Study on Reasonable Replaceable Path Acquiring Method Based on Similarity

In order to avoid the convergence of dynamic navigation users' behavior, a reasonable replaceable path model based on similarity is set up in this paper, which reflects the users' diverse and personal requirements. Generally there is no absolute shortest path simultaneous with minimizations of multiple objectives for a multi-objective shortest path problem, and usually it is necessary only to attain the efficient paths meeting the decision-maker's requirements. By integrating the k-shortest path algorithm and the multi-objective decision-making theory, this paper proposes an algorithm to get the efficient paths for the multi-objective shortest path problem. After clustering analysis for the efficient paths attained above based on similarity, the paper acquires the reasonable replaceable paths meeting different requirements, and provides several reasonable paths with different attributes for users to choose. The algorithm in the paper is a polynomial time algorithm, and the example demonstrates the specific application for the algorithm.