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

A Fast Algorithm for Biobjective Shortest Path

作　　者：郝光[1] 张殿业[2] 王东梅[3] 

机构地区：[1]铁道部经济规划研究院,北京100038 [2]西南交通大学交通运输学院,四川成都610031 [3]西南交通大学经济管理学院,四川成都610031

出　　处：《公路交通科技》2007年第11期96-99,104,共5页Journal of Highway and Transportation Research and Development

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

关 键 词：交通工程 k-最短路 双目标 有效路径 

分 类 号：U491[交通运输工程—交通运输规划与管理]