A Fast Algorithm for Biobjective Shortest Path
Dongmei Wang · Journal of Highway and Transportation Research and Development · 2007
Generally there is no absolute path for a bi-objective path problem.By combining k-shortest path algorithm with bi-objective decision-making method,a practical algorithm of acquiring the efficient paths for the bi-objective path problem is developed.The algorithm is a polynomial time algorithm which can get all the efficient paths quickly.The paths set and the minimum for each single-object are evaluated by using Dijstra algorithm.If the intersection of each single-objective path set is void,a rectangle will constructed,and then the feasible paths will acquired in the rectangle using the k-shortest path algorithm.Finding out the efficient paths in the shortest paths set of bi-objective in the remaining points,so another new rectangle well acquired.The rest can be deduced by analogy.Following this way,all the feasible paths can be achieved from diminishing scope gradually.In the process of searching,once finding the intersection of the shortest paths set for single-object is not void,the path of the intersection is the right one that decision-maker is seeking for.Here the algorithm is terminated.