双目标最短路有效解的快速算法

双目标最短路问题往往不存在绝对最短路径。通过综合k-最短路算法和双目标决策方法获得了双目标最短路问题的有效路径实用算法，该算法属多项式算法，可快速求出所有有效路径。利用Oijstra算法先求出两个单目标的最短路径集，若交集为空集，则构造一个矩形，利用k-最短路算法获得该矩形内的可行路径，再在矩形内找出两个单目标的最短路径集中的有效路径，得一个新的矩形。依此类推，逐步缩小搜索范围，直至找出所有的有效解。上述搜索过程中，一旦出现单目标最短路径集的交集不为空，则交集中的路径即为有效路径，此时算法结束。

A Fast Algorithm for Biobjective Shortest Path

Generally there is no absolute shortest path for a bi-objective shortest 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 shortest path problem is developed.The algorithm is a polynomial time algorithm which can get all the efficient paths quickly.The shortest paths set and the minimum for each single-object are evaluated by using Dijstra algorithm.If the intersection of each single-objective shortest 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.